License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.05031.21
URN: urn:nbn:de:0030-drops-743
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2005/74/
|
Go to the corresponding Portal |
Epstein, Leah ;
Stee, Rob van
Online scheduling of splittable tasks
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:DagSemProc.05031.21,
author = {Epstein, Leah and Stee, Rob van},
title = {{Online scheduling of splittable tasks}},
booktitle = {Algorithms for Optimization with Incomplete Information},
pages = {1--3},
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 = {https://drops.dagstuhl.de/opus/volltexte/2005/74},
URN = {urn:nbn:de:0030-drops-743},
doi = {10.4230/DagSemProc.05031.21},
annote = {Keywords: online scheduling , splittable tasks , parallel machines , greedy algorithm}
}
|
Keywords: |
|
online scheduling , splittable tasks , parallel machines , greedy algorithm |
|
Collection: |
|
05031 - Algorithms for Optimization with Incomplete Information |
|
Issue Date: |
|
2005 |
|
Date of publication: |
|
30.05.2005 |
