A partition-based branch-and-bound algorithm for the project duration problem with partially renewable resources and general temporal constraints

Artikel

The concept of partially renewable resources provides a general modeling framework that can be used for a wide range of different real-life applications. In this paper, we consider a resource-constrained project duration problem with partially renewable resources, where the temporal constraints between the activities are given by minimum and maximum time lags. We present a new branch-and-bound algorithm for this problem, which is based on a stepwise decomposition of the possible resource consumptions by the activities of the project. It is shown that the new approach results in a polynomially bounded depth of the enumeration tree, which is obtained by kind of a binary search. In a comprehensive experimental performance analysis, we compare our exact solution procedure with all branch-and-bound algorithms and state-of-the-art heuristics from the literature on different benchmark sets. The results of the performance study reveal that our branch-and-bound algorithm clearly outperforms all exact solution procedures. Furthermore, it is shown that our new approach dominates the state-of-the-art heuristics on well known benchmark instances.

Angaben zum Objekt

• Sprache: Englisch

Verweise und Beziehungen

• Erschienen in: Journal: OR Spectrum ; ISSN: 1436-6304 ; Volume: 44 ; Year: 2021 ; Issue: 2 ; Pages: 575-602 ; Berlin, Heidelberg: Springer

Klassifikation und Themen

• Klassifikation: Management
• Thema: Project scheduling ; Branch and bound ; Resource-constrained project scheduling ; Partially renewable resources ; Minimum and maximum time lags

Beteiligte, Orts- und Zeitangaben

• Ereignis: Geistige Schöpfung
• (wer): Watermeyer, Kai ; Zimmermann, Jürgen
• Ereignis: Veröffentlichung
• (wer): Springer
• (wo): Berlin, Heidelberg
• (wann): 2021

Weitere Informationen

• DOI: doi:10.1007/s00291-021-00654-9
• Letzte Aktualisierung: 10.03.2025, 11:42 MEZ