Minimizing makespan and preemption costs on a system of uniform machines

DOI10.1007/s00453-005-1171-0zbMath1086.90028OpenAlexW2944906438MaRDI QIDQ818662

Gerhard J. Woeginger, Hadas Shachnai, Tami Tamir

Publication date: 21 March 2006

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-005-1171-0

zbMATH Keywords

minimum preemptions scheduling

Mathematics Subject Classification ID

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

Related Items (13)

Parametric analysis of the quality of single preemption schedules on three uniform parallel machines ⋮ Mathematical programming algorithms for bin packing problems with item fragmentation ⋮ An AFPTAS for variable sized bin packing with general activation costs ⋮ Preemptive scheduling on uniformly related machines: minimizing the sum of the largest pair of job completion times ⋮ Schedules with a single preemption on uniform parallel machines ⋮ Dynamic Windows Scheduling with Reallocation ⋮ Approximation schemes for packing with item fragmentation ⋮ Robust algorithms for preemptive scheduling ⋮ Algorithms with limited number of preemptions for scheduling on parallel machines ⋮ Preemptive Scheduling on Selfish Machines ⋮ Robust algorithms for preemptive scheduling on uniform machines of non-increasing job sizes ⋮ Optimal and online preemptive scheduling on uniformly related machines ⋮ How small are shifts required in optimal preemptive schedules?

This page was built for publication: Minimizing makespan and preemption costs on a system of uniform machines