Scheduling parallelizable tasks

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 ε {1,…, N } is a nonincreasing function t j (β j ) of the number of processors β j ε {1,…, P } allotted to it. The goal is to find, for each task j , an allotment of processors β j , 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 rectangles 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.