Paper Info
Title
Unrelated Machine Scheduling with Stochastic Processing Times.
Abstract
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.
Year
DOI
Venue
2016
10.1287/moor.2015.0757
MATHEMATICS OF OPERATIONS RESEARCH
Keywords
Field
DocType
stochastic scheduling,approximation algorithm,linear programming relaxation
Fixed-priority pre-emptive scheduling,Mathematical optimization,Multiprocessor scheduling,Fair-share scheduling,Computer science,Flow shop scheduling,Rate-monotonic scheduling,Dynamic priority scheduling,Earliest deadline first scheduling,Round-robin scheduling
Journal
Volume
Issue
ISSN
41
3
0364-765X
Citations 
PageRank 
References 
7
0.50
19
Authors
3
Name
Order
Citations
PageRank
Martin Skutella1128597.86
MAXIM SVIRIDENKO22072140.65
Marc Uetz345643.99