Probabilistic Analysis of a Machine Scheduling Problem

There are n jobs that have to be processed on one available machine. The ith job arrives at epoch r₁ and it takes P₁ units of time to carry out its operation. No preemptions are allowed. It is desired to minimize total flow time. A probabilistic analysis is presented for this NP-hard problem (known as 1/r_j/∑C_j in the scheduling literature). Under very general probability distributions of the problem data, it is shown that the problem can be broken into 2 categories: the undersaturated and the oversaturated case. Asymptotically optimal algorithms are presented for each case.