Analysis of Smith's rule in stochastic machine scheduling

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.