2006 | OriginalPaper | Buchkapitel
On the Value of Preemption in Scheduling
verfasst von : Yair Bartal, Stefano Leonardi, Gil Shallom, Rene Sitters
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
It is well known that on-line preemptive scheduling algorithms can achieve efficient performance. A classic example is the Shortest Remaining Processing Time (SRPT) algorithm which is optimal for flow time scheduling, assuming preemption is costless. In real systems, however, preemption has significant overhead. In this paper we suggest a new model where preemption is costly. This introduces new considerations for preemptive scheduling algorithms and inherently calls for new scheduling strategies. We present a simple on-line algorithm and present lower bounds for on-line as well as efficient off-line algorithms which show that our algorithm performs close to optimal.