A branch-and-bound algorithm for the resource-constrained project scheduling problem

We describe a time-oriented branch-and-bound algorithm for the resource-con strained project scheduling problem which explores the set of active schedu les by enumerating possible activity start times, The algorithm uses constr aint-propagation techniques that exploit the temporal and resource constrai nts of the problem in order to reduce the search space. Computational exper iments with large, systematically generated benchmark test sets, ranging in size from thirty to one hundred and twenty activities per problem instance , show that the algorithm scales well and is competitive with other exact s olution approaches. The computational results show that the most difficult problems occur when scarce resource supply and the structure of the resourc e demand cause a problem to be highly disjunctive.