title   
  

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

Akkan, Can and Drexl, Andreas and Kimms, Alf (2005) Network decomposition-based benchmark results for the discrete time-cost tradeoff problem. European Journal of Operational Research, 165 (2). pp. 339-358. ISSN 0377-2217

[img]PDF - Repository staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
353Kb
[img]
Preview
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
709Kb

Official URL: http://dx.doi.org/10.1016/j.ejor.2004.04.006

Abstract

In project management, the project duration can often be compressed by accelerating some of its activities at an additional expense. This is the so-called time–cost tradeoff problem which has been extensively studied in the past. However, the discrete version of the problem which is of great practical relevance, did not receive much attention so far. Given a set of modes (time–cost pairs) for each activity, the objective of the discrete time–cost tradeoff problem is to select a mode for each activity so that the total cost is minimized while meeting a given project deadline. The discrete time–cost tradeoff problem is a strongly -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.

Item Type:Article
Uncontrolled Keywords:project scheduling; activity network; time-cost tradeoff; network decomposition; column generation
Subjects:H Social Sciences > H Social Sciences (General)
ID Code:704
Deposited By:Can Akkan
Deposited On:30 Dec 2005 02:00
Last Modified:25 May 2011 14:03

Repository Staff Only: item control page