Evolutionary algorithms for multi-objective stochastic resource availability cost problem

Abstract

This paper investigates the resource availability cost problem in a PERT-type network, where both activities duration and resource requirement are considered as stochastic parameters. The problem has two objective functions in which the first one, namely the project’s makespan, is to minimize the project’s duration. However, the second one tries to minimize the total cost of resources. Since its NP-hardness is proven in a strong sense, four well-known evolutionary algorithms including strength pareto evolution algorithm II, non-dominated sorting genetic algorithm II, multi-objective particle swarm optimization, and pareto envelope-based selection algorithm II are proposed to solve the problem. Furthermore, to enhance the algorithms’ performance, some efficient mutation and crossover operators, as well as two novel operators called local search and movement, are employed to solution structure for producing new generations. Also, in order to tackle uncertainty, Monte-carlo simulation is utilized. In order to tune the effective parameters, the Taguchi method is used. The performance of our proposed algorithms is evaluated by numerical test problems in different size which generated based on PSPLIB benchmark problems. Finally, to assess the relative performance of the four proposed algorithms, six well-known performance criteria are employed. Using relative percentage deviation and TOPSIS approach, the performance of algorithms is elucidated.

1 Introduction

In the early 1960s, the project scheduling problem is decided by the schedule of allocating resources in order to optimize an objective function. Since Blazewicz et al. [6] proved that the NP-hardness of RCPSP, the problem has been widely studied. The decision variables for the RCPSP are the starting time of the activities while the objective is to minimize the completion time of the project. For a comprehensive survey on exact and heuristic procedures, which have been applied to solve the deterministic RCPSP refers to Icmeli et al. [26], Elmaghraby, [18], Herroelen et al. [24], Demeulemeester et al. [15] and Kolisch and Hartmann [32].

The resource availability cost problem (RACP) is an extended form of RCPSP, which introduced by Mohring as the resource investment problem [41]. solving the problem, he proposed an exact method. Besides, the author proved that the problem belongs to the NP-hard class of problems due to its complexity. The RACP consists of scheduling the activities subject to the total cost of the required resources is minimized. In RACP, both activities’ start time, and the resources’ capacity value are decision variables. Besides, precedence relations, as well as a fixed deadline, are imposed. It is also assumed that the resources (no matter if they are employed or not) are assigned to the project for the total project duration, and the unit cost of each resource is to be fixed independently of its period of availability.

Plenty of studies have been fulfilled in this topic. Rangaswamy [50] developed a branch-and-bound algorithm to solve the RACP. To validate the algorithms, he solved a set of problems introduced by Demeulemeester [14]. Drexl and Kimms [16] presented two lower-bound approaches for the RACP. Rodrigues and Yamashita [52] introduced an exact algorithm. To study about the heuristic and meta-heuristic methods in detail, which have been applied to solve RACP, refers to Yamashita et al. [63], Shadrokh and Kianfar [54], Ranjbar et al. [51], and Van Peteghem and Vanhoucke [61]. Nadjafi [44] defined a multi-mode RACP with recruitment and release dates for resources. To solve the problem, he proposed the simulated annealing algorithm. Finally, Arjmand and Najafi [1] proposed meta-heuristic algorithms to solve a multi-mode RACP in the determined environment.

Compare to the vast literature on deterministic project scheduling problems, there are minimal works considering uncertainty in the scheduling problems. Nonetheless, the complexity of the real project has forced scholars to consider uncertainty in the problem. A good example of which is vagueness in activity durations. Because of the ambiguity in activity durations, uncertainty exists in a project scheduling problem. Initially, Freeman [20] presented probability theory into project scheduling problem. A substantial issue in stochastic networks with non-deterministic activity duration is the total completion time of the project [23]. To deal with stochastic networks, authors employed different methods, i.e., Martin [40] applied series–parallel reductions to analyze PERT networks. Charnes et al. [7] presented a chance-constrained programming (CCT) approach to solve PERT-type problems. Fatemi Ghomi and Hashemin [19] generalized the Gaussian quadrature formula to compute F(T). Kulkarni and Adlakha [35] applied a continuous-time Markov process method to PERT-type networks considering exponentially distributed activity durations. Elmaghraby [17] calculated lower bounds for the expected project completion time. Besides, several authors have applied the Monte Carlo simulation (MCS) to estimate F(T) in PERT networks, e.g., Golenko-Ginzburg and Gonik [21] employed a heuristic method for the problem in which the duration of activities are random variables. Tsai and Gemmil [60] propose a tabu search that can be applied to the RCPSP whether it has stochastic or deterministic activity duration times. Möhring and Stork [42] presented linear preselective policies to minimize the makespan with non-deterministic activity durations. Stork [55] compares four different scheduling policies to minimize the makespan in stochastic RCPSP. Ke and Liu [28] employed a genetic algorithm to solve the RCPSP with stochastic activity durations. Baradaran and Fatemi-Ghomi [2] introduced a hybrid heuristic rule to solve the problem. Later on, they presented a hybrid algorithm based on scatter search [3]. Furthermore, they presented the multi-mode stochastic RCPSP in which each activity has several execution modes and solved it with the same method [4]. Mukherjee and Basu [43] developed a method for solving an internal PERT/CPM in AOA networks. This method involves tabular, which is more intelligible for both technical and non-technical persons. Yellapu and Penmestsa [64] presented a mathematical model for stochastic RACP where availability to resources is periodical and described by resource calendar. To solve the problem, they employed a heuristic algorithm. Goto [22] developed a max-plus-linear (MPL) representation to model and analyze discrete-event systems. Ning et al. [45] considered multi-mode cash flow balanced project scheduling problem with stochastic activity durations. To solve the problem, two meta-heuristic algorithms, namely Tabu Search (TA) and Simulated Annealing (SA) were developed. Their objective was to minimize the contractor’s maximal cumulative gap between cash outflows and cash inflows. Khalilzadeh et al. [27] presented a heuristic algorithm for project scheduling with fuzzy parameters. Chen et al. [8] studied the performance of 17 priority rule heuristics and the justification technique on stochastic project scheduling problems. The outcome proved that the best priority rules performed as well as best meta-heuristic when the variance of activity duration was medium and outperformed all algorithms when this variance was high. Finally, Creemers [12] studied preemptive stochastic project scheduling problem in which activity durations are exponentially distributed. The author developed a new Markov chain to find an optimal solution.

