Exact and approximation algorithms for makespan minimization on unrelated parallel machines

DOI10.1016/S0166-218X(96)00087-XzbMath0882.68016OpenAlexW2013929918MaRDI QIDQ1363647

François Soumis, Paolo Toth, Silvano Martello

Publication date: 10 August 1997

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

schedulingNP-hard problem

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

A heuristic and a branch-and-bound algorithm for the assembly line worker assignment and balancing problem, Hybrid tabu search and a truncated branch-and-bound for the unrelated parallel machine scheduling problem, The robust (minmax regret) assembly line worker assignment and balancing problem, Exact makespan minimization of unrelated parallel machines, Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems, Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration, Unrelated parallel machine scheduling -- perspectives and progress, Models and matheuristics for the unrelated parallel machine scheduling problem with additional resources, Modeling and solving rich quay crane scheduling problems, A branch-and-bound algorithm for assembly line worker assignment and balancing problems, Makespan minimization for scheduling unrelated parallel machines: a recovering beam search approach, Iterated greedy local search methods for unrelated parallel machine scheduling, Unrelated Parallel Machine Scheduling Problem with Precedence Constraints: Polyhedral Analysis and Branch-and-Cut, Workload balancing and loop layout in the design of a flexible manufacturing system, A cutting plane algorithm for the unrelated parallel machine scheduling problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for scheduling unrelated parallel machines
• Analysis of a linear programming heuristic for scheduling unrelated parallel machines
• The bottleneck generalized assignment problem
• Heuristics for scheduling unrelated parallel machines
• An Additive Bounding Procedure for Combinatorial Optimization Problems
• Algorithms for Scheduling Tasks on Unrelated Processors
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• Duality-Based Algorithms for Scheduling Unrelated Parallel Machines