An Approximation Algorithm for Scheduling Malleable Tasks under General Precedence Constraints

In this article, we study the problem of scheduling malleable tasks with precedence constraints. We are given m identical processors and n tasks. For each task the processing time is a function of the number of processors allotted to it. In addition, the tasks must be processed according to the precedence constraints. The goal is to minimize the makespan (maximum completion time) of the resulting schedule. The best previous approximation algorithm (that works in two phases) in Lepere et al. [2002b] has a ratio 3 + root 5 approximate to 5.236. We develop an improved approximation algorithm with a ratio at most 100/43 + 100(root 4349 - 7)/2451 approximate to 4.730598. We also show that our resulting ratio is asymptotically tight.