# 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)

## 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 language Undefined 31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014 Ernst W. Mayr, Natacha Portier Dagstuhl, Germany Dagstuhl 639-650 12 978-3-939897-65-1 https://doi.org/10.4230/LIPIcs.STACS.2014.639 Published - 19 Feb 2014 31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014 - Lyon, FranceDuration: 5 Mar 2014 → 8 Mar 2014

### Publication series

Name Leibniz International Proceedings in Informatics Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik 25 1868-8969

### Conference

Conference 31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014 5/03/14 → 8/03/14 5-8 March 2014

## Keywords

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