Complexity of the Discrete Time-Cost Tradeoff Problem for Project Networks
Prabuddha De, E. James Dunne, Jay B. Ghosh, Charles E. Wells
Operations Research · 1997 · Volume 45 · Issue 2
Abstract
This note addresses the discrete version of the well-known time-cost tradeoff problem for project networks, which has been studied previously in the standard project management literature as well as in the related literature on Decision-CPM. All the algorithms proposed thus far for the solution of the general problem exhibit exponential worst-case complexity, with the notable exception of the pseudo-polynomial dynamic program due to Hindelang and Muth. We first demonstrate that this algorithm is flawed, and that when we correct it, it no longer remains pseudo-polynomial. Continuing on in the main result of the note, we show that this is not at all surprising, since the problem is strongly NP-hard. Finally, we discuss the complexities of various network structures and validate an old conjecture that certain structures are necessarily more difficult to solve.
Keywords
project management, time-cost tradeoff, analysis of algorithms, computational complexity, strong NP-completeness
Enable JavaScript for citation tools and additional paper interactions.