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)
62 Downloads (Pure)

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

Publication series

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

Conference

Conference31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014
Period5/03/148/03/14
Other5-8 March 2014

Keywords

  • EWI-24580
  • unrelated machines
  • minsum objective
  • Stochastic Scheduling
  • Approximation Algorithm
  • METIS-304022
  • IR-89687

Cite this