1 Introduction

The Resource Leveling Problem (RLP) is stated as follows. There is a set of jobs that must be implemented under a strict deadline. There are precedence relations between the jobs in a form of an oriented and acyclic precedence graph. A set of renewable resources is available for the project realization. Each resource is defined by a set of parameters such as available amount and price. Each job requires the utilization of a specified amount of renewable resources, which, in a general case, may involve several resources of different types.

Under the constraint of the project deadline, the objective functions used in the RLP formulations are resource-oriented. These objective functions aim to optimize the resource usage for completing the project in time (Rieck & Zimmermann, 2015). They include managing total overloads over the given limit of available resources, tracking fluctuations in the utilized amount of resources through time periods, and calculating the total aggregated cost of resource usage. These general formulations of the RLP were proved to be NP-hard by Neumann et al. (2002). In this paper, we consider the objective of the minimization of extra resource costs. This problem arises when it is not possible to complete the project in time with a given available amount of resources. Therefore, additional resources have to be deployed during certain periods. In addition, we relax the classic hypothesis of the RLP that each job has a fixed duration. In our formulation, the duration of each job depends on the amount of resources allocated to it. With more resources allocated, it is possible to finish the job faster and thus reduce the total duration of the project. The obtained problem formulation is referred to as the Generalized Resource Leveling Problem, or the GRLP.

Managing a fixed deadline and the associated resources to meet it is challenging in practice, primarily due to data uncertainty and reliability issues. In the literature, various approaches have been developed to tackle data uncertainty, including: (i) representing uncertain data as random variables using probability theory, (ii) creating robust solutions for different scenarios, (iii) employing reactive re-optimization as data modifications are observed, and (iv) conducting sensitivity analysis to estimate thresholds for data modifications that won’t compromise solution feasibility.

Reactive methods and sensitivity analysis techniques have been relatively poorly developed both for project planning in general and particularly for the RLP class (Hazir & Ulusoy, 2020). To help practitioners to manage unexpected changes in the input data for the RLP, this paper proposes a novel approach based on metric estimation which can aid in managing input data fluctuations during project execution and in evaluating the need for rescheduling.

Metric approach that has been originally developed for machine scheduling problems (Lazarev, 2009). These NP-hard scheduling problems have known polynomially solvable instances. The solutions that can be rapidly found for these polynomially solvable instances can serve as a basis for finding a solution for NP-hard problem instances. Metric estimation is employed to evaluate the theoretical deviation of the obtained objective function from its lower bound.

For the RLP, because of the existence of precedence constraints, it is not possible to rely on the polynomially solvable cases. Therefore, we develop a different scheme for comparison of 2 problem instances: the initial one and modified one. The developed methods assist in verifying whether the solution found for the initial problem instance will remain optimal or feasible for the modified problem instance. With the use of these methods, the need for rescheduling can be rapidly evaluated. The rest of the paper is organized as follows. In the next Sect. 2, we provide a brief literature review on anterior studies on resource leveling problems, on uncertainty management in project scheduling, and on the metric approach. In Sect. 3, we present the mathematical formulation of the considered version of the GRLP. Further, in Sect. 4, we develop a set of metric estimations for the GRLP model and study their performances. We discuss the results of numerical experiments in Sect. 5 and conclude this study in Sect. 6.

2 Literature review

The objective of this section is to demonstrate the existing gap in the literature related to the management of uncertainty in the RLP.

Several recent surveys of variants and extensions of the Resource-Constrained Project Scheduling Problem (RCPSP) dedicated a special section to the RLP. They discussed the difference in objective functions and constraints (Hartmann & Briskorn, 2022; Sánchez et al., 2022).

In our study, we consider a generalized formulation of the RLP, initially introduced in Artigues et al. (2013) then developed by Bianco et al. (2016) and Baydoun et al. (2016). In this generalized formulation, each job does not have a fixed duration but can be performed faster or longer depending on the amount of resources available for its execution. Thus, the duration of a job is not a parameter, but a decision variable of the corresponding optimization model. For example, heating process was used as an application of the RLP model in the paper of Artigues et al. (2013). Each heating operation requires a certain amount of energy that can be supplied with more or less power, and thus, can be completed in respectively less or more time.

In comparison to the formulation of Artigues et al. (2013), we propose and use a different mathematical model. If a job requires a set of resources of different types, the resources of each type can be applied with individually defined intensity. It means that for each period of time, the intensity of each resource can be adapted to its availability independently of the availability of other resources. This flexible resource management allows for achieving solutions of a better quality i.e. lower associated overload costs. We proved this fact in our previous work (Tarasov et al., 2019) by directly comparing the baseline problem formulation and a variant with flexible resource management on a set of RLP benchmarks. Although our formulation requires more decision variables and constraints, it can provide efficient solutions in terms of the total cost due to the developed solution methods (Tarasov et al., 2021). It was also shown for another objective function, resource usage fluctuations, by Kazemi and Davari-Ardakani (2020). To the best of our knowledge, none of the existing models for the RLP with flexible job duration addresses the issue of uncertainty, and in particular of the uncertainty of the availability of the resources. Below we discuss how this issue has been dealt with in classic formulations of the RLP.

