Decision CPM: Network Reduction and Solution

The Decision Critical Path Method (DCPM) applies to problems having a discrete time-cost tradeoff and including the possibility of interdependency constraints between the discrete job alternatives. Previously, it has been formulated as an integer-programming problem and solved by integer programming or by heuristic techniques. This paper shows that a variant of the usual critical path method may be used to reduce DCPM networks to equivalent networks containing only decision nodes and maximal distances between them. This operation, along with feasibility tests on the interdependency constraints, allows substantial simplification. A branch-and-bound method is then developed to solve the reduced problem.