Analysis of Smith's rule in stochastic machine scheduling

Caroline Jagtenberg; Uwe Schwiegelshohn; Marc Uetz

doi:10.1016/j.orl.2013.08.001

Analysis of Smith's rule in stochastic machine scheduling

Caroline Jagtenberg
, Uwe Schwiegelshohn^*
, Marc Uetz

^*Corresponding author for this work

Research output: Contribution to Journal › Article › Academic › peer-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 language	English
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 - 3 Sept 2013
Externally published	Yes

Keywords

Keywords Stochastic scheduling WSEPT Exponential distribution

Access to Document

10.1016/j.orl.2013.08.001

Persistent URL (handle)

Persistent link

Cite this

@article{5df8dc3e3aec466fbefdb9725e3d55a5,

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

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.",

keywords = "Keywords Stochastic scheduling WSEPT Exponential distribution",

author = "Caroline Jagtenberg and Uwe Schwiegelshohn and Marc Uetz",

year = "2013",

month = sep,

day = "3",

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

language = "English",

volume = "41",

pages = "570--575",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

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

AU - Jagtenberg, Caroline

AU - Schwiegelshohn, Uwe

AU - Uetz, Marc

PY - 2013/9/3

Y1 - 2013/9/3

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

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

KW - Keywords Stochastic scheduling WSEPT Exponential distribution

UR - https://www.scopus.com/pages/publications/84883148947

UR - https://www.scopus.com/pages/publications/84883148947#tab=citedBy

U2 - 10.1016/j.orl.2013.08.001

DO - 10.1016/j.orl.2013.08.001

M3 - Article

AN - SCOPUS:84883148947

SN - 0167-6377

VL - 41

SP - 570

EP - 575

JO - Operations Research Letters

JF - Operations Research Letters

IS - 6

ER -

Analysis of Smith's rule in stochastic machine scheduling

Abstract

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this