Analysis of Smith's rule in stochastic machine scheduling

C. Jagtenberg; U. Schwiegelshohn; Marc Jochen Uetz

doi:10.1016/j.orl.2013.08.001

Analysis of Smith's rule in stochastic machine scheduling

C. Jagtenberg, U. Schwiegelshohn, Marc Jochen Uetz

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

1 Citation (Scopus)

9 Downloads (Pure)

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 language	Undefined
Pages (from-to)	570-575
Number of pages	6
Journal	Operations research letters
Volume	41
Issue number	6
DOIs	https://doi.org/10.1016/j.orl.2013.08.001
Publication status	Published - Nov 2013
Event	8th International Workshop on Approximation and Online Algorithms 2010 - University of Liverpool, Liverpool, United Kingdom Duration: 9 Sept 2010 → 10 Sept 2010 Conference number: 8

Keywords

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

Access to Document

10.1016/j.orl.2013.08.001

http://eprints.eemcs.utwente.nl/secure2/23589/01/ORL-2013.pdf

Cite this

@article{735ae9922e7e403da4493fb41539d6eb,

title = "Analysis of Smith's rule in stochastic machine scheduling",

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{\textquoteright}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{\textquoteright}s rule is not better than 1.243 when processing times are exponentially distributed.",

keywords = "WSPT, Stochastic Scheduling, EWI-23589, IR-86968, Scheduling, METIS-297782, Exponential distribution",

author = "C. Jagtenberg and U. Schwiegelshohn and Uetz, {Marc Jochen}",

note = "eemcs-eprint-23589 ; 8th International Workshop on Approximation and Online Algorithms 2010 ; Conference date: 09-09-2010 Through 10-09-2010",

year = "2013",

month = nov,

doi = "10.1016/j.orl.2013.08.001",

language = "Undefined",

volume = "41",

pages = "570--575",

journal = "Operations research letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "6",

}

TY - JOUR

T1 - Analysis of Smith's rule in stochastic machine scheduling

AU - Jagtenberg, C.

AU - Schwiegelshohn, U.

AU - Uetz, Marc Jochen

N1 - Conference code: 8

PY - 2013/11

Y1 - 2013/11

N2 - 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.

AB - 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.

KW - WSPT

KW - Stochastic Scheduling

KW - EWI-23589

KW - IR-86968

KW - Scheduling

KW - METIS-297782

KW - Exponential distribution

U2 - 10.1016/j.orl.2013.08.001

DO - 10.1016/j.orl.2013.08.001

M3 - Article

SN - 0167-6377

VL - 41

SP - 570

EP - 575

JO - Operations research letters

JF - Operations research letters

IS - 6

T2 - 8th International Workshop on Approximation and Online Algorithms 2010

Y2 - 9 September 2010 through 10 September 2010

ER -