Resource overload problems with tardiness penalty: structural properties and solution approaches

Wohlert, Lena Sophie; Zimmermann, Jürgen Article — Published Version Resource overload problems with tardiness penalty: structural properties and solution approaches Annals of Operations Research Provided in Cooperation with: Springer Nature Suggested Citation: Wohlert, Lena Sophie; Zimmermann, Jürgen (2024) : Resource overload problems with tardiness penalty: structural properties and solution approaches, Annals of Operations Research, ISSN 1572-9338, Springer US, New York, NY, Vol. 338, Iss. 1, pp. 151-172, https://doi.org/10.1007/s10479-023-05789-2 This Version is available at: https://hdl.handle.net/10419/315291 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:151–172 https://doi.org/10.1007/s10479-023-05789-2 ORIGINAL RESEARCH Resource overload problems with tardiness penalty: structural properties and solution approaches Lena Sophie Wohlert1·Jürgen Zimmermann1 Received: 7 December 2022 / Accepted: 11 December 2023 / Published online: 16 January 2024 © The Author(s) 2024 Abstract In this paper, we consider a resource overload problem and add a tardiness penalty to the objective function when a prescribed project makespan is exceeded, which enables a tradeoff between a balanced resource utilization and a project delay. For the tardiness penalty, we distinguish between a constant and variable delay cost variant. Based on the structural properties of the resource overload problem, we show that the search space of the resource overload problem with tardiness penalty can also be reduced utilizing quasistable schedules. In addition, we discuss the application of these findings to further problems, which include objectives composed of a locally concave and a concave function or a reward structure for an early project completion instead of a tardiness penalty. As solution approaches, we present mixed-integer linear model formulations as well as a novel genetic algorithm with a decoding procedure, which exploits the devised structural properties. The performance of the genetic algorithm is improved by implementing learning methods and utilizing lower bounds. Finally, we present results from experiments on small to medium sized problem instances. Keywords Project scheduling ·Resource overload ·Tardiness penalty ·Quasistable schedules ·Genetic algorithm 1 Introduction Instances of the resource overload problems often arise when costly fluctuations in resource utilization are to be minimized and a maximum project duration is given. However, as the scheduling of projects is an inherent multi-objective optimization problem, the exceeding of the prescribed project makespan can be allowed at additional cost. This enables a trade-off between a more balanced resource utilization and a project completion delay to achieve a more cost and resource efficient outcome. These additional cost may represent opportunity BLena Sophie Wohlert [email protected] Jürgen Zimmermann [email protected] 1Institute of Management and Economics, Clausthal University of Technology, Julius-Albert-Str. 2, 38678 Clausthal-Zellerfeld, Germany 123 152 Annals of Operations Research (2024) 338:151–172 cost for further orders, an earlier market entry, or alternatively tardiness penalties for missed deadlines (Schnabel et al., 2018). For the resource overload problem and other resource levelling problems several mixedinteger linear models are presented in Rieck et al. (2012) and Rieck and Zimmermann (2015). To solve the resource overload problem heuristically, Ballestin et al. (2007) propose a population-based greedy algorithm that constructs quasistable schedules, among which there is at least one optimum. Schnabel et al. (2018) consider a resource-constrained project scheduling problem where the objective includes revenues, which decrease with an increasing makespan, as well as resource overload cost. They observe that for this problem, unlike the resource overload problem, there is not always an optimum among the quasistable schedules, which would allow for a search space reduction. To solve the proposed problem, they present a genetic algorithm with different representations based on an activity list and either a maximum allowable overload per resource or per activity. Atan and Eren (2018) discuss the impact of relaxing a prescribed project makespan at no additional cost for different resource levelling problems to identify the minimum project duration for the best levelled schedule. As an heuristic, the authors use the population-based approach of Ballestin et al. (2007)but do not restore the quasistableness of the schedules. In Kim et al. (2005), the project duration is extended stepwise in increments of one time unit to determine different schedules for a project manager to decide from. Hegazy (1999) present objectives that consider the sum of the project duration and a resource levelling metric, which can be weighted. Koulinas and Anagnostopoulos (2012) formalize the approach of Hegazy (1999) further by introducing a trade-off coefficient to weight the cost factors in the objective function. Ponz-Tienda et al. (2013) present an adaptive genetic algorithm for a resource levelling problem in which exceeding the prescribed project makespan is allowed with a tardiness penalty that increases linearly with the project extension. In Hartmann and Briskorn (2022), an overview of further incorporations of makespan-dependent cost and respectively the minimization of the project makespan into various project scheduling problems is given. For instance, Shadrokh and Kianfar (2007) and Gerhards and Stürck (2018) consider a resource investment problem with tardiness penalty. An overview of the discussed literature related to resource levelling isgiveninTable1, focusing on the utilized objective function and solution approach. In this paper, we discuss the resource overload problem with different variants of tardiness penalties. The latter applies if a prescribed project makespan is exceeded, whereby a distinction is made between constant and variable cost for each time unit of delay. We close the research gap outlined in Schnabel et al. (2018) by proofing that the problem can be divided into subproblems for which there is at least one optimum among the quasistable schedules. As a result, the search space can be reduced, and in most cases only a considerably smaller subset of schedules needs to be investigated in order to obtain an optimal solution. The findings obtained are of particular importance since they also apply to other bi-objective problems whose objective function is a weighted sum of a locally concave function and a concave function. Besides mixed-integer linear model formulations, we present a novel genetic algorithm with a decoding procedure, which constructs only solutions within the derived set of quasistable schedules of different project durations. In addition, the solution representation indicates a start time selection rule for each activity and two learning methods are incorporated in the algorithm. We contribute a parametrization of the resource overload problem with tardiness penalty and test the two solution approaches on small to medium sized problem instances. This paper is organized as follows: Sect. 2is devoted to the problem description of the resource overload problem with tardiness penalty. Some structural properties of the basic resource overload problem are presented in Sect.3and are adapted to consider tardiness 123 Annals of Operations Research (2024) 338:151–172 153 Table 1 Overview of relevant literature First author Year Objective Solution approaches RL RL + TP RV – ROP MIP GA POP w. QS Hegazy 1999  Kim 2005 * Ballestin 2007  Koulinas 2012  Rieck 2012  Ponz-Tienda 2013  Rieck 2015  Atan 2018 * Schnabel 2018  RL: Resource levelling (including resource overload), TP: Tardiness penalty, RV: Revenue MIP: Mixed-integer linear program, GA: Genetic algorithm, POP w. QS: Population based approach with quasistable schedules * different project makespans are investigated penalty, too. The application of these findings to other (bi-objective) problems is discussed in Subsection 3.4. In Sect.4, mathematical model formulations are presented. Section5intro- duces our novel genetic algorithm. We test the solution approaches in experiments, which are described in Sect.6and the paper is concluded in Sect. 7. 2 Problem description We assume that a project consists of a set of activities V, where each activity i∈Vis assigned a processing time pi≥0 that cannot be interrupted. Among the activities, there are nreal activities and two fictitious activities 0 and n+1 with p0=pn+1=0 corresponding to the project start and completion. The start time of activity iis given by Si≥0, where the project start is assumed to be scheduled at time zero (S0=0). Moreover, the completion time of an activity iis defined as Ci:= Si+pi. Between the start times of two activities iand j, general temporal constraints Sj−Si≥δij are assumed with δij ∈R. A minimum time lag between the start of activity iand japplies if δij ≥0, whereas δij <0 denotes a maximum time lag. Among the maximum time lags, the maximum project duration d(specifying the underlying planning horizon) is described by a temporal constraint from project completion to project start S0−Sn+1≥−d. For each activity ian earliest start time ES iand latest start time LS ican be computed by means of some longest path algorithm (Ahuja et al., 1993), from which the total float TF i:= LS i−ES iof each activity ican be derived. A schedule S=(S0,S1,...,Sn+1)contains a sequence of start times, which are ordered according to the numbering of the activities. To visualize the project, we use an activity-on- node network N=(V,E,δ), where the processing time piis given above each node i∈V and an arc i,j∈Edepicts a minimum or maximum time lag δij. A schedule that satisfies all the temporal constraints is termed time-feasible and the set of those schedules is denoted as ST. The set of renewable resources, which are utilized to carry out the activities, is represented by R. Each activity iis assigned a resource utilization rik ≥0 for each resource k∈R, which are listed below the respective activity in the project network N. The resource function rk(S,·)of a schedule Sand a resource kis a stepwise function, 123 154 Annals of Operations Research (2024) 338:151–172 Fig. 1 Activity-on-node project network which computes the sum of the resource utilization of every active activity at point in time t∈R≥0. An activity iis active if the current time tis greater or equal to the start time Siand less than Ci. A resource profile visualizes the resource function rk(S,·)for a given resource k∈Rand schedule Sin dependence of t. The resources are assumed to be uncapacitated. However, a resource threshold Ykis defined for each resource k∈Rfrom which positive deviations in the resource utilization rk(S,t)at any point in time tare penalized. Example 1 Figure1depicts an activity-on-node network which contains three real activities and one renewable resource. The earliest project completion is 10 and the maximum project duration dis limited to 14. Activity 2 has only one feasible start time S2=1 and activity 3 has to be scheduled at S3=6. Only activities 1 and 4 have a total float greater than zero. The objective of the basic resource overload problem coincides with the cumulative cost of positive deviations from the resource thresholds Yk. The positive deviations for each resource can be weighted differently by cost factors ck∈R>0. fROP(S)= k∈R ck t∈[0,d] (rk(S,t)−Yk)+dt The resource overload problem is to determine an optimal schedule that minimizes the objective function fROP while satisfying the temporal constraints. It can be formulated as follows: Minimize fROP(S) subject to Sj−Si≥δij i,j∈E S0=0 Si≥0i∈V As there are no other constraints such as resource capacities, the set of time-feasible schedules equals the set of feasible schedules i.e. S=ST. For the resource overload problem with tardiness penalty, we assume that besides a maximum project duration da prescribed project makespan T∈[ES n+1,d]is given. Tcan be exceeded at additional cost fTP, which is added to the objective function (Ponz-Tienda et al., 2013; Shadrokh & Kianfar, 2007). f(S)=fROP(S)+fTP(S) Here, we assume that the prescribed project makespan Tand the maximum project duration dare positive integers. Additionally, we suppose that an increase in tardiness penalty only occurs with each whole unit of time and not with each arbitrarily small delay. First, the delay 123 Annals of Operations Research (2024) 338:151–172 155 Fig. 2 Tardiness penalty function with a constant delay cost factor ρ=1 Fig. 3 Tardiness penalty function with a variable delay cost factor ρ13 =0.5andρ14 =1.25 cost factor ρ∈R≥0is assumed to be constant, with the value of fTP increasing linearly with an additional time unit to be penalized. The resulting tardiness penalty function fTP is piecewise defined depending on the project completion Sn+1and has jump points at every integer time point greater or equal to T. Moreover, fTP is lower semi-continuous on all schedules. fTP(S)=0,Sn+1∈ES n+1,T; ρ·(a+1), Sn+1∈T+a,T+a+1,a∈0,...,d−T−1. In typical real-world examples, different additional cost ρt≥0,t∈{T+1,...,d} may apply for every additional time unit of delay. The resulting function fTP is also lower semi-continuous and monotonically increasing. fTP(S)=⎧ ⎪ ⎨ ⎪ ⎩ 0,Sn+1∈ES n+1;T; Sn+1  t=T+1 ρt,Sn+1∈T+a;T+a+1,a∈0,...,d−T−1. Example 2 In the following, an example is given for each tardiness penalty function variant. As in the project network in Fig.1, a maximum project duration of 14 is assumed. Let T=12 be the prescribed project makespan. In Fig.2, a tardiness penalty function with a constant delay cost factor ρ=1 is shown. Figure 3depicts a tardiness penalty cost function with variable, increasing, delay cost factors. Remark 1 The formulation of fTP can be further generalized for constant and variable delay cost. Instead of no cost ( fTP =0) for Sn+1∈ES n+1;T, any constant ρ0∈Rcan be utilized. Obviously, for two schedules S1and S2with fTP(S1)< fTP(S2), the same holds even if the constant ρ0is considered. The generalization can be used to represent a reward structure for an early project completion which may only decrease with an increase of the project duration like in Schnabel et al. (2018). However, such a function must be multiplied by −1 to satisfy the minimization objective. As shown in Neumann et al. (2003), the basic resource overload problem is already NP- hard in the strong sense. Thus, the same applies to the resource overload problem with tardiness penalty. However, finding a feasible solution is easy, because the ES-schedule is always feasible. 123 156 Annals of Operations Research (2024) 338:151–172 Fig. 4 Resource profile of ES =(0,0,1,6,10) 3 Structural properties In this section, we discuss order-based structural properties and properties of the resource overload objective function. These can be utilized to reduce the search space of the basic resource overload problem, and then similarly for variants with tardiness penalty. As described in Neumann et al. (2003), a strict order relation is implicated if an activity jstarts after an activity iis completed (Sj≥Si+pi). A schedule induced order O(S)is introduced to refer to all strict order relations between pairs of real activities (i,j)∈{1,...,n}×{1,...,n} that are met by the schedule S.Let ST(O(S)) := {S∈ST|Sj≥Si+pifor all (i,j)∈O(S)} denote the set of all time-feasible schedules that satisfy the strict order given by O(S).A set of schedules that induces an identical strict order as schedule Sis termed equal order set S= T(O(S)). If the start time Siof at least one activity iis shifted forward or backward from a time feasible schedule S, resulting in a non-identical and time-feasible schedule S,this movement is referred to as a shift. An order preserving shift describes a shift from a schedule Sto another feasible schedule Ssuch that the order of the initial schedule is preserved (O(S)⊇O(S)). Two shifts that transform a schedule Sinto a schedule Sand a schedule S are called a pair of opposite shifts if S −S=λ(S−S)with λ<0 holds. A feasible schedule Sis said to be quasistable if there is no pair of opposite order preserving shifts. 3.1 Resource overload problem The function fROP is continuous and thus also lower semi-continuous. Moreover, the function is concave on each equal order set, denoted as locally concave. Neumann et al. (2003) proof that there is always a quasistable schedule among the optima for functions fthat are locally concave. A quasistable schedule Shas useful structural properties: For the start time of each activity i∈V, there is always an activity j∈Vfor which either a precedence relationship Sj=Si+pior Sj=Si−pjor a temporal constraint Sj=Si+δij or Sj=Si−δji is binding (Neumann et al., 2003). If δij ∈Z(including d), pi∈N0and ST=∅, quasistable schedules contain only integer start times. Since there is always an optimum among quasistable schedules, there is also always an integer optimum solution. Therefore, the time horizon can be discretized for the resource overload problem without loss of solution quality. In the following, we assume that the temporal input fulfills the above mentioned conditions. In addition, if only one renewable resource is used in an example, the corresponding indices are omitted. Example 3 We consider again the project depicted in Fig.1. The resource profile of the ES- schedule is displayed in Fig.4.TheES-schedule induces the order O(ES)={(1,3), (2,3)}. In Fig.5,fROP is depicted in dependence of the start time S1of activity 1 where the cost per resource overload unit is assumed to be c=1 and the resource threshold is set to be Y=1. It is obvious that the minimum of fROP(S1)is at S1=10. In the same figure, the different 123 Annals of Operations Research (2024) 338:151–172 157 Fig. 5 Resource overload function, schedule induced orders, equal order sets and quasistable schedules Fig. 6 Resource overload function with a constant delay cost factor induced orders are highlighted in different shades depending on the start time of activity 1. Since identical schedule induced orders belong to the same shade of gray, their respective equal order sets are the union of all schedules marked with the same shade. It can be seen that the resource overload function is concave on equal order sets. The quasistable schedules are marked with dots, which include the minimum of the function fROP. 3.2 Constant delay cost factor In this subsection, we discuss structural properties of the resource overload problem with a constant delay cost factor. Example 4 We consider again the project depicted in Fig. 1.For fTP, a constant delay cost factor ρ=c=1 is assumed for every additional time unit of delay when the prescribed project makespan of T=12 is exceeded (see Fig.2). In contrast to the resource overload function in Fig.5,fROP can also be visualized as a function of the completion C1of activity 1. This is useful here because the completion of activity 1 and the project completion Sn+1 coincide if activity 1 completes at time 6 or later. Moreover, activity 1 is the only real activity that can be shifted. As a result, fTP and thus fcan also be represented as a function of C1in this specific example. In Fig.6, the course of function fis depicted. The quasistable schedules are marked in light gray. It can be seen that the minimum of the combined objective function fis reached when activity 1 ends at 12, which is the prescribed project makespan T. However, this schedule is not a quasistable schedule. In the following, we provide an extension of the set of quasistable schedules that contains at least one optimum for resource overload problems with a constant delay cost factor. This set is obtained by dividing the problem into two subproblems based on different minimum and maximum project durations and determining the set of quasistable schedules for both subproblems. Theorem 1 Given a resource overload problem with a constant delay cost factor P, two subproblems Pand P can be constructed. The set of feasible schedules of subproblem P 123 158 Annals of Operations Research (2024) 338:151–172 is further limited by an adjusted maximum project duration of T . The set of feasible schedules of the second subproblem P is further limited by a minimum project duration of T . Among the quasistable schedules of the two subproblems Pand P, there is at least one optimal solution of P. Proof A resource overload problem with a constant delay cost factor can be divided into two subproblems. For the first subproblem, a maximum project duration of Tapplies. This subproblem has a set of feasible schedules ST,≤T, all of which have no tardiness penalty. Therefore, this subproblem is a basic resource overload problem and among the set of its quasistable schedules, there is at least one of its optima. The second subproblem has a minimum project duration of Tand a maximum project duration of d. The connected set of time-feasible schedules ST,≥Tcontains schedules S∈STwith a project duration of T≤Sn+1≤d. The equal order sets of this subproblem are denoted as S= T(O(S))≥T:= S= T(O(S)) ∩S∈ST:S n+1≥T. On the equal order sets S= T(O(S))≥T, the resource overload function fROP is still concave. However, for this subproblem the combined objective function fis not equal to fROP because the values of the tardiness penalty function fTP can be greater than zero. To nevertheless determine schedules that minimize fin this subproblem, the auxiliary function fhis defined for S∈STwith Sn+1≥T. fh(S)=ρ·Sn+1−T The function fTP is the ceiling function of fhwithin the discussed subproblem. Therefore, fhunderestimates the value of fTP at every point in time t∈[T,d]by a value within the interval [0,1). Moreover, functions fhand fTP have the same objective function values if the project makespan Sn+1is an integer and thus fROP +fTP =fROP +fhfor all schedules with Sn+1∈N. The auxiliary function fhis concave and therefore also locally concave. The sum of locally concave functions, here fROP and fh, is again locally concave. Since fROP +fhunderestimates fand they have the same value for each schedule with only integer start times, among the quasistable schedules that satisfy T≤Sn+1≤dis at least one optimum of this subproblem. Remark 2 Let Ibe an instance of the resource overload problem with a constant delay cost factor. The project network Nof Ican be modified to represent the temporal constraints of either of the two subproblems described. By adding an arc n+1,0with the weight δn+1,0=−T, the project network Nis adapted to the first subproblem. For the second subproblem an arc 0,n+1with a weight of δ0,n+1=Tis added, which indicates a minimum time lag and therefore a minimum project duration. 3.3 Variable delay cost factor We now assume that for every additional time unit of delay different additional tardiness penalty cost ρt≥0, with t∈T+1,...,dapply, which results in a monotonically increasing penalty function. This function cannot be necessarily underestimated by a linear function. Moreover, it can be seen in Fig. 7that the minimum is not among the schedules described in Theorem 1. The problem is therefore divided into further subproblems. Theorem 2 Given a resource overload problem with a variable delay cost factor, the following subproblems can be constructed. The subproblem Phas a set of feasible schedules that is 123 Annals of Operations Research (2024) 338:151–172 165 process of an activity iis completed when it is removed from the set of unscheduled activities Cand inserted into the set of completed activities C.IfCis empty, the algorithm terminates. The resulting schedule is always feasible. Algorithm 1 Decoding procedure 1: Set S 0:= 0, initialize C:= {0}and C:= V\{0} 2: Compute ES i:= d0iand LS i:= −di0,∀i∈C 3: while C=∅do 4: Initialize i:= −1andrk1,max := −1 5: for h∈Cdo 6: if rk1,h>rk1,max then 7: for j∈Cdo 8: if (h,j∈Eand ES h≤S j−δhj ≤LS h) 9: or (j,h∈Eand ES h≤S j+δjh ≤LS h) 10: or (ES h≤S j−ph≤LS h) 11: or (ES h≤S j+pj≤LS h)then 12: i:= h,rk1,max := rk1,h. 13: break 14: Initialize Di:= ∅ 15: for j∈Cdo 16: if i,j∈Eand ES i≤S j−δij ≤LS ithen Di:= D∪{S j−δij}. 17: if j,i∈Eand ES i≤S j+δji ≤LS ithen Di:= D∪{S j+δji}. 18: if ES i≤S j−pi≤LS ithen Di:= D∪{S j−pi}. 19: if ES i≤S j+pj≤LS ithen Di:= D∪{S j+pj}. 20: if i=n+1and constant delay cost then 21: Di:= Di∪({ES n+1,...,LS n+1}∩{T}). 22: else if i=n+1and variable delay cost then 23: Di:= Di∪({ES n+1,...,LS n+1}∩{T,...,d−1}). 24: if b2,i=1then choose S i:= argmin τ∈Di ( fROP(τ )) 25: else choose τ∈Diaccording to rk3,iand set S i:= τ 26: Remove activity ifrom C, insert activity iinto C 27: for h∈Cdo 28: ES h:= max(ES h,S i+dih),LS h:= min(LS h,S i−dhi) 5.5 Lower bound of the optimal objective function value The lower bound (LB) for the objective function value of the resource overload problem with tardiness penalty described in this subsection can be used as a termination criterion for the genetic algorithm or otherwise as an estimate of its solution quality. To compute LB, a lower bound for the cost of resource overload k∈Rckomin kSn+1can be estimated first for every feasible project makespan Sn+1∈{ES n+1,...,d}, to which the applicable tardiness penalty fTP(Sn+1)must then be added. Of these values, the minimum is then used as the lower bound for the optimal objective function value. LB := min Sn+1∈{ES n+1,...,d} k∈R ckomin kSn+1+fTP(Sn+1) 123 166 Annals of Operations Research (2024) 338:151–172 Fig. 8 Resource utilization of all real activities at their feasible execution times for a project makespan of 12 There are several ways to determine the variables omin kSn+1for each k∈R,ofwhichthe maximum is selected. An option is to calculate the total resource utilization of resource k and reduce it by the product of the project duration Sn+1and the resource threshold Yk.This lower bound can be tightened by determining for each time period t∈{0,...,Sn+1−1}the sum of resource units rmax k(t)utilized by all real activities that can possibly be in execution. If rmax kis below the threshold Ykin one or more periods, this may increase the resource overload that must occur in the remaining periods. A second way to determine the minimum resource overload omin kSn+1can be to look at the resource utilization rik of each activity and evaluate whether and how much it exceeds Ykalone during its execution. Example 5 We adjust the project network shown in Fig. 1by adapting the minimum time lag between the project start 0 and activity 1 to δ01 =1, resulting in an earliest start ES 1=1. Moreover, the minimum and maximum time lag between the start of activity 2 and the start of activity 3 is increased to exactly 6. In this project, the three real activities have a total resource utilisation of 12 resource units. Let us consider a project makespan of Sn+1=11. Calculating the minimum resource overload omin 11 by reducing the total resource usage by the resource threshold Y=1 multiplied by the project duration 11 yields in a value of 1. If we depict the maximum resource units rmax possibly utilized in each time period (see Fig. 8), we see that in period 0 the maximum resource utilization is 0 and thus below the threshold Y=1. The minimum resource overload omin 11 therefore can be adjusted to 2. This is a tight lower bound for a project duration of 11 as the optimal resource overload function value equals 2 resulting, for example, from the schedule S=(0,5,1,7,11). The other variant of determining omin kt is not relevant here because none of the activities alone exceeds the resource threshold. 6 Experiments In the following section, the performance of the MIP-formulation as well as the novel genetic algorithm is investigated. We first describe how we extend well-known instance sets to incorporate tardiness penalty. Then, the parametrization of the solution approaches is described. Finally, we present and discuss the results of experimental results for constant and variable delay cost, distinguishing between different prescribed project makespans and maximum project durations. 6.1 Test design The computational tests are based on the test sets UBO for the RCPSP/max, which were obtained by the problem generator ProGen/max (Schwindt, 1998), cf). Every test set incorporates 90 instances with either 10, 20, 50 or 100 real activities and 5 renewable resources. In addition, the restrictiveness of Thesen (RT) is given for the instances that measures the degree to which the total number of feasible activity sequences is restricted by the precedence 123 Annals of Operations Research (2024) 338:151–172 167 relationships. If RT = 0, the real activities are all parallel to each other. RT = 1 occurs only for a serial project network. For the test instances, RTs in {0.25,0.5,0.75}are targeted. In order to perform our experiments, further parametrizations of the instances are required. The maximum project duration is set with a coefficient α>1tod:= αES n+1. Moreover, the prescribed project makespan Tis initialized as T:= βES n+1where 1 ≤β<α.The resource thresholds Ykfor all k∈Rare chosen according to the total resource utilization and the prescribed project makespan Tinstead of the maximum project duration used in Neumann et al. (2003)(Yk:= i∈Vrik ·pi/T,k∈R). We assume that the cost factor ckfor each overload unit of resource kis 1. To calculate the tardiness penalty, a factor γ is introduced. The constant delay cost factor ρis then calculated as ρ:= γk∈RYk.To test the solution approaches with variable delay cost factors, monotonically increasing cost factors ρtare chosen. ρt:= ⎧ ⎨ ⎩ γ· k∈R Yk·(1+γ) (t−T),t>T; 0,t≤T. We use C++ in the Microsoft Visual Studios 2022 development environment to implement the mixed-integer linear models and the genetic algorithm. For the MILPs the solver IBM ILOG CPLEX 20.1 is utilized. For CPLEX, the time limit is set to be 1800s for all instances. Preliminary results have shown that providing the previously described lower bound to the solver does not improve the run time or the best objective function value overall. The parameters of the genetic algorithm are chosen as follows: the population size is set according to the number of real activities in the instance to be 2n. The proportion of elitist individuals is defined as 0.35 of the population size. The crossover probability is set to be 0.7 and the mutation probability as 0.1. For small instances with n=10, the genetic algorithm runs until K-iterations without an improvement of the best objective function value are performed. We choose K:= 500. For larger instances, a time limit is set. For instances with n=20, the run time is limited to 30s, for n=50 and n=100 to 300s. The genetic algorithm is terminated early if the best objective function value equals the calculated lower bound. Preliminary runs have shown that the two learning methods (opposition-based learning and adapting mutation probabilities) lead to a better overall result for instances with 50 or more activities. Therefore, the learning methods are only applied for these instances. To create an initial population for smaller instances, only the first step described in Sect.5.2 is performed. To adjust the mutation probabilities in case of n=50 and n=100, the number of analysed solutions is set to l:= 3 and the scaling factor to s:= 4. For the first experiments, the maximum project duration is set using α:= 1.25. In order to examine the influence of different prescribed project makespans, we solve the instances with β∈{1.0,1.1}. To determine γ, preliminary CPLEX runs are performed for instances with 10 activities, where optimality can always be proven in a short time for each instance solution. However, runs with γ=0.3 for the resource overload problem with a constant delay factor and γ=0.1 for variable delay cost factors have a slightly higher average run time in contrast to other parametrizations. Moreover, it is observed that the project durations of the optimal schedules are comparatively widely scattered across instances compared to other parametrizations. Therefore, γ. =0.3 for the resource overload problem with a constant delay factor and γ:= 0.1 for variable delay cost factors is investigated for all instance sizes. 123 168 Annals of Operations Research (2024) 338:151–172 Table 2 Resource overload problem with a constant delay cost factor with α=1.25 Instances CPLEX Genetic algorithm αβγn#opt ∅gap ∅topt[s]∅gapr∅tga[s]∅ss 1.25 1.0 0.3 10 90 0 0.92 0.35 0.59 23.36 20 79 1.17 149.71 0.76 30.00 19.90 50 0 44.22 −− −6.68 300.02 20.72 100 0 60.92 −− −13.42 300.14 17.55 1.25 1.1 0.3 10 90 0 1.00 0.14 0.81 23.61 20 82 0.82 160.86 0.51 29.15 20.39 50 0 38.62 −− −4.34 300.02 21.25 100 0 60.16 −− −21.25 300.12 17.51 6.2 Results All of the tests were conducted on computers with 64 GB RAM and an Intel(R) Core(TM) i7-7700K with 4x4.20 GHz and 8 threads. The results provide the number of instances per test set which are solved to optimality and its optimality is proven (#opt) and the average gap over all instances (∅gap) achieved by CPLEX. The average run time of the instances counted in #opt is denoted as ∅topt and is measured in seconds. To investigate the quality of the genetic algorithm, the average relative gap (∅gapr), which is calculated in regards to the best objective function value obtained by CPLEX, is depicted. The average run time in seconds of the genetic algorithm is denoted as ∅tga. To obtain an estimate of the search space reduction, the number of start times within the decision set |Di|is compared to the number of feasible start times LS i−ES i+1 for each activity i∈V\{0}and the average over all solutions in all generations within a test set is denoted as ∅ss. 6.2.1 Constant delay cost Table 2summarizes the results for the resource overload problem with a constant delay cost factor, where we differentiate between two mentioned prescribed project makespan parametrizations, which also lead to different resource thresholds. For all of the instances with 10 activities, an optimal solution is found and its optimality is proven by CPLEX in under 11s. Moreover, for the majority of instances with 20 activities (90 %) the solver determines an optimum within half an hour and ∅topt is for both different prescribed project makespan parametrizations relatively equal. As we expected, the solution quality of the solver decreases with an increasing number of activities. CPLEX could not prove the optimality for any of the instances with 50 or 100 activities and the average gap is approximately 40% for n=50 and 60% for n=100 after half an hour of run time for both β.However,the gap varies significantly across the instances. The gap is considerably larger than the average for instances with a rather parallel network (RT ≈0.25), whereby for more serial networks with RT ≈0.75 the gap is significantly smaller. For the test sets with 50 or 100 activities, the correlation coefficients of RT and the solver gap lie in the range of −0.8 to −0.7. The last columns of Table 2reveal the performance results of the genetic algorithm. On instances with n=10 and n=20, the genetic algorithm performs similarly well as CPLEX. But especially for instances with 20 activities, the average run time ∅tga is significantly shorter. An early termination due to reaching the calculated lower bound never occurs for 123 Annals of Operations Research (2024) 338:151–172 169 instances with a tight prescribed project makespan (β=1.0). When setting β=1.1, considering the calculated lower bound leads to the termination of the genetic algorithm 5 times with 10 activities and 3 times with 20 activities. All of the affected instances have a project duration that does not exceed the prescribed project makespan Tand therefore no tardiness penalty applies. On larger instances with 50 activities, the genetic algorithm obtains an average relative gap of −6.68% and −4.34%. Comparing the solution quality of instances with 100 activities, the genetic algorithm obtains on average significantly better results than CPLEX within a significantly shorter run time. With a tight prescribed project makespan (β=1.0), CPLEX only obtains a better solution for 5 out of 90 instances. With β=1.1this is only the case for one instance. Considering the average search space size ∅ss, it is evident that the genetic algorithm only considers a small subset of feasible start times and thus a search space reduction is in place. The values of ∅ss for both prescribed project makespan parametrizations are similar, although no separate consideration of Tas the project makespan is necessary for β=1.0in contrast to β=1.1. In addition, we investigate the average of the binary values b2,ifor all i∈V\{0}for the best solution obtained for each instance, in order to draw conclusions about the start time selection rules. The average varies widely for instances with 10 activities (0.25 to 1.0) and the least for instances with 50 and 100 activities (0.51 to 0.88). In regards to the good performance of the genetic algorithm, an objective function value-oriented start time selection, indicated by b2,i=1, seems to be appropriate for the resource overload problem with tardiness penalty. This is especially the case with medium-sized instances. To test the usefulness of opposition-based learning and mutation probability adjustment, we conduct runs with 50 and 100 activities where we excluded the learning methods. The results show that for all four runs the gap is at least 0.9% higher without them, with the difference being greater for instance sets with 100 activities, being as high as 3.4%. With additional runs, we observed that the benefit of adapting mutation probabilities is far greater than the impact of opposition-based learning. We regard this as reasonable, since the latter affects only one generation. 6.2.2 Variable delay cost In Table 3, the results of the experiments of the resource overload problem with variable delay cost factors parametrized with γ=0.1, α=1.25 and β∈{1.0,1.1}are provided. Generally, the results shown are similar to the previous ones with a constant delay cost factor. Regarding small instances, the genetic algorithm terminates early for the same instances and the same β as before. As the number of activities increases, the superiority of genetic algorithm is evident again. Regarding the test set with 100 activities and β=1.1, the genetic algorithm obtains a better result than CPLEX for each of the 90 instances. For a tighter prescribed project makespan (β=1.0), the genetic algorithm yields a better solution for 80 instances within 300s. As expected, the average search space is larger than for the test sets with a constant delay cost factor. However, increasing βfrom 1.0 to 1.1 results in a reduction of the number of project durations, which additionally need to be considered in the genetic algorithm. This search space reduction is also evident from ∅ss. The lowest average binary value for the best solution of the instances here is 33%, obtained for an instance with n=10 and β=1.1. Increasing the number of activities, leads also to an increase of the lowest average binary value found in the best solutions in both test sets up to 0.57. To us, this once again underlines the effectiveness of the two start time selection rules considered. 123 170 Annals of Operations Research (2024) 338:151–172 Table 3 Resource overload problem with a variable delay cost factor with α=1.25 Instances CPLEX Genetic algorithm αβγn#opt ∅gap ∅topt[s]∅gapr∅tga[s]∅ss 1.25 1.0 0.1 10 90 0 1.36 0.34 0.60 27.21 20 82 0.98 155.70 0.67 30.00 23.42 50 0 43.57 −− −6.18 300.02 21.79 100 0 59.49 −− −13.54 300.12 21.65 1.25 1.1 0.1 10 90 0 0.85 0.16 0.81 26.68 20 80 0.98 93.88 0.80 29.01 22.23 50 0 39.42 −− −6.20 300.02 21.62 100 0 62.76 −− −28.75 300.13 18.94 Table 4 Resource overload problem with a constant delay cost factor with α=1.5 Instances CPLEX Genetic algorithm αβγn#opt ∅gap ∅topt[s]∅gapr∅tga[s]∅ss 1.5 1.2 0.1 10 90 0 3.13 0.46 0.46 17.57 20 63 2.57 349.73 1.09 26.03 14.93 50 0 34.52 −− −11.34 300.02 15.57 100 0 59.36 −− −32.82 300.14 12.62 6.2.3 Constant delay cost with a longer time horizon We test the robustness of the solution approaches by increasing α:= 1.5 for instances with a constant delay cost factor (Table 4). We assume that with a longer planning horizon, the prescribed project makespan already allows more float. Therefore, we choose β:= 1.2. To maintain a scattering of optimal project durations, γis reduced to 0.1. With the increased planning horizon, both approaches deteriorate on instances with 10 and 20 activities, with CPLEX being more affected especially regarding the number of optimal solutions found and its optimality proven as well as ∅topt .Forn=10, the genetic algorithm terminates 16 times due to reaching the calculated lower bound, which explains the lowest average run time for n=10 over all experiments. For n=20, the genetic algorithm terminates 9 times early. The respective instances for both numbers of activities have again a project duration equal or less than T. Across all experiments, the best average relative gaps (∅gapr) are obtained for problem instances with 50 and 100 activities. Since the number of start times considered in the genetic algorithm depend primarily on the number of other activities and not on the planning horizon in contrast to the mathematical model formulation, this performance improvement seems reasonable to us. In addition, for 83 instances containing 100 real activities the calculated lower bound is better that the one provided by CPLEX. If this lower bound is considered, the average gap for the genetic algorithm is 40.46% and thus nearly 20% lower than the average gap of CPLEX. 123 Annals of Operations Research (2024) 338:151–172 171 7 Conclusion In this paper, we have shown that the set of quasistable schedules can be adapted to reduce the search space for the resource overload problem with tardiness penalty. Besides a mixedinteger linear model, we present a genetic algorithm with a decoding procedure that ensures that only solutions within the reduced search space are examined. The experiments show that small instances are solved efficiently by CPLEX. Our genetic algorithm performs similarly well as the solver on these instances, however on average it is slightly faster. On the majority of the medium sized instances, the devised genetic algorithm outperforms the mixed-integer linear models implemented in CPLEX. An area of future research could be the development of an exact algorithm for the resource overload problem with tardiness penalty. To further enable a trade-off between resource levelling and the project makespan, a multi-mode resource overload problem with tardiness penalty can be investigated. Of particular interest are activity execution modes that lead to different processing times (We˛glarz et al., 2011). Both constant resource utilizations for each execution mode and varying execution intensities in terms of a workload perspective can be considered (Bianco et al., 2016; Tarasov et al., 2021). Future research could address, to what extent the search space can be reduced for these extensions and which prerequisites that have to be satisfied for that. Funding Open Access funding enabled and organized by Projekt DEAL. No funding was received to assist with the preparation of this article Declarations Conflicts 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 Abbasi Iranagh, M. (2015). Development of high performance heuristic and meta-heuristic methods for resource optimization of large scale construction projects. Ph.D. thesis, Middle East Technical University. Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows. Prentice Hall. Atan, T., & Eren, E. (2018). Optimal project duration for resource leveling. European Journal of Operational Research, 266(2), 508–520. Ballestin, F., Schwindt, C., & Zimmermann, J. (2007). Resource leveling in make-to-order production: Modeling and heuristic solution method. International Journal of Operations Research, 4(1), 50–62. Bianco, L., Caramia, M., & Giordani, S. (2016). Resource levelling in project scheduling with generalized precedence relationships and variable execution intensities. OR Spectrum, 38, 405–425. Gerhards, P., & Stürck, C. (2018). A hybrid metaheuristic for the multi-mode resource investment problem with tardiness penalty. In A. Fink, A. Fügenschuh, & M. J. Geiger (Eds.), Operations Research Proceedings 2016 (pp. 515–520). Cham: Springer. 123 172 Annals of Operations Research (2024) 338:151–172 Hartmann, S., & Briskorn, D. (2022). An updated survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 297(1), 1–14. Hegazy, T. (1999). Optimization of resource allocation and leveling using genetic algorithms. Journal of Construction Engineering and Management, 125(3), 167–175. Kim, J., Kim, K., Jee, N., & Yoon, Y. (2005). Enhanced resource leveling technique for project scheduling. Journal of Asian Architecture and Building Engineering, 4(2), 461–466. Kolisch, R., & Hartmann, S. (1999). Heuristic algorithms for the resource-constrained project scheduling problem: Classification and computational analysis. In J. Wéglarz (Ed.), Project scheduling (pp. 147– 178). Kluwer. Koulinas, G. K., & Anagnostopoulos, K. P. (2012). Construction resource allocation and leveling using a threshold accepting-based hyperheuristic algorithm. Journal of Construction Engineering and Management, 138(7), 854–863. Kreter, S., Rieck, J., & Zimmermann, J. (2014). The total adjustment cost problem: Applications, models, and solution algorithms. Journal of Scheduling, 17(2), 145–160. Neumann, K., Schwindt, C., & Zimmermann, J. (2003). Project scheduling with time windows and scarce resources (2nd ed.). Springer. Neumann, K., & Zimmermann, J. (1999). Resource levelling for projects with schedule-dependent time windows. European Journal of Operational Research, 117(3), 591–605. Ponz-Tienda, J. L., Yepes, V., Pellicer, E., & Moreno-Flores, J. (2013). The resource leveling problem with multiple resources using an adaptive genetic algorithm. Automation in Construction, 29(2), 161–172. Pritsker, A. A. B., Waiters, L. J., & Wolfe, P. M. (1969). Multiproject scheduling with limited resources: A zero-one programming approach. Management Science, 16(1), 93–108. Rahnamayan, S., Tizhoosh, H. R., & Salama, M. M. A. (2008). Opposition-based differential evolution. IEEE Transactions on Evolutionary computation, 12(1), 64–79. Rieck, J., & Zimmermann, J. (2015). Exact methods for resource leveling problems, In C. Schwindt & J. Zimmermann (Eds.), Handbook on Project Management and Scheduling (Vol. 4, pp. 361–387). Springer. Rieck, J., Zimmermann, J., & Gather, T. (2012). Mixed-integer linear programming for resource leveling problems. European Journal of Operational Research, 221(1), 27–37. Schnabel, A., Kellenbrink, C., & Helber, S. (2018). Profit-oriented scheduling of resource-constrained projects with flexible capacity constraints. Business Research, 11(2), 329–356. Schwindt, C. (1998). Generation of resource-constrained project scheduling problems subject to temporal constraints. Technical Report WIOR-543, Institute for Economic Theory and Operations Research, University Karlsruhe. Shadrokh, S., & Kianfar, F. (2007). A genetic algorithm for resource investment project scheduling problem, tardiness permitted with penalty. European Journal of Operational Research, 181(1), 86–101. Tarasov, I., Hait, A., & Battaia, O. (2021). Benders decomposition for a period-aggregated resource leveling problem with variable job duration. Computers & Operations Research, 132, 105258. We˛glarz, J., Józefowska, J., Mika, M., & Waligóra, G. (2011). Project scheduling with finite or infinite number of activity processing modes-a survey. European Journal of Operational Research, 208(3), 177–205. Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 123