Lower bounds for Smith’s rule in stochastic machine scheduling. (English) Zbl 1314.90044
Jansen, Klaus (ed.) et al., Approximation and online algorithms. 8th international workshop, WAOA 2010, Liverpool, UK, September 9–10, 2010. Revised papers. Berlin: Springer (ISBN 978-3-642-18317-1/pbk). Lecture Notes in Computer Science 6534, 142-153 (2011).
Summary: We consider the problem to minimize the weighted sum of completion times in nonpreemptive parallel machine scheduling. In a landmark paper, T. Kawaguchi and S. Kyan [SIAM J. Comput. 15, 1119–1129 (1986; Zbl 0621.68024)] showed that scheduling the jobs according to the WSPT rule – also known as Smith’s rule – has a performance guarantee of \(\frac{1}{2}(1+\sqrt{2})\approx 1.207\). They also gave an instance to show that this bound is tight. We consider the stochastic variant of this problem in which the processing times are exponentially distributed random variables. We show, somehow counterintuitively, that the performance guarantee of the WSEPT rule, the stochastic analogue of WSPT, is not better than 1.243. This constitutes the first lower bound for WSEPT in this setting, and in particular, it sheds new light on the fundamental differences between deterministic and stochastic scheduling problems.
For the entire collection see [Zbl 1206.68011].
For the entire collection see [Zbl 1206.68011].
MSC:
| 90B36 | Stochastic scheduling theory in operations research |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