Data uncertainty stands as a critical concern in project planning. Existing literature distinguishes proactive, reactive, and proactive-reactive approaches to address this issue. Proactive methodologies, primarily stochastic and robust optimization, aim to anticipate data variations. Reactive approaches, often employing heuristics, strive to promptly respond to effective changes. Proactive-reactive approaches formulate a comprehensive plan with some foresight while also incorporating reactive methods to adjust the anticipated plan based on observed data changes. In Table 1, we compare studies sharing the most common features with our work. Regarding the methods, GA denotes Genetic Algorithm, and PERT refers to the Project Evaluation and Review Technique.

Table 1 Addressing the uncertainty issue in project scheduling (PS) and the RLP
Full size table

Dunham (2015) studied the robustness of solutions provided with a genetic algorithm (GA). Li and Demeulemeester (2016) considered the uncertainty of job duration as well as of time lags between the jobs. They developed a genetic algorithm for a robust version of the RLP. Li et al. (2020) extended the consideration of uncertainties to job overlaps and resource availability. They developed a Markov decision process and an approximate dynamic programming algorithm. Li et al. (2015) presented two scheduling policies for the stochastic RLP with uncertain job times. The first one was used to solve a deterministic equivalent of the stochastic problem, and the second one applied a tabu search directly to the stochastic formulation. Ke and Zhao (2017) also studied uncertain job times and proposed a heuristic approach. Li et al. (2023) addressed the RLP with a flexible precedence graph.

As it can be seen, the literature lacks of direct application of reactive scheduling and sensitivity analysis for the RLP. Moreover, all cited robust and stochastic approaches were developed for the original version of the RLP where the job durations are static input parameter. In contrast, our model (marked as the GRLP) represents the generalized problem with flexible job durations. Our contribution aims to close this gap with the development of metric evaluation. Its concepts are discussed here below.

The metric approach was first presented by Lazarev (2009) as an approximation scheme that builds suboptimal schedules with guaranteed estimated accuracy in a polynomial time for a problem that is NP-hard in general but has some polynomially solvable cases. The metric approach has been applied to the single-machine scheduling problem (Lazarev & Kvaratskheliya, 2010), to the total tardiness minimization problem (Lazarev et al., 2017), to the problem of two parallel machines with precedence delays (Bukueva et al., 2022), and to the problem of lateness minimization for scheduling on M parallel machines (Lazarev et al., 2021) as well as to the single-track railway scheduling problem with a maximum lateness objective (Cheng et al., 2022).

The authors of the metric approach have already noted that it is not suitable for classical project management problems due to the impossibility of building metrics for strict resource requirements and precedence constraints. Nevertheless, the method is partially applicable with flexible job durations, where the form of resource requirements is different. In this paper, we explore this direction and evaluate the applicability of the developed approach.

To summarize the literature review, two important research gaps can be observed. The issue of unexpected changes in input parameters during project execution is under-investigated for RLP in general and in particular for the generalized RLP (GRLP) formulation with flexible job duration. To fill this research gap, we develop a novel approach that can be applied when unexpected changes in input parameters are observed during the project execution. The use of this approach can also help to determine if a rescheduling is needed when unforeseen events modify the availability of resources.

In the next section, we present the GRLP model formulation.

3 The generalized RLP: formulation and definitions

3.1 Mathematical model

We provide a formal description of the MILP model for the considered type of the generalized RLP that has been initially introduced in Tarasov et al. (2019). A decomposition approach for this model was discussed in Tarasov et al. (2021). The contribution of the current paper is in the development of metric estimation approach for this formulation. In Table 2, we provide all the model parameters and notations needed for the presentation of the problem.

Table 2 Instance parameters
Full size table

The planning horizon consists of m periods each having the length of d. There is a set R of resource types. Each resource type r has a given extra resource price \(e_r\) and an available resource amount \(L_{rt}\) for each period t. There is a set of jobs J. Each job requires work volume \(W_{jr}\) from resource type r. In Table 3, we present all decision variables.

Table 3 Model parameters and decision variables
Full size table

Decision variable \(c_{jrt}\) defines the amount of resource \(r\in R\) used for job \(j\in J\) in period t:

$$\begin{aligned} \sum \limits _{t\in T} c_{jrt} = W_{jr},\;\forall j\in J,\;\forall r\in R. \end{aligned}$$
(1)

Duration \(d_{jt}\) of job \(j\in J\) in period \(t\in T\) is also a decision variable, its value is situated between two limits defined by parameters \(p_{min,jr}\) and \(p_{max,jr}\):

$$\begin{aligned} p_{min,jr}d_{jt}\le c_{jrt} \le p_{max,jr}d_{jt},\;\forall j\in J,\;\forall r\in R,\;\forall t\in T. \end{aligned}$$
(2)

