Lower bounds for Smith's rule in stochastic machine scheduling

Caroline Jagtenberg*, Uwe Schwiegelshohn, Marc Uetz

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review


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.

Original languageEnglish
Title of host publicationApproximation and Online Algorithms - 8th International Workshop, WAOA 2010, Revised Papers
Number of pages12
Publication statusPublished - 7 Feb 2011
Externally publishedYes
Event8th International Workshop on Approximation and Online Algorithms, WAOA 2010 - Liverpool, United Kingdom
Duration: 9 Sept 201010 Sept 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6534 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference8th International Workshop on Approximation and Online Algorithms, WAOA 2010
Country/TerritoryUnited Kingdom


  • exponential distribution
  • stochastic scheduling


Dive into the research topics of 'Lower bounds for Smith's rule in stochastic machine scheduling'. Together they form a unique fingerprint.

Cite this