Article ID: | iaor20003419 |
Country: | United States |
Volume: | 45 |
Issue: | 2 |
Start Page Number: | 302 |
End Page Number: | 306 |
Publication Date: | Mar 1997 |
Journal: | Operations Research |
Authors: | De Prabuddha, Ghosh J.B., Wells C.E., Dunne E.J. |
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.