Network decomposition-based benchmark results for the discrete time-cost tradeoff problem

The discrete time-cost tradeoff problem is a strongly NP-hard optimization problem for general activity networks. In terms of what current state-of-art algorithms can do, instances with (depending on the structure of the network and the number of processing alternatives per activity) no more than 20-50 activities can be solved to optimality in reasonable amount of time. Hence, heuristics must be employed to solve larger instances. To evaluate such heuristics, lower bounds are needed. This paper provides lower and upper bounds using column generation techniques based on “network decomposition”. Furthermore, a computational study is provided to demonstrate that the presented bounds are tight and that large and hard instances can be solved in short run-time.