Jäger, Sven ;
Skutella, Martin
Generalizing the KawaguchiKyan Bound to Stochastic Parallel Machine Scheduling
Abstract
Minimizing the sum of weighted completion times on m identical
parallel machines is one of the most important and classical
scheduling problems. For the stochastic variant where processing
times of jobs are random variables, Möhring, Schulz, and Uetz (1999) presented the first and still best known approximation result,
achieving, for arbitrarily many machines, performance
ratio 1+1/2(1+Delta), where Delta is an upper bound on the
squared coefficient of variation of the processing times. We prove
performance ratio 1+1/2(sqrt(2)1)(1+Delta)
for the same
underlying algorithmthe Weighted Shortest Expected Processing
Time (WSEPT) rule. For the special case of deterministic scheduling
(i.e., Delta=0), our bound matches the tight performance
ratio 1/2(1+sqrt(2)) of this algorithm (WSPT rule), derived by
Kawaguchi and Kyan in a 1986 landmark paper. We present several
further improvements for WSEPT's performance ratio, one of them
relying on a carefully refined analysis of WSPT yielding, for every
fixed number of machines m, WSPT's exact performance ratio of
order 1/2(1+sqrt(2))O(1/m^2).
BibTeX  Entry
@InProceedings{jger_et_al:LIPIcs:2018:8503,
author = {Sven J{\"a}ger and Martin Skutella},
title = {{Generalizing the KawaguchiKyan Bound to Stochastic Parallel Machine Scheduling}},
booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
pages = {43:143:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770620},
ISSN = {18688969},
year = {2018},
volume = {96},
editor = {Rolf Niedermeier and Brigitte Vall{\'e}e},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8503},
URN = {urn:nbn:de:0030drops85034},
doi = {10.4230/LIPIcs.STACS.2018.43},
annote = {Keywords: Stochastic Scheduling, Parallel Machines, Approximation Algorithm, List Scheduling, Weighted Shortest (Expected) Processing Time Rule}
}
27.02.2018
Keywords: 

Stochastic Scheduling, Parallel Machines, Approximation Algorithm, List Scheduling, Weighted Shortest (Expected) Processing Time Rule 
Seminar: 

35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Issue date: 

2018 
Date of publication: 

27.02.2018 