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

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
Volume41
Issue number6
DOIs
Publication statusPublished - 3 Sep 2013
Externally publishedYes

Keywords

  • Keywords Stochastic scheduling WSEPT Exponential distribution

Fingerprint

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

Cite this