A Dynamic Programming Algorithm for Decision CPM Networks

This paper proposes a dynamic programming algorithm for decision CPM (DCPM) networks. DCPM is a natural, powerful, and general way of handling the discrete-time/cost-tradeoff problem. Solution approaches developed to date have not been efficient enough to handle realistically sized problems. The main approaches have been general integer programming algorithms and the specialized branch-and-bound methods for DCPM of Crowston and Wagner. Both of these approaches have many inherent shortcomings solution times grow exponentially with the number of decision nodes, storage requirements quickly become excessive, pre-processing or decomposition of the problem must be undertaken before the algorithms themselves can be called upon to solve the problem, and large variations in solution times have been found based on differences in the structure of the problem. The algorithm presented here overcomes all of these shortcomings. Most significantly, it exhibits only a linear growth in the solution times based on the number of connections between nodes. In addition, the structure of the algorithm is such that it simultaneously determines the optimal solution for any desired number of project due dates with only a slight increase in computer time. This feature provides valuable information in performing a sensitivity analysis for the project and in preparing for negotiations about the project due date, etc. Test problem results are reported and recommendations are made for extending the algorithm to handle related problems.