Lower bounds for Smith's rule in stochastic machine scheduling

Caroline Jagtenberg, Uwe Schwiegelshohn, Marc Jochen Uetz

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

3 Citations (Scopus)


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 languageUndefined
Title of host publication8th International Workshop on Approximation and Online Algorithms, WAOA 2010
EditorsK. Jansen, R Solis-Oba
Place of PublicationHeidelberg
Number of pages12
ISBN (Print)978-3-642-18317-1
Publication statusPublished - 2011
Event8th International Workshop on Approximation and Online Algorithms 2010 - University of Liverpool, Liverpool, United Kingdom
Duration: 9 Sep 201010 Sep 2010
Conference number: 8

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference8th International Workshop on Approximation and Online Algorithms 2010
Abbreviated titleWAOA 2010
CountryUnited Kingdom


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

Cite this