The considered objective function aims to minimize the total cost of extra resources required to finish the project in time. Decision variable \(o_{rt}\) defines the amount of extra resource usage for resource \(r\in R\) in period \(t\in T\):

$$\begin{aligned} Minimize\;\sum \limits _{r\in R}\sum \limits _{t\in T} e_r o_{rt} \end{aligned}$$
(3)

where

$$\begin{aligned} o_{rt} \ge \sum \limits _{j\in J} c_{jrt} - L_{rt}, \;\forall t\in T,\;\forall r\in R. \end{aligned}$$
(4)

Binary variables \(S_{jt}\) and \(E_{jt}\) define the start and the end period of job j:

  • if job j starts at period t, then \(\forall t_1 < t\) \(S_{jt_1}=0\) and \(\forall t_2\ge t\) \(S_{jt_2}=1\);

  • if job j ends at period t, then \(\forall t_1 \le t\) \(E_{jt}=0\) and \(\forall t_2 > t\) \(E_{jt}=1\);

$$\begin{aligned} S_{jt} \ge E_{jt};\; S_{jt} \le S_{j,t+1};\; E_{jt} \le E_{j,t+1};\;\forall j\in J,\;\forall t\in T. \end{aligned}$$
(5)

Binary variables \(S_{jt}\) and \(E_{jt}\) are connected to continuous variables \(d_{jt}\in [0,d]\) as follows:

$$\begin{aligned} d_{jt} \le d \; (S_{jt} - E_{jt}),\;\forall j\in J,\;\forall t\in T. \end{aligned}$$
(6)

If job \(j\in J\) is not implemented in period \(t\in T\), then \(d_{jt}=0\). To avoid preemption, \(d_{jt} = d\) in any period \(t\in T\) after the first and before the last period where job \(j\in J\) is implemented:

$$\begin{aligned} d_{jt} \ge d \; (S_{jt} + S_{j,t-1} -1 - E_{jt} - E_{j,t+1}),\;\forall j\in J,\;\forall t\in T. \end{aligned}$$
(7)

Precedence constraints between jobs \((j_1,j_2)\):

$$\begin{aligned} S_{j_2t} \le E_{j_1,t+1},\;\forall t\in T,\;\forall (j_1,j_2)\in P. \end{aligned}$$
(8)

Additional constraint to manage the situations where two jobs related by a precedence constraint start or end in the same period:

$$\begin{aligned} d_{j_1t} + d_{j_2t} \le d,\;\forall t\in T,\;\forall (j_1,j_2)\in P. \end{aligned}$$
(9)

3.2 The criteria of instance solvability and solution applicability

This subsection introduces the essential definitions for our metric-based approach.

Definition 1

Instance I can be entirely described by the following set of parameters,

$$\begin{aligned} I = \{d^I,L_{rt}^I,e_r^I,W_{jr}^I,p_{min,jr}^I,p_{max,jr}^I,(i,j)_p^I;\;t\in T,\;r\in R,\;j\in J,\;p\in P\}. \end{aligned}$$
(10)

In total, I is defined by N parameters (see Table 2), where

$$\begin{aligned} N=1+|R|(|T|+1+3|J|)+|P|. \end{aligned}$$
(11)

In a general case, |P| is bounded by \(\frac{|J|(|J|-1)}{2}\).

Here, we used the upper index I for emphasizing the fact that all parameters belong to instance I. Here below if there is no need to emphasize the reference to the instance name, the upper index representing it is not used.

Definition 2

Instance I is solvable if:

  • the limits of all assigned resources are defined correctly for all jobs,

    $$\begin{aligned} p_{min,jr} \le p_{max,jr},\;\forall j\in J,\;\forall r\in R; \end{aligned}$$
    (12)

  • the chain of jobs with the longest total minimal required duration in the precedence graph is less than the total duration of the planning horizon,

  • for every job \(j\in J\) the minimal duration \(d_{min,j}=\max \limits _{r\in R} \frac{W_{jr}}{p_{max,jr}}\) is less than or equal to the maximal duration \(d_{max,j}=\min \limits _{r\in R} \frac{W_{jr}}{p_{min,jr}}\),

    $$\begin{aligned} d_{min,j} \le d_{max,j}, \;\forall j\in J. \end{aligned}$$
    (13)

We introduce the notion of “schedule” representing a partially defined solution to a problem instance.

Definition 3

Solution \(\sigma \) is defined by the following decision variable values:

$$\begin{aligned} \sigma = \{d_{jt},c_{jrt};\;t\in T,\;r\in R,\;j\in J\} \end{aligned}$$
(14)

The value of other decision variables can be calculated based on solution \(\sigma \).

Definition 4

Schedule \(\pi \) is defined by the following decision variable values

$$\begin{aligned} \pi = \{d_{jt};\;t\in T,\;j\in J\} \end{aligned}$$
(15)

Definition 5

