ALCOMFT-TR-03-148

Thomas Decker, Thomas Lücking and Burkhard Monien
A 5/4-approximation algorithm for scheduling identical malleable tasks
Paderborn. Work package 4. December 2003.

Abstract: We consider the problem of finding a schedule for n identical malleable tasks on p identical processors with minimal completion time. This problem arises while using the branch & bound or the divide & conquer strategy to solve a problem on a parallel system. If nothing is known about the sub-problems, then they are assumed to be identical. We assume that the execution time decreases with the number of processors while the computational work increases. We give an algorithm with running time exponential in p which computes an optimal schedule. In order to approximate an optimal schedule, we use the concept of phase-by-phase schedules. Here schedules consist of phases in which every job uses the same number of processors. We prove that one can approximate an optimal schedule up to a factor 5/4 using constant time. We show that this is optimal. Furthermore, we give an epsislon-approximation algorithm if the speed-up is optimal up to a constant factor.

Postscript file: ALCOMFT-TR-03-148.ps.gz (102 kb).