Title: Computational experience with a branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence relations
Authors: De Reyck, B
Editors: Herroelen, Willy
Issue Date: 1996
Publisher: K.U.Leuven - Departement toegepaste economische wetenschappen
Series Title: DTEW Research Report 09628 pages:1-40
Abstract: In a previous paper (De Reyck and Herroelen, 1996a), we presented an optimal procedure for the resource-constrained project scheduling problem (RCPSP) with generalised precedence relations (further denoted as RCPSP-GPR) with the objective of minimizing the project makespan. The RCPSP-GPR extends the RCPSP to arbitrary minimal and maximal time lags between the starting and completion times of activities. The procedure is a depth-first branch -and-bound algorithm in which the nodes in the search tree represent the original project network extended with extra precedence relations, which resolve a resource conflict present in the project network of the parent node. Resource conflicts are resolved using the concept of minimal delaying alternatives, i.e. minimal sets of activities which, when delayed, release enough resources to resolve the conflict. Precedence- and resource-based lower bounds as well as dominance rules are used to fathom large portions of the search tree. In this paper we report new computational experience with the algorithm using a new RCPSP-GPR random problem generator developed by Schwindt (1995). A comparison with other computational results reported in the literature is included.
Publication status: published
KU Leuven publication type: IR
Appears in Collections:Research Center for Operations Management, Leuven

Files in This Item:
File Description Status SizeFormat
OR_9628.pdf Published 1604KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.