Resource allocation via dynamic programming in activity networks

The paper investigates the application of dynamic programming to the problem of resource allocation in a project, with the objective of minimizing the project completion time. It assumes that there is a relationship between the amount of the resource allocated to an activity and its duration, which is monotone nonincreasing in its argument. The motivation for this study is the recent development of a procedure which yields the minimum number of nodes to be ‘reduced’ in the AN. This drastically alters the complexity of the DP approach from O(U^h) to O(U^c), where h is the number of ‘common’ activities and c is the minimum number of ‘reduced’ nodes since, typically, h>>c. The paper presents and illustrates the DP optimizing procedure, which is easily seen to be still plagued by the ‘curse of dimensionality’ despite the drastic reduction in complexity mentioned above. It then presents an elementary approximating procedure which provides an upper bound on the optimum and is computationally more economical for c≥3. The paper illustrates both procedures by a small numerical example. Continuing research is devoted to evaluating the efficacy of the approximating procedure, and investigating other approximations.