Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2018.43
URN: urn:nbn:de:0030-drops-85034
URL: https://drops.dagstuhl.de/opus/volltexte/2018/8503/
Jäger, Sven ; Skutella, Martin
Generalizing the Kawaguchi-Kyan Bound to Stochastic Parallel Machine Scheduling
| pdf-format: |
|
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 algorithm---the 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 Kawaguchi-Kyan Bound to Stochastic Parallel Machine Scheduling}},
booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
pages = {43:1--43:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-062-0},
ISSN = {1868-8969},
year = {2018},
volume = {96},
editor = {Rolf Niedermeier and Brigitte Vall{\'e}e},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8503},
URN = {urn:nbn:de:0030-drops-85034},
doi = {10.4230/LIPIcs.STACS.2018.43},
annote = {Keywords: Stochastic Scheduling, Parallel Machines, Approximation Algorithm, List Scheduling, Weighted Shortest (Expected) Processing Time Rule}
}
| 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 |