Another emerging research area in this field considers flexible networks for project scheduling problem, in which some of the activities of the project may not be implemented. Several authors did research considering various assumptions. Kellenbrink and Helber [29] presented RCPSP with the flexible project structure, in which the activities that must be scheduled are not totally known. They employed a genetic algorithm to solve the problem. Tao et al. [58] investigated a project scheduling problem with hierarchical alternative methods regarding uncertain activity durations. A meta-heuristic combining average sample approximation with an artificial algae algorithm is developed to solve the problem. Experimental results showed that the proposed method outperformed GA. Tao and Dong [57] considered resource constraint project scheduling problem with alternative activity chain inspired form project scheduling practices. They designed an AND-OR project network representation for the problem. To solve the problem, an extended simulated annealing algorithm was proposed. Later on, They extended their research considering multi-mode activities for the project [59]. They employed hybrid meta-heuristic algorithms to resolve the issue.

Resource unavailabilities in project scheduling problem is another term in this regard. Lambrechts et al. [36] defined uncertainty as stochastic resource availability. They presented two parameters to model resources’ breakdown: meantime of failure of resources, and mean time to repair resources. They aimed at generating a stable baseline schedule for the problem. Therefore, they presented a tabu search procedure operating on a surrogate, free slack-based objective function [37]. They continued their work on resource constraint project scheduling problem subject to resource unavailabilities [38]. In this paper, they determined the impact of unexpected resource breakdown on activity durations. Using this information, they developed an approach in order to insert exact idle time into the project schedule. Ma et al. [39] introduced the best surrogate measures for two types of disruptions in project scheduling, i.e., resource availability disruptions and activity duration disruptions. To deal with the above disruptions, they proposed a general framework of slack-based surrogate robustness measures.

More detailed about the differences and similarities between this paper and the mentioned paper regarding stochastic project scheduling can be found in Table 1.

Table 1 Differences and similarities between this paper and other related works

To the best of our knowledge, all papers concerning project scheduling problem with stochastic activity duration times just resolved problems concentrating on optimizing completion time under resource or cost limits. In addition, there is a few research in the field of RACP, considering both stochastic activity durations and resource requirements, simultaneously. To bridge the gap, in this paper, a resource availability cost problem with two types of uncertain environments, i.e., stochastic resource availabilities and stochastic activity durations, are taken into account. Furthermore, the problem is assumed with two objective functions; the first one, namely makespan, which minimizes the project completion time, and the second one tries to reduce the total resource cost. In order to deal with the uncertainty, we used Monte Carlo simulation (MCS). To solve the problem, four well-known meta-heuristic algorithms, namely SPEA-II, NSGA-II, PESA-II, and MOPSO, are employed. To evaluate the performance of the algorithms, a set of 90 problems are generated based on PSPLIB benchmark problems. Also, six performance criteria are applied to illustrate the algorithms’ performance.

The remainder of the paper is set out as follows. Section 2 is started with the problem formulation consisting of a mathematical model and notations. In Sect. 3, the solution approaches and meta-heuristic algorithms applied in the PERT-type network are defined. In Sect. 4, computational results are treated. Finally, in Sect. 5, the conclusion is explained.

2 Mathematical model descriptions

