Lower bounds for Smith's rule in stochastic machine scheduling

Jagtenberg, Caroline and Schwiegelshohn, Uwe and Uetz, Marc (2011) Lower bounds for Smith's rule in stochastic machine scheduling. In: 8th International Workshop on Approximation and Online Algorithms, WAOA 2010, September 9-10, 2010, Liverpool, England.

PDF
Restricted to UT campus only: Request a copy
247Kb

Abstract:	We consider the problem to minimize the weighted sum of completion times in nonpreemptive parallel machine scheduling. In a landmark paper from 1986, Kawaguchi and Kyan showed that scheduling the jobs according to the WSPT rule -also known as Smith's rule- has a performance guarantee of 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.
Item Type:	Conference or Workshop Item
Copyright:	© 2011 Springer
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/76015
Official URL:	http://dx.doi.org/10.1007/978-3-642-18318-8
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page