TY - GEN
T1 - Preemptive scheduling with rejection
AU - Hoogeveen, J.A.
AU - Skutella, M.
AU - Woeginger, G.J.
PY - 2000
Y1 - 2000
N2 - We consider the problem of preemptively scheduling a set of n jobs on m (identical, uniformly related, or unrelated) parallel machines. The scheduler may reject a subset of the jobs and thereby incur job-dependent penalties for each rejected job, and he must construct a schedule for the remaining jobs so as to optimize the preemptive makespan on the m machines plus the sum of the penalties of the jobs rejected. We provide a complete classification of these scheduling problems with respect to complexity and approximability. Our main results are on the variant with an arbitrary number of unrelated machines. This variant is APX-hard, and we design a 1.58-approximation algorithm for it. All other considered variants are weakly NP-hard, and we provide fully polynomial time approximation schemes for them.
AB - We consider the problem of preemptively scheduling a set of n jobs on m (identical, uniformly related, or unrelated) parallel machines. The scheduler may reject a subset of the jobs and thereby incur job-dependent penalties for each rejected job, and he must construct a schedule for the remaining jobs so as to optimize the preemptive makespan on the m machines plus the sum of the penalties of the jobs rejected. We provide a complete classification of these scheduling problems with respect to complexity and approximability. Our main results are on the variant with an arbitrary number of unrelated machines. This variant is APX-hard, and we design a 1.58-approximation algorithm for it. All other considered variants are weakly NP-hard, and we provide fully polynomial time approximation schemes for them.
U2 - 10.1007/3-540-45253-2_25
DO - 10.1007/3-540-45253-2_25
M3 - Conference contribution
SN - 3-540-41004-X
T3 - Lecture Notes in Computer Science
SP - 268
EP - 277
BT - Algorithms - ESA 2000 : proceedings 8th annual european symposium, Saarbrücken, Germany, September 5-8, 2000
A2 - Paterson, M.
PB - Springer
CY - Berlin
ER -