DagSemProc.05031.21.pdf
- Filesize: 63 kB
- 3 pages
Document
Online scheduling of splittable tasks
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 5031
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2005-05-30
Cite AsGet BibTex
Leah Epstein and Rob van Stee. Online scheduling of splittable tasks. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)
https://doi.org/10.4230/DagSemProc.05031.21
https://doi.org/10.4230/DagSemProc.05031.21
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.
Keywords
- online scheduling
- splittable tasks
- parallel machines
- greedy algorithm
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads