A new average case analysis for completion time scheduling

(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.

Authors

• Mark Scharbrodt
• Thomas Schickinger
• Angelika Steger

Keywords

No keywords are indexed for this paper.