Scheduling parallelizable tasks: Putting it all on the shelf

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.