Complexity of the Discrete Time-Cost Tradeoff Problem for Project Networks

Prabuddha De, E. James Dunne, Jay B. Ghosh and Charles E. Wells
Additional contact information
Prabuddha De: University of Dayton, Dayton, Ohio
E. James Dunne: University of Dayton, Dayton, Ohio
Jay B. Ghosh: University of Dayton, Dayton, Ohio
Charles E. Wells: University of Dayton, Dayton, Ohio

Operations Research, 1997, vol. 45, issue 2, 302-306

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 (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.2.302 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:45:y:1997:i:2:p:302-306

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().