Nonpreemptive scheduling of independent tasks with prespecified processor allocations

Nonpreemptive scheduling of independent tasks with prespecified processor allocations

0.00 Avg rating0 Votes
Article ID: iaor1995953
Country: United States
Volume: 41
Issue: 7
Start Page Number: 959
End Page Number: 971
Publication Date: Dec 1994
Journal: Naval Research Logistics
Authors: , ,
Abstract:

In this article the authors study the problem of scheduling independent tasks, each of which requires the simultaneous availability of a set of prespecified processors, with the objective of minimizing the maximum completion time. They propose a graph-theoretical approach and identify a class of polynomial instances, corresponding to comparability graphs. The authors show that the scheduling problem is polynomially equivalent to the problem of extending a graph to a comparability graph whose maximum weight clique has minimum weight. Using this formulation they show that in some cases it is possible to decompose the problem according to the canonical decomposition of the graph. Finally, a general solution procedure is given that includes a branch-and-bound algorithm for the solution of subproblems which can be neither decomposed nor solved in polynomial time. Some examples and computational results are presented.

Reviews

Required fields are marked *. Your email address will not be published.