Inhalt des Dokuments
Preprint 596-1998
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- Resource constrained project scheduling with time windows: A branching scheme based on dynamic release dates
- Authors
- 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]
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe