TY - GEN

T1 - Minimizing makespan and preemption costs on a system of uniform machines

AU - Shachnai, H.

AU - Tamir, T.

AU - Woeginger, G.J.

PY - 2002

Y1 - 2002

N2 - It is well known that for preemptive scheduling on uniform machines there exist polynomial time exact algorithms,whereas for non- preemptive scheduling there are probably no such algorithms.However, it is not clear how many preemptions (in total,or per job)suffice in order to guarantee an optimal polynomial time algorithm.In this paper we investigate exactly this hardness gap, formalized as two variants of the classic preemptive scheduling problem. In generalized multiprocessor scheduling (GMS),we have job-wise or total bound on the number of pre- emptions throughout a feasible schedule.We need to find a schedule that satisfies the preemption constraints, such that the maxim m job completion time is minimized. In minimum preemptions scheduling (MPS), the only feasible schedules are preemptive schedules with smallest possible make span. The goal is to find a feasible schedule that minimizes the overall number of preemptions. Both problems are NP-hard, even for two machines and zero preemptions.
For GMS, we develop polynomial time approximation schemes distinguishing between the cases where the number of machines is fixed or given as part of the input.For MPS, we derive matching lower and upper bounds on the number of preemptions required by any optimal schedule.

AB - It is well known that for preemptive scheduling on uniform machines there exist polynomial time exact algorithms,whereas for non- preemptive scheduling there are probably no such algorithms.However, it is not clear how many preemptions (in total,or per job)suffice in order to guarantee an optimal polynomial time algorithm.In this paper we investigate exactly this hardness gap, formalized as two variants of the classic preemptive scheduling problem. In generalized multiprocessor scheduling (GMS),we have job-wise or total bound on the number of pre- emptions throughout a feasible schedule.We need to find a schedule that satisfies the preemption constraints, such that the maxim m job completion time is minimized. In minimum preemptions scheduling (MPS), the only feasible schedules are preemptive schedules with smallest possible make span. The goal is to find a feasible schedule that minimizes the overall number of preemptions. Both problems are NP-hard, even for two machines and zero preemptions.
For GMS, we develop polynomial time approximation schemes distinguishing between the cases where the number of machines is fixed or given as part of the input.For MPS, we derive matching lower and upper bounds on the number of preemptions required by any optimal schedule.

U2 - 10.1007/3-540-45749-6_74

DO - 10.1007/3-540-45749-6_74

M3 - Conference contribution

T3 - Lecture Notes in Computer Science

SP - 859

EP - 871

BT - Algorithms - ESA 2002 (Proceedings of the 10th Annual European Symposium, Rome, Italy, September 17-21, 2002)

PB - Springer

CY - Berlin

ER -