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 - http://www.scopus.com/inward/record.url?scp=84883148947&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84883148947&partnerID=8YFLogxK
U2 - 10.1016/j.orl.2013.08.001
DO - 10.1016/j.orl.2013.08.001
M3 - Article
AN - SCOPUS:84883148947
VL - 41
SP - 570
EP - 575
JO - Operations Research Letters
JF - Operations Research Letters
SN - 0167-6377
IS - 6
ER -