Approximate algorithms for scheduling parallelizable tasks

Abstract

A parallelizable task is one that can be run on an arbitrary number of processors with a running time that depends on the number of processors allotted to it. Consider a parallel system having m identical processors and n independent parallelizable tasks to be scheduled on those processors. The goal is to find (1) for each task j, an allotment of processors βj, and, (2) overall, a nonpreemptive schedule assigning the tasks to the processors which minimizes the makespan, or latest task completion time. This multiprocessor scheduling problem is known to be NP-complete in the strong sense. We therefore concentrate on providing a heuristic that has polynomial running time with provable worst case bounds on the suboptimality of the solution. In particular, we give an algorithm that selects a family of (up to n(m - 1) + 1) candidate allotments of processors to tasks, thereby allowing us to use as a subroutine any algorithm A that 'solves' the simpler multiprocessor scheduling problem in which the number of processors allotted to a task is fixed. Our algorithm has the property that for a large class of previously studied algorithms our extension will match the same worst case bounds on the suboptimality of the solution while increasing the computational complexity of A by at most a factor of O(nm). As consequences we get polynomial time algorithms for the following: Assuming that processor addresses assigned to a task need not be contiguous, a schedule with makespan w ≤ 2w*, where w* is the makespan of the optimal schedule. Assuming that processor addresses need to be contiguous, a schedule with makespan w ≤ 2.5w*.