Resource constrained project scheduling with time windows: A branching scheme based on dynamic release dates
| dc.contributor.author | Fest, Andreas | |
| dc.contributor.author | Möhring, Rolf H. | |
| dc.contributor.author | Stork, Frederik | |
| dc.contributor.author | Uetz, Marc | |
| dc.date.accessioned | 2021-12-17T10:11:29Z | |
| dc.date.available | 2021-12-17T10:11:29Z | |
| dc.date.issued | 1998 | |
| dc.description.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. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15783 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14556 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | project scheduling | en |
| dc.subject.other | time windows | en |
| dc.subject.other | branching scheme | en |
| dc.subject.other | dynamic release dates | en |
| dc.subject.other | branch-and-bound algorithm | en |
| dc.title | Resource constrained project scheduling with time windows: A branching scheme based on dynamic release dates | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 1998, 596 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |