Complexity of the discrete time-cost tradeoff problem for project networks
成果类型：
Article
署名作者：
De, P; Dunne, EJ; Ghosh, JB; Wells, CE
署名单位：
Ihsan Dogramaci Bilkent University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.45.2.302
发表日期：
1997
页码：
302-306
关键词：
摘要：
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.