作者:Skutella, Martin; Sviridenko, Maxim; Uetz, Marc
作者单位:Technical University of Berlin; Yahoo! Inc; University of Twente
摘要:Two important characteristics encountered in many real-world scheduling problems are heterogeneous processors and a certain degree of uncertainty about the processing times of jobs. In this paper we address both, and study for the first time a scheduling problem that combines the classical unrelated machine scheduling model with stochastic processing times of jobs. By means of a novel time-indexed linear programming relaxation, we show how to compute in polynomial time a scheduling policy with...