Approximation in stochastic scheduling: The power of LP-based priority policies

We consider the problem to minimize the total weighted completion time of a set of jobs with individual release dates which have to be scheduled on id entical parallel machines. Job processing times are not known in advance, t hey are realized on-line according to given probability distributions. The aim is to find a scheduling policy that minimizes the objective in expectat ion. Motivated by the success of LP-based approaches to deterministic sched uling, we present a polyhedral relaxation of the performance space of stoch astic parallel machine scheduling. This relaxation extends earlier relaxati ons that have been used, among others, by Hall et al. [1997] in the determi nistic setting. We then derive constant performance guarantees for priority policies which are guided by optimum LP solutions, and thereby generalize previous results from deterministic scheduling. In the absence of release d ates, the LP-based analysis also yields an additive performance guarantee f or the WSEPT rule which implies both a worst-case performance ratio and a r esult on its asymptotic optimality, thus complementing previous work by Wei ss [1990]. The corresponding LP lower bound generalizes a previous lower bo und from deterministic scheduling due to Eastman et al. [1964], and exhibit s a relation between parallel machine problems and corresponding problems w ith only one fast single machine. Finally, we show that all employed LPs ca n be solved in polynomial time by purely combinatorial algorithms.