Schedule \(\pi \) is applicable to instance I, if:

  • instance I is solvable;

  • schedule \(\pi \) is feasible for instance I, i.e. \(\sum \limits _{T} d_{jt} \in [d_{min,j},d_{max,j}],\;j\in J\);

  • schedule \(\pi \) satisfies all the precedence relations, i.e. if \(d_{j_2t}\ge 0\), then \(\sum \nolimits _{k=t}^{|T|} d_{j_1k} = 0\) for all \((j_1,j_2)\in P\), \(t\in T\).

Definition 6

Solution \(\sigma \) is applicable to instance I, if:

  • the scheduling part of \(\sigma \) is applicable to I;

  • the following inequalities are correct

    $$\begin{aligned}{} & {} d_{jt}p_{min,jr} \le c_{jrt} \le d_{jt}p_{max,jr},\;j\in J,\;r\in R,\;t\in T; \end{aligned}$$
    (16)
    $$\begin{aligned}{} & {} \sum \limits _{t\in T} c_{jrt} = W_{jr},\;j\in J,\;r\in R. \end{aligned}$$
    (17)

We use the following definition and notations for a more compact explanation of the metric approach.

Definition 7

The LP part of the RLP model is defined as a submodel \(PS(\bar{d_{jt}})\) with

  • a set of decision variables \(c_{jrt}\), \(o_{rt}\);

  • all the constraints related to these variables, see equations (1), (2), (4);

  • the initial objective function 3.

Submodel \(PS(\bar{d_{jt}})\) defines the resource allocation or solution \(\sigma \) for the fixed scheduling part defined by \(\bar{d_{jt}}\) (schedule \(\pi \)).

In our metric approach, the following notations are used:

  • for a schedule \(\pi \) or a solution \(\sigma \) a superscript index A means that this solution/schedule is optimal for instance A;

  • for all estimations a superscript index \(\sigma \) or \(\pi \) means an estimation for a solution or a schedule (for example, \(\rho _e^\sigma (A,B)\) or \(\rho _e^\pi (A,B)\));

  • \(\sigma ^A(\pi )\) is an optimal resource allocation found for schedule \(\pi \) obtained for instance A.

  • \(V^A(\sigma )\) provides the value of the objective function for solution \(\sigma \) for instance A, and \(V^A(\sigma ^A(\pi ))\) provides the value of the objective function for solution \(\sigma \) obtained from schedule \(\pi \).

4 Metric approach for the GRLP

Let us consider two similar RLP instances A and B with an identical number of parameters and identical precedence constraints but different in values of some parameters. The parameters that may differ for A and B are:

  1. 1.

    \(e_r\) – extra cost of resource \(r\in R\);

  2. 2.

    \(L_{rt}\) – availability of resource \(r\in R\) in period \(t\in T\);

  3. 3.

    \(p_{min,jr}\) or/and \(p_{max,jr}\) – job \(j\in J\) minimal/maximal requirement per period in resource \(r\in R\);

  4. 4.

    \(W_{jr}\) – job \(j\in J\) work volume with resource \(r\in R\).

Here below, we consider Cases 1–4. The proofs for the Lemmas and Theorem are included in “Appendix A” for convenience.

4.1 Case 1: Difference in extra resource costs \(e_{r}\)

Lemma 1

Let instances A and B differ only in parameters \(e_{r}\). If we apply the same solution \(\sigma \) to both instances, the upper bound for the difference between the values of the objective function for A and B defined as \(\rho _e^\sigma (A,B)\) can be calculated as follows:

$$\begin{aligned} \rho _e^\sigma (A,B) = \max \left\{ \sum \limits _{r\in R} min\{e_r^A - e_r^B, 0\}\sum \limits _{j\in J} W_{jr},\sum \limits _{r\in R} max\{e_r^A - e_r^B, 0\} \sum \limits _{j\in J} W_{jr}\right\} \qquad \end{aligned}$$
(18)

Now let us consider the situation where we know \(\sigma ^A\), the optimal solution for instance A, but the optimal solution for instance B is unknown.

Lemma 2

Let instances A and B differ only in parameters \(e_{r}\). If we apply \(\sigma ^A\) to instance B, then the upper bound on the difference between the value of the objective function for the unknown optimal solution for instance B and the value of the objective function obtained with solution \(\sigma ^A\) applied to instance B can be calculated as follows:

$$\begin{aligned} \Delta _e^\sigma (A,B) = \sum \limits _{r\in R} |e_r^A - e_r^B| \sum \limits _{j\in J} W_{jr}. \end{aligned}$$
(19)

Consequently, the decision-makers can estimate the eventual loss in the solution quality and decide if it is worth spending time searching for the optimal solution for instance B.

4.2 Case 2: Difference in available resource levels \(L_{rt}\)

It is important to note that in contrast to the classic Resource Constrained Project Scheduling Problem (RCPSP), for the RLP, \(L_{rt}\) has no impact on the solution feasibility since missing resources can be acquired at additional cost.

Lemma 3

Let instances A and B differ only in parameters \(L_{rt}\). If we apply the same solution \(\sigma \) to the both instances, \(\rho _L^\sigma (A,B)\) can be evaluated as follows:

