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

Kai Watermeyer () and Jürgen Zimmermann ()
Additional contact information
Kai Watermeyer: Clausthal University of Technology
Jürgen Zimmermann: Clausthal University of Technology

OR Spectrum: Quantitative Approaches in Management, 2022, vol. 44, issue 2, No 9, 575-602

Abstract: Abstract 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.

Keywords: Project scheduling; Branch and bound; Resource-constrained project scheduling; Partially renewable resources; Minimum and maximum time lags (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s00291-021-00654-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:orspec:v:44:y:2022:i:2:d:10.1007_s00291-021-00654-9

Ordering information: This journal article can be ordered from
http://www.springer. ... research/journal/291

DOI: 10.1007/s00291-021-00654-9

Access Statistics for this article

OR Spectrum: Quantitative Approaches in Management is currently edited by Rainer Kolisch

More articles in OR Spectrum: Quantitative Approaches in Management from Springer, Gesellschaft für Operations Research e.V.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().