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

Ulrich Dorndorf (), Erwin Pesch () and Toàn Phan-Huy ()
Additional contact information
Ulrich Dorndorf: Faculty of Economics, University of Bonn, Adenauerallee 24-42, D-53113 Bonn, Germany
Erwin Pesch: Faculty of Economics, University of Bonn, Adenauerallee 24-42, D-53113 Bonn, Germany
Toàn Phan-Huy: Faculty of Economics, University of Bonn, Adenauerallee 24-42, D-53113 Bonn, Germany

Management Science, 2000, vol. 46, issue 10, 1365-1384

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: project scheduling; resource constraints; time windows; generalised precedence constraints; branch and bound; constraint propagation (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (22)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.46.10.1365.12272 (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:inm:ormnsc:v:46:y:2000:i:10:p:1365-1384

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().