Analysis of Smith's rule in stochastic machine scheduling

Caroline Jagtenberg, Uwe Schwiegelshohn*, Marc Uetz

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review


Abstract In a landmark paper from 1986, Kawaguchi and Kyan show that scheduling jobs according to ratios weight over processing time-also known as Smith's rule-has a tight performance guarantee of (1+2)/2≈1.207 for minimizing the weighted sum of completion times in parallel machine scheduling. We prove the counterintuitive result that the performance guarantee of Smith's rule is not better than 1.243 when processing times are exponentially distributed.

Original languageEnglish
Pages (from-to)570-575
Number of pages6
JournalOperations Research Letters
Issue number6
Publication statusPublished - 3 Sept 2013
Externally publishedYes


  • Keywords Stochastic scheduling WSEPT Exponential distribution


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

Cite this