A Dynamic Programming Algorithm for Decision CPM Networks

Thomas J. Hindelang and John Muth
Additional contact information
Thomas J. Hindelang: Drexel University, Philadelphia, Pennsylvania

Operations Research, 1979, vol. 27, issue 2, 225-241

Abstract: 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.

Date: 1979
References: Add references at CitEc
Citations: View citations in EconPapers (23)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.27.2.225 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:27:y:1979:i:2:p:225-241

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().