We propose a branch-and-bound algorithm for resource-constrained
project scheduling where any two of jobs can be linked by arbitrary
minimal and maximal time lags. The jobs have to be scheduled
non-preemptively, and while in process, they require several limited
resources. The objective is to find a feasible schedule which
minimizes the project makespan. Different branch-and-bound
algorithms have been previously proposed - either based on
constraint propagation techniques, or based on the idea to branch
over so-called resource conflicts which are resolved by introducing
additional precedence constraints. Our approach also follows the
latter principle. The new idea is to resolve resource conflicts
only locally by a dynamic update of job release dates instead of
introducing precedence constraints. This gives rise to a reduction
of both computation time and memory requirements in every node of
the enumeration tree, however, at the expense of a loss of
information. Nevertheless, enriched by preprocessing, strong
dominance rules, and a flexible search strategy, our computational
results show that the algorithm performs better than previous
branch-and-bound algorithms, and is competitive with a very recent
constraint propagation approach as well as tailor-made heuristics,
also for large-scale instances.
