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

Epstein, Leah ; Stee, Rob van

Online scheduling of splittable tasks

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

Abstract

We consider online scheduling of splittable tasks on parallel machines. In our model, each task can be split into a limited number of parts, that can then be scheduled independently. We consider both the case where the machines are identical and the case where some subset of the machines have a (fixed) higher speed than the others. We design a class of algorithms which allows us to give tight bounds for a large class of cases where tasks may be split into relatively many parts. For identical machines we also improve upon the natural greedy algorithm in other classes of cases.

BibTeX - Entry

@InProceedings{epstein_et_al:DSP:2005:74,
  author =	{Leah Epstein and Rob van Stee},
  title =	{Online scheduling of splittable tasks},
  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/74},
  annote =	{Keywords: online scheduling , splittable tasks , parallel machines , greedy algorithm}
}

Keywords: online scheduling , splittable tasks , parallel machines , greedy 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