The resource availability cost problem (RACP) in a PERT-type network can be concerned with n activities j = 1, 2, …, n, in which Nodes 1 and n, initial and terminal nodes respectively, are considered to be dummies. Consequently, the start and end nodes have zero duration and zero resource consumption. Activities are represented on activity on node (AON) network. In addition, both activities durations d_j and resource requirements r_jk, in which k = 1, 2, …,ρ, are independent continuous random numbers with given distribution functions. The precedence relations of activities are assumed to be finished to start with zero time lags. Moreover, each activity j has a set of predecessor P_j and can be started when all of its predecessors are terminated. Each activity has one execution mode. Remark that each resource k has a fixed resource cost of C_k for each unit of available capacity. We have two objective functions. The first one is to schedule activities such that the completion time of the project is minimized; however, the second one is to minimize the total cost of the resource capacities considering precedence and resource constraints. According to the objective functions, the problem has two decision variables. Including x_jt and R_k. Let x_jt = 1, if activity j is finished at time t and 0 otherwise. Furthermore, activity j can be finished at a time between the earliest finish time $(EF_{j } )$ and latest finish time $(LF_{j} )$. The mathematical model is as follow:

$$Min Z_{1} = E\left[ {\mathop \sum \limits_{{t = EF_{n} }}^{T} t.x_{nt} } \right]$$

(1)

$$Min Z_{2} = E\left[ {\mathop \sum \limits_{k = 1}^{\rho } C_{k} . R_{k} } \right]$$

(2)

S.T.

$$\mathop \sum \limits_{t = 1}^{T} x_{jt} = 1;\quad j = 1, \ldots ,n,t = 1, \ldots ,T$$

(3)

$$\mathop \sum \limits_{{t = EF_{i} }}^{T} \left( {t + d_{i} } \right) \cdot x_{it} \le \mathop \sum \limits_{{t = EF_{j} }}^{T} t \cdot x_{jt} ;\quad j = 1, \ldots ,n,i \in p_{j}$$

(4)

$$\mathop \sum \limits_{j = 2}^{n - 1} r_{jk} \mathop \sum \limits_{q = t}^{{ t + d_{j} - 1}} x_{jq} \le R_{K} ;\quad k = 1, \ldots ,\rho ,t = 1, \ldots ,T$$

(5)

$$x_{jt} \in \left\{ {0,1} \right\};\quad j = 1, \ldots ,n,t = 1, \ldots ,T$$

(6)

$$R_{K} \ge 0;\quad K = 1, \ldots ,\rho$$

(7)

Where the decision variables are:

