Stochastic scheduling on unrelated machines

Two important characteristics encountered in many real-world scheduling problems are hetero-geneous processors and a certain degree of uncertainty about the sizes of jobs. In this paper we address both, and study for the first time a scheduling problem that combines the classical un-related machine scheduling model with stochastic processing times of jobs. Here, the processing time of job j on machine i is governed by random variable Pij, and its realization becomes known only upon job completion. With wj being the given weight of job j, we study the objective to minimize the expected total weighted completion time E j wjCj, where Cj is the completion time of job j. By means of a novel time-indexed linear programming relaxation, we compute in polynomial time a scheduling policy with performance guarantee (3+∆)/2+ε. Here, ε> 0 is ar-bitrarily small, and ∆ is an upper bound on the squared coefficient of variation of the processing times. When jobs also have individual release dates rij, our bound is (2 + ∆) + ε. We also show that the dependence of the performance guarantees on ∆ is tight. Via ∆ = 0, currently best known bounds for deterministic scheduling on unrelated machines are contained as special case