$$\begin{aligned} \rho _L^\sigma (A,B)= \max \left\{ \sum \limits _{r\in R} e_r \sum \limits _{t\in T} max\left\{ L^B_{rt} - L^A_{rt},0\right\} ,\sum \limits _{r\in R} e_r \sum \limits _{t\in T} min\left\{ L^B_{rt} - L^A_{rt},0\right\} \right\} \qquad \end{aligned}$$
(20)

We can note that this estimation does not depend on solution \(\sigma \) but only on the parameters of both instances.

Now let us consider the situation where we know \(\sigma ^A\), the optimal solution for instance A, but the optimal solution for instance B is unknown.

Lemma 4

Let instances A and B differ only in parameters \(L_{rt}\). If we apply \(\sigma ^A\) to instance B, then the upper bound on the difference between the value of the objective function for the unknown optimal solution for instance B and the value of the objective function obtained with solution \(\sigma ^A\) applied to instance B can be calculated as follows:

$$\begin{aligned} \Delta _L^\sigma (A,B) = \sum \limits _{r\in R} e_r \sum \limits _{t\in T} |L^A_{rt} - L^B_{rt}| \end{aligned}$$
(21)

4.3 Case 3: Difference in the job-related parameters \(p_{min,jr}\) or \(p_{max,jr}\)

In this case, it is necessary to check if a particular solution (or a schedule) is applicable to a particular instance A or B (see Definitions 5 and 6).

Lemma 5

Let instances A and B differ only in parameters \(p_{min,jr}\) or (and) \(p_{max,jr}\). If solution \(\sigma \) is applicable to both instances, there is no change for the objective function value, i.e.

$$\begin{aligned} \rho _{p_{min/max}}(A,B) = 0. \end{aligned}$$

This also stands for the optimal solutions for instances A and B.

Lemma 6

Let instances A and B differ only in parameters \(p_{max,jr}\) and/or \(p_{min,jr}\). Suppose that an optimal solution \(\sigma ^A\) of instance A is applicable to instance B and an optimal solution \(\sigma ^B\) of instance B is applicable to instance A. If we apply an optimal solution of instance A i.e. \(\sigma ^A\) as a solution to instance B, then we obtain the same value of the objective function.

$$\begin{aligned} \Delta ^{\sigma }_{a,p_{min/max}}(A,B) = V^B(\sigma ^A) - V^B(\sigma ^B) = 0 \end{aligned}$$
(22)

Now, let us consider the situation with schedules for instances A and B.

Lemma 7

Let instances A and B differ only in parameters \(p_{max,jr}\) (or \(p_{min,jr}\)). If schedule \(\pi \) is applicable to both instances, the upper bound on the difference between the values of the objective function for A and B, defined as \(\rho _{p_{max}}^\pi (A,B)\), can be calculated as follows:

$$\begin{aligned} \begin{aligned}&\rho _{p_{max}}^\pi (A,B) = md \max \{\sum \limits _{r\in R} e_r \sum \limits _{j\in J} \min \{p_{max,jr}^A - p_{max,jr}^B,0\}, \\&\sum \limits _{r\in R} e_r \sum \limits _{j\in J} \max \{p_{max,jr}^A - p_{max,jr}^B,0\}\} \end{aligned} \end{aligned}$$
(23)

Lemma 8

Let instances A and B differ only in parameters \(p_{max,jr}\). Suppose that the optimal solution \(\sigma ^A\) of instance A is applicable to instance B and the optimal solution \(\sigma ^B\) of instance B is not applicable to instance A. If we apply the optimal solution of instance A, \(\sigma ^A\), as a solution to instance B, then the difference from the optimal value for B is bounded by the following expression:

$$\begin{aligned} \Delta ^{\sigma }_{n,p_{max}}(A,B) \le \sum \limits _{r\in R} e_r md \sum \limits _{j\in J} |p_{max,jr}^A - p_{max,jr}^B | \end{aligned}$$
(24)

The same expressions can be formed for the lower limit \(p_{min,jr}\).

4.4 Case 4: Difference in work volume \(W_{jr}\).

Let instances A and B differ only in values of \(W_{jr}\). It is impossible to apply the same solution \(\sigma \) (with the same values of \(c_{jrt}\)) to both instances, so the metric estimation is not applicable in the same form but can be derived for the scheduling part using a common schedule applicable to both instances (see Definition 5).

Lemma 9

Let instances A and B differ only in \(W_{jr}\). If we apply the same schedule \(\pi \) to both instances, the upper bound on the difference in values of the objective function for instances A and B can be estimated as follows:

$$\begin{aligned} \rho _W^\pi (A,B)= \max \left\{ \sum \limits _{r\in R} e_r \sum \limits _{j\in J} \max \left\{ W^A_{jr} - W^B_{jr},0\right\} ,\sum \limits _{r\in R} e_r \sum \limits _{j\in J} \min \left\{ W^A_{jr} - W^B_{jr},0\right\} \right\} \nonumber \\ \end{aligned}$$
(25)

With this schedule, an optimal resource allocation can be found for B in a polynomial time. Secondly, we construct an estimation for an optimal schedule for instance A applied to instance B.

