de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Preemptive scheduling with rejection

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45503

Skutella,  Martin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Hoogeveen, H., Skutella, M., & Woeginger, G. J. (2003). Preemptive scheduling with rejection. Mathematical Programming, 94, 361-374.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2DC9-4
Abstract
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.