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 ϵ > 0, the algorithm computes a non-preemptive schedule of length at most (1+ϵ) times the optimum (plus an additive term) and has running time polymial in n, m and 1/ϵ.