A Time-Oriented Branch-and-Bound Algorithm for Resource-Constrained Project Scheduling with Generalised Precedence Constraints
- 1 October 2000
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Management Science
- Vol. 46 (10), 1365-1384
- https://doi.org/10.1287/mnsc.46.10.1365.12272
Abstract
Resource-constrained project scheduling with generalised precedence constraints is a very general scheduling model with applications in areas such as make-to-order production planning. We describe a time-oriented branch-and-bound algorithm that uses constraint-propagation techniques which actively exploit the temporal and resource constraints of the problem in order to reduce the search space. Extensive computational experiments with systematically generated test problems show that the algorithm solves more problems to optimality than other exact solution procedures which have recently been proposed, and that the truncated version of the algorithm is also a very good heuristic.Keywords
This publication has 20 references indexed in Scilit:
- Resource-constrained project scheduling: Notation, classification, models, and methodsEuropean Journal of Operational Research, 1999
- A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence relationsEuropean Journal of Operational Research, 1998
- Resource-constrained project scheduling: A survey of recent developmentsComputers & Operations Research, 1998
- Activity-on-node networks with minimal and maximal time lags and their application to make-to-order productionOR Spectrum, 1997
- Heuristic procedures for resource—constrained project scheduling with minimal and maximal time lags: the resource—levelling and minimum project—duration problemsJournal of Decision Systems, 1996
- Heuristics for scheduling resource-constrained projects in MPM networksEuropean Journal of Operational Research, 1994
- Implementation of resource constraints in ILOG SCHEDULE: a library for the development of constraint-based scheduling systemsIntelligent Systems Engineering, 1994
- A generic arc-consistency algorithm and its specializationsArtificial Intelligence, 1992
- Scheduling project networks with resource constraints and time windowsAnnals of Operations Research, 1988
- On the Resource Constrained Project Scheduling ProblemA I I E Transactions, 1971