COMPLEXITY OF THE DISCRETE TIME-COST TRADEOFF PROBLEM FOR PROJECT NETWORKS

This note addresses the discrete version of the well-known time-cost t radeoff problem for project networks, which has been studied previousl y in the standard project management literature as well as in the rela ted literature on Decision-CPM, All the algorithms proposed thus far f or the solution of the general problem exhibit exponential worst-case complexity, with the notable exception of the pseudo-polynomial dynami c program due to Hindelang and Muth. We first demonstrate that this al gorithm is flawed, and that when we correct it. it no longer remains p seudo-polynomial. Continuing on in the main result of the note, we sho w that this is not at all surprising, since the problem is strongly NP -hard. Finally, we discuss the complexities of various network structu res and validate an old conjecture that certain structures are necessa rily more difficult to solve.