$$\begin{array}{*{20}l} {x_{jt} } \hfill & {\quad \left\{ {\begin{array}{*{20}l} 1 \hfill & {\quad {\text{if}}\,{\text{activity}}\,{\text{j}}\,{\text{is}}\,{\text{completed}}\,{\text{in}}\,{\text{time}}\,{\text{period}}\,{\text{t}}} \hfill \\ 0 \hfill & {\quad {\text{otherwise}}} \hfill \\ \end{array} } \right.} \hfill \\ {R_{K} } \hfill & {\quad {\text{The}}\,{\text{Resource}}\,{\text{level}}\,{\text{for}}\,{\text{a}}\,{\text{resource}}\,{\text{type}}} \hfill \\ \end{array}$$

The first objective function (1) represents the expected value of the project makespan. However, the second objective function (2) denotes the expected total cost of the resource capacities. Constraint (3) assures that each activity can only be finished in one time period. Constraints (4) and (5) illustrate the precedence and resource constraints, respectively. Finally, Constraints (6) and (7) determine that the decision variables are binary and positive integer variables, respectively.

3 Solution approaches

In this section, four well-known multi-objective algorithms, i.e., SPEA-II, PESA-II, NSGA-II, and MOPSO, which have been widely applied to many NP-hard problems, as well as employed operators are discussed in the ensuing sub-sections.

3.1 Common characteristics of algorithms

This section denotes common elements of our algorithms, including solution representation, generating a feasible solution, and applying our algorithms to the PERT network.

3.1.1 Solution representation

Designing a convenient solution representation is one of the key factors of the process of solving any problem. Also, for each solution in the original space, there is a unique solution in the encoded space and each encoded solution pertains to one feasible solution in the original space [47]. According to the model, the solution representation for meta-heuristic algorithms consists of two parts: the first part is an activity sequence, which has been proposed by Kolisch and Hartmann [31] as an adequate representation, and the second part represents a list of available resource capacities. The chromosome structure for a solution I is demonstrated in Fig. 1.

Fig. 1

Chromosome structure

3.1.2 Generating a feasible solution

Since Kelley [30] introduced a schedule generation scheme, several heuristic methods have been proposed [33]. The scheduling generation scheme constructed a feasible schedule by assigning the start times to the activities. There are two different schemes to decode the solution: the serial schedule generation scheme (SSGS) and the parallel schedule generation scheme (PSGS).

In the RCPSP cases, the set of schedules, which is generated through the SSGS or the PSGS, have different properties [34]. In this Paper, the serial-SGS is employed to decode a solution. SSGS includes several stages in which the activity with the highest priority is chosen and assigned the earliest possible starting time (ESS) if the activity does not violate both the precedence relation and resource level. In order to build a feasible capacity list, a number for each employed resource between a defined the lower and upper bound should be chosen. The lower and upper bound is calculated via Eqs. (8) and (9).

$$\underline{{R_{k} }} = Max\left\{ {\sum\limits_{i = 1}^{n} {\frac{{r_{ik} \cdot d_{i} }}{T}} ,\mathop {\hbox{max} }\limits_{i = 1, \ldots ,n} \left\{ {r_{ik} } \right\}} \right\}$$

(8)

$$\overline{{R_{k} }} = \sum\limits_{i = 1}^{n} {r_{ik} }$$

(9)

Each solution or individual of the MOEAs posses a fitness value. Owing to the fact that the problem has several constraints, a randomly generated solution might be infeasible. Note that an infeasible solution may either has an activity started before its predecessors that have been finished or the resource requirements in any time periods are greater than the maximum level. In this regard, the technique called Repair, which is explained later, is employed to resolve the issue.

3.1.3 Applying meta-heuristic algorithms in PERT-type network

The solution techniques, which are available for resource-constrained project scheduling with stochastic activity durations, are very restricted. Owing to computational complexity in the uncertainty, optimal solution or heuristics for scheduling have been found useful for large-deterministic problems, and they are not appropriate. In this regard, various methods are developed. One of the renowned procedures, which are employed in the stochastic project scheduling environment, is Monte Carlo simulation (MCS). This method has become more practical when it is difficult or impossible to use mathematical methods. In this method, the random numbers are generated as the activity completion time. Then, the time of the longest path is determined as the project completion time. This procedure is repeated for the number we want the network to be simulated [19].

3.2 Strength pareto evolution algorithm (SPEA-II)

SPEA-II is one of the efficient algorithms in the field of multi-objective optimization (MOO). This algorithm is based on the domination concept and forming a Pareto Front. SPEA-II is found by [66]. They tried to improve the performance of SPEA and overcome the potential weakness. The overall pseudo code of the SPEA-II is explained in Fig. 2.

Fig. 2

Pseudo code of the SPEA-II

3.3 Non-dominated sorting genetic algorithm (NSGA-II)

Widely used in the literature, NSGA-II is considered as one of the well-known multi-objective evolutionary algorithms (MOEA’s), developed by [13]. Moreover, NSGA-II has ensured a high resolving capacity for multi-objective combinatorial optimization problems. The structure of NSGA-II is given in Fig. 3.

Fig. 3

Pseudo code of the NSGA-II

3.4 Multi-objective particle swarm optimization (MOPSO)

MOPSO is inspired by the PSO algorithm to solve multi-objective problems. This method is motivated by the simulation of social behavior. In order to determine the movement, each individual utilizes two pieces of information. The first one is their own experience, i.e., they have tried the different alternatives and find out the best state so far. The second one is others’ experiences; that is, they have utilized other individuals’ information.Therefore, each individual makes his decision regarding both his own experiences and others’ experiences [10]. Figure 4 shows the pseudo-code of the MOPSO algorithm.

Fig. 4

Pseudo code of the MOPSO

3.5 Pareto envelope based selection (PESA-II)

PESA-II is one of the well-known algorithms in the multi-objective optimization area. This algorithm uses a grid-based selection strategy instead of assigning a selective fitness to an individual. Using Deb’s test suite of ‘T’ functions with varying properties, the performance of this algorithm is proved [11]. The overall structure of the algorithm is depicted in Fig. 5.

Fig. 5

Pseudo code of the PESA-II

3.6 Mutation

The mutation is an operator that only applied to the activity list. In this article, we defined three different operators that change the activities sequence order, but only one of them, which is selected randomly, will be applied to the chosen chromosome. It should be mentioned that capacity list for the new chromosome will be obtained through the selected member. An example of mutation operators is illustrated in Fig. 6. Also, the employed structure of the swap, insertion, and reversion operators are described, respectively.

Fig. 6

Mutation operator for activity list

3.6.1 Swap operator

In this operator, we initially choose two numbers, a and b, randomly from the interval [2 n-1]. The numbers are selected activities. We consider the smaller number a. Note that the initial and terminal node cannot be selected. Let individual $I = \left( {\left( {j_{1}^{I} , \ldots ,j_{n}^{I} } \right),\left( {R_{1}^{I} , \ldots , R_{\rho }^{I} } \right)} \right)$ be the selected chromosome for mutation. For O_a < O_b, i.e., activity a precedes activity b, the activity list of I is replaced by $\left( {j_{1}^{I} , \ldots ,j_{a - 1 }^{I} , j_{b}^{I} , j_{a + 1}^{I} , \ldots , j_{b - 1}^{I} , j_{a}^{I} , j_{b + 1}^{I} , \ldots , j_{n}^{I} } \right)$. An example of a swap operator is shown in Fig. 6a. In this example, a and b are 4 and 3, respectively.

3.6.2 Insertion operator

Like Swap operator, Let a and b two randomly selected numbers from the interval [2 n-1]. The numbers are the selected activity and their new place, respectively. Therefore, let the activity list of the selected chromosome be $\left( {j_{1}^{I} , \ldots ,j_{a - 1 }^{I} , j_{a}^{I} , j_{a + 1}^{I} , \ldots , j_{b - 1}^{I} , j_{b}^{I} , j_{b + 1}^{I} , \ldots , j_{n}^{I} } \right)$. After applying insertion, activity list will be $\left( {j_{1}^{I} , \ldots ,j_{a - 1 }^{I} , j_{a + 1}^{I} , \ldots , j_{b - 1}^{I} , j_{a}^{I} ,j_{b}^{I} , j_{b + 1}^{I} , \ldots , j_{n}^{I} } \right)$. Fig. 6b demonstrates an example in which a and b are 1 and 3, respectively.

3.6.3 Reversion operator

This operator will select two activities from the activity list and reverses the sequence of the activities between them. Let chromosome $I = \left( {j_{1}^{I} , \ldots ,j_{a - 1 }^{I} , j_{a}^{I} , j_{a + 1}^{I} , \ldots , j_{b - 1}^{I} , j_{b}^{I} , j_{b + 1}^{I} , \ldots , j_{n}^{I} } \right)$ as the selected member and a and b as the selected activities. After applying reversion, the obtained activity list will be $I_{new} = \left( {j_{1}^{I} , \ldots ,j_{a - 1 }^{I} , j_{b}^{I} , j_{b - 1}^{I} , \ldots , j_{a + 1}^{I} , j_{a}^{I} , j_{b + 1}^{I} , \ldots , j_{n}^{I} } \right)$. In Fig. 6c, an example, considering a and b are 4 and 5, respectively, are shown.

3.7 Crossover

Crossover is also applied to the activity list. We employed two permutation-based crossover operators for the activity list of the chromosome. The first operator crossover, called one-point crossover, selects an integer number r randomly from the interval [2 n-1]. Note that the initial and terminal nodes are dummy activities. Let $P_{1} = \left( {\left( {j_{1}^{1} , \ldots ,j_{n}^{1} } \right),\left( {R_{1}^{1} , \ldots , R_{\rho }^{1} } \right)} \right)$ and $P_{2} = \left( {\left( {j_{1}^{2} , \ldots ,j_{n}^{2} } \right),\left( {R_{1}^{2} , \ldots , R_{\rho }^{2} } \right)} \right)$ be selected parents. Two children C₁ and C₂ are defined through the crossover whose activity lists are $C_{1} = \left( {j_{1}^{{c_{1} }} , \ldots ,j_{r}^{{c_{1} }} ,j_{r + 1}^{{c_{2} }} , \ldots ,j_{n}^{{c_{2} }} } \right)$ and $C_{2} = \left( {j_{1}^{{c_{2} }} , \ldots ,j_{r}^{{c_{2} }} ,j_{r + 1}^{{c_{1} }} , \ldots ,j_{n}^{{c_{1} }} } \right)$ respectively. $\left( {j_{1}^{{c_{1} }} , \ldots ,j_{r}^{{c_{1} }} } \right) = \left( {j_{1}^{1} , \ldots ,j_{r}^{1} } \right)$ and $\left( {j_{r + 1}^{{c_{1} }} , \ldots ,j_{n}^{{c_{1} }} } \right) = \left( {j_{r + 1}^{2} , \ldots ,j_{n}^{2} } \right)$ where $j_{b}^{2} \notin \left\{ {j_{1}^{{c_{2} }} , \ldots ,j_{r}^{{c_{2} }} } \right\}$ Moreover, $\left( {j_{1}^{{c_{2} }} , \ldots ,j_{r}^{{c_{2} }} } \right) = \left( {j_{1}^{2} , \ldots ,j_{r}^{2} } \right)$ and $\left( {j_{r + 1}^{{c_{2} }} , \ldots ,j_{n}^{{c_{2} }} } \right) = \left( {j_{r + 1}^{1} , \ldots ,j_{n}^{1} } \right)$ where $j_{b}^{1} \notin \left\{ {j_{1}^{{c_{1} }} , \ldots ,j_{r}^{{c_{1} }} } \right\}$. Figure 7a shows an example of this operator.

Fig. 7

Crossover operator for activity list

The second crossover operator is a two-point crossover, in which two integer numbers, r₁ and r₂, r₁ < r₂ are generated from the interval [2 n−1], which is called cutting point. Two children called C₁ and C₂ are defined by this crossover. Their activity lists are $C_{1} = \left( {j_{1}^{{c_{1} }} , \ldots ,j_{{r_{1} }}^{{c_{1} }} ,j_{r + 1}^{{c_{1} }} , \ldots ,j_{{r_{2} }}^{{c_{1} }} ,j_{{r_{2} + 1}}^{{c_{1} }} , \ldots , j_{n}^{{c_{1} }} } \right)$ and $C_{2} = \left( {j_{1}^{{c_{2} }} , \ldots ,j_{{r_{1} }}^{{c_{2} }} ,j_{r + 1}^{{c_{2} }} , \ldots ,j_{{r_{2} }}^{{c_{2} }} ,j_{{r_{2} + 1}}^{{c_{2} }} , \ldots , j_{n}^{{c_{2} }} } \right)$ respectively. Thus, $\left( {j_{1}^{{c_{1} }} , \ldots ,j_{r}^{{c_{1} }} } \right) = \left( {j_{1}^{1} , \ldots ,j_{r}^{1} } \right)$ and $j_{a}^{{c_{1} }} , a = r_{1} + 1, \ldots , r_{2}$ is $j_{2}^{b}$ where b is the lowest index such that $j_{b}^{2} \notin \left\{ {j_{1}^{{c_{1} }} , \ldots ,j_{a - 1}^{{c_{1} }} } \right\}$ and $j_{a}^{{c_{1} }} , a = r_{2} + 1, \ldots , n$ is $j_{1}^{b}$ where b is the lowest index such that $j_{b}^{1} \notin \left\{ {j_{1}^{{c_{1} }} , \ldots ,j_{a - 1}^{{c_{1} }} } \right\}$ The definition of C₂ is similar to C₁. An example is illustrated in Fig. 7b.

3.8 Local search

This operator is exerted to the second part, namely the capacity list, of a chromosome. This operator consists of one-point and multi-point operators. Remark that one of the operators is selected randomly and employed. Figure 8 illustrates an example of both a one-point and multi-point local search.

Fig. 8

Local Search operator for a capacity list

3.9 Movement

This operator is designed to minimize both objective functions simultaneously (Fig. 9). To do so, this operator alters both parts of the solution: activity list, and capacity list. Initially, a solution and resource type K are chosen randomly.

Fig. 9

Pseudo code of the movement

It is noticeable that by applying all the mentioned operators, to the chromosome, the solutions might be infeasible in terms of precedence constraints. Therefore, a function called repair function is used to make the chromosome feasible. To elucidate the issue, an example is provided to show how this method works. Table 2 illustrates the activities and their related prerequisite activities. Since the relation between activities in this paper is FS(0), an activity can only be started if all of its prerequisite activities have been fulfilled. Figure 10 clarifies the repair function by which a solution changed to a feasible one. Accordingly, the precedence relationships of all the activities are monitored. If its prerequisite activities are not finished, the activity shifted to place forward and started at the earliest possible time. Considering Fig. 10, two activities that are not in the right place have been moved after their precedence activities. This function is applied to all newly generated solution before their evaluating its fitness. As a result, all the solutions generated will be feasible.

Table 2 Precedence relationship of example

Fig. 10

An example of a repair function

4 Computational experiments

In this section, the performance of the proposed four multi-objective algorithms, namely PESA-II, NSGA-II, and MOPSO, are compared. Note that the algorithms studied in this paper are coded using MATLAB 2014a.

4.1 The test problems

Since the presented mathematical model is a newly defined problem in some aspects, we redefine a set of 90 standard problems categorized into three different groups, small, medium, and hard, from PSPLIB. More details about the problems are provided in Table 3.

Table 3 Test problem classification

These standard test problems containing the activities and predecessor relations between the activities are chosen as our fundamental test problems. Also, some new data are required for our problems, according to its mathematical model, which are produced and described as below:

• The number of (non-dummy) activities in different groups is 10, 20, or 30.

• The activity duration is stochastic and is randomly produced by uniform U(1,10).

• Resource requirement r_ik is also considered as a stochastic parameter randomly produced by uniform U(1,10).

• The maximal number of predecessors and successors for each activity is equal to three.

• The network complexity (NC) coefficient is assumed to be three.

• Resource Factor (RF) is considered to be 1.5.

• The number of renewable resources considering different groups varies from 2 to 4.

• The average cost of each resource level C_k is supposed to be equal.

• The number of initial and terminal activities is equal to three.

4.2 Comparison criteria for algorithms evaluation

In this paper, six comparison criteria are applied to evaluate the performance of the algorithms. For more information about criteria, refer to Table 4.

Table 4 Performance criteria

4.3 Parameters tuning

It is obvious that the various levels of the parameters affect the quality of the solutions obtained by the hybrid algorithms. Thereby, selecting the best combination of parameters can augment the search process to find more suitable solution, and prevent being trapped in a local optimum. There are many techniques for designing an experimental investigation. Although a full factorial experiment is most appropriate used method, the investigation becomes more complicated when the number of factors and their decided levels is significantly increased. To overcome this defect, fractional factorial experiments are used to diminish the number of required tests [9].

In this regard, the Taguchi method is utilized to set the parameters of the presented algorithms. This method that is designed based on orthogonal arrays can be used efficiently as an alternative for the full factorial experimental design to investigate a group of factors. These factors are divided into two groups: controllable noise factors and noise factors. The method initial goal is to select the best level of the factors such that the effect of controllable factors is maximized and the effect of noise factors is minimized [56]. Hence, a measure called signal to noise ratio (S/N) is employed to evaluate the algorithms’ performance. The value is calculated through Eq. (10):

$$S/N\,Ratio = - 10\log \frac{1}{n}\left( {S\left( {Y^{2} } \right)} \right)$$

(10)

where n and Y are the number of orthogonal arrays and the response value, respectively. SM criterion is the most crucial criterion among the mentioned criteria due to the fact that it considers two critical criteria, MID and D, simultaneously, SM is applied for tuning the parameters. Consequently, the response factor is calculated through the Eq. (11);

$$SM = \, MID/D$$

(11)

where MID and D are considered to assess convergence and diversity, respectively. For each algorithm, three levels of parameters are shown in Table 5. Using the Minitab software, the orthogonal arrays are obtained.

Table 5 Algorithm parameter ranges along with their levels

As we mentioned before, we divide the test problems into small, medium, and large size problems. In this paper, the Taguchi method is applied to all scales for parameter tuning. To do so, for each category of problem, one problem is randomly selected. To yield more reliable results, each problem is tackled five times. The best result among the 5-time runs of each problem is considered the result of that problem.

Parameter tuning by the Taguchi method is explained in detail by representing the step by step results for small-size problems. The result for each level is represented in Figs. 11 and 12. Accordingly, the optimal levels of factors are represented in Table 6. The orthogonal arrays of these designs along with the all experimental results are represented in (“Appendix 1”). Furthermore, the delta value represented in Table 7, the Archive size has the most influence on the SPEA-II. P-movement and P-local search operators are the other practical factors on SPEA-II, respectively. Therefore, movement and local search operators have an impact on SPEA-II.

Fig. 11

The S/N ratio plots for each level of the factors (small-size problem)

Fig. 12

The mean plots for each level of the factors (small-size problem)

Table 6 Parameters setting values

Table 7 S/N ratio value for SPEA-II

4.4 The computational results

In this section, the performance of the proposed algorithm is evaluated. Remark that the computational results are presented in (“Appendix 2”). Figure 13 illustrates Box-Plots of each criterion, of the four presented algorithms. Furthermore, Fig. 14 shows the results of the problems for different criteria graphically. According to Figs. 13, and 14, in terms of some criteria, it is denoted that the SPEA-II has the best performance; e.g., the obtained result of NPS criterion shows that SPEA-II outperforms other algorithms. Afterward, MOPSO, PESA-II, and NSGA-II are placed, respectively. Moreover, in terms of CPU-time, the SPEA-II, and MOPSO has also obtained the best performance, respectively. However, the results of the PESA-II and NSGA-II are slightly close. However, in terms of other criteria, the outcomes are very close.

Fig. 13

Box-plot results for statistical comparison

Fig. 14

A detailed comparison of criteria on different test problems

4.5 Sensitivity analysis

Since the results in some of the criteria are very close, and we cannot compare them, in this section, we use the Relative Percentage Deviation (RPD). In this method, the obtained results of these performance criteria for each problem are transformed to a Relative Percentage Deviation (RPD) that is calculated by Eq. (12):

$$RPD = \left| {\frac{{Algorithm_{solution} - Best_{solution} }}{{Best_{solution} }}} \right| \times 100$$

(12)

where $Algorithm_{solution}$ is the obtained value for each experiment by each performance criteria, $Best_{solution}$ is the best value between the obtained values of four algorithms. Then, the average of the RPD’s obtained for problems are calculated. The results are shown in Table 8. Remark that the less value shows the higher performance. Also, the best result in each metric is bolded. Accordingly, SPEA-II has the best performance in NPS, MID, and CPU-time criteria. Furthermore, MOPSO has gain better results in D and SM criteria, and PESA-II is the best in terms of S criterion. Remark that NSGA-II has obtained the worst results.

Table 8 Average RPD for criteria on test problems

4.6 TOPSIS approach

Since the algorithms’ results are close in some aspects, and each of the defined algorithms has some advantages in some criteria rather than others, we cannot certainly determine which algorithm has the best performance. Hence, in order to investigate the performance more comprehensively, a Multi-Attribute Decision Making (MADM) technique is employed. We apply a renown multi-attribute decision-making method called TOPSIS (a technique for order performance by similarity to ideal solution), which was introduced by Hwang and Yoon [25]. This method can also be integrated with other approaches, e.g., AHP and Fuzzy techniques, to deal with various decision-making problems [5, 46].

TOPSIS is a practical and useful technique for ranking alternatives. This method is derived from the Euclidean distance of each quality performance of the distance between the positive ideal solution and the negative ideal one. TOPSIS considers both positive and negative simultaneously to chose the most suitable alternative: the most preferred alternative should not only have the shortest distance from the positive ideal solution but also have the longest distance from the negative ideal solution. The final score is calculated according to the distance between the positive and negative ideal [62]. The overall process of the TOPSIS method to find the best possible solution is described in Fig. 15.

Fig. 15

Flow chart for the TOPSIS method

To evaluate the algorithms’ performance more precisely, the final score for algorithms are calculated. As it is obvious, the more (less) final score shows a better result. Figure 16 demonstrates the results graphically. Remark that, in Fig. 16, the problems are distinguished by their number of renewable resources and activities. Furthermore, Fig. 16a–c demonstrate the results from all problems with two, three, and four renewable resources, respectively, and Fig. 16d illustrates the final result, considering all test problems.

Fig. 16

TOPSIS results

Accordingly, it is implied that the number of activities has no impact on the efficiency of SPEA-II, and SPEA-II has gained the best result in almost all modes. Meanwhile, MOPSO is sensitive to the number of activities and has obtained the most relevant result in all problems with 30 activities. Moreover, NSGA-II is sensitive to the number of resources. As a result, by increasing the number of resources, NSGA-II has a better performance. However, it is clear that by increasing the number of activities, MOPSO has better performance. As a result, it has the best performance in problems with 30 activities.

In addition, the final result is demonstrated in Table 9. Accordingly, NSGA-II with 0.8975 values score has the worst result. In contrast, SPEA-II has gained a 0.8157 value score and be in the first place. Moreover, after SPEA-II, MOPSO, and PESA-II with 0.4766 and 0.4353 value score are placed, respectively.

Table 9 TOPSIS final result

5 Conclusions and future research

In this paper, a bi-objective resource availability cost problem with stochastic activity durations and resource requirement are considered. Furthermore, in order to consider uncertainty in the model, a PERT-type network, where activities require a random amount of resources of various types with random duration, is considered. The problem has two objectives, in which the first one is to minimize the regular criterion namely project’s makespan, and the second one is to minimize the total resource cost. Since the problem is NP-hard in the strong sense, meta-heuristic algorithms are presented. To do so, four meta-heuristic algorithms, namely SPEA-II, PESA-II, MOPSO, and NSGA-II, are employed to solve the problem. The parameters of these algorithms are tuned by the Taguchi method, and finally, six performance criteria are used to analyze the diversity and convergence of proposed algorithms. Results for project completion time are provided from Monte Carlo simulation (MCS) runs. The performance of the algorithms is tested on the redefined problem from PSPLIB, including different sizes. Moreover, to investigate the performance of the algorithms more comprehensively, a MADM technique called TOPSIS and RPD method are applied.

According to the obtained results, in terms of NPS and CPU-time criteria, SPEA-II has acquired the best performance. Furthermore, Average RPD for criteria on all test problems has shown that PESA-II has relatively best performance considering S criterion with an average 21.54 percent deviation. Regarding D and SM criteria, MOPSO with average less deviation has represented the best performance. Considering Fig. 16d, it is noteworthy that MOPSO, in contrast to PESA-II, has shown better performance by increasing the complexity of the problem. It is also proved that SPEA-II has the best performance in all types of problems. According to Table 7, it has been determined that movement and local search, after the archive size, have the most impact on the performance of the SPEA-II, respectively.

Some extensions of this research as a future study might be of interest. We can consider multiple execution modes for each activity, considering the required resource and activity duration. We can also consider preemption in the model. Finally, applying other solution approaches to this model would be proper research as a future study.

Appendices

Appendix 1: Tuning the algorithms’ parameters

See Tables 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 and 21.

Table 10 Computational results to tune SPEA-II for small-size problem

Table 11 Computational results to tune PESA-II for small-size problem

Table 12 Computational results to tune NSGA-II for small-size problem

Table 13 Computational results to tune MOPSO for small-size problem

Table 14 Computational results to tune SPEA-II for medium-size problem

Table 15 Computational results to tune PESA-II for medium-size problem

Table 16 Computational results to tune NSGA-II for medium-size problem

Table 17 Computational results to tune MOPSO for medium-size problem

Table 18 Computational results to tune SPEA-II for large-size problem

Table 19 Computational results to tune PESA-II for large-size problem

Table 20 Computational results to tune NSGA-II for large-size problem

Table 21 Computational results to tune MOPSO for large-size problem

Appendix 2: Computational results for meta-heuristic algorithms

See Tables 22, 23, 24 and 25.

Table 22 Computational result for NSGA-II

Table 23 Computational result for PESA-II

Table 24 Computational result for MOPSO

Table 25 Computational result for SPEA-II