Lemma 10

Let instances A and B differ only in parameters \(W_{jr}\). If we apply the optimal schedule \(\pi ^A\) of instance A to instance B, then the upper bound for the difference in the values of the objective function can be estimated as follows:

$$\begin{aligned} \Delta _W^\pi (A,B)= \sum \limits _{r\in R} e_r \sum \limits _{j\in J} |W^A_{jr} - W^B_{jr}|. \end{aligned}$$
(26)

4.5 Scalability of instances

Lemma 11

Suppose there are two instances A and B that differ in one of the parameters \(p_{min,jr}\), \(p_{max,jr}\) or \(W_{jr}\). Any schedule \(\pi \), applicable to instance A, is also applicable to instance B, if B is solvable and:

$$\begin{aligned} d_{min,j}^B \le d_{min,j}^A;\;d_{max,j}^A \le d_{max,j}^B;\;\forall j\in J, \end{aligned}$$
(27)

or it can be reformulated in a linear form for the parameters of B:

$$\begin{aligned} W_{jr}^B \le d_{min,j}^A p_{max,jr}^B;\; d_{max,j}^A p_{min,jr}^B \le W_{jr}^B;\;\forall j\in J;\;\forall r\in R. \end{aligned}$$
(28)

4.6 Summary of contributions

In Table 4, we summarise our findings presented in the previous subsections.

Table 4 The summary of all estimations
Full size table

It is also necessary to take into account that the fluctuations of some parameters may lead to the infeasibility of a solution or to the infeasibility of a schedule. Here below, Theorem 1 aggregates the estimations for two instances A and E, varying in any of the listed parameters.

Theorem 1

Suppose there are two instances A and E that differ by parameters \(L_{rt}\), \(W_{jr}\), \(p_{min,jr}\), and \(p_{max,jr}\). If we apply a schedule \(\pi ^A\) that is optimal for instance A to instance E, the upper bound for the difference in the values of the objective function can be estimated as follows:

$$\begin{aligned} \Delta ^\pi (A,E) =\Delta _L^\pi (A,E) + \Delta _{p_{min}}^\pi (A,E) + \Delta _{p_{max}}^\pi (A,E) + \Delta _{W}^\pi (A,E). \end{aligned}$$
(29)

Lemma 12

Suppose that instance B is produced from instance A by the following transformation: all job-resource-related parameters are multiplied by a coefficient \(k > 0\). We will define it as \(kA = B\) meaning that \( k L_{rt}^A = L_{rt}^B;\;\forall r \in R;\;\forall t \in T; \) and \( k p_{min,jr}^A = p_{min,jr}^B;\; k p_{max,jr}^A = p_{max,jr}^B;\; k W_{jr}^A = W_{jr}^B;\;\forall j\in J;\;\forall r\in R. \)

In this case, both instances A and B have the same set of feasible schedules and a set of optimal schedules with scaled solution variables

$$\begin{aligned} k c_{jrt}^A = c_{jrt}^B;\;\forall j\in J;\;\forall r\in R;\; k o_{rt}^A = o_{rt}^B;\;\forall r \in R;\;\forall t \in T. \end{aligned}$$
(30)

Thus, objective function values are also scaled:

$$\begin{aligned} V^B(\sigma ^B) = k V^A(\sigma ^A). \end{aligned}$$
(31)

We can use this scaling feature to improve the previous estimation. Let us consider instance A with a known (sub)optimal schedule \(\pi ^A\) (and a solution \(\sigma ^A\)). To estimate the impact of the application of \(\pi ^A\) (and \(\sigma ^A\)) to instance b, we calculate \(\Delta (A,B)\) with the following two stage-approach:

  1. 1.

    construct a scaled instance kA (\(k>0\)), \(\Delta (kA,B) \le \Delta (A,B)\);

  2. 2.

    apply \(\pi ^A = \pi ^{kA}\) to B.

We illustrate this scheme in Fig. 1. We consider two points A and B of \(\Omega \), the space of problem instances. A metric estimation \(\Delta (A,B)\) can be improved, if we can find an instance kA that is closer to B and have the same solution.

Fig. 1
figure 1

Representation of scaling case

Full size image

In Fig. 1, we mark two squares representing a set of instances with a fixed \(l_1\) metric, equal to a metric between A and B, and a metric between kA and B. We define a \(l_1\) norm \(||\cdot ||_1\) on space \(\Omega \) based on function \(\Delta (A,B)\):

$$\begin{aligned} ||A||=\sum \limits _{r\in R} e_r^A \left( \sum \limits _{t\in T} |L_{rt}^A| + md \sum \limits _{j\in J} \left( |p_{min,jr}^A| + |p_{max,jr}^A|\right) + \sum \limits _{j\in J} |W_{jr}^A| \right) . \end{aligned}$$

Norm axioms are verified for this formula:

