Dynamic Programming Models of the Nonserial Critical Path-Cost Problem

One of the major contributions to the planning and management of Research and Development organizations is the evolution of methods for dealing with PERT-Cost or CPM-Cost problems. Classically however, variations of the critical path-cost (CPM-Cost) problem, arising when different cost duration relationships are assumed, have been mostly studied via techniques other than dynamic programming. If the precedence relations possess a serial structure, one can develop two essentially equivalent dynamic programming formulations, of the resource allocation variety, by minimizing either the project cost or the completion time. When nonserial precedence relationships are involved, this problem cannot be solved by routine invocation of conventional dynamic programming formulations or algorithms. The intent of this paper is to show that efficient nonserial dynamic programming formulations can be developed for several complex nonserial CPM-Cost problem situations. In particular, the project time minimization procedure results in less complex dynamic programming models and is thus employed in this paper. Three recent computational reduction techniques based primarily on the introduction of the artifice of pseudo-tasks and pseudo-stages are invoked to treat different variations of this essentially nonserial critical path-cost problem. Considerable savings in computational requirements are achieved by consolidating all phases preceding a junction node prior to the invocation of the dynamic programming procedure. The advantages of these approaches over existing mathematical programming methods include their ability to handle nonlinear cost functions and constraints, as well as their highly efficient parametrization capabilities. Further, the complexity of the dynamic programming formulation does not, unlike other methods, increase with the number of phases (tasks) but only with the degree in which the additional tasks change the structure of the precedence relations.