@inproceedings{1eafcc9bb1ec4e4187b836309cc9008d,

title = "Stochastic scheduling on unrelated machines",

abstract = "Two important characteristics encountered in many real-world scheduling problems are heterogeneous 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 unrelated machine scheduling model with stochastic processing times of jobs. Here, the processing time of job $j$ on machine $i$ is governed by random variable $\p_{ij}$, and its realization becomes known only upon job completion. With $w_j$ being the given weight of job $j$, we study the objective to minimize the expected total weighted completion time~$E[\sum_j w_jC_j]$, where~$C_j$ 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+\Delta)/2+\epsilon$. Here, $\epsilon>0$ is arbitrarily small, and $\Delta$ is an upper bound on the squared coefficient of variation of the processing times. When jobs also have individual release dates~$r_{ij}$, our bound is $(2+\Delta)+\epsilon$. We also show that the dependence of the performance guarantees on~$\Delta$ is tight. Via $\Delta=0$, currently best known bounds for deterministic scheduling on unrelated machines are contained as special case.",

keywords = "EWI-24580, unrelated machines, minsum objective, Stochastic Scheduling, Approximation Algorithm, METIS-304022, IR-89687",

author = "Martin Skutella and Maxim Sviridenko and Uetz, {Marc Jochen}",

note = "10.4230/LIPIcs.STACS.2014.639 ; null ; Conference date: 05-03-2014 Through 08-03-2014",

year = "2014",

month = feb,

day = "19",

doi = "10.4230/LIPIcs.STACS.2014.639",

language = "Undefined",

isbn = "978-3-939897-65-1",

series = "Leibniz International Proceedings in Informatics",

publisher = "Dagstuhl",

pages = "639--650",

editor = "Mayr, {Ernst W.} and Natacha Portier",

booktitle = "31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014",

address = "Germany",

}