$$\begin{aligned}{} & {} ||A|| = 0 \Longleftrightarrow A = 0;\\{} & {} ||kA|| = |k|\cdot ||A||;\\{} & {} ||A+B|| \le ||A|| + ||B||;\\{} & {} \Delta (A,B) = ||A-B||. \end{aligned}$$

To evaluate our metric approach, we perform numerical experiments in the next section.

5 Numerical experiments

5.1 Dataset description

For the classic RLP settings with fixed job duration, there are several known datasets, e.g. see Kolisch et al. (1999) or Rieck et al. (2012). These instances were generated with a tool ProGen/Max that constructs instances for project scheduling problems with minimal and maximal time lags between jobs (Schwindt, 1998). These instances involved 10–50 jobs in the project and 1–5 resources. However, these instances were built for the basic formulation with fixed job duration and they lack parameters related to flexible resource allocation, e.g. the total workload and lower/upper intensity per resource and per job. Hans (2001) and Baydoun et al. (2016) have also created a dataset for the Rough-Cut Capacity Planning (RCCP) problem. Similarly, they lack of such parameters such as lower limits or resource costs.

In order to create a diverse and representative dataset for our numerical experiment, we used the following parameters:

  1. 1.

    resource availability \(L_{rt}\);

  2. 2.

    job-resource linking parameters (\(W_{jr}\), \(p_{min,jr}\) and \(p_{max,jr}\));

  3. 3.

    precedence relations P.

The instances used in the numerical experiment were generated as follows:

  1. 1.

    construct a precedence graph P;

  2. 2.

    define lower and upper bounds \(W^L\) and \(W^U\) to generate random values for all \(W_{jr}\) in range \([W^L, W^U]\);

  3. 3.

    produce random values for \(p_{min,jr}\) and \(p_{max,jr}\) while keeping the solvability of the instance, i.e.

    • \(p_{min,jr}\le p_{max,jr}\);

    • \(d_{min,j} \ge d\);

    • resulting job duration bounds are synchronized \(d_{min,j}\le d_{max,j}\);

    • the longest path in graph |P| is inferior to the length of the planning horizon.

  4. 4.

    construct \(L_{rt}\) in range \([0, \frac{\sum \limits _{j\in J} p_{max,jr}d}{SP\cdot |J| + 1}]\);

Here we define an upper bound for \(L_{rt}\) in the following way: \(\sum \limits _{j\in J} p_{max,jr}d\) is a maximal total required amount for resource \(r\in R\) if we do not take into account precedence constraints.

Resource availability does not impact the feasibility of the problem instances, merely the value of the objective function. For job-resource linking parameters, we have determined the conditions of solvability (see Definition 2) and applicability (see Definitions 5 and 6). Precedence relations are important both in terms of feasibility and the quality of solutions. Basically, they are represented as a direct acyclic graph with jobs on nodes. To generate the various precedence relations, it is important to construct formally different direct acyclic graphs, but also vary a set of non-redundant arcs.

Our approach for the generation of precedence relations is based on the ProGen/max procedure (Kolisch et al., 1995; Schwindt, 1998). To create a diversified dataset, we varied the parameters used for the generation of the precedence graph: Order Strength (OS) and the ratio between sequential and parallel arcs (SP) (Coelho & Vanhoucke, 2020; Vanhoucke et al., 2016). To illustrate the variety of the generated instances, two different examples with 20 jobs and 19 precedence relations are shown in Fig. 2. Table 5 presents the summary of the parameters of the generated datasets.

Fig. 2
figure 2

Two examples of precedence graph with 20 jobs and 19 precedence relations

Full size image
Table 5 Parameters of datasets
Full size table

There are three datasets, having a different number of resources and jobs, with different precedence graph sizes and structures. Within our numerical experiment, we first evaluate the frequency of original schedule \(\pi ^A\) remaining applicable to instance B and remaining optimal. Secondly, we assess the accuracy of our upper bound on the difference of the values of the objective function for the optimal solution found for instance B, and the value obtained with the application of solution for instance A.

For each instance A, we find an optimal solution (or a suboptimal obtained with a time limit). Instances B are generated on the basis of datasets of instances A in Table 5 with some fluctuations in parameters \(W_{jr}\) and \(L_{rt}\) since in practice they are frequently affected by unexpected changes. The value of the magnitude of generated changes in instances B is measured with \(|\delta |\). Firstly, we vary workload \(W_{jr}\). With a fixed magnitude of changes \(|\delta | = 5.0\) (equal to 10% of \(W^U\)), we increase the number of changes from 1 to 30, that is the maximal value, as \(N_{max}=|J|\cdot |R| = 30\). For each group and each pair magnitude-quantity of changes, we test 200 different instances. We use the MILP model described in Sect. 3 and solver CPLEX 12.10 to solve all instances A and B for comparison. The LP subproblem (see Definition 7) is used to obtain an optimal solution \(\sigma ^B(\pi ^A)\) based on given schedule \(\pi ^A\). We measure the accuracy G(A, B) of our estimation with the following indicator:

$$\begin{aligned} G(A,B) = \frac{V^B(\sigma ^B(\pi ^A)) - V^B(\sigma ^B(\pi ^B))}{\Delta ^\pi (A,B)}. \end{aligned}$$
(32)

We note that \(G(A,B)=0\) when \(V^B(\sigma ^B(\pi ^A)) = V^B(\sigma ^B(\pi ^B))\), meaning that schedule \(\pi ^A\) remains optimal and provides an optimal solution for instance B in polynomial time. The obtained results are discussed in the following subsection.

5.2 Results

We start with dataset inst_j10_r3. The results are presented in Table 6. As we can observe, the accuracy is predictably decreasing with the amplitude of changes. A real value of the difference in the objective function is between 0.18 and 0.3 in our estimation. We note that the schedule is quite stable in terms of optimality for one change. For about 30–40% of instances, it is possible to reconstruct the solution for a modified instance with an existing schedule and keep it optimal. With variations in the given available resource amount \(L_{rt}\) values, we can make the same conclusion. A lot of variations of low magnitude gradually reduce the percentage of schedules remaining optimal, with a relative accuracy decreasing from 0.3 to 0.1.

We increase the number of jobs in the second dataset inst_j15_r3. The results are reported in Table 7. For this dataset, we also note that the schedule is more stable in the case of a single change. Finally, the results for the third dataset inst_j20_r5 are presented in Table 8. For this last dataset, we note that with an increased scale of instances, the mean relative accuracy has been increased.

Experimental results demonstrate that a schedule had significant stability in terms of optimality in many considered cases. The reallocation of resources within the same schedule works better for a single change, but it is also possible for some instances with multiple changes. The value of relative accuracy G(A, B) for the cases where the optimality has not been reached is gradually decreasing with a number and a magnitude of changes. As can be shown, the increase of the problem scale with additional jobs and resource types does not reduce the accuracy of the method, as a consequence, the method can be also applied to large-scale problem instances.

Table 6 Results for dataset group inst_j10_r3
Full size table
Table 7 Results for dataset inst_j15_r3
Full size table
Table 8 Results for dataset inst_j20_r5
Full size table

The realized tests provide important information for the decision-makers. First of all, it can be observed that the solution or schedule optimality can be kept for the modified problem instance in many cases, up to 60% of problem instances of a dataset. Therefore, with a simple check with the developed Lemmas, the decision makers can receive information about the stability of the existing solution even if the parameters of the problem instance change (e.g. some costs increase or decrease, or the availability of resources is modified). This is extremely important in practice, since all changes in the established schedule may bring unexpected consequences in terms of disruptions or quality problems, especially if they imply changes in the information communicated to the human operators that usually can decrease their performances in the situation of frequent changes.

The second important managerial insight is that the quality of the accuracy estimation does not decrease with the increase of the scale of the problem in terms of jobs or the number of resources. As a consequence, the proposed method remains applicable and even more useful for large-size projects where the exact resolution of a new problem instance can take considerable time.

6 Conclusions

Uncertainty management plays an important role in the efficient project scheduling. In this paper, we considered the generalized formulation of the resource leveling problem with flexible job duration under the uncertainty of input data. The analysis of the literature showed that neither reactive nor sensitivity analysis methods have been previously developed for this problem. In this paper, to fill this gap, we elaborated a new approach based on metric estimation of the impact of the fluctuations in the input parameters on the final solution and the objective function which minimized the total cost of extra resources required to finish the project in time.

The main idea behind this approach was to use a known solution of one instance to estimate the value of the objective function for another instance not solved yet on the basis of the analysis of the differences in the parameters between these two instances. We have demonstrated the applicability of our approach for the GRLP instances having the same dimension and same precedence constraints through an extended numerical experiment. The fluctuations in all resource-job parameters have been analyzed with this method in order to estimate their impact on the value of the objective function and on the applicability of the known solution for the scheduling part of the new problem and the resource allocation part. We have shown the conditions to be respected to conduct such an analysis and we have developed the estimation method for each type of input data fluctuations.

The obtained results showed that the developed approach could be used to apply the same baseline schedule for a large variety of instances and even to guarantee optimality in some cases. Due to our approach, it became possible to estimate for each fluctuation in input parameters, if the initially found solution remains feasible, optimal, or partially optimal (i.e. if the original schedule can be kept but the resource allocation should be recalculated). It became also possible due to our approach to estimate the gap in the value of the objective function for the cases where the known solution loses its optimality. These contributions form a basis for an efficient reactive re-optimization approach that can be completed in a consequent study.

There are also other perspectives for further research. In our study, we considered the precedence constraints unchangeable. In a general case, modifications in precedence constraints will imply important changes in the structure of feasible and optimal solutions, but it will be interesting to investigate the existence of particular cases with possibly a less significant impact. Also, the present study was dedicated to the RLP, but a similar approach can be developed for other problems belonging to the project scheduling class with flexible resource requirements and aggregated linear objective functions. However, an original RCPSP with strict resource limits seems to be very difficult for the application of a metric approach because of its high sensitivity to the changes in resource availability that make easily an instance unfeasible.