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
SIGMETRICS 1992
Conference paper
Scheduling parallelizable tasks: Putting it all on the shelf
Abstract
In this paper we formulate the following natural multiprocessor scheduling problem: Consider a parallel system with P processors. Suppose that there are N tasks to be scheduled on this system, and that the execution time of each task j G {1,..., N} is a nonincreasing function tj(B1) of the number of processors fij € {l,...,P} allotted to it. The goal is to find, for each task j} an allotment of processors ftj, and, overall, a schedule assigning the tasks to the processors which minimizes the makespan, or latest task completion time. The so-called shelf strategy is commonly used for orthogonal rectangle packing, a related and classic optimization problem. The prime difference between the orthogonal rectangle problem and our own is that in our case the rectan-gles are, in some sense, malleable; The height of each rectangle is a nonincreasing function of its width. In this paper, we solve our multiprocessor scheduling problem exactly in the context of a shelf-based paradigm. The algorithm we give uses techniques from resource allocation theory and employs a variety of other combinatorial optimization techniques.