Please use this identifier to cite or link to this item: http://hdl.handle.net/10419/147586
Authors: 
Sprecher, Arno
Year of Publication: 
1998
Series/Report no.: 
Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel No. 493
Abstract: 
Over the years numerous branch-and-bound procedures for solving the resource-constrained project scheduling problem (RCPSP) have been developed. Enumerating delaying alternatives, extension alternatives, feasible posets, feasible sequences, feasible completion times or feasible subsets, they all aim at finding as fast as possible a makespan minimal schedule among the resource and precedence feasible ones. Some of the enumeration schemes have been modified to solve variants of the so-called resource-constrained project scheduling problem, like the resource-constrained project scheduling problem with multiple modes or with work content defined modes. We compare the enumeration of delaying alternatives and the enumeration of extension alternatives. Roughly considered the concepts that analyze only minimal delaying alternatives and the concept that analyze only maximal extension alternatives seem to be equivalent. Counterexamples will show that - in contrast to claims made in the literature - search tree reduction to minimal delaying alternatives and search tree reduction to maximal extension alternatives are not equivalent. While the former reduction preserves optimality the latter one is neither correct for the RCPSP with single execution modes nor for the RCPSP with work content defined modes.
Subjects: 
Project Scheduling
Resource Constraints
Branch-and-Bound
Delaying Alternatives
Extension Alternatives
Document Type: 
Working Paper
Document Version: 
Digitized Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.