License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-707
URL: http://drops.dagstuhl.de/opus/volltexte/2005/70/
Go to the corresponding Portal


Sanders, Peter ; Sivadasan, Naveen ; Skutella, Martin

Online Scheduling with Bounded Migration

pdf-format:
Document 1.pdf (120 KB)


Abstract

Consider the classical online scheduling problem where jobs that arrive one by one are assigned to identical parallel machines with the objective of minimizing the makespan. We generalize this problem by allowing the current assignment to be changed whenever a new job arrives, subject to the constraint that the total size of moved jobs is bounded by~$\beta$ times the size of the arriving job. Our main result is a linear time `online approximation scheme', that is, a family of online algorithms with competitive ratio~$1+\epsilon$ and constant migration factor~$\beta(\epsilon)$, for any fixed~$\epsilon>0$. This result is of particular importance if considered in the context of sensitivity analysis: While a newly arriving job may force a complete change of the entire structure of an optimal schedule, only very limited `local' changes suffice to preserve near-optimal solutions. We believe that this concept will find wide application in its own right. We also present simple deterministic online algorithms with migration factors~$\beta=2$ and~$\beta=4/3$, respectively. Their competitive ratio~$3/2$ beats the lower bound on the performance of any online algorithm in the classical setting without migration. We also present improved algorithms and similar results for closely related problems. In particular, there is a short discussion of corresponding results for the objective to maximize the minimum load of a machine. The latter problem has an application for configuring storage servers that was the original motivation for this work.

BibTeX - Entry

@InProceedings{sanders_et_al:DSP:2005:70,
  author =	{Peter Sanders and Naveen Sivadasan and Martin Skutella},
  title =	{Online Scheduling with Bounded Migration},
  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/70},
  annote =	{Keywords: scheduling, sensitivity analysis, online algorithm}
}

Keywords: scheduling, sensitivity analysis, online algorithm
Seminar: 05031 - Algorithms for Optimization with Incomplete Information
Issue Date: 2005
Date of publication: 30.05.2005


DROPS-Home | Fulltext Search | Imprint Published by LZI