Analysis of Smith's rule in stochastic machine scheduling

C. Jagtenberg, U. Schwiegelshohn, Marc Jochen Uetz

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

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 approximately 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 languageUndefined
Pages (from-to)570-575
Number of pages6
JournalOperations research letters
Volume41
Issue number6
DOIs
Publication statusPublished - Nov 2013
Event8th International Workshop on Approximation and Online Algorithms 2010 - University of Liverpool, Liverpool, United Kingdom
Duration: 9 Sep 201010 Sep 2010
Conference number: 8

Keywords

  • WSPT
  • Stochastic Scheduling
  • EWI-23589
  • IR-86968
  • Scheduling
  • METIS-297782
  • Exponential distribution

Cite this