A Dynamic Programming Solution to Cost-Time Tradeoff for CPM

To solve the problem of time-cost tradeoff in project management with available models, a choice must be made between heuristic approaches and algorithms based upon restrictive assumptions about the shape of the cost-time functions of the activities. The algorithm presented in this article involves a dynamic-programming approach to determine the allocation which minimizes the duration of the project (critical path). The main advantage of this model is its ability to determine the optimum allocation among activities with arbitrary cost-time functions. Also, computational shortcuts for functions with special properties can be used to increase the efficiency of the model.

Objective functions of networks with special structures decompose into sequences of one-dimensional optimization problems. Although some complex networks have objective functions which cannot be fully decomposed, the dimensions of these functions are considerably less than the number of activities involved.

If the activities have nonincreasing cost-time functions, an optimal policy can be used to eliminate the usual search procedure for one-dimensional problems which involve minimizing the maximum of stage returns.