direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 684-2000

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Preemptive scheduling with rejection
Han Hoogeveen, Martin Skutella, and Gerhard J. Woeginger
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).
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
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.
Download as [PDF] [ps.gz]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe