TY - GEN
T1 - Lower bounds for Smith's rule in stochastic machine scheduling
AU - Jagtenberg, Caroline
AU - Schwiegelshohn, Uwe
AU - Uetz, Marc
PY - 2011/2/7
Y1 - 2011/2/7
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 [5] showed that scheduling the jobs according to the WSPT rule -also known as Smith's rule- has a performance guarantee of 1/2(1 + √2) ≈ 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 [5] showed that scheduling the jobs according to the WSPT rule -also known as Smith's rule- has a performance guarantee of 1/2(1 + √2) ≈ 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 - exponential distribution
KW - stochastic scheduling
KW - WSEPT
UR - http://www.scopus.com/inward/record.url?scp=79551523004&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79551523004&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-18318-8_13
DO - 10.1007/978-3-642-18318-8_13
M3 - Conference contribution
AN - SCOPUS:79551523004
SN - 9783642183171
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 142
EP - 153
BT - Approximation and Online Algorithms - 8th International Workshop, WAOA 2010, Revised Papers
T2 - 8th International Workshop on Approximation and Online Algorithms, WAOA 2010
Y2 - 9 September 2010 through 10 September 2010
ER -