A new average case analysis for completion time scheduling

Abstract

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 goal is to use the concept of competitive ratio---which is a typical worst case notion---also within an average case analysis. We show that the classic SEPT scheduling strategy with Ω( n ) worst-case competitive ratio achieves an average of O(1) under several natural distributions, among them the exponential distribution. Our analysis technique allows to also roughly estimate the probability distribution of the competitive ratio. Thus, our result bridges the gap between worst case and average case performance guarantee.