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 -hard, and we provide fully polynomial time approximation schemes
for them. Finally, we argue that our results for unrelated machines can be carried over to the corresponding preemptive open
shop scheduling problem with rejection.
Received: October 30, 2000 / Accepted: September 26, 2001 Published online: September 5, 2002
Key words. scheduling – preemption – approximation algorithm – worst case ratio – computational complexity – in-approximability
Supported in part by the EU Thematic Network APPOL, Approximation and Online Algorithms, IST-1999-14084
Supported by the START program Y43-MAT of the Austrian Ministry of Science.