License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-1106
URL: http://drops.dagstuhl.de/opus/volltexte/2005/110/

Megow, Nicole ; Uetz, Marc ; Vredeveld, Tjark

Models and Algorithms for Stochastic Online Scheduling

pdf-format:
Dokument 1.pdf (138 KB)


Abstract

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

@InProceedings{megow_et_al:DSP:2005:110,
  author =	{Nicole Megow and Marc Uetz and Tjark Vredeveld},
  title =	{Models and Algorithms for Stochastic Online Scheduling},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  year =	{2005},
  editor =	{Susanne Albers and Rolf H. M{\"o}hring and Georg Ch. Pflug and R{\"u}diger Schultz},
  number =	{05031},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2005/110},
  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 Published by LZI