Generation schemes for the resource-constrained project scheduling problem with partially renewable resources and generalized precedence constraints

Karnebogen, Mareike; Zimmermann, Jürgen Article — Published Version Generation schemes for the resource-constrained project scheduling problem with partially renewable resources and generalized precedence constraints Annals of Operations Research Provided in Cooperation with: Springer Nature Suggested Citation: Karnebogen, Mareike; Zimmermann, Jürgen (2024) : Generation schemes for the resource-constrained project scheduling problem with partially renewable resources and generalized precedence constraints, Annals of Operations Research, ISSN 1572-9338, Springer US, New York, NY, Vol. 338, Iss. 1, pp. 173-192, https://doi.org/10.1007/s10479-023-05788-3 This Version is available at: https://hdl.handle.net/10419/315292 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ Annals of Operations Research (2024) 338:173–192 https://doi.org/10.1007/s10479-023-05788-3 ORIGINAL RESEARCH Generation schemes for the resource-constrained project scheduling problem with partially renewable resources and generalized precedence constraints Mareike Karnebogen1·Jürgen Zimmermann1 Received: 7 December 2022 / Accepted: 11 December 2023 / Published online: 17 January 2024 © The Author(s) 2024 Abstract In recent years, new resource types have been established in project scheduling. These include so-called partially renewable resources, whose total capacity applies only to a subset of periods in the planning horizon. In this paper, we consider the extension of the resourceconstrained project scheduling problem with those partially renewable resources as well as generalized precedence constraints with the objective of minimizing the project duration (RCPSP/max-π). For this problem it is known that already the determination of a feasible solution is NP-hard in the strong sense. Hence, we present two different generation schemes that are able to find good feasible solutions in short time for most tested instances. The first one is a construction-based heuristic wherein the activities of the project are scheduled iteratively timeand resource-feasibly. The second one is a relaxation-based generation scheme, in which—starting from the schedule consisting of the earliest start times—resource conflicts are identified and resolved by inserting additional resource constraints. Keywords Project scheduling ·Generalized precedence constraints ·RCPSP/max · Partially renewable resources ·Generation schemes 1 Introduction Due to new requirements in the field of project planning, such as the increasingly necessary flexibilization of production or higher expectations of employees on their working times, renewable resources are often coming up to their limits. Therefore, more and more resource types have been established in the literature in recent years. One of them are so-called partially renewable resources, which are a generalization of renewable and non-renewable resources and also include discrete cumulative resources (Watermeyer, 2021). Partially renewable BMareike Karnebogen [email protected] Jürgen Zimmermann [email protected] 1Institute of Management and Economics, Clausthal University of Technology, Julius-Albert-Str. 2, D-38678 Clausthal-Zellerfeld, Germany 123 174 Annals of Operations Research (2024) 338:173–192 resources are characterized by the fact that their total capacity is limited for a subset of periods in the planning horizon. However, for the complementary set of periods, the resource is assumed to be available in sufficient quantity. Partially renewable resources thus open up the possibility of modeling new types of conditions in the field of project scheduling, e.g., special working hour models such as particular weekend arrangements or certain production constraints like planning dependent downtimes or setup times. In this paper, the resource-constrained project scheduling problem with partially renewable resources and generalized precedence constraints (RCPSP/max-π) is considered, which was first addressed by Watermeyer and Zimmermann (2020). Even though the problem is based on the well studied RCPSP/max, the solution procedures cannot be simply transferred - due to the differently behaving resources and the associated changed problem characteristics. Since real-world projects often involve many activities as well as resources that have to be considered, exact solution methods for realistic instance sizes are usually not able to determine exact solutions to the problem within an acceptable amount of time. Therefore, this paper is devoted to the development of problem-specific heuristics for the RCPSP/max-π.We present two different generation schemes that generate feasible solutions for the considered problem. In Sect. 2the problem is described and a mixed-integer linear formulation (MILP) is introduced, followed by an overview of the relevant literature on partially renewable resources in the context of project scheduling in Sect. 3. Then, in Sect. 4first a construction-based generation scheme and afterwards a relaxation-based generation scheme is presented. Finally, Sect. 5provides the results of a performance analysis comparing the results of both generation schemes to the results of the presented MILP model solved by IBM ILOG CPLEX and the best performing branch-and-bound procedure of Watermeyer (2021). 2 Problem description The RCPSP/max-πis based on the well-known project scheduling problem with generalized precedence constraints (PSP/max). Thereby, a set of activities V={0,1, ..., n+1}is given, consisting of the fictitious project start 0, nreal activities and the fictitious project completion n+1. Each activity i∈Vhas a deterministic processing time pi∈Z≥0during which the activity cannot be interrupted. For both fictitious activities, p0=pn+1=0 applies. Between the activities of the project generalized precedence constraints have to be observed, which can be both minimal and maximal timelags. Due to deterministic activity durations, all precedence constraints can be converted into minimal start-start-timelags. A time constraint δij ≥0 indicates that more than δij periods must have elapsed between the start of activity i∈Vand the start of activity j∈V\{i}. A time constraint δij <0 states that the start of activity i∈Vmust not be more than −δij periods after the start of activity j∈V\{i}. Furthermore, a maximal project duration dis given in which the project must be completed modeled as a maximal timelag between project start and end. The PSP/max as introduced before can be visualized by an activity-on-node network. The nodes V={0,1, ..., n+1}correspond to the activities of the project whereas the arcs i,j∈Eweighted with δij ∈Zrepresent the temporal constraints. The maximal project duration can be displayed by an arc from n+1 to 0 weighted with −d. As common practice, let dij be the length of a longest path from node i∈Vto node j∈Vin the project network, which can be determined using the Floyd-Warshall Algorithm by Floyd (1962). Then, d0i corresponds to the earliest start time ES iand −di0to the latest start time LS iof activity i∈V. Based on that, for each activity i∈VasetWi={ES i,ES i+1, ..., LS i}containing all time-feasible integer start times between its earliest and latest start time can be initialized. 123 Annals of Operations Research (2024) 338:173–192 175 Fig. 1 Project network Fig. 2 Relevant cumulative resource consumption of activity 1 The PSP/max can be extended to the RCPSP/max-πby additionally considering a set of partially renewable resources R={1, ..., m}. While an activity i∈Vis in execution, it consumes rik ∈Z≥0units of resource k∈Rper period. The resource requirements of the fictitious activities are assumed to be zero. For each partially renewable resource k∈Ra resource capacity Rkis given, which is only related to a subset k⊆{1,2, ..., d}of not necessarily connected time periods of the planning horizon. All activities executed in this restricted periods of resource kare not allowed to in total consume more than Rkunits within. However, for all periods not contained in k, it is assumed that the resource availability is unlimited. In the activity-on-node network for each resource k∈Rthe resource demand per period rik of an activity i∈Vis noted below the corresponding node. An exemplary network for a project with n=4 real activities and m=1 partially renewable resource is shown in Fig.1. According to Watermeyer and Zimmermann (2020) the relevant cumulative resource consumption of an activity i∈Vof a resource k∈Ris based on its start time Siand can be calculated as rc ik(Si)=|{Si+1,Si+2,...,Si+pi}∩k|·rik. Assuming one resource k=1 with 1={2,3,4,7,8}for the project visualised in Fig.1, for activity i=1the function for the cumulative resource consumption as shown in Fig.2results. The objective of the problem is to find a timeand resource-feasible schedule S= (S0,S1,...,Sn+1)minimizing the project duration Sn+1. A schedule is called time-feasible, if Sj−Si≥δij applies to all i,j∈E, meaning that all temporal constraints are observed. 123 176 Annals of Operations Research (2024) 338:173–192 A schedule is resource-feasible, if the accumulated resource consumption within all capacitated periods not exceeds the given capacity Rkfor any partially renewable resource k∈R. To ensure this, for each resource k∈Rthe start time dependent cumulative resource consumption rc ik(Si)is summed up over all activities i∈Vand limited by Rk. Formally, the RCPSP/max-πdescribed above can be formulated as follows: Minimize f(S)=Sn+1 subject to Sj−Si≥δij (i,j∈E) S0=0 i∈Vrc ik(Si)≤Rk(k∈R) Si∈Z≥0(i∈V) As is common practice in resource-constrained project scheduling, the RCPSP/max-π can also be formulated with binary time-indexed variables xit for each activity i∈Vand each start time point t∈Wi. If activity istarts at t(Si=t) or at an earlier point in time, the corresponding binary variable xit takes the value 1, otherwise xit has the value 0. This type of binary decision variables are also called step variables, because the variables xit jump from value 0 to value 1, i.e. one step up, exactly once over time for each activity i∈V. Hence, the decision variable Sican be replaced by the term t∈Wi\{0}(xit −xi,t−1).Ifwedefine sets Qit := {t−pi+1,...,t}containing all points in time an activity i∈Vcould start so that it would be in execution at point in time t, the cumulative resource consumption can be expressed dependent on the binary decision variables xit. For this, for each time-feasible start time t∈Wiof an activity i∈V, the number of capacitated periods in which iwould be active if started at tis determined. The discrete-time formulation based on step start variables can then be given according to Watermeyer and Zimmermann (2020) as follows: Min.  t∈Wn+1 t·(xn+1,t−xn+1,t−1) s.t.  t∈Wj\{0} t·(xjt −xj,t−1) − t∈Wi\{0} t·(xit −xi,t−1)≥δij (i,j∈E)  i∈V rik  τ∈k  t∈Qi,(τ−1)∩Wi (xit −xi,t−pi)≤Rk(k∈R) xi,t−1≤xit (i∈V,t∈Wi\{0}) xit =0(i∈V,t∈{0, ..., ES i−1}) xit =1(i∈V,t∈{LS i, ..., d}) xit ∈{0,1}(i∈V,t∈Wi) ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ (RCPSP/ max-π) In order to motivate the relevance of partially renewable resources, an example is given where partially renewable resources are utilized to model all existing resource constraints. Suppose a company plans a two-week project on a daily basis. For this, two identical machines are available. Normally, the daily capacity of the machines is modeled by renewable resources, but partially renewable resources can be used instead. Therefore, for each period of the planning horizon a new partially renewable resource with a capacity of two is defined, i.e. 123 Annals of Operations Research (2024) 338:173–192 177 Fig. 3 Example for partially renewable resources k={k}and Rk=2fork∈{1, ..., 14}. In addition, each 5-day workweek one of the two machines has to be cleaned and maintained, leading to a downtime of a whole day. A restriction like this can be modeled with renewable resources and dummy activities or - quite easy - with partially renewable resources. For that, a resource k=15 is defined restricted to theperiods1to5(15 ={1, ..., 5}) to a capacity of 2 ·5−1=9(R15 =9). Similarly, for the second week a resource k=16 with 16 ={8, ..., 12}and R16 =9 is introduced. As a further limitation, each machine may not run for more than two days on both weekends due to higher operating costs on saturday and sunday. To map this restriction, another partially renewable resource k=17 is defined with 17 ={6,7,13,14}and R17 =4. The resource restrictions as introduced before are shown in a resource profile in Fig.3. The dashed line represents the 14 partial renewable resources limiting the machine capacity per day. The maintenance restrictions are depicted by broad striped areas, while the weekend restriction is displayed by narrow striped areas. Resource constraints such as in the given example show the relevance of the concept of partially renewable resources, because they enable to model new restrictions as flexible working time models or special weekend arrangements. 3 Literature review Partially renewable resources embedded in the context of project scheduling were first mentioned by Drexl et al. (1993) as well as Drexl and Salewski (1997) for modeling an academic course scheduling problem. Over the next few years, several papers were published dealing with the problem of RCPSP/πand problem specific solution methods. Böttcher et al. (1999) adapt a branch-and-bound procedure of Talbot and Patterson (1978), so that the RCPSP/π can be solved to optimality. In addition, they developed a serial scheduling scheme to construct feasible solutions for the RCPSP/π. Schirmer (1999) also present construction methods for project scheduling with partially-renewable resources. Furthermore, he developed local search procedures, e.g. a tabu search heuristic. Alvarez-Valdés et al. (2006) present a scatter search heuristic for the RCPSP/π. Two years later, they also introduced a GRASP (AlvarezValdés et al., 2008). A summary and overview of the literature can be found in Alvarez-Valdés et al. (2015). The resource-constrained project scheduling problem with partially renewable resources and generalized precedence constraints was first considered by Watermeyer and Zimmermann (2020). They present a branch-and-bound procedure which is based on the resource relaxation. As part of their further research they also developed a partition-based branch-and-bound procedure (Watermeyer & Zimmermann, 2022) as well as a constructive branch-and-bound 123 178 Annals of Operations Research (2024) 338:173–192 procedure (Watermeyer & Zimmermann, 2023). To the best knowledge of the authors, apart from the schedule-generation scheme of Watermeyer and Zimmermann (2023)thereexistno appropriate heuristic solution methods for the RCPSP/max-πso far. 4 Generation schemes Due to the lack of heuristic solution methods for the RCPSP/max-π, in the following we present two different generation schemes to get feasible solutions. The first one is a construction-based heuristic presented at the 17th International Conference on Project Management and Scheduling (Karnebogen & Zimmermann, 2021) and will be described in Sect.4.1. The other one is a relaxation-based heuristic first introduced at the 18th International Conference on Project Management and Scheduling (Karnebogen & Zimmermann, 2022) that will be explained in Sect.4.2. 4.1 Construction-based generation scheme The construction-based generation scheme is characterized by iteratively scheduling the activities of a project until a timeand resource-feasible schedule is built. The general concept of the heuristic is based on the well-known generation scheme for the RCPSP/max developed by Franck et al. (2001). However, due to the partially renewable resources, it is - in contrast to the RCPSP/max - not sufficient to restrict the construction to the set of active schedules, i.e. generally select the earliest timeand resource-feasible start time in the course of the construction phase. Accordingly, the unscheduling phase must also be changed, since a rightward shift as in Franck et al. (2001) is not appropriate. Moreover, the reasons for the necessity of an unscheduling step are more diverse. In addition to binding time restrictions that prevent an activity from being scheduled, one or more resources may also no longer be available in sufficient quantity due to previous scheduling steps. Algorithm 1shows the procedure of our construction-based generation scheme. In the beginning, an initialization process is done (line 1–7), in which the fictitious project start 0 is scheduled at point in time zero (S0=0) and included in the set Cof activities that have already been scheduled. Furthermore, a counter u=0 is initialized to count the number of unscheduling steps done in the recurring main step of the generation scheme as well as an empty tabu-list ifor each activity i∈Vto manage tabu-set start times. Since the total resource requirement rc ik(Si)of an activity i∈V\{0}in the restricted periods of a partially renewable resource k∈Ronly depends on its own start time Siand not on those of other activities, it can be calculated in advance for all possible start times t∈Wi= {ES i,ES i+1, ..., LS i}between its earliest and latest start time. In the main step of the generation scheme, which is iterated until all activities are feasibly scheduled, for each partially renewable resource k∈Rand each activity i∈V\{C}the minimal cumulative demand rmin ik and the maximal cumulative demand rmax ik are determined. Since an activity i∈Vcannot have less than its minimal cumulative resource demand rmin ik for each resource k∈Rin any feasible schedule, this demand is already deducted from the total capacity RCkas well as the demand of already scheduled activities. In the next step, the eligible set Eis established containing all activities i∈V\Cwhose immediate predecessors regarding the distance order ≺Dare already scheduled. An activity h∈V\{i} is a predecessor of activity iregarding the distance order ≺D, if either dhi >0ordhi =0 and dih <0 applies (Neumann et al., 2003). Then, based on a predefined priority rule, for all 123 Annals of Operations Research (2024) 338:173–192 179 eligible activities i∈Epriority values are calculated and the activity j∗∈Ewith the highest priority is selected. For activity j∗asetZj∗containing all points in time t∈[ESj∗,LSj∗], which are resource-feasible and dominant, is determined. A point in time t∈[ES i,LS i] is called dominant for an activity i∈V, if the resource demand rc ik(t)is smaller for at least one resource k∈Rcompared to all points in time τ∈Zj∗|τ<t. The restriction to dominant points in time is motivated by the fact that, due to the aim of minimizing the project duration, an activity should generally be scheduled as early as possible and therefore a later start time is only accepted if it leads to a saving for at least one resource compared to all previous dominant as well as timeand resource-feasible points in time. This is not a limitation for the generation scheme, because dominated points in time can become dominant due to the unscheduling step in the further course of the heuristic, and thus are not necessarily unselectable. If Zj∗is empty, i.e. no timeand resource-feasible start time exists for activity j∗, an unscheduling step is performed and the counter uis increased by one. Otherwise, based on priority values calculated according to a given priority rule, the earliest point in time t∗∈Zj∗with highest priority is selected and set as start time of j∗(Sj∗=t∗). As this causes the activity to be scheduled, j∗is added to C. If all activities are scheduled, the procedure terminates. Otherwise, since the scheduling of the activity may have reduced the time windows of other activities, the earliest and latest start times of all activities not scheduled so far are updated and the procedure is repeated. Algorithm 2shows the unscheduling step which is performed if no timeand resourcefeasible point in time for the start of activity j∗can be found. In case uis higher than a maximal number of unscheduling steps ˆuthe algorithm aborts and no feasible schedule can Algorithm 1 Construction-based generation scheme Input: RCPSP/max-πinstance 1: Determine longest path lengths dij for all i,j∈V 2: Determine Pred≺D(i)for all i∈V 3: Set ES i=d0i,LS i=−di0for all i∈V 4: Set C:= {0},S0:= 0, u:= 0, i:= ∅ for all i∈V 5: Determine rc ik(t)for all i∈V\{0}and k∈Rand t∈Wi 6: for all i∈V\{0}do 7: if ESi=LSithen Si=ES i,C:= C∪{i} 8: while C= Vdo 9: rmin ik := mint∈Wirc ik(t)for all i∈V\Cand k∈R 10: rmax ik := maxt∈Wirc ik(t)for all i∈V\Cand k∈R 11: RCk:= Rk−i∈V\Crmin ik −i∈Crc ik(Si)for all k∈R 12: E:= {i∈V\C|Pred≺D(i)⊆C} 13: priority based choice of activity j∗∈Eto be scheduled next 14: Zj∗:= {t∈Wj∗\j∗|rc j∗k(t)−rmin j∗k≤RCkfor all k∈Rand mink∈R{rc j∗k(t)−rc j∗k(τ)}<0 for all τ∈Wj∗\j∗|τ<t} 15: if Zj∗=∅then u:= u+1andUnschedule 16: else 17: priority based choice of point in time t∗∈Zj∗as start time of j∗ 18: Sj∗:= t∗,C:= C∪{j∗} 19: for all h∈V\Cdo 20: ESh:= max(ESh,Sj∗+dj∗h) 21: LSh:= min(LSh,Sj∗−dhj∗) 22: Wh:= {ESh, ..., LSh} 23: if ESh=LShthen Sh=ES h,C:= C∪{h} 24: return S 123 180 Annals of Operations Research (2024) 338:173–192 Algorithm 2 Unschedule Input: C,Siand ifor all i∈V,j∗,rc ik(Si)for all i∈Vand k∈R 1: if u≥ˆuthen terminate 2: if ES j∗= d0j∗then U:= {i∈C|ES j∗=Si+dij∗} 3: if LS j∗=−dj∗0then U:= U∪{i∈C|LS j∗=Si−dj∗i} 4: if U:= ∅ then U:= {i∈C|min {rik(Si), rj∗k}>0 for at least one k∈R} 5: for all i∈Udo 6: C:= C\{i} 7: i=i∪{Si} 8: j∗:= ∅ 9: for all i∈Cwith Si>minh∈UShdo 10: C:= C\{i} 11: for all h∈V\Cdo 12: ESh:= d0h 13: LSh:= −dh0 14: for all i∈Cdo 15: ESh:= max(ESh,Si+dih) 16: LSh:= min(LSh,Si−dhi) 17: return C,ES iand LS ifor all i∈V\C,ifor all i∈V be returned. Otherwise, all activities i∈Cthat cause j∗to be unfeasibly scheduled are identified and stored in set U. For this, we first examine if one or more activities i∈Crestrict the time window of the chosen activity j∗i.e. increases ESj∗or decreases LSj∗.Ifthisis not the case for any of the scheduled activities, we determine all activities i∈Cthat require one or more resource k∈Rthat activity j∗also needs to be executed, but whose capacity is insufficient. Because at least one activity i∈Uhas to be rescheduled in order to obtain a feasible schedule, all activities i∈Uare unscheduled and removed from the set C. Moreover, the current start point Siis forbidden by storing it in the tabu-list iwhereas j∗is cleared. Points in time t∈ican no longer be chosen as start time of activity iin the scheduling phase of the generation scheme until they are removed from the tabu-list. In addition, all activities i∈Cwith Si>minh∈UShare also unscheduled, because they could start earlier in time due to the unscheduling of activities and potentially increasing remaining resource availabilities. Finally, for all activities i∈V\Cthe earliest and latest start times ES iand LS i are recalculated. In addition to the approach presented above, only scarce resources are considered to further improve the heuristic. If the remaining capacity for a resource k∈Ris higher than the sum of the maximal resource demands rmax ik of all activities that remain to be scheduled, the resource is no longer critical and consequently can be removed from the set of resources Rto be observed. Since this can change again later in the procedure due to deallocation, resources that are used by unscheduled activities but have been removed from Rare checked whether a resumption is necessary. Moreover, to improve the generation scheme and to prevent it to getting stuck, we extended the activity selection to consider strong components of the network. A strong component of a network denotes a maximum set of activities for which each activity is reachable from every other activity (without using n+1,0) (Neumann et al., 2003). Once an activity of a strong component has been scheduled, the remaining activities of this component are prioritized during the activity selection in the following iterations. For the activity selection, we used the priority rules LSTd ("latest start time first - dynamic") and TFd ("smallest total float first - dynamic"), since resource-based priority rules have shown worse performance in pre-tests. For the start time selection the priority 123 Annals of Operations Research (2024) 338:173–192 187 5 Results This section provides the results of an experimental performance analysis of the two generation schemes. All combinations of different priority rules and reverse step strategies as introduced before were tested. For each combination the generation schemes were executed as multistart procedure with one deterministic and 100 stochastic runs. The maximal number of unscheduling or reverse steps per run were limited to the instance dependent number of activities n. Within the experimental performance analysis, we used test instances for the RCPSP/maxπgenerated by Watermeyer and Zimmermann (2020), which are based on the well-known benchmark UBO-instances for the RCPSP/max developed and described by Schwindt (1998). We used the test sets UBO50π, UBO100π, and UBO200πwith n∈{50,100,200}real activities and m=30 partially renewable resources. Each of these test sets consists of 243 instances with different specifications. For better comparability, analogous to Watermeyer the maximum project duration dis calculated by d=i∈Vmax{pi,maxi,j)∈Eδij}.Note, that for the RCPSP/max-πin contrast to the RCPSP/max this value does not represent an upper bound for the project duration and consequently no feasible solution may exist. All instances that are known to be either trivial or infeasible assuming das introduced before are excluded. Consequently, a total of 502 instances of testset UBO50π, 479 instances of testset UBO100π, and 466 instances of testset UBO200πremain. In order to better benchmark the results of our generation schemes, they are compared to those of the presented MIP formulation as well as to those of the best-performing branch-andbound procedure of Watermeyer and Zimmermann (2022). All solution methods are coded in C++. To solve the MIP we used the ILOG IBM CPLEX 12.0 solver with a runtime limit of 3600s, whereas Watermeyer and Zimmermann (2022) specifies a time limit of 300 s for the UBO50πand UBO100πtest sets and 600s for the UBO200πtest set, which was adopted for our generation schemes. All runs were done on an Intel Core i7-7700K CPU with 4.2 GHz and 64 GB RAM under Windows 10 on a single thread. Since the feasibility problem of the RCPSP/max-πis NP-complete in the strong sense (cf. Watermeyer, 2021, p.34), both heuristic generation schemes do not necessarily find a feasible solution for an instance of the RCPSP/max-πeven if a feasible solution exists. Therefore, in a first step in Tabel 1the percentage of instances for which a feasible solution could be found (%feas) was evaluated for both generation schemes and compared to those obtained by the time indexed formulation solved by the solver ILOG IBM CPLEX (MIP) and the partitioningbased branch-and-bound procedure (B&B) of Watermeyer and Zimmermann (2022). The results show that both generation schemes are able to find feasible solutions for a high percentage of the tested instances (at worst 91.04%), especially using the resource-based priority rules. However, for the instances with 50 or 100 real activities, the construction-based method using the priority rule RD for the start time selection outperforms the relaxationsbased generation scheme for all tested combinations of priority rules and reverse step strategies. For the instances with 200 real activities, both generation schemes are able to find feasible solutions for almost all tested instances regardless of the selected priority rules and reverse step strategies (at worst 99.36%). For both generation schemes as well as for the branch-and-bound procedure, it can be observed that the proportion of feasibly solved instances rises with increasing instance size, whereas for the MIP the percentage decreases significantly. This indicates that due to the planning horizon, which increases with growing instance size, and the overall available resource capacity, there is more flexibility for planning the activities, which is exploited especially in the problem-specific solution methods. 123 188 Annals of Operations Research (2024) 338:173–192 Table 1 Performance regarding the percentage of feasibility UBO50πUBO100πUBO200π Tmin 96.81 98.07 99.36 LSTd RD 97.21 98.20 99.57 constr. GS RL 97.21 98.07 99.36 Tmin 96.41 98.07 99.36 TFd RD 97.21 98.20 99.57 RL 97.21 98.07 99.36 σ=1 91.04 95.82 99.36 TFd σ=2 92.23 96.24 99.36 σ=3 93.23 96.45 99.36 σ=4 93.63 96.66 99.57 GRDd σ=1 91.63 96.03 99.36 RDd σ=2 92.43 96.45 99.36 σ=3 93.22 96.87 99.57 σ=4 94.02 97.29 99.57 GRDTd σ=1 91.63 96.03 99.36 σ=2 92.63 97.08 99.57 σ=3 93.82 97.29 99.57 relax. GS σ=4 94.22 97.70 99.57 σ=1 91.63 96.03 99.36 TFd σ=2 92.63 96.66 99.36 σ=3 93.43 97.08 99.57 σ=4 93.83 97.08 99.57 GRDd σ=1 92.03 92.63 99.36 ROd σ=2 93.22 97.08 99.36 σ=3 94.02 97.29 99.57 σ=4 94.44 97.29 99.57 σ=1 92.03 97.70 99.57 GRDTd σ=2 93.43 97.49 99.57 σ=3 94.22 97.70 99.57 σ=4 94.44 97.91 99.57 MIP 96.81 63.26 25.11 B&B 98.80 98.96 100.00 Beside the percentage of feasibly solved instances, for each tested generation scheme specification, the number of instances for which it finds the best solution over both generation schemes (#best) was counted and also the average percentage deviation (∅gap) from this best solution over all feasibly solved instances was determined. The results are shown in Table 2. For some instances the different specifications come to the same objective function value, so the sum of #best per instance size is greater than the number of instances contained in the instance set. But for a part of the instances, there are also strong variations between the best solutions of the tested specifications of both generation methods. For the construction-based generation scheme, the quality of the solutions generated with the priority rules LSTd and TFd are quite similar. However, regarding the average gap both are outperformed by the 123 Annals of Operations Research (2024) 338:173–192 189 Table 2 Performance of the generation schemes UBO50πUBO100πUBO200π #best ∅gap #best ∅gap #best ∅gap Tmin 177 2.83 85 4.65 92 4.27 LSTd RD 221 3.46 147 6.21 152 5.35 constr. GS RL 259 4.20 206 6.06 224 5.28 Tmin 141 3.04 64 5.99 78 4.53 TFd RD 202 3.76 134 7.35 143 5.42 RL 242 3.59 170 7.32 179 5.33 σ=1 105 4.00 47 4.48 60 4.60 TFd σ=2 120 2.62 65 2.95 73 2.83 σ=3 123 2.83 53 3.86 64 3.59 σ=4 124 2.84 59 4.05 64 4.10 GRDd σ=1 99 4.24 44 4.68 57 4.98 RDd σ=2 114 2.84 62 3.11 66 3.03 σ=3 110 3.16 50 4.27 59 3.79 σ=4 109 3.22 57 4.30 62 4.37 GRDTd σ=1 93 4.16 47 4.45 58 4.74 σ=2 122 2.82 69 2.92 73 2.84 σ=3 119 3.12 53 3.80 61 3.66 relax. GS σ=4 116 3.19 57 4.02 63 4.22 σ=1 103 3.96 48 4.41 60 4.44 TFd σ=2 132 2.38 72 2.42 77 2.41 σ=3 123 2.54 54 4.23 62 3.34 σ=4 124 2.63 59 3.75 66 3.73 GRDd σ=1 97 4.23 43 4.55 62 4.92 ROd σ=2 110 2.80 63 3.07 71 3.00 σ=3 110 3.12 48 4.24 60 3.74 σ=4 106 3.17 58 4.25 65 2.30 σ=1 104 4.11 48 4.39 60 4.71 GRDTd σ=2 123 2.75 69 2.87 74 2.80 σ=3 120 3.12 54 3.72 63 3.59 σ=4 120 3.13 59 4.00 66 4.22 time-based rule Tmin for the smaller as well as the larger instances, even if they provide the best solutions over all tested specifications for a higher number of instances. This can be explained by the fact that – although they generate very good results for many instances – they perform comparatively poor for some of the instances, resulting in a higher average gap. The results also show that for the relaxation-based generation scheme, the combination of the resource selection rule ROd and reverse strategy σ=2 performs best. Now, the results of the best performing combinations of priority rules and strategies for both generation schemes are compared to those obtained by the time indexed formulation solved by the solver ILOG IBM CPLEX (MIP). For all solution methods, the average percentage deviation ∅gap from the best found solution over all feasibly solved instance and the average computation time ∅time in seconds were examined. The results are displayed in Table 3. 123 190 Annals of Operations Research (2024) 338:173–192 Table 3 Performance of the generation schemes in comparison UBO50πUBO100πUBO200π ∅gap ∅time ∅gap ∅time ∅gap ∅time constr. GS 7.43 24.48 9.45 89.94 6.48 262.23 relax. GS 6.89 59.24 8.58 172.71 5.25 332.62 MIP 0.37 2175.01 22.58 2985.09 25.31 3198.26 For the MIP, in general, it can be observed, that the larger the instance, the higher the achieved gap and the required computation time. To improve the performance of the MIP, higher time limits of up to eight hours were tested. However, it can be observed that several of the tested instances, especially the larger ones, still cannot be solved with a small gap or even optimally. Therefore, solving the instances using a solver is not expedient even with an extended solution time. For the generation schemes, the gap first rises, but then falls again for the instances with 200 real activities. For the UBO50πinstances, the MIP outperforms the heuristics. With increasing instance size, the generation schemes are not only able to solve more instances feasibly than the MIP, but also the constructed schedules are better for UBO100πand significantly better for UBO200πcompared to the MIP. Regarding the average computation time, it can be observed, that the relaxation-based generation scheme takes more time than the construction-based generation scheme. In particular, returning to the initial state as reverse step strategy causes a high time overhead compared to the other reverse step strategies. For all tested instance sizes, the average computation time solving the MIP is drastically higher than for both generation schemes. Overall, the relaxation-based generation scheme generates a marginal smaller gap than the construction-based, but also takes more time. 6 Conclusion In this paper we presented two generation schemes for the resource-constrained project scheduling problem with partially renewable resources and generalized precedence constraints (RCPSP/max-π). In the first one, a successive scheduling of the activities is done to finally construct a feasible solution. In the second, starting from the ES-Schedule, which in general is resource-unfeasible, resource conflicts are solved until a feasible solution has been found. The results of a comprehensive experimental performance analysis show, that both generation schemes are able to generate feasible solutions for nearly all tested instances in a short time and that the relaxation-based generation schemes finds marginal better solutions while requiring slightly more time. In order to improve the solutions obtained in this way, further research should address the development of improvement heuristics, such as a genetic algorithm or a fix-and-optimize heuristic. Also, machine learning approaches seem promising. For example, our generation schemes could be extended to include a learning component that, from run to run, gives higher weight to promising scheduling sequences or resource conflict solutions in the selection process and, in contrast, gives less preference to steps that have led to unscheduling or reverse steps. In addition, projects with renewable and partially renewable resources should be considered, since in practice both resource types usually occur together. Funding Open Access funding enabled and organized by Projekt DEAL. No funding was received to assist with the preparation of this article. 123 Annals of Operations Research (2024) 338:173–192 191 Declarations Conflict of interest There are no interests to declare. Ethical approval This article does not contain any studies with human participants or animals performed by any of the authors. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. References Alvarez-Valdés, R., Crespo, E., Tamarit, J., & Villa, F. (2006). A scatter search algorithm for project scheduling under partially renewable resources. Journal of Heuristics, 12(1), 95–113. Alvarez-Valdés, R., Crespo, E., Tamarit, J., & Villa, F. (2008). Grasp and path relinking for project scheduling under partially renewable resources. European Journal of Operational Research, 189, 1153–1170. Alvarez-Valdés, R., Tamarit, J., & Villa, F. (2015). Partially renewable resources. In C. Schwindt & J. Zimmermann (Eds.), Handbook on Project Management and Scheduling (Vol. 1, pp. 203–227). Springer. Böttcher, J., Drexl, A., Kolisch, R., & Salewski, F. (1999). Project scheduling under partially renewable resource constraints. Management Science, 45(4), 543–559. Drexl, A., Juretzka, J., & Salewski, F. (1993). Academic course scheduling under workload and changeover constraints. Working paper of the University of Kiel No. 337. Drexl, A., & Salewski, F. (1997). Distribution requirements and compactness constraints in school timetabling. European Journal of Operational Research, 102(1), 193–214. Floyd, R. W. (1962). Algorithm 97: Shortest path. Communications of the ACM, 5(6), 345. Franck, B., Neumann, K., & Schwindt, C. (2001). Truncated branch-and-bound, schedule-construction, and schedule-improvement procedures for resource-constrained project scheduling. OR-Spektrum, 23, 297– 324. Karnebogen, M., & Zimmermann, J. (2021). A generation scheme for the resource-constrained project scheduling problem with partially renewable resources and time windows. In: Book of Extended Abstracts of 17th International Conference on Project Management and Scheduling, Toulouse. pp. 195–198. Karnebogen, M., & Zimmermann, J. (2022). A relaxation-based generation scheme for the RCPSP/max,π.In: Book of Extended Abstracts of 18th International Conference on Project Management and Scheduling, Ghent. pp. 72–75. Neumann, K., Schwindt, C., & Zimmermann, J. (2003). Project scheduling with time windows and scarce resources. Springer. Talbot, F. B. & J. H. Patterson. (1978). An efficient integer programming algorithm with network cuts for solving resource-constrained scheduling problems. Management Science, 24(11), 1163–117. Schirmer, A. (1999). Project scheduling with scarce resources: Models, methods and applications. Springer. Schwindt, C. (1998). Generation of resource-constrained project scheduling problems subject to temporal constraints. Technical Report WIOR-543, University of Karlsruhe. Watermeyer, K. (2021). Projektplanung mit partiell erneuerbaren Ressourcen. Düren: Shaker. Watermeyer, K., & Zimmermann, J. (2020). A branch-and-bound procedure for the resource-constrained project scheduling problem with partially renewable resources and general temporal constraints. OR Spectrum, 42(2), 427–460. Watermeyer, K., & Zimmermann, J. (2022). A partition-based branch-and-bound algorithm for the project duration problem with partially renewable resources and general temporal constraints. OR Spectrum, 44(2), 575–602. Watermeyer, K., & Zimmermann, J. (2023). A constructive branch-and-bound algorithm for the project duration problem with partially renewable resources and general temporal constraints. Journal of Scheduling, 26, 95–111. 123 192 Annals of Operations Research (2024) 338:173–192 Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 123