A scheduling algorithm for parallelizable dependent tasks

Scheduling a collection of tasks on a multiprocessor consisting of p processors, that minimizes the maximum completion time has attracted a lot of attention in the literature. The paper introduces a new problem of scheduling a task graph on a multiprocessor, called the parallelizable dependent task scheduling problem. Associated with each task is the time it takes to run on a uniprocessor, and the speedup that can be obtained by running it on i processors, 1⩽i⩽p. The paper presents an algorithm for the problem and analyzes the performance