Scheduling malleable parallel tasks: An asymptotic fully polynomial time approximation scheme

A malleable parallel task is one whose execution time is a function of the number of (identical) processors allotted to it. We study the problem of scheduling a set of n independent malleable tasks on an arbitrary number m of parallel processors and propose an asymptotic fully polynomial time approximation scheme. For any fixed epsilon > 0, the algorithm computes a non-preemptive schedule of length at most (1 + epsilon) times the optimum (plus an additive term) and has running time polynomial in n, m and 1/epsilon.