Resource constrained project scheduling with time windows: A branching scheme based on dynamic release dates

dc.contributor.authorFest, Andreas
dc.contributor.authorMöhring, Rolf H.
dc.contributor.authorStork, Frederik
dc.contributor.authorUetz, Marc
dc.date.accessioned2021-12-17T10:11:29Z
dc.date.available2021-12-17T10:11:29Z
dc.date.issued1998
dc.description.abstractWe 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.en
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15783
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14556
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.otherproject schedulingen
dc.subject.othertime windowsen
dc.subject.otherbranching schemeen
dc.subject.otherdynamic release datesen
dc.subject.otherbranch-and-bound algorithmen
dc.titleResource constrained project scheduling with time windows: A branching scheme based on dynamic release datesen
dc.typeResearch Paperen
dc.type.versionsubmittedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften>Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber1998, 596en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
Files
Original bundle
Now showing 1 - 2 of 2
Loading…
Thumbnail Image
Name:
Report-596-1998.pdf
Size:
220.54 KB
Format:
Adobe Portable Document Format
Description:
Loading…
Thumbnail Image
Name:
Report-596-1998.ps
Size:
244.33 KB
Format:
Postscript Files
Description:
Collections