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.

Object Details

• Language: Englisch

References and Relationships

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

Classification and Topics

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

Contributors, Places and Time

• Event: Geistige Schöpfung
• (who): Watermeyer, Kai ; Zimmermann, Jürgen
• Event: Veröffentlichung
• (who): Springer
• (where): Berlin, Heidelberg
• (when): 2021

Further information

• DOI: doi:10.1007/s00291-021-00654-9
• Last update: 10.03.2025, 11:42 AM CET