About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SPAA 1992
Conference paper
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*.