Analysis of a linear programming heuristic for scheduling unrelated parallel machines

DOI10.1016/0166-218X(85)90009-5zbMath0571.90035OpenAlexW1965349277MaRDI QIDQ1061599

Chris N. Potts

Publication date: 1985

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

Full work available at URL: https://doi.org/10.1016/0166-218x(85)90009-5

zbMATH Keywords

worst-case performanceunrelated parallel machinesmaximum completion timeheuristic method

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (28)

Unrelated parallel machine scheduling using local search ⋮ Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches ⋮ A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search ⋮ Exact and approximation algorithms for makespan minimization on unrelated parallel machines ⋮ Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems ⋮ Scheduling with job rejection and nonsimultaneous machine available time on unrelated parallel machines ⋮ Approximating a two-machine flow shop scheduling under discrete scenario uncertainty ⋮ Scheduling jobs with release dates and tails on two unrelated parallel machines to minimize the makespan ⋮ Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration ⋮ On the geometry, preemptions and complexity of multiprocessor and shop scheduling ⋮ Unrelated parallel machine scheduling -- perspectives and progress ⋮ Approximation results for flow shop scheduling problems with machine availability constraints ⋮ Assigning real-time tasks on heterogeneous multiprocessors with two unrelated types of processors ⋮ Task assignment algorithms for two-type heterogeneous multiprocessors ⋮ Real-time scheduling with resource sharing on heterogeneous multiprocessors ⋮ An optimal rounding gives a better approximation for scheduling unrelated machines ⋮ Makespan minimization for scheduling unrelated parallel machines: a recovering beam search approach ⋮ Heuristics for scheduling unrelated parallel machines ⋮ Iterated greedy local search methods for unrelated parallel machine scheduling ⋮ 2-approximation algorithm for a generalization of scheduling on unrelated parallel machines ⋮ Approximation algorithms for the multiprocessor scheduling with submodular penalties ⋮ New bounds for truthful scheduling on two unrelated selfish machines ⋮ Approximation algorithms for scheduling unrelated parallel machines ⋮ Approximation scheduling algorithms: a survey ⋮ Approximability of flow shop scheduling ⋮ Heuristics for unrelated machine scheduling with precedence constraints ⋮ A cutting plane algorithm for the unrelated parallel machine scheduling problem ⋮ Preemptive and non-preemptive scheduling on two unrelated parallel machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding the median
• Time bounds for selection
• Technical Note—Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times
• Worst-Case Analysis of Heuristic Algorithms
• Algorithms for Scheduling Tasks on Unrelated Processors
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Performance Guarantees for Scheduling Algorithms
• Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors

This page was built for publication: Analysis of a linear programming heuristic for scheduling unrelated parallel machines