Title
Preemptive scheduling with rejection
Authors
-
Publication
Mathematical Programming B, to appear. An extended abstract appeared in Mike Paterson (ed.):
Algorithms - ESA 2000, Lecture Notes in Computer Science 1879,
Springer: Berlin, 2000, pp. 268-277, Proceedings of the 8th
Annual European Symposium on Algorithms (ESA'00).
Source
-
Classification
-
| MSC: |
| primary: | 90C27 | Combinatorial optimization |
| secondary: | 68Q25 | Analysis of algorithms and problem complexity |
| 90B35 | Scheduling theory, deterministic |
| 68M20 | Performance evaluation; queueing; scheduling |
| 90C59 | Approximation methods and heuristics |
Keywords
-
scheduling, preemption, approximation algorithm,
worst case ratio, computational complexity, in-approximability
-
-
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.
Finally, we argue that our results for unrelated machines can be
carried over to the corresponding preemptive open shop scheduling
problem with rejection.
See also
-
