Complexity of the discrete time–cost tradeoff problem for project networks

Complexity of the discrete time–cost tradeoff problem for project networks

0.00 Avg rating0 Votes
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: , , ,
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.

Reviews

Required fields are marked *. Your email address will not be published.