Paper Info
Title
Stochastic Scheduling on Unrelated Machines.
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-i,P-j, 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[Sigma(j) 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 + 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 our bound is (2 + Delta) + epsilon. We also show that the dependence of the performance guarantees on A is tight. Via Delta = 0, currently best known bounds for deterministic scheduling on unrelated machines are contained as special case.
Year
DOI
Venue
2014
10.4230/LIPIcs.STACS.2014.639
Leibniz International Proceedings in Informatics
Keywords
Field
DocType
Stochastic Scheduling,Unrelated Machines,Approximation Algorithm
Approximation algorithm,Discrete mathematics,Random variable,Combinatorics,Square (algebra),Upper and lower bounds,Computer science,Scheduling (computing),Time complexity,Linear programming relaxation,Special case
Conference
Volume
ISSN
Citations 
25
1868-8969
2
PageRank 
References 
Authors
0.41
19
3
Name
Order
Citations
PageRank
Martin Skutella1128597.86
MAXIM SVIRIDENKO22072140.65
Marc Uetz345643.99