Unrelated Machine Scheduling with Stochastic Processing Times

Martin Skutella, Maxim Sviridenko, Marc Uetz

Research output: Contribution to journalArticleAcademicpeer-review

31 Citations (Scopus)
36 Downloads (Pure)


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 provable performance guarantee for the stochastic version of the unrelated parallel machine scheduling problem with the weighted sum of completion times objective. Our performance guarantee depends on the squared coefficient of variation of the processing times and we show that this dependence is tight. Currently best-known bounds for deterministic scheduling problems are contained as special cases.
Original languageEnglish
Pages (from-to)851-864
Number of pages14
JournalMathematics of operations research
Issue number3
Publication statusPublished - Aug 2016


  • Stochastic scheduling
  • Approximation algorithm
  • Unrelated machines
  • 90B36, 68M20, 90C27, 90C59, 68W25, 68W40, 68Q25
  • Minsum objective
  • 22/4 OA procedure


Dive into the research topics of 'Unrelated Machine Scheduling with Stochastic Processing Times'. Together they form a unique fingerprint.

Cite this