Abstract
We revisit the classical stochastic scheduling problem of nonpreemptively scheduling n jobs so as to minimize total completion time on m identical machines, P \mid \mid \mathbb{E} \sum C_j in the standard 3field scheduling notation. Previously it was only known how to obtain reasonable approximation if jobs sizes have low variability. However, distributions commonly arising in practice have high variability, and the upper bounds on the approximation ratio for the previous algorithms for such distributions can be even inversepolynomial in the maximum possible job size. We start by showing that
the natural list scheduling algorithm Shortest Expected Processing Time (SEPT) has a bad approximation ratio for high variability jobs. We observe that a simple randomized rounding of a natural linear programming relaxation is a (1+\epsilon)machine O(1)approximation assuming the number of machines is at least logarithmic in the number of jobs. Turning to the case of a modest number of machines, we develop a list scheduling algorithm that is O(\log^2 n + m \log n)approximate. Our results together imply a (1+\epsilon)machine O(\log^2 n )approximation for an arbitrary number of machines. Intuitively our list scheduling algorithm finds an ordering that not only takes the expected size of a job into account, but also takes into account the probability that job will be big.
BibTeX  Entry
@InProceedings{im_et_al:LIPIcs:2015:4935,
author = {Sungjin Im and Benjamin Moseley and Kirk Pruhs},
title = {{Stochastic Scheduling of Heavytailed Jobs}},
booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
pages = {474486},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897781},
ISSN = {18688969},
year = {2015},
volume = {30},
editor = {Ernst W. Mayr and Nicolas Ollinger},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/4935},
URN = {urn:nbn:de:0030drops49359},
doi = {10.4230/LIPIcs.STACS.2015.474},
annote = {Keywords: stochastic scheduling, completion time, approximation}
}
Keywords: 

stochastic scheduling, completion time, approximation 
Collection: 

32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) 
Issue Date: 

2015 
Date of publication: 

26.02.2015 