Stochastic scheduling on unrelated machines

Martin Skutella, Maxim Sviridenko, Marc Jochen Uetz

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)
66 Downloads (Pure)


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.
Original languageEnglish
Title of host publication31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014
EditorsErnst W. Mayr, Natacha Portier
Place of PublicationDagstuhl, Germany
Number of pages12
ISBN (Print)978-3-939897-65-1
Publication statusPublished - 19 Feb 2014
Event31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014 - Lyon, France
Duration: 5 Mar 20148 Mar 2014
Conference number: 31

Publication series

NameLeibniz International Proceedings in Informatics
PublisherSchloss Dagstuhl-Leibniz-Zentrum fuer Informatik
ISSN (Print)1868-8969


Conference31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014
Abbreviated titleSTACS


  • Unrelated machines
  • Minsum objective
  • Stochastic scheduling
  • Approximation algorithm


Dive into the research topics of 'Stochastic scheduling on unrelated machines'. Together they form a unique fingerprint.

Cite this