direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 1998

Resource constrained project scheduling with time windows: A branching scheme based on dynamic release dates
Zitatschlüssel Report-596-1998
Autor Andreas Fest and Rolf H. Möhring and Frederik Stork and Marc Uetz
Jahr 1998
Nummer 596
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag