Network decomposition-based lower and upper bounds for the discrete time-cost tradeoff problem

Can Akkan, Andreas Drexl and Alf Kimms

No 527, Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel from Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre

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 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 twenty to fifty 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. The aim of this paper is to provide such lower bounds using column generation techniques based on "network decomposition". We will show that a heuristic solution can be derived from that result as well. 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.

Keywords: Project Scheduling; Activity Network; Time-Cost Tradeoff; Network Decomposition; Column Generation (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.econstor.eu/bitstream/10419/147607/1/manuskript_527.pdf (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:zbw:cauman:527

Access Statistics for this paper

More papers in Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel from Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre Contact information at EDIRC.
Bibliographic data for series maintained by ZBW - Leibniz Information Centre for Economics ().