Lower bounds for Smith's rule in stochastic machine scheduling

Caroline Jagtenberg; Uwe Schwiegelshohn; Marc Jochen Uetz

doi:10.1007/978-3-642-18318-8

Lower bounds for Smith's rule in stochastic machine scheduling

Caroline Jagtenberg, Uwe Schwiegelshohn, Marc Jochen Uetz

Discrete Mathematics and Mathematical Programming

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

3 Citations (Scopus)

Abstract

We consider the problem to minimize the weighted sum of completion times in nonpreemptive parallel machine scheduling. In a landmark paper from 1986, Kawaguchi and Kyan showed that scheduling the jobs according to the WSPT rule -also known as Smith's rule- has a performance guarantee of 1.207. They also gave an instance to show that this bound is tight. We consider the stochastic variant of this problem in which the processing times are exponentially distributed random variables. We show, somehow counterintuitively, that the performance guarantee of the WSEPT rule, the stochastic analogue of WSPT, is not better than 1.243. This constitutes the first lower bound for WSEPT in this setting, and in particular, it sheds new light on the fundamental differences between deterministic and stochastic scheduling problems.

Original language	Undefined
Title of host publication	8th International Workshop on Approximation and Online Algorithms, WAOA 2010
Editors	K. Jansen, R Solis-Oba
Place of Publication	Heidelberg
Publisher	Springer
Pages	142-153
Number of pages	12
ISBN (Print)	978-3-642-18317-1
DOIs	https://doi.org/10.1007/978-3-642-18318-8
Publication status	Published - 2011
Event	8th International Workshop on Approximation and Online Algorithms 2010 - University of Liverpool, Liverpool, United Kingdom Duration: 9 Sep 2010 → 10 Sep 2010 Conference number: 8

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Verlag
Volume	6534
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	8th International Workshop on Approximation and Online Algorithms 2010
Abbreviated title	WAOA 2010
Country	United Kingdom
City	Liverpool
Period	9/09/10 → 10/09/10

Keywords

METIS-277547
IR-76015
Scheduling
EWI-19621
Stochastic Scheduling
WSPT
Exponential distribution

Access to Document

10.1007/978-3-642-18318-8

http://eprints.eemcs.utwente.nl/secure2/19621/02/65340142.pdf

Cite this

@inproceedings{ed6879b94af746699261cd3a8b6fdfc8,

title = "Lower bounds for Smith's rule in stochastic machine scheduling",

abstract = "We consider the problem to minimize the weighted sum of completion times in nonpreemptive parallel machine scheduling. In a landmark paper from 1986, Kawaguchi and Kyan showed that scheduling the jobs according to the WSPT rule -also known as Smith's rule- has a performance guarantee of 1.207. They also gave an instance to show that this bound is tight. We consider the stochastic variant of this problem in which the processing times are exponentially distributed random variables. We show, somehow counterintuitively, that the performance guarantee of the WSEPT rule, the stochastic analogue of WSPT, is not better than 1.243. This constitutes the first lower bound for WSEPT in this setting, and in particular, it sheds new light on the fundamental differences between deterministic and stochastic scheduling problems.",

keywords = "METIS-277547, IR-76015, Scheduling, EWI-19621, Stochastic Scheduling, WSPT, Exponential distribution",

author = "Caroline Jagtenberg and Uwe Schwiegelshohn and Uetz, {Marc Jochen}",

note = "10.1007/978-3-642-18318-8 ; null ; Conference date: 09-09-2010 Through 10-09-2010",

year = "2011",

doi = "10.1007/978-3-642-18318-8",

language = "Undefined",

isbn = "978-3-642-18317-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "142--153",

editor = "K. Jansen and R Solis-Oba",

booktitle = "8th International Workshop on Approximation and Online Algorithms, WAOA 2010",

}

Jagtenberg, C, Schwiegelshohn, U & Uetz, MJ 2011, Lower bounds for Smith's rule in stochastic machine scheduling. in K Jansen & R Solis-Oba (eds), 8th International Workshop on Approximation and Online Algorithms, WAOA 2010. Lecture Notes in Computer Science, vol. 6534, Springer, Heidelberg, pp. 142-153, 8th International Workshop on Approximation and Online Algorithms 2010, Liverpool, United Kingdom, 9/09/10. https://doi.org/10.1007/978-3-642-18318-8

Lower bounds for Smith's rule in stochastic machine scheduling. / Jagtenberg, Caroline; Schwiegelshohn, Uwe; Uetz, Marc Jochen.

8th International Workshop on Approximation and Online Algorithms, WAOA 2010. ed. / K. Jansen; R Solis-Oba. Heidelberg : Springer, 2011. p. 142-153 (Lecture Notes in Computer Science; Vol. 6534).

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

TY - GEN

T1 - Lower bounds for Smith's rule in stochastic machine scheduling

AU - Jagtenberg, Caroline

AU - Schwiegelshohn, Uwe

AU - Uetz, Marc Jochen

N1 - Conference code: 8

PY - 2011

Y1 - 2011

N2 - We consider the problem to minimize the weighted sum of completion times in nonpreemptive parallel machine scheduling. In a landmark paper from 1986, Kawaguchi and Kyan showed that scheduling the jobs according to the WSPT rule -also known as Smith's rule- has a performance guarantee of 1.207. They also gave an instance to show that this bound is tight. We consider the stochastic variant of this problem in which the processing times are exponentially distributed random variables. We show, somehow counterintuitively, that the performance guarantee of the WSEPT rule, the stochastic analogue of WSPT, is not better than 1.243. This constitutes the first lower bound for WSEPT in this setting, and in particular, it sheds new light on the fundamental differences between deterministic and stochastic scheduling problems.

AB - We consider the problem to minimize the weighted sum of completion times in nonpreemptive parallel machine scheduling. In a landmark paper from 1986, Kawaguchi and Kyan showed that scheduling the jobs according to the WSPT rule -also known as Smith's rule- has a performance guarantee of 1.207. They also gave an instance to show that this bound is tight. We consider the stochastic variant of this problem in which the processing times are exponentially distributed random variables. We show, somehow counterintuitively, that the performance guarantee of the WSEPT rule, the stochastic analogue of WSPT, is not better than 1.243. This constitutes the first lower bound for WSEPT in this setting, and in particular, it sheds new light on the fundamental differences between deterministic and stochastic scheduling problems.

KW - METIS-277547

KW - IR-76015

KW - Scheduling

KW - EWI-19621

KW - Stochastic Scheduling

KW - WSPT

KW - Exponential distribution

U2 - 10.1007/978-3-642-18318-8

DO - 10.1007/978-3-642-18318-8

M3 - Conference contribution

SN - 978-3-642-18317-1

T3 - Lecture Notes in Computer Science

SP - 142

EP - 153

BT - 8th International Workshop on Approximation and Online Algorithms, WAOA 2010

A2 - Jansen, K.

A2 - Solis-Oba, R

PB - Springer

CY - Heidelberg

Y2 - 9 September 2010 through 10 September 2010

ER -