A Time-Oriented Branch-and-Bound Algorithm for Resource-Constrained Project Scheduling with Generalised Precedence Constraints

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 e...

Full description

Saved in:
Bibliographic Details
Published in:Management science 2000-10, Vol.46 (10), p.1365-1384
Main Authors: Dorndorf, Ulrich, Pesch, Erwin, Phan-Huy, Toan
Format: Article
Language:English
Subjects:
Algorithms
branch and bound
Children
constraint propagation
Experiments
generalised precedence constraints
Heuristic
Heuristics
Job shops
Management science
Mathematical economics
Mathematical models
Mean absolute deviation
Production planning
Programming
Project management
project scheduling
Resource allocation
resource constraints
Resources conflict
Run time
Scheduling
Scholarly publishing
Studies
Supply and demand
Time windows
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0025-1909
1526-5501
DOI:10.1287/mnsc.46.10.1365.12272