STOC Conference 2002 Conference Paper
A new average case analysis for completion time scheduling
- Mark Scharbrodt
- Thomas Schickinger
- Angelika Steger
(MATH) We present a new average case analysis for the problem of scheduling n jobs on $m$ machines so that the sum of job completion times is minimized. Our analysis transfers the concept of competitive analysis --- which is a typical worst case notion --- to the average case. We show that the classic SEPT scheduling strategy with Ω( n ) worst case competitive ratio achieves ${\cal O}(1)$ on the average. Moreover, bounds on the probability distribution of the competitive ratio are derived which provide an in-depth understanding of the stochastic version of the min sum scheduling problem.