2026-07-23T19:43:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4494 2024-03-06T10:35:08Z ddc:004 open_access

Stochastic Scheduling on Unrelated Machines Skutella, Martin Sviridenko, Maxim Uetz, Marc Stochastic Scheduling Unrelated Machines Approximation Algorithm 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 w_j.C_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+D)/2+e. Here, e>0 is arbitrarily small, and D 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+D)+e. We also show that the dependence of the performance guarantees on D is tight. Via D=0, currently best known bounds for deterministic scheduling on unrelated machines are contained as special case. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Skutella and Maxim Sviridenko and Marc Uetz 2014 Is Part Of LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2014.639 urn:nbn:de:0030-drops-44946 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.639 eng https://creativecommons.org/licenses/by/3.0/legalcode