Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Megow, Nicole; Uetz, Marc; Vredeveld, Tjark License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-1106

; ;

Models and Algorithms for Stochastic Online Scheduling



We introduce a model for non-preemptive scheduling under uncertainty. In this model, we combine the main characteristics of online and stochastic scheduling in a simple and natural way. Job processing times are assumed to be stochastic, but in contrast to the classical stochastic scheduling models, we assume that jobs arrive online over time, and there is no knowledge about the jobs that will arrive in the future. The model incorporates both, stochastic scheduling and online scheduling as a special case. The particular setting we analyze is parallel machine scheduling, with the objective to minimize the total weighted completion times of jobs. We propose simple, combinatorial online scheduling policies for that model, and derive performance guarantees that match the currently best known performance guarantees for stochastic parallel machine scheduling. For processing times that follow NBUE distributions, we improve upon previously best known performance bounds, even though we consider a more general setting.

BibTeX - Entry

  author =	{Megow, Nicole and Uetz, Marc and Vredeveld, Tjark},
  title =	{{Models and Algorithms for Stochastic Online Scheduling}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-1106},
  doi =		{10.4230/DagSemProc.05031.15},
  annote =	{Keywords: stochastic scheduling , online optimization , weighted completion time}

Keywords: stochastic scheduling , online optimization , weighted completion time
Seminar: 05031 - Algorithms for Optimization with Incomplete Information
Issue date: 2005
Date of publication: 09.06.2005

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