On the value of preemption in scheduling

Yair Bartal; Stefano Leonardi; Gil Shallom; Rene Sitters

On the value of preemption in scheduling

Yair Bartal^*, Stefano Leonardi, Gil Shallom, Rene Sitters

^*Corresponding author for this work

Amsterdam Business Research Institute

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

Abstract

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.

Original language	English
Title of host publication	Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 a
Publisher	Springer/Verlag
Pages	39-48
Number of pages	10
Volume	4110 LNCS
ISBN (Print)	3540380442, 9783540380443
Publication status	Published - 2006
Event	9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006 - Barcelona, Spain Duration: 28 Aug 2006 → 30 Aug 2006

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4110 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006
Country/Territory	Spain
City	Barcelona
Period	28/08/06 → 30/08/06

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Persistent URL (handle)

Persistent link

Cite this

Bartal, Y., Leonardi, S., Shallom, G., & Sitters, R. (2006). On the value of preemption in scheduling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 a (Vol. 4110 LNCS, pp. 39-48). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4110 LNCS). Springer/Verlag.

Bartal, Yair ; Leonardi, Stefano ; Shallom, Gil et al. / On the value of preemption in scheduling. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 a. Vol. 4110 LNCS Springer/Verlag, 2006. pp. 39-48 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1294279130384ebb83efd949a41f16e0,

title = "On the value of preemption in scheduling",

abstract = "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.",

author = "Yair Bartal and Stefano Leonardi and Gil Shallom and Rene Sitters",

year = "2006",

language = "English",

isbn = "3540380442",

volume = "4110 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer/Verlag",

pages = "39--48",

booktitle = "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 a",

note = "9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006 ; Conference date: 28-08-2006 Through 30-08-2006",

}

Bartal, Y, Leonardi, S, Shallom, G & Sitters, R 2006, On the value of preemption in scheduling. in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 a. vol. 4110 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4110 LNCS, Springer/Verlag, pp. 39-48, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, 28/08/06.

On the value of preemption in scheduling. / Bartal, Yair; Leonardi, Stefano; Shallom, Gil et al.
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 a. Vol. 4110 LNCS Springer/Verlag, 2006. p. 39-48 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4110 LNCS).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - On the value of preemption in scheduling

AU - Bartal, Yair

AU - Leonardi, Stefano

AU - Shallom, Gil

AU - Sitters, Rene

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=33750067360&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33750067360&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:33750067360

SN - 3540380442

SN - 9783540380443

VL - 4110 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 39

EP - 48

BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 a

PB - Springer/Verlag

T2 - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006

Y2 - 28 August 2006 through 30 August 2006

ER -

Bartal Y, Leonardi S, Shallom G, Sitters R. On the value of preemption in scheduling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 a. Vol. 4110 LNCS. Springer/Verlag. 2006. p. 39-48. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

On the value of preemption in scheduling

Abstract

Publication series

Conference

UN SDGs

Persistent URL (handle)

Other files and links

Fingerprint

Cite this