Non-equivalent search strategies for resource-constrained project scheduling

Arno Sprecher

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

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.

Keywords: Project Scheduling; Resource Constraints; Branch-and-Bound; Delaying Alternatives; Extension Alternatives (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.econstor.eu/bitstream/10419/147586/1/manuskript_493.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:493

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 ().