Publication Type

Journal Article

Version

publishedVersion

Publication Date

11-1998

Abstract

We present an optimal solution procedure for the resource-constrained project scheduling problem (RCPSP) with generalized precedence relations (RCPSP-GPR) with the objective of minimizing the project makespan. The RCPSPGPR extends the RCPSP to arbitrary minimal and maximal time lags between the starting and completion times of activities. The proposed procedure is suited for solving a general class of project scheduling problems and allows for arbitrary precedence constraints, activity ready times and deadlines, multiple renewable resource constraints with time-varying resource requirements and availabilities, several types of permissible and mandatory activity overlaps and multiple projects. It can be extended to other regular and non-regular measures of performance. Essentially, 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 to resolve a number of resource conflicts. These conflicts are resolved using the concept of minimal delaying modes, which is an extension of the notion of minimal delaying alternatives for the RCPSP. Several bounds and dominance rules are used to fathom large portions of the search tree. Extensive computational experience is reported.

Keywords

Project management, Critical path methods, Branch-and-bound, Generalized precedence relations

Discipline

Business Administration, Management, and Operations | Management Information Systems

Research Areas

Operations Management

Publication

European Journal of Operational Research

Volume

111

Issue

1

First Page

152

Last Page

174

ISSN

0377-2217

Identifier

10.1016/S0377-2217(97)00305-6

Publisher

Elsevier: 24 months

Embargo Period

8-31-2021

Download

Share

COinS