Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9663747 | European Journal of Operational Research | 2005 | 20 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Can Akkan, Andreas Drexl, Alf Kimms,