Preprint 596-1998

Title
Resource constrained project scheduling with time windows: A branching scheme based on dynamic release dates
Authors
Andreas Fest, Rolf H. Möhring, Frederik Stork, and Marc Uetz
Publication
An extended abstract appeared in the Proceedings of the 6th International Workshop on Project Management and Scheduling, Istanbul, Turkey, pp.98-101.
Classification
not available
Keywords
not available
Abstract
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.
Source
Download as [ps.gz]