License: 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.2015.474
URN: urn:nbn:de:0030-drops-49359
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4935/
Go to the corresponding LIPIcs Volume Portal

Im, Sungjin ; Moseley, Benjamin ; Pruhs, Kirk

Stochastic Scheduling of Heavy-tailed Jobs

pdf-format:
35.pdf (0.7 MB)

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 3-field 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 inverse-polynomial 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 Heavy-tailed Jobs}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{474--486},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Ernst W. Mayr and Nicolas Ollinger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4935},
  URN =		{urn:nbn:de:0030-drops-49359},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI