PROJECT SCHEDULING WITH DISCRETE AND CONTINUOUS RESOURCES

Allocation is discussed of constrained resources among activities of a network project, when the resource requirements of activities concern a unit of a discrete resource (machine, processor) from a finite set of m parallel units and an amount of a continuously divisible resource (power, fuel flow, approximate manpower) which is arbitrary within a certain interval. For every activity the function relating the performing speed to the allotted amount of continuous resource is known as is the state which has to be reached in order to complete the activity. Two optimality criteria; project duration and the mean finishing time of an activity are considered. For the first criterion the way in which finding the optimal solution is reduced to a constrained nonlinear programming problem is described. The number of variables in this problem depends on the number of m-element combinations of activities which may be performed simultaneously in accordance with the precedence constraints. Consequently, this approach is of more theoretical than practical importance. For some special cases, however, it allows analytical results to be obtained. Next, an approximate method is described which consists of two stages. In the first stage the problem of scheduling activities with known performing times on parallel machines is solved, and in the second, the continuous resource is allocated among the activities (or parts of activities) which are performed simultaneously in the obtained schedule. For the cases in which polynomial-in-time procedures for the first stage of the method exist, this method is capable of solving projects involving several hundred activities and several dozen units of a discrete resource. Computational experiments show that for simple problems which may be solved optimally, heuristic solutions differ from the optimum by several percent on the average. The idea of the suboptimal algorithm is extended to the case of the mean finishing time criterion. Possible further generalizations of the presented results are pointed out. Copyright © 1979 by The Institute of Electrical and Electronics Engineers, Inc.