A time-oriented branch-and-bound algorithm for resource-constrained project scheduling with generalised precedence constraints

Resource-constrained project scheduling with generalised precedence constra ints is a very general scheduling model with applications in areas such as make-to-order production planning. We describe a time-oriented branch-and-b ound algorithm that uses constraint-propagation techniques which actively e xploit the temporal and resource constraints of the problem in order to red uce the search space. Extensive computational experiments with systematical ly generated test problems show that the algorithm solves more problems to optimality than other exact solution procedures which have recently been pr oposed, and that the truncated version of the algorithm is also a very good heuristic.