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
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.