This is the authors' abstract. We don't add key points for this paper.
In this paper we formulate the following natural multiprocessor scheduling problem: Consider a parallel system with P processors. Suppose that there are Ntasks to be scheduled on this system, and that the execution time of each task j ε {1,…,N} is a nonincreasing function tj(β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.
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Turek et al. (1992) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: