Online scheduling of splittable tasks
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.
|Dagstuhl Seminar Proceedings|
|Algorithms for Optimization with Incomplete Information 2005|
|Organisation||Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands|
Epstein, L, & van Stee, R. (2005). Online scheduling of splittable tasks. In Proceedings of Algorithms for Optimization with Incomplete Information 2005.