NONPREEMPTIVE SCHEDULING OF INDEPENDENT TASKS WITH PRESPECIFIED PROCESSOR ALLOCATIONS

In this article we study the problem of scheduling independent tasks, each of which requires the simultaneous availability of a set of presp ecified processors, with the objective of minimizing the maximum compl etion time. We propose a graph-theoretical approach and identify a cla ss of polynomial instances, corresponding to comparability graphs. We show that the scheduling problem is polynomially equivalent to the pro blem of extending a graph to a comparability graph whose maximum weigh ted clique has minimum weight. Using this formulation we show that in some cases it is possible to decompose the problem according to the ca nonical decomposition of the graph. Finally, a general solution proced ure is given that includes a branch-and-bound algorithm for the soluti on of subproblems which can be neither decomposed nor solved in polyno mial time. Some examples and computational results are presented. (C) 1994 John Wiley & Sons, Inc.