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

In the field of project scheduling, a great deal of effort has been devoted over the years to renewable resources, which are able to model resources like staff or machines that are assumed to be available in a specific quantity at each point in time (or period). In this work, we consider a more general resource type, which has firstly been introduced under the term partially renewable resources in the framework of project scheduling by Böttcher et al. (1999). The corresponding problem, denoted by RCPSP/\(\pi \), is a generalization of the classical resource-constrained project scheduling problem (RCPSP). The motivation for the extension of RCPSP by partially renewable resources stems from the restrictiveness of the renewable resources in the sense that the availability for each time period has to be fixed in advance, separated from the scheduling process. This limitation is resolved by partially renewable resources that are defined over multiple time periods with a given capacity. Thereby, the resources are consumed only on the defined time periods by the activities of the project. Examples for the application of RCPSP/\(\pi \) can be found in Böttcher et al. (1999) for the flexible planning of lunch breaks, in Alvarez-Valdes et al. (2008) for the assignment of weekend work, or in Alvarez-Valdes et al. (2015) for a school timetabling problem.

In the last decades, approximation and exact solution procedures have been developed for RCPSP/\(\pi \). In Böttcher et al. (1999) and Schirmer (1999), priority rule-based methods for RCPSP/\(\pi \) are investigated. The works of Alvarez-Valdes et al. (2006, 2008, 2015) are devoted to a GRASP and a scatter search algorithm, and in Schirmer (1999) different local-search procedures are considered. The state-of-the-art approximation method for RCPSP/\(\pi \) in terms of the solution quality is given by the scatter search algorithm. This procedure makes use of a priority rule-based generation scheme to determine feasible schedules, which are iteratively combined with each other to obtain better solutions. Böttcher et al. (1999) devised the only exact solution procedure for RCPSP/\(\pi \). The branch-and-bound algorithm (BnB) is based on the enumeration scheme by Talbot and Patterson (1978) for which the authors have developed two feasibility bounds.

For the first time, Watermeyer and Zimmermann (2020) have extended RCPSP/\(\pi \) by taking minimum and maximum time lags between the activities into account (RCPSP/max-\(\pi \)). An example for this problem is the planning of a training program for an employee that consists of a theoretical and a practical course. Thereby, the theory has to be taught first, the practical course is not supposed to be conducted more than two weeks after, and at most one course should take place at a weekend day. The temporal constraints between both courses are represented by minimum and maximum time lags, while the weekend constraint is given by a partially renewable resource that is defined over all weekend days with a capacity for one course. The state-of-the-art exact solution procedure for RCPSP/max-\(\pi \) and RCPSP/\(\pi \) is provided in Watermeyer and Zimmermann (2020) by a relaxation-based BnB. The procedure progressively reduces the possible resource consumptions by the activities of the project in each branching step and solves the corresponding resource relaxations.

In this work we present a new BnB for RCPSP/max-\(\pi \) that is based on a serial schedule-generation scheme. The new enumeration approach schedules all activities of the project successively by assigning a start time to an activity in each branching step. In this way, partial schedules are augmented in the course of the enumeration until there is no feasible start time left or a complete schedule is determined.

The remainder of this paper is organized as follows. Section 2 provides a formal description of RCPSP/max-\(\pi \). In Sect. 3 we discuss the enumeration scheme of our BnB. Section 4 deals with improving techniques, and Sect. 5 describes the BnB. In Sect. 6 we present the results of a comprehensive experimental performance analysis and provide some conclusions in Sect. 7.

RCPSP/max-\(\pi \) can be represented by an activity-on-node project network N with node set V, covering all activities of the project, and arc set \(E\subset V\times V\), implying the precedence relationships among them. Each activity \(i\in V\) is assigned a non-interruptible processing time \(p_i\in \mathbb {Z}_{\ge 0}\) and a resource demand \(r^d_{ik}\in \mathbb {Z}_{\ge 0}\) for each partially renewable resource \(k\in \mathcal {R}\). The temporal constraint for each activity pair \((i,j)\in E\) is specified by a start-to-start precedence relationship and arc weight \(\delta _{ij}\in \mathbb {Z}\), meaning that each temporal constraint is given by \(S_j\ge S_i +\delta _{ij}\), establishing a time lag between the start times of activities i and j. In the following we speak of a minimum time lag between activities i and j if \(\delta _{ij}\ge 0\) and say that a maximum time lag is given if \(\delta _{ji}<0\). The node set \(V{:}{=}\{0,1,\ldots ,n+1\}\) includes two fictitious activities 0 and \(n+1\), i.e., \(p_0=p_{n+1}=0\), which represent the beginning and the termination of the project, respectively. It is assumed that each project starts at time 0 and is completed before a prescribed deadline \(\bar{d}\), i.e., \(S_0=0\) and \(S_{n+1}\le \bar{d}\). In the remainder of this work, we call a vector \(S=(S_i)_{i\in V}\) with \(S_i\in \mathbb {Z}_{\ge 0}\) and \(S_0=0\) a schedule and speak of a time-feasible schedule if all temporal constraints are satisfied and \(S_{n+1}\le \bar{d}\). By \(\mathcal {S}_T\), we denote the set of all time-feasible schedules. The resource constraints of RCPSP/max-\(\pi \) are given by the resource capacities \(R_k\in \mathbb {Z}_{\ge 0}\) of all partially renewable resources \(k\in \mathcal {R}\). Thereby, the availability of each resource is only limited on a specified subset of all time periods within the entire planning horizon \(\varPi _k\subseteq \{1,2,\ldots ,\bar{d}\}\). As a consequence, only the resource consumption of an activity \(i\in V_k{:}{=}\{i\in V\, |\, r^d_{ik}>0\}\) over the time periods in \(\varPi _k\) has to be taken into account. In order to express the number of the time periods in \(\varPi _k\) an activity \(i\in V\) is in execution, we introduce the so-called resource usage \(r^u_{ik}(S_i){:}{=}|]S_i,S_i+p_i]\cap \varPi _k|\). Based on the resource usage, the resource consumption of a resource \(k\in \mathcal {R}\) by an activity \(i\in V\) follows directly with \(r^c_{ik}(S_i){:}{=}r^u_{ik}(S_i)\cdot r^d_{ik}\), so that the resource constraints can be stated by \(\sum _{i\in V} r^c_{ik}(S_i) \le R_k\) for all \(k\in \mathcal {R}\). In the following, we call a schedule S that fulfills all resource constraints a resource-feasible schedule and denote the set of all resource-feasible schedules by \(\mathcal {S}_R\). Furthermore, we say that schedule \(S\in \mathcal {S}\) is feasible with \(\mathcal {S}{:}{=}\mathcal {S}_T\cap \mathcal {S}_R\) as the set of all feasible schedules.

The objective of RCPSP/max-\(\pi \) is to determine a feasible schedule \(S^*\) with the shortest project duration among all feasible schedules \(S\in \mathcal {S}\). The corresponding problem is stated bywith \(f:\mathcal {S}\mapsto \mathbb {R}\) as the objective function that assigns the project duration to each feasible schedule S. We call a schedule S that solves problem (P) an optimal schedule and denote the set of all optimal schedules by \(\mathcal {OS}\).

It should be noted that there also exist other approaches to model partially renewable resources by assigning multiple subsets of time periods to each of them with the advantage of a more intuitive connection to resources in real-life applications (Böttcher et al. 1999). In this work, we use the so-called normalized formulation for partially renewable resources that turned out to be more appropriate for theoretical issues since each restriction of a real-life resource is represented by exactly one partially renewable resource.

In general, the enumeration scheme of a BnB specifies the procedure to construct the search tree or rather implicates how to generate all direct descendants of a search node. In the following, we present the enumeration scheme of our BnB, which is based on a serial schedule-generation procedure complemented by an unscheduling step. The concept of unscheduling is based on the work of Franck et al. (2001) that provides a serial schedule-generation scheme for RCPSP with general temporal constraints (RCPSP/max).

The construction procedure of the directed outtree corresponding to the enumeration scheme of our BnB is described in Algorithm 1. In this procedure, each enumeration node is represented by a pair \((\mathcal {C},S)\) with \(\mathcal {C}\subseteq V\) as the set of all currently scheduled activities and S as a time-feasible schedule that represents the start times \(S_i\) for all activities \(i\in \mathcal {C}\) and the earliest time-feasible start times for all not currently scheduled activities \(i\in V\setminus \mathcal {C}\). To simplify the following explanations, we use the concept of partial schedules, referring to Definition (2.6.3) in Neumann et al. (2003), to describe the start times of all currently scheduled activities for some enumeration node.

Algorithm 1 outlines the enumeration scheme of our BnB. In the initialization step, the distance matrix \(D{:}{=}(d_{ij})_{i,j\in V}\) with \(d_{ij}\) as the length of a longest path between activities i and j in project network N is calculated with the Floyd-Warshall algorithm (Ahuja et al. 1993,  Sect. 5.6). Then, the earliest and latest time-feasible schedules \( ES \) and \( LS \) are derived and the root node \((\mathcal {C},S)\) is initialized by \(\mathcal {C}{:}{=}\{0\}\) and \(S{:}{=} ES \), meaning that the project start is scheduled at time 0, so that partial schedule \(S^\mathcal {C}=(0)\) with \(S_0=0\) corresponds to the root node. For the enumeration scheme we use set \(\varOmega \) to store all generated enumeration nodes that are still to be explored, and \(\varPhi \) to gather all generated schedules during the construction procedure. Accordingly, these sets are initialized by \(\varOmega {:}{=}\{(\mathcal {C},S)\}\) and \(\varPhi {:}{=}\emptyset \).

In each iteration of Algorithm 1 some pair \((\mathcal {C},S)\) is removed from \(\varOmega \). In case that \(\mathcal {C}\ne V\), some activity \(i\in \bar{\mathcal {C}}\) from the set of all not currently scheduled activities \(\bar{\mathcal {C}}{:}{=}V\setminus \mathcal {C}\) is chosen. For this activity, all resource-feasible start times in \(\{S_i,\ldots , LS _i\}\) are determined and stored in the so-called scheduling set \(\varTheta _i\). The resource-feasibility is ensured by taking the resource consumption \(r^c_k(S^\mathcal {C}){:}{=}\sum _{j\in \mathcal {C}}r^c_{jk}(S_j)\) for each resource \(k\in \mathcal {R}_i{:}{=}\{k\in \mathcal {R}\,|\,r^d_{ik}>0\}\) of partial schedule \(S^\mathcal {C}\) into account. Afterward, based on a dominance criterion with similarities to left-shift dominance rules for renewable resources (see, e.g., Stinson et al.,  1978; Demeulemeester and Herroelen, 1992), the reduced scheduling set \(T_i\) is calculated. \(T_i\) comprises all start times from \(\varTheta _i\) with a lower resource consumption for at least one resource \(k\in \mathcal {R}_i\) compared to all lower start times in \(\varTheta _i\). The calculation of \(T_i\), which is defined by , is described in Sect. 3.1. Based on the reduced scheduling set \(T_i\), all direct descendants of enumeration node \((\mathcal {C},S)\) are generated. For each descendant node \((\mathcal {C}',S')\), some scheduling time \(t\in T_i\) is established as the start time \(S'_i\) of activity i, followed by an update of the earliest time-feasible start times for all activities by \(S'{:}{=}(\max (S_j,S'_i+d_{ij}))_{j\in V}\) if it is assumed that activity i starts at time t. Since for each start time \(t\in T_i\) the conditions \(S_j+d_{ji}\le t\) for all currently scheduled activities \(j\in \mathcal {C}\) are satisfied, in case that t is not time-feasible, there has to be at least one activity \(j\in \mathcal {C}\) with \(S_j - d_{ij} < t\). This means that the induced latest start time \( LS _i(S_j){:}{=}S_j-d_{ij}\) of activity i by some activity \(j\in \mathcal {C}\) prevents the time-feasibility of start time t. As a consequence, in order to achieve the time-feasibility of \(S'^{\,\mathcal {C}\cup \{i\}}\) with \(S'_i=t\), all currently scheduled activities \(j\in \mathcal {C}\) with \(t > LS _i(S_j)\) or rather \(S'_j > S_j\) are unscheduled by setting \(\mathcal {C}'{:}{=}\mathcal {C}\setminus \{j\in \mathcal {C}\, |\, S'_j > S_j\}\). More precisely, the unscheduling of an activity is done by removing it from the set of all currently scheduled activities \(\mathcal {C}\) of the direct ancestor node. It should be noted that \(0\in \mathcal {C}'\) is always ensured by \(t \le LS _i\) due to the definition of \(\varTheta _i\). In case that start time t is time-feasible (\(t\le \min _{j\in \mathcal {C}} LS _i(S_j)\)), activity i is scheduled at start time \(S'_i=t\) by setting \(\mathcal {C}'{:}{=}\mathcal {C}\cup \{i\}\). Finally, after the scheduling or unscheduling step, the descendant node \((\mathcal {C}',S')\) is stored in \(\varOmega \) in order to be explored in one of the following iterations. From the description of the procedure to schedule or unschedule activities it follows directly that each partial schedule \(S^\mathcal {C}\) of an enumeration node \((\mathcal {C},S)\) is feasible. Therefore, in case that some node \((\mathcal {C},S)\) with \(\mathcal {C}=V\) is removed from \(\varOmega \), schedule \(S=S^\mathcal {C}\in \mathcal {S}\) is stored in \(\varPhi \) as a candidate schedule. After all enumeration nodes have been explored, i.e., \(\varOmega =\emptyset \), Algorithm 1 terminates and returns set \(\varPhi \), which contains all candidate schedules generated in the course of the enumeration procedure.

In Watermeyer and Zimmermann (2020) it has already been shown for a relaxation-based BnB for RCPSP/max-\(\pi \) that the application of consistency tests, lower bounds , and techniques to avoid redundancies can have a great impact on the performance. In what follows, we extend our enumeration scheme to be able to use consistency tests and lower bounds from Watermeyer and Zimmermann (2020) and to apply new devised pruning techniques that are described in Sect. 4.3.

In this section we present the general framework of our BnB that enables a wide range of different settings concerned with the construction of the enumeration tree and the application of improving techniques. The first part of this section is devoted to the search strategy of our BnB that determines the way to construct the enumeration tree. In order to provide a generic framework for the construction of the search tree, in line with Watermeyer and Zimmermann (2020), we divide the search strategy in different parts, called traversing, branching, generation, and ordering strategy.

For the traversing strategy, which determines the node to be considered next in the course of the BnB, we have implemented two alternatives. The first alternative is the well-known depth-first search (DFS), while the second one is an extension of the DFS that has been introduced by Watermeyer and Zimmermann (2020). The so-called scattered-path search (SPS) selects after a predefined time span, among all not completely explored nodes with lowest search tree level, a node with the lowest bound on the project duration. After some node has been chosen to be explored next, the branching strategy determines the activity to be considered in the branching step. For this, in a first step, the so-called eligible set \(\mathcal {E}\subseteq \bar{\mathcal {C}}\), i.e., the set of all activities that could be used for the branching step, is determined. The first alternative takes all not currently scheduled activities into consideration (\(\bar{\mathcal {C}}\)), i.e., \(\mathcal {E}{:}{=}\bar{\mathcal {C}}\). In contrast, the other two alternatives that are both based on a strict order \(\prec \) in set V, reduce the set \(\bar{\mathcal {C}}\), where \(\mathcal {E}\subseteq \{i\in \bar{\mathcal {C}}\, |\, Pred ^{\prec }(i)\subseteq \mathcal {C}\}\) holds with \( Pred ^{\prec }(i)\) as the set of all direct predecessors of activity \(i\in V\) in a precedence graph \(G^{\prec }\) with V as the node set and the covering relation \(cr(\prec )\) of the strict order as the arc set. The strict orders we use in this work have been introduced as distance order (\(\prec _{\text { D}}\)) and cycle order (\(\prec _{\text { C}}\)) in Franck et al. (2001) and Neumann et al. (2003, Sect. 2.6). For further details we refer the reader to those references. In the following, we assume that the eligible set \(\mathcal {E}\) is given. Then in the next step of the branching strategy, the activity with the best priority value \(\pi _i\) and the lowest index in set \(\mathcal {E}\) is selected for the branching step. Accordingly the branching activity is given bywhere \(\text {ext}\in \{\text {min},\text {max}\}\) indicates if lower (min) or greater (max) priority values are preferred. In what follows, we present some priority rules that have shown promising results in preliminary tests. First, we deal with priority rules that have already been discussed in the literature (see, e.g., Kolisch,  1996; Franck et al., 2001) and are concerned with the temporal constraints of the problem. These include among others the latest start time rule (LST) with \(\pi _i=\textit{LS}_i\) and the slack time rule (ST) with \(\pi _i= LS _i- ES _i\). For both priority rules we have also tested dynamic versions that take the start time restrictions and the best found solution \( UB \) into account that are given by \(\pi _i= LS ^{ UB }_i(W)\) (LSTd) and \(\pi _i= LS ^{ UB }_i(W)- ES _i(W)\) (STd) with \( LS ^{ UB }_i(W){:}{=} LS _i(W,n+1, UB -1)\). Additionally, we have implemented a dynamic version of ST (STd\(^\text {I}\)) that considers the number of start times in the start time restriction by \(\pi _i=|W_i\cap [ ES _i(W), LS ^{ UB }_i(W)]|\). Further rules are given by the total successor rule (TS) with \(\pi _i=| \mathrm Reach ^\prec (i)|\) and \( \mathrm Reach ^\prec (i)\) as the set of all successors of activity \(i\in V\) in \(G^\prec \), the path following rule (PF) with \(\pi _i=l(i)\) and l(i) as the maximal number of nodes on any longest directed path from node \(i\in V\) to \(n+1\) in project network N, and the maximal resource consumption rule (MRC) with \(\pi _i=p_i\sum _{k\in \mathcal {R}_i} r^d_{ik}\). In contrast to the priority rules from the literature, the following rules make use of the properties of the partially renewable resources. For this, the maximal possible additional resource consumption \(p_i\,r^d_{ik}\) by an activity in relation to the maximal remaining resource capacity \(\bar{R}_k\) is considered withand \(\underline{r}^c_{ik}(W,d){:}{=}\min \{r^c_{ik}(\tau ){\,:\,}|{\,:\,} \tau {\,\in \,} W_i{\,\cap \,} [ ES _i(W),d]\}\). We have tested the following two different versions. The total maximal additional relative resource consumption rule (TMAR) withand the average maximal additional relative resource consumption rule (AMAR) with \(\pi _i=\pi '_i/|\mathcal {R}_i|\) and \(\pi '_i\) as the priority value of TMAR.

After the branching activity has been selected for some enumeration node, the last part of the search strategy is concerned with the generation and the ordering of the direct descendants. For the generation strategy, we distinguish between the possibilities either to generate all direct descendants (all) or to restrict the number of generated nodes by a maximal value (restr), where one and the same node must possibly be explored more than once. Furthermore, we have implemented different orders in which all start times in the reduced scheduling set \(T_i\) of branching activity \(i\in \mathcal {E}\) are considered. The most intuitive alternative for this takes always the lowest start time from \(T_i\) that has not been used so far to generate a direct descendant node (LT). The other alternative assigns a priority value \(\pi _{t}\) to each start time \(t\in T_i\) and considers all start times in \(T_i\) in an order of non-decreasing priority values (PV), where ties are broken on the basis of lower start times. In what follows, we present the best priority value we have found to order the start times in \(T_i\). The corresponding priority valuewithandis a combination of a priority value that is highly related to the TMAR rule and a penalty term that increases the priority value in a linear fashion based on the difference between start time t and the earliest W-feasible start time \( ES _i(W)\). Finally, after all direct descendant nodes have been generated, the ordering strategy determines the order in which they are considered in the further course of the BnB. In this work, all generated descendant nodes are explored in an order of non-decreasing lower bounds on the project duration (LB), which has shown to provide good results in computational experiments.

In accordance with Watermeyer and Zimmermann (2020), we apply three different sets of consistency tests in our BnB. Set \(\varGamma ^B\) contains the temporal- and resource-bound consistency test, \(\varGamma ^D\) the temporal-bound and D-interval consistency test, and \(\varGamma ^W\) the temporal and W-interval consistency test. \(\gamma ^\alpha _\beta (W)\) denotes the start time restriction that results if all consistency tests in \(\varGamma ^\beta \) are applied on W for \(\alpha \) iterations. \(\alpha =\infty \) implies that the fixed point corresponding to \(\varGamma ^\beta \) is determined. To be able to differentiate between the possibilities for the D-interval and W-interval consistency test to use all resources or only the resources that are demanded by activity i, we use the notations \(\gamma ^\alpha _\beta (W)[\mathcal {R}]\) and \(\gamma ^\alpha _\beta (W)[\mathcal {R}_i]\).

In what follows, we outline the framework of our BnB, which is given in Algorithm 4. It should be noted that in order to simplify the presentation, we assume that a depth-first search (DFS) is used and that all direct descendants of each enumeration node are generated at once (all). Accordingly, all other alternatives for the traversing and the generation strategy are omitted. In the first part of Algorithm 4, a preprocessing step is performed on the start time restriction W, for which we calculate the fixed point of set \(\varGamma ^W\) considering all resources, meaning that \(W{:}{=}\gamma ^\infty _W(W)[\mathcal {R}]\) is set. In case that the preprocessing step cannot prove the infeasibility (\(\mathcal {S}_T(W)\ne \emptyset \)), the global lower bound \( LB ^G\) is set to \(\min W_{n+1}\), the upper bound on the minimum project duration \( UB \) is set to \(\bar{d}+1\), and the root node is initialized and put on stack \(\varOmega \). In each iteration, an enumeration node \((\mathcal {C},S,W, LB )\) is removed from stack \(\varOmega \) and it is checked if it could provide a solution with a better project duration than \( UB \), i.e., \( LB < UB \). In this case, consistency tests from set \(\varGamma ^D\) or \(\varGamma ^W\) are applied on the start time restriction W. If the consistency tests can show that the considered node and all its descendants cannot generate any feasible schedule with a better project duration than \( UB \), i.e., \(\mathcal {S}^{ UB }_T(W){:}{=}\widehat{\mathcal {S}}_T(W,n+1, UB -1)=\emptyset \), the next enumeration node in \(\varOmega \) is considered. Otherwise, based on the branching strategy, the eligible set \(\mathcal {E}\) is determined and the branching activity \(i\in \mathcal {E}\) is selected, followed by the initialization of \(\varLambda \), which is used to store all direct descendants of the considered enumeration node. In the next step, analogously to Algorithm 3, \(\varTheta _i\) and the reduced scheduling set \(T_i\) are calculated. The start times in \(T_i\) are considered in an order depending on the generation strategy. Given some start time t that has been removed from \(T_i\), t is established as the earliest start time of the branching activity. It should be noted that line 19 of Algorithm 4 can be adapted as described in Sect. 4.3 to apply the pruning techniques UPT and ULT. After the initialization (and update) of start time restriction \(W'\), the consistency tests from set \(\varGamma ^B\) are applied on \(W'\). The direct descendant node corresponding to \(W'\) is directly pruned from the enumeration tree if \(\mathcal {S}^{ UB }_T(W')=\emptyset \). Otherwise, in case that the existence of any feasible schedule in \(\mathcal {S}_T(W')\) with a better objective function value than \( UB \) cannot be excluded, it is checked if some activities have to be unscheduled or if the branching activity can be scheduled. If \(\mathcal {C}'=V\) after the scheduling of the branching activity, a new best feasible solution \(S^*{:}{=}S'\) has been found, \( UB \) is set to \(S^*_{n+1}\), and all start times in \(T_i\) that are greater than t are removed, noticing that they cannot generate any better feasible solution. Otherwise, the lower bound \( LB '\) for the descendant node is calculated by \( LB0 ^\pi \) or \( LBD ^\pi \). In case that \( LB '< UB \), the node is added to the list \(\varLambda \), which is used after the generation of all direct descendant nodes to put them on the stack \(\varOmega \) in an order of non-increasing values of their lower bounds \( LB '\). The described procedure reiterates until there is no enumeration node left to be considered, i.e., \(\varOmega =\emptyset \). In case that \( UB =\bar{d}+1\) at the end of the algorithm, we can state that there is no feasible solution, while otherwise, Algorithm 4 returns an optimal solution \(S^*\).

In this section, we evaluate the performance of our BnB. For this, we conduct computational experiments on different benchmark sets with partially renewable resources. To provide a comprehensive investigation, we compare our procedure with all available BnB from the literature for RCPSP/max-\(\pi \) and RCPSP/\(\pi \). In a second step, we derive a priority rule-based approximation method from our new enumeration approach and evaluate its performance in comparison with the associated BnB.

The computational experiments have been conducted on a workstation with an Intel Core i7-8700 CPU with a clock pulse of 3.2 GHz and 64 GB RAM under Windows 10 on a single thread. The algorithms were all coded in C++ and compiled by the 64-bit Visual Studio 2017 C++-compiler.

We have presented a branch-and-bound algorithm (BnB) for the resource-constrained project duration problem with partially renewable resources and general temporal constraints (RCPSP/max-\(\pi \)) that is based on a serial schedule-generation scheme. For the first time it has been shown that it is sufficient to consider only a subset of all resource-feasible start times in each branching step. By an extension of the enumeration scheme by start time domains, improving techniques from the literature could be included. Furthermore, we were able to devise new pruning techniques to prevent redundancies with a significant impact on the performance.

In a comprehensive experimental performance analysis we have compared our exact solution procedure with all BnB that are available in the open literature for partially renewable resources. The computational experiments could reveal a great dominance of our BnB for RCPSP/max-\(\pi \). The favorable performance could also be confirmed for instances that are restricted to precedence constraints with significant better results compared to the only available BnB for RCPSP/\(\pi \). In a second step, we investigated a directly derived schedule-generation scheme from our new enumeration approach. It has been shown that the approximation procedure obtains reasonable results for small instances, while a limitation for large instances became apparent.

As the computational experiments have shown, the performance of a BnB for RCPSP/max-\(\pi \) is strongly influenced by the way to enumerate the candidate solutions. Therefore, the investigation of further enumeration schemes seems to be a promising field for future research. Moreover, the experiments could demonstrate that there is a great need for new types of approximation methods that goes beyond classical priority rule-based generation schemes.