# A Memetic Algorithm for Multiskill Resource-Constrained Project Scheduling Problem under Linear Deterioration

Authors: Huafeng Dai; Wenming Cheng
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

This paper proposes a general variable neighborhood search-based memetic algorithm (GVNS-MA) for solving the multiskill resource-constrained project scheduling problem under linear deterioration. Integrating a solution recombination operator and a local optimization procedure, the proposed GVNS-MA is assessed on two sets of instances and achieves highly competitive results. One set of benchmark instances is commonly used in the literature where the capability of the proposed algorithm to find high quality solutions is demonstrated, compared with the state-of-the-art algorithms in the literature. The other set revises the former through incorporating the linear deterioration effect. Two key components of the proposed algorithm are investigated to confirm their critical role to the success of the proposed method.


---

## Body

## 1. Introduction

Scheduling is a form of decision-making that plays an essential role in manufacturing and service industries. A function that assigns tasks to resources to complete the project can be formulated as an informal definition of the scheduling problem. However, such simplification is not enough to cover all real-world applications with a variety of complex environments. Take the task duration; for example, the processing time of any task is fixed and constant in classical scheduling theory and system [1] while a hypothesis that the actual duration of the task is a linearly nondecreasing function of its starting time is put forward by Gupta and Gupta [2] in contrast to the cases found in traditional literature. From then on, many approaches concerning various scheduling types, accompanying with the phenomenon denominated as deterioration effect [3], constantly spring up.Scheduling with deterioration is very common. For instance, in traditional manufacturing industries like the furniture, some tasks need to be processed by a carpenter and the carpenter may lower his machining speed gradually due to fatigue. In this case, the later a task is handled, the longer the time it needs to complete. For another example, in steel rolling mills, ingots need to be heated to required temperature before rolling. Heating time relies on the ingots’ current temperature, which depends upon the time it has been waiting to be heated. It is because the ingot cools down consequently requiring more heating time in the period of waiting. Similar cases often occur in manufacturing, financial management, steel production, medicine treatment, and so on. Scheduling deteriorating jobs was first considered by Browne and Yechiali [4] who assumed that task processing times are nondecreasing, start time dependent linear functions. Since then, researchers have devoted considerable efforts to this area and lots of remarkable papers have been published. Alidaee and Womer [5], as well as Cheng et al. [6] made the comprehensive overviews of existing scheduling problems with various deteriorating mechanisms.In addition to changes in the definition of duration time in terms of research hotpot in the field of scheduling, project scheduling problem (PSP) provided a set of precedence-constrained tasks to be scheduled aiming at minimizing a given objective. Furthermore, tasks need to compete for scarce resources additionally in the resource-constrained project scheduling problem (RCPSP), which make it possible through a better adaption to apply in production planning, project management, or manufacturing, etc. Ultimately more adaptable multiskill resource-constrained project scheduling problem (MS-RCPSP) gives each resource a set of capabilities and each resource can bid for being assigned tasks.Scheduling with deterioration and MS-RCPSP are two research hotspots of scheduling area and these two subfields are not absolutely separate. In terms of most tasks of actual MS-RCPSP, deterioration effects existed, for the reason of fatigued (humans or machines). However, there is no research concentrated on the integration of MS-RCPSP and deterioration.In this paper, we pick the deterioration mechanism as linear deterioration. As for the researched MS-RCPSP with linear deterioration, which is dubbed MS-RCPSPLD, the differences compared to the scheduling problems with linear deterioration in the reported literature can be explained here. Foremost, the resource, or the machine in the usually researched scheduling problem with deterioration, mostly is restricted to be single-mode, which means that it owns only one capability, and can execute just a kind of task.Moreover, as the RCPSP is proven to be NP-hard [7], there is no optimal solution that could be computed in polynomial time. And this paper also demonstrates that the MS-RCPSP and the MS-RCPSPLD are NP-hard because they are more general problems compared with the single-mode RCPSP. Hence, methods that find feasible solutions, which may not achieve global optimal but can obtained in acceptable time, are built by researchers. In such cases soft computing methods are used, mostly heuristics and metaheuristics.Within the metaheuristics group of methodologies, it is noticed that memetic algorithm (MA), as a quite simple approach, gives promising results in the fields of both computer science and operational research [8]. MA represents one of the recent growing areas of research in evolutionary computation and is introduced by Moscato [9], inspired by both Darwinian principles of natural evolution and Dawkins’ notion of a meme. With MA, the traits of Universal Darwinism are more appropriately captured, in particular dealing with areas of evolutionary algorithms that marry other deterministic refinement techniques for solving optimization problems [10]. As a general framework, MA provides the search with desirable trade-off between intensification and diversification through the combined use of a crossover operator to generate new promising solutions and a local optimization procedure to locally improve the generated solutions [11, 12].In next stages, to make MA more efficient, it needs to be supported by other metaheuristics, e.g., general variable neighborhood search (GVNS) proposed by Hansen et al. [13]. GVNS is a simple and effective metaheuristic for combinatorial optimization, yield through systematic change of neighborhoods within a refinement local search. It can avoid becoming mired in local optima and develop the search direction to an excellent solution ultimately by means of exploring new regions throughout the whole solution space. The GVNS has attracted attentions and shows remarkable performance compared to other basic variable neighborhood search (VNS) variants. Up to now, various optimization problems have taken the GVNS to pursue better solutions, such as the single-machine total weighted tardiness problem with sequence dependent setup times [14], the one-commodity pickup-and-delivery traveling salesman problem [15], and the vehicle routing problem [16].As far as we know, there is no published work on solving the MS-RCPSP by the GVNS-MA. By natural extension, it makes sense to solve the MS-RCPSPLD with the GVNS-MA. The main goal of this paper is to get an insight to the problem integrating the MS-RCPSP with linear deterioration. How GVNS can be effectively hybridized with MA to solve MS-RCPSP and MS-RCPSPLD is examined in the GVNS-MA. The proposed approach is demonstrated to show its effectiveness in comparison to other state-of-the-art methods.The remaining part of this paper is organized as follows. In Section2, a short summary of existing publications is presented. Section 3 gives the description of the problem under consideration. In Section 4, the proposed GVNS-MA is elaborated. Section 5 shows performed experiments and their results before concluding the paper in Section 6 finally.


## 2. Related Work

### 2.1. Deterioration Effect

There are many practical situations that any delay or waiting in starting time of a task may cause to increase its processing time and two main deterioration mechanisms are discussed.Besides usual linear deterioration mechanism discussed in this paper, situations in which task’s processing times are represented by step functions characterized by a sharp change in processing time at the deadline points [17–22] also are fairly common. Sundararaghvan and Kunnathur [23] firstly considered the corresponding single-machine scheduling problem for minimizing the sum of the weighted completion times while Mosheiov [17] provided some simple heuristics for these NP-hard problems to minimize the makespan. Next, Jeng and Lin [24] introduced a branch and bound algorithm for the single-machine problem with the same goal. The problem was extended by Cheng et al. [19] to the case with parallel machines, where a variable neighborhood search algorithm (VNS) was proposed.As for the linear deterioration mechanism, Mosheiov [25] considered the case that processing times increase at a common rate and job weights are proportional to their normal processing time. He demonstrated that the optimal schedule is Λ-shaped if the optimal objective is to minimize the total weighted completion time on a single machine. Moreover, simple linear deterioration where jobs have a fixed job-dependent growth rate but no basic processing time was further considered [17]. Ji and Cheng [26] discussed corresponding methods refer to the parallel-machine scheduling and gave a fully polynomial-time approximation scheme, whereas a single-machine scheduling problem with linear deterioration was studied by Jafari and Moslehi [27]; Wu et al. [28]; Wang and Wang [29], with respective goals of minimizing the number of tardy jobs and earliness penalties as well as total weighted completion time. More studies and discussions about linear deteriorating scheduling problems were shown in Bachman and Janiak [30]; Oron [31]; Wang and Wang [29]; Wu et al. [28].


### 2.2. MS-RCPSP

For the sake of its practicality, RCPSP has received more and more attentions [32]. U. and Kusiak [33]; Babiceanu et al. [34], and Coban [35] deal with the RCPSP in a dynamic, real time way. To obtain particular schedules at some point, metaheuristics are the most used techniques for solving RCPSP, including Tabu search [36, 37], Simulated Annealing [38, 39], or Genetic Algorithm [40]. Swarm Intelligence metaheuristics [41] are also effective for solving related issues. For example, Particle Swarm Optimization [42], Bee Colony Optimization [43], or the popular Ant Colony Optimization [44, 45]. Although classical RCPSP is deeply investigated and numerous methods could be easily compared using PSPLIB instances, it is not same for MS-RCPSP. There are not too many researches paying attention to MS-RCPSP.Myszkowski et al. [46] defined new problem MS-RCPSP and benchmark to compare the effectiveness of examined approaches. Next, a hybrid ant colony optimization approach (HAC) [47], which links classical heuristic priority and the worst solutions stored by ants to update pheromone value, was proposed. To research this problem more thoroughly, a greedy randomized adaptive search procedure (GRASP) [48], a hybrid differential evolution and greedy algorithm [49], and a Co-Evolutionary algorithm [50] are developed to improve the quality of solutions. Before this period, Alanzi et al. [51] proposed a lower bound using a linear programming scheme for the RCPSP to solve the new extended MS-RCPSP model while Santos and Tereso [52] developed a filtered beam as a bonus for early completion into account. Zheng et al. [53] presented a teaching-learning-based optimization algorithm with a task-resource list-based encoding scheme combining the task list and the resource list and a left-shift decoding scheme where the balance between global exploration and local exploitation to achieve satisfactory performances was mainly stressed. Dai et al. [54] did the related work on the integration of MS-RCPSP and proposed step structures as well as two mutation operators.


## 2.1. Deterioration Effect

There are many practical situations that any delay or waiting in starting time of a task may cause to increase its processing time and two main deterioration mechanisms are discussed.Besides usual linear deterioration mechanism discussed in this paper, situations in which task’s processing times are represented by step functions characterized by a sharp change in processing time at the deadline points [17–22] also are fairly common. Sundararaghvan and Kunnathur [23] firstly considered the corresponding single-machine scheduling problem for minimizing the sum of the weighted completion times while Mosheiov [17] provided some simple heuristics for these NP-hard problems to minimize the makespan. Next, Jeng and Lin [24] introduced a branch and bound algorithm for the single-machine problem with the same goal. The problem was extended by Cheng et al. [19] to the case with parallel machines, where a variable neighborhood search algorithm (VNS) was proposed.As for the linear deterioration mechanism, Mosheiov [25] considered the case that processing times increase at a common rate and job weights are proportional to their normal processing time. He demonstrated that the optimal schedule is Λ-shaped if the optimal objective is to minimize the total weighted completion time on a single machine. Moreover, simple linear deterioration where jobs have a fixed job-dependent growth rate but no basic processing time was further considered [17]. Ji and Cheng [26] discussed corresponding methods refer to the parallel-machine scheduling and gave a fully polynomial-time approximation scheme, whereas a single-machine scheduling problem with linear deterioration was studied by Jafari and Moslehi [27]; Wu et al. [28]; Wang and Wang [29], with respective goals of minimizing the number of tardy jobs and earliness penalties as well as total weighted completion time. More studies and discussions about linear deteriorating scheduling problems were shown in Bachman and Janiak [30]; Oron [31]; Wang and Wang [29]; Wu et al. [28].


## 2.2. MS-RCPSP

For the sake of its practicality, RCPSP has received more and more attentions [32]. U. and Kusiak [33]; Babiceanu et al. [34], and Coban [35] deal with the RCPSP in a dynamic, real time way. To obtain particular schedules at some point, metaheuristics are the most used techniques for solving RCPSP, including Tabu search [36, 37], Simulated Annealing [38, 39], or Genetic Algorithm [40]. Swarm Intelligence metaheuristics [41] are also effective for solving related issues. For example, Particle Swarm Optimization [42], Bee Colony Optimization [43], or the popular Ant Colony Optimization [44, 45]. Although classical RCPSP is deeply investigated and numerous methods could be easily compared using PSPLIB instances, it is not same for MS-RCPSP. There are not too many researches paying attention to MS-RCPSP.Myszkowski et al. [46] defined new problem MS-RCPSP and benchmark to compare the effectiveness of examined approaches. Next, a hybrid ant colony optimization approach (HAC) [47], which links classical heuristic priority and the worst solutions stored by ants to update pheromone value, was proposed. To research this problem more thoroughly, a greedy randomized adaptive search procedure (GRASP) [48], a hybrid differential evolution and greedy algorithm [49], and a Co-Evolutionary algorithm [50] are developed to improve the quality of solutions. Before this period, Alanzi et al. [51] proposed a lower bound using a linear programming scheme for the RCPSP to solve the new extended MS-RCPSP model while Santos and Tereso [52] developed a filtered beam as a bonus for early completion into account. Zheng et al. [53] presented a teaching-learning-based optimization algorithm with a task-resource list-based encoding scheme combining the task list and the resource list and a left-shift decoding scheme where the balance between global exploration and local exploitation to achieve satisfactory performances was mainly stressed. Dai et al. [54] did the related work on the integration of MS-RCPSP and proposed step structures as well as two mutation operators.


## 3. Problem Statement

To define two considered MS-RCPSP and MS-RCPSPLD, as well as make them clear, the problem description and a mixed integer programming model can be described as follows. LetG
(
V
,
E
) be a task-on-node network consisting of a set V of nodes denoting task i, (
i
∈
V
) and a set E of edges representing the precedence relationships between a pair of tasks (
i
,
j
)
,
(
i
,
j
)
∈
E. Specifically, each pair (
i
,
j
)
∈
E means the task i precedes j. In other words, task j cannot start until task i finished. The duration of each task i in MS-RCPSP is a prior known and constant while the value of duration in MS-RCPSPLD, turning out to hinge on the basic processing time a
i and deteriorating rate h
i, can be calculated by the function d
i
=
a
i
+
S
i
∗
h
i, where S
i shall be the earliest available time of assigned resource k, i
∈
V
k. To perform any task i, the specific skill q
i also is required. To make the n tasks completed, a set of K of m renewable resources, which unassigned tasks can compete for when resources are idle, will be provided. Resources differ in mastered skills and let Q
k denote the skills covered by resource k. Naturally, a subset V
k of V also is available to incorporate all tasks that can be processed by resource k (q
i
∈
Q
k
,
i
∈
V
k). In same way, a subset of resources K
i, including all resources which can be utilized to handle task i, is obtained. Moreover, each resource can perform at most one task at a time and a task can be executed by at most one resource simultaneously. The objective is to minimize the makespan (the completion time of all tasks).Based on the above description, we formulate the problem as a 0-1 integer programming model. Firstly, the binary variablesx
j
k receive value 1 if task j is assigned to resource k, and 0 otherwise. As for the binary variables y
i
j are set to 1 if task i is scheduled to precede task j, 0 otherwise. Then, MS-RCPSP and MS-RCPSPLD can be formulated by objective function (1) subject to constraints (2) to (9). (1)
M
i
n
i
m
i
z
e
C
m
a
x
(2)
s
u
b
j
e
c
t
t
o
F
i
=
S
i
+
d
i
∀
i
∈
V
(3)
∑
k
∈
K
j
x
j
k
=
1
∀
j
∈
V
(4)
x
j
k
=
0
∀
j
∉
K
j
(5)
s
j
-
s
i
≥
d
i
∀
i
,
j
∈
E
(6)
y
i
j
+
y
j
i
≥
x
i
k
+
x
j
k
-
1
∀
i
,
j
∈
E
,
k
∈
K
(7)
S
j
≥
S
i
+
d
i
-
M
1
-
y
i
j
∀
i
≠
j
,
i
,
j
∈
V
(8)
C
m
a
x
≥
F
i
∀
i
∈
V
(9)
x
j
k
,
y
i
j
∈
0,1
,
s
j
≥
0
∀
i
∈
V
,
j
∈
VIn the above mode, objective function (1) denotes the optimal direction of MS-RCPSP and MS-RCPSPLD. Equation (2) defines the finishing time of any task. Constraint (3) restricts exactly one resource to a specific task among all available resources. Constraint (4) respects the skill constraints between resources and tasks. Constraint (5) highlights the precedence relationship between a pair of nodes (
i
,
j
): in other words, task j can start only after i is finished. Constraint (6) shows logical relationships between the assignment variables and sequencing variables. That is, when resource k is simultaneously assigned to task i and task j, the sequence between two tasks must be determined: either i precedes j or j precedes i. Constraint (7) is the big-M formulation to enforce the relationship between the sequencing variable and the continuous starting time variable. Constraint (8) calculates the makespan of project, while Constraint (9) regulars the domains of the variables.


## 4. GVNS-Based Memetic Algorithm

In this section, we describe in detail the general solution methodology and the supporting procedures in the following subsections.


### 4.1. Search Space and Evaluation Function

For a given problem, the GVNS-MA searches a spaceΩ composed of all possible assignments respecting skill constraints in any order of tasks, including both legal and illegal configurations. The size of the search space Ω is bounded by O
(
m
n
∗
2
n
).Based on preceding notations and depictions, to evaluate the quality of a candidate solutions
∈
Ω, we adopt an evaluation function which is defined as f
(
s
) induced by s: (10)
f
s
=
m
a
x
i
m
i
z
e
F
i
:
i
∈
V
+
M
∗
∑
i
,
j
∈
E
δ
i
,
j
(11)
δ
i
,
j
=
1
,
i
,
j
∈
E
,
S
j
<
F
i
0
,
o
t
h
e
r
w
i
s
e
∀
i
∈
V
,
j
∈
Vwhere M is a large positive constant such that M
→
∞ as n
→
∞. The first part of (10) represents the completion time of the last unfinished task, and the last part is an augmented penalty function where ∑
(
i
,
j
)
∈
E
‍
δ
(
i
,
j
) denotes the degree violation to precedence relationships. If δ
(
i
,
j
)
=
0 holds for any (
i
,
j
)
∈
E, it demonstrates the solution is feasible, corresponding to a legal configuration, and its evaluation function will all depend on the first part, equal to the completion time of the schedule. When a problem instance admits no solution able to satisfy δ
(
i
,
j
)
=
0, ∀
(
i
,
j
)
∈
E, the search space of GVNS-MA is empty and no feasible solution can be found. Given two solutions s
′ and s
′
′, s
′ is better than s
′
′ if f
(
s
′
)
≤
f
(
s
′
′
). This statement implies an assumption that a better solution has fewer precedence constraint violations.


### 4.2. Methodology and General Procedure

LetP denote a population of p candidate configurations. Let s
b
,
s
w represent the best solution attainable so far and the worst solution in P (in terms of the evaluation function in Section 4.1), respectively. Let P
a
i
r
S
e
t be a set of solution pairs (
s
i
,
s
j
) initially composed of all possible pairs in P. Next, the proposed GVNS-MA can be described as depicted in Algorithm 1.Algorithm 1:Main sketch of the proposed GVNS-MA.
(
1
)
Input: Problem instance I, the size of population
(p), the depth of GVNS α
(
2
)
Output: the best configuration found during the
search
(
3
)
P
=
{
s
1
,
...
,
s
p
}
← Population_initialization(I) /∗Sec-
tion 4.3∗/
(
4
)
P
a
i
r
S
e
t
←
{
(
s
i
,
s
j
)
:
1
≤
i
<
j
≤
p
}
(
5
)
while
P
a
i
r
S
e
t
≠
⌀
do
(
6
)
Isolate a solution pair (
s
i
,
s
j
)
∈
P
a
i
r
S
e
t ran-
domly
(
7
)
P
a
i
r
S
e
t
←
P
a
i
r
S
e
t
∖
{
(
s
i
,
s
j
)
}
(
8
)
s
c
← crossOver(
s
i
,
s
j
) /∗Section 4.4∗/
(
9
)
s
← GVNS_Operator(
s
c
,
α
) /∗Section 4.5∗/
(
10
)
if
f
(
s
)
≤
f
(
s
w
)
then
(
11
)
UpdatePopulation(
s
,
P
,
P
a
i
r
S
e
t
,
f
(
s
)
) /∗Sec-
tion 4.6∗/
(
12
)
end if
(
13
)
end while
(
14
)
Return s
b
← arg min {
f
(
s
i
)
:
i
=
1
,
...
,
p
}GVNS-MA first builds an initial populationP including p candidate configurations by the procedures in Section 4.3. Then, the algorithm enters into a while loop which constitutes the main part of the GVNS-MA. On each new generation, the subsequent operations are executed. In the first place, a configuration pair (
s
i
,
s
j
) is taken at random and deleted fromPairSet. Next, GVNS-MA builds, with a crossover operator (see Section 4.4), a new configuration s
c (the offspring). After that, the offspring is used as a starting point to further improve by the GVNS_operator (see Section 4.5). Finally, if the improved offspring s is better than the worst solution s
w in P, it is used to update the population P andPairSet. The detailed update operations are described in Section 4.6. The while loop continues untilPairSet becomes empty. At the end of the while loop, the algorithm terminates and returns the best configuration s
b found during the search. Note that the depth of GVNS α represents a maximum number between two iterations without improvement, regarded as the stopping criterion of the GVNS_operator.


### 4.3. Population Initialization

In order to build the initial population (in Algorithm2), the construction operator to generate a new solution is executed 3
×
p times. From the scratch, a new configuration is constructed as follows. The operator starts from assigning each task with a random resource satisfying skill constraint. Subsequently all tasks assigned to same resource are sequenced randomly at the end of previous task-to-resource phase. Then, for each generated solution, theGVNS_operator with the evaluation function f
(
s
) (see Section 4.1) is used to optimize it to a local optimum and the obtained p best configurations are selected to form the initial population. The detailed procedures are described in Algorithm 2.Algorithm 2:
Population_initialization.
(
1
)
Input: The set V
=
{
v
1
,
v
2
,
...
,
v
n
} of n tasks; the set K
=
{
k
1
,
k
2
,
.
.
.
,
k
m
} of m renewable resources; skill constraints;
precedence relationships and the size of population (p)
(
2
)
Output: The best p configurations
(
3
)
for  pop
=
1
:
3
p
do
(
4
)
Set RA
:
=
V
(
5
)
while
R
A
≠
⌀
do
(
6
)
Choose v
i randomly from R
A; remove v
i from R
A;
randomly isolate k
j
∈
K
i— the set covering all re-
sources can perform v
i and record this assignment
as A
(
v
i
)
:
=
j
(
7
)
end while
(
8
)
for
j
:
=
1
,
.
.
.
,
m
do
(
9
)
Generate a random task sequence T
Q
j for candidate
tasks assigned to k
j
(
10
)
end for
(
11
)
Calculate the objective value f
(
A,TQ
) with the evalu-
ation function f
(
s
) (see Section 4.1)
(
12
)
s
p
o
p
b
← GVNS_operator(
f
(
A,TQ
)
,
α
) /∗Section 4.5∗/
(
13
)
end for
(
14
)
Sort the 3
p configurations in an ascending sort of evalua-
tion function values and return the first p solutions as the
initial population.


### 4.4. The Crossover Operator

Within a memetic algorithm, the crossover operator is another essential ingredient whose main goal is to bring the search process to new promising search regions to diversify the search. In this paper, the offspring of two parent configurationss
1
=
(
A
1
,
T
Q
1
), s
2
=
(
A
2
,
T
Q
2
) shows as s
o
=
(
A
o
,
T
Q
o
). To inherit the advantages of parent solutions, the tasks assigned to same resource in s
1, s
2 are given priority to keep the task-to-resource assignment unchanged. As for the remain unassigned tasks and T
Q
0, they will be determined by same methods in Section 4.3. Analogously, we apply theGVNS_operator (see Section 4.5) to the offspring to finally gain the candidate for further population updating. The principle of this operator is detailed in the procedure crossover (Algorithm 3).Algorithm 3:
Procedure crossover.
(
1
)
Input: Two parent solutions s
1
=
(
A
1
,
T
Q
1
), s
2
=
(
A
2,
T
Q
2
); Problem instance I
(
2
)
Output: The offspring s
o
=
(
A
o
,
T
Q
o
)
(
3
)
Set RA
:
=
V contains n tasks remaining to be assigned
resource to and n
u
m represents the size of R
A.
(
4
)
for
r
:
=
1
:
n
do
(
5
)
if
A
1
(
v
r
)
=
=
A
2
(
v
r
)
then
(
6
)
A
o
(
v
r
)
:
=
A
1
(
v
r
)
(
7
)
RA
:
=
RA
\
v
r
(
8
)
end if
(
9
)
end for
(
10
)
for
r
:
=
1
:
num
do
(
11
)
Assign randomly resource k
j
∈
K
r to v
r
(
12
)
end for
(
13
)
Obtain T
Q
o and refine the offspring s
o
=
(
A
o
,
T
Q
o
) in the
same way as Algorithm 2/∗Section 4.3∗/


### 4.5. GVNS_Operator

This section discusses the local optimization phase of GVNS_MA, a key part of memetic algorithm. Its function ensures an intensified search to locate high quality local optima from any starting point. Here we design a generable variable neighborhood search (GVNS) heuristic as the local refinement procedure which shows good performance compared to other variable neighborhood search variants in terms of local search capability.Given three neighborhood structuresN
1
,
N
2
,
N
3 and an initial solution (s
0), ourGVNS_operator does the refinement as follows. Attention, the quality of any solution is evaluated as depicted in Section 4.1. To start with, the sequential orderSO, which determines the applying sequence of these neighborhood structures is at random generated. For example, assuming that the sequenceSO equals (
3,1
,
2
), the search begins from N
3 and ends at N
1 at the given iteration. For each neighborhood structure, a new local optima s
′
′ is obtained by applying the corresponding local search procedures to the incumbent solution s
′, set at s
0 at the beginning of GVNS procedure. If s
′
′ is better than s
′, s
′ is updated with the new solution s
′
′, accepted as a descent to continue the local search for current neighborhood; otherwise the search turns to the next neighborhood structure inSO. One iteration terminates until the last neighborhood structure inSO is explored and then the search goes on with the next iteration until the stopping criteria is met; i.e., the best solution s
′ has not improved for α consecutive iterations. The general sketch ofGVNS operator is described in Algorithm 4, and the neighborhoods employed as well as the technique to calculate objective value rapidly are depicted in the following subsections.Algorithm 4:
GVNS_operator.
(
1
)
Input: Initial solution s
0; a set of neighborhood structures
N
k
(
k
=
1
,
.
.
.
,
3
); α
(
2
)
Output: The current best solution s
b found during GVNS
process
(
3
)
Calculate the objective value f
(
s
0
) according to the eval-
uation function in Section 4.1
(
4
)
s
′
←
s
0 /∗s
′ is the current solution ∗/
(
5
)
s
b
←
s
′ /∗s
b is the best solution found so far∗/
(
6
)
d
=
0 /∗d counts the consecutive iterations where s
′ is not
improved ∗/
(
7
)
repeat
(
8
)
Generate a random sequence (SO) to apply three
neighborhood structures
(
9
)
Apply the relevant mechanism (Section 4.5.1) in pre-
determined order specified by SO, update s
′ if a better
configuration is attained
(
10
)
if
f
(
s
′
)
<
f
(
s
b
)
then
(
11
)
s
b
←
s
′
(
12
)
reset the counter d
:
=
0
(
13
)
else
(
14
)
d
:
=
d
+
1
(
15
)
end if
(
16
)
until
d
=
=
α
(
17
)
return
s
b


#### 4.5.1. Move and Neighborhood

Three neighborhoodsN
k
(
k
=
1
,
…
,
3
) are adopted in GVNS_MA. The neighborhood N
1 is defined by the swap move operator which swaps two tasks processed by same resource and keeps previous task-to-resource assignment unchanged. As such given a solution s, the swap neighborhood N
1
(
s
) of s is composed of all possible configurations that can be applied with the swap move to s. The neighborhood N
2 is designed on the base of reversion which reverses all the tasks incorporated into two designated random tasks of one resource. As for the neighborhood N
3
(
s
), it is designed by the alter move operator which alters assigned resource from the original to another resource, equipped with demanded skill for one selected randomly task, with a random position in the task sequence of given resource. To efficiently assess the quality of any neighborhood solution, we devise a rapid evaluation technique for neighborhood solutions which is committed greatly to the computational efficiency of the GVNS-MA.


#### 4.5.2. Rapid Evaluation Mechanism

Our rapid evaluation technique to neighborhood solutions realizes through effectively calculating the move value (Δ
f) which identifies the change in the evaluation function f (see Section 4.1) of each possible move applicable to the incumbent solution s. It functions in the reduction of computational cost to evaluate any attainable neighborhood solution, inspired by the situation where the starting and finishing times of most tasks will not be changed when neighborhood solutions are generated.ForN
1 and N
2 generated by swap and reversion move, the set of tasks with changed starting and ending times only incorporate the elements ranking next to the isolated first task in the sequence of given resource. Without consideration of deterioration, only the elements located in the position between two picked tasks are influenced. As for N
3 achieved by alter move, all the tasks lined up behind the designated task in the sequence of its initial assigned resource and the new distributed one are included. Attention, for three moves we recalculate the relevant parameters of above-mentioned tasks and the rest are ignored. In addition, the impact that the new solutions is defying the precedence relationships to varying degrees will be respected in terms of M
∗
∑
(
i
,
j
)
∈
E
‍
δ
(
i
,
j
) in evaluation function f (see Section 4.1).


### 4.6. Updating population and PairSet

As illustrated in Algorithm1, the population P and thePairSet are updated when an excellent offspring is obtained through thecrossover operator and improved further byGVNS_operator. First of all, if it is better than the worst solution s
w in P, for any improved offspring solution s, the worst configuration s
w is replaced by the offspring solution s. When the population is updated, thePairSet should be updated accordingly: all pairs containing s
w solution are deleted from setPariSet and all pairs generated by combining s solution with others in P are incorporated intoPairSet.


## 4.1. Search Space and Evaluation Function

For a given problem, the GVNS-MA searches a spaceΩ composed of all possible assignments respecting skill constraints in any order of tasks, including both legal and illegal configurations. The size of the search space Ω is bounded by O
(
m
n
∗
2
n
).Based on preceding notations and depictions, to evaluate the quality of a candidate solutions
∈
Ω, we adopt an evaluation function which is defined as f
(
s
) induced by s: (10)
f
s
=
m
a
x
i
m
i
z
e
F
i
:
i
∈
V
+
M
∗
∑
i
,
j
∈
E
δ
i
,
j
(11)
δ
i
,
j
=
1
,
i
,
j
∈
E
,
S
j
<
F
i
0
,
o
t
h
e
r
w
i
s
e
∀
i
∈
V
,
j
∈
Vwhere M is a large positive constant such that M
→
∞ as n
→
∞. The first part of (10) represents the completion time of the last unfinished task, and the last part is an augmented penalty function where ∑
(
i
,
j
)
∈
E
‍
δ
(
i
,
j
) denotes the degree violation to precedence relationships. If δ
(
i
,
j
)
=
0 holds for any (
i
,
j
)
∈
E, it demonstrates the solution is feasible, corresponding to a legal configuration, and its evaluation function will all depend on the first part, equal to the completion time of the schedule. When a problem instance admits no solution able to satisfy δ
(
i
,
j
)
=
0, ∀
(
i
,
j
)
∈
E, the search space of GVNS-MA is empty and no feasible solution can be found. Given two solutions s
′ and s
′
′, s
′ is better than s
′
′ if f
(
s
′
)
≤
f
(
s
′
′
). This statement implies an assumption that a better solution has fewer precedence constraint violations.


## 4.2. Methodology and General Procedure

LetP denote a population of p candidate configurations. Let s
b
,
s
w represent the best solution attainable so far and the worst solution in P (in terms of the evaluation function in Section 4.1), respectively. Let P
a
i
r
S
e
t be a set of solution pairs (
s
i
,
s
j
) initially composed of all possible pairs in P. Next, the proposed GVNS-MA can be described as depicted in Algorithm 1.Algorithm 1:Main sketch of the proposed GVNS-MA.
(
1
)
Input: Problem instance I, the size of population
(p), the depth of GVNS α
(
2
)
Output: the best configuration found during the
search
(
3
)
P
=
{
s
1
,
...
,
s
p
}
← Population_initialization(I) /∗Sec-
tion 4.3∗/
(
4
)
P
a
i
r
S
e
t
←
{
(
s
i
,
s
j
)
:
1
≤
i
<
j
≤
p
}
(
5
)
while
P
a
i
r
S
e
t
≠
⌀
do
(
6
)
Isolate a solution pair (
s
i
,
s
j
)
∈
P
a
i
r
S
e
t ran-
domly
(
7
)
P
a
i
r
S
e
t
←
P
a
i
r
S
e
t
∖
{
(
s
i
,
s
j
)
}
(
8
)
s
c
← crossOver(
s
i
,
s
j
) /∗Section 4.4∗/
(
9
)
s
← GVNS_Operator(
s
c
,
α
) /∗Section 4.5∗/
(
10
)
if
f
(
s
)
≤
f
(
s
w
)
then
(
11
)
UpdatePopulation(
s
,
P
,
P
a
i
r
S
e
t
,
f
(
s
)
) /∗Sec-
tion 4.6∗/
(
12
)
end if
(
13
)
end while
(
14
)
Return s
b
← arg min {
f
(
s
i
)
:
i
=
1
,
...
,
p
}GVNS-MA first builds an initial populationP including p candidate configurations by the procedures in Section 4.3. Then, the algorithm enters into a while loop which constitutes the main part of the GVNS-MA. On each new generation, the subsequent operations are executed. In the first place, a configuration pair (
s
i
,
s
j
) is taken at random and deleted fromPairSet. Next, GVNS-MA builds, with a crossover operator (see Section 4.4), a new configuration s
c (the offspring). After that, the offspring is used as a starting point to further improve by the GVNS_operator (see Section 4.5). Finally, if the improved offspring s is better than the worst solution s
w in P, it is used to update the population P andPairSet. The detailed update operations are described in Section 4.6. The while loop continues untilPairSet becomes empty. At the end of the while loop, the algorithm terminates and returns the best configuration s
b found during the search. Note that the depth of GVNS α represents a maximum number between two iterations without improvement, regarded as the stopping criterion of the GVNS_operator.


## 4.3. Population Initialization

In order to build the initial population (in Algorithm2), the construction operator to generate a new solution is executed 3
×
p times. From the scratch, a new configuration is constructed as follows. The operator starts from assigning each task with a random resource satisfying skill constraint. Subsequently all tasks assigned to same resource are sequenced randomly at the end of previous task-to-resource phase. Then, for each generated solution, theGVNS_operator with the evaluation function f
(
s
) (see Section 4.1) is used to optimize it to a local optimum and the obtained p best configurations are selected to form the initial population. The detailed procedures are described in Algorithm 2.Algorithm 2:
Population_initialization.
(
1
)
Input: The set V
=
{
v
1
,
v
2
,
...
,
v
n
} of n tasks; the set K
=
{
k
1
,
k
2
,
.
.
.
,
k
m
} of m renewable resources; skill constraints;
precedence relationships and the size of population (p)
(
2
)
Output: The best p configurations
(
3
)
for  pop
=
1
:
3
p
do
(
4
)
Set RA
:
=
V
(
5
)
while
R
A
≠
⌀
do
(
6
)
Choose v
i randomly from R
A; remove v
i from R
A;
randomly isolate k
j
∈
K
i— the set covering all re-
sources can perform v
i and record this assignment
as A
(
v
i
)
:
=
j
(
7
)
end while
(
8
)
for
j
:
=
1
,
.
.
.
,
m
do
(
9
)
Generate a random task sequence T
Q
j for candidate
tasks assigned to k
j
(
10
)
end for
(
11
)
Calculate the objective value f
(
A,TQ
) with the evalu-
ation function f
(
s
) (see Section 4.1)
(
12
)
s
p
o
p
b
← GVNS_operator(
f
(
A,TQ
)
,
α
) /∗Section 4.5∗/
(
13
)
end for
(
14
)
Sort the 3
p configurations in an ascending sort of evalua-
tion function values and return the first p solutions as the
initial population.


## 4.4. The Crossover Operator

Within a memetic algorithm, the crossover operator is another essential ingredient whose main goal is to bring the search process to new promising search regions to diversify the search. In this paper, the offspring of two parent configurationss
1
=
(
A
1
,
T
Q
1
), s
2
=
(
A
2
,
T
Q
2
) shows as s
o
=
(
A
o
,
T
Q
o
). To inherit the advantages of parent solutions, the tasks assigned to same resource in s
1, s
2 are given priority to keep the task-to-resource assignment unchanged. As for the remain unassigned tasks and T
Q
0, they will be determined by same methods in Section 4.3. Analogously, we apply theGVNS_operator (see Section 4.5) to the offspring to finally gain the candidate for further population updating. The principle of this operator is detailed in the procedure crossover (Algorithm 3).Algorithm 3:
Procedure crossover.
(
1
)
Input: Two parent solutions s
1
=
(
A
1
,
T
Q
1
), s
2
=
(
A
2,
T
Q
2
); Problem instance I
(
2
)
Output: The offspring s
o
=
(
A
o
,
T
Q
o
)
(
3
)
Set RA
:
=
V contains n tasks remaining to be assigned
resource to and n
u
m represents the size of R
A.
(
4
)
for
r
:
=
1
:
n
do
(
5
)
if
A
1
(
v
r
)
=
=
A
2
(
v
r
)
then
(
6
)
A
o
(
v
r
)
:
=
A
1
(
v
r
)
(
7
)
RA
:
=
RA
\
v
r
(
8
)
end if
(
9
)
end for
(
10
)
for
r
:
=
1
:
num
do
(
11
)
Assign randomly resource k
j
∈
K
r to v
r
(
12
)
end for
(
13
)
Obtain T
Q
o and refine the offspring s
o
=
(
A
o
,
T
Q
o
) in the
same way as Algorithm 2/∗Section 4.3∗/


## 4.5. GVNS_Operator

This section discusses the local optimization phase of GVNS_MA, a key part of memetic algorithm. Its function ensures an intensified search to locate high quality local optima from any starting point. Here we design a generable variable neighborhood search (GVNS) heuristic as the local refinement procedure which shows good performance compared to other variable neighborhood search variants in terms of local search capability.Given three neighborhood structuresN
1
,
N
2
,
N
3 and an initial solution (s
0), ourGVNS_operator does the refinement as follows. Attention, the quality of any solution is evaluated as depicted in Section 4.1. To start with, the sequential orderSO, which determines the applying sequence of these neighborhood structures is at random generated. For example, assuming that the sequenceSO equals (
3,1
,
2
), the search begins from N
3 and ends at N
1 at the given iteration. For each neighborhood structure, a new local optima s
′
′ is obtained by applying the corresponding local search procedures to the incumbent solution s
′, set at s
0 at the beginning of GVNS procedure. If s
′
′ is better than s
′, s
′ is updated with the new solution s
′
′, accepted as a descent to continue the local search for current neighborhood; otherwise the search turns to the next neighborhood structure inSO. One iteration terminates until the last neighborhood structure inSO is explored and then the search goes on with the next iteration until the stopping criteria is met; i.e., the best solution s
′ has not improved for α consecutive iterations. The general sketch ofGVNS operator is described in Algorithm 4, and the neighborhoods employed as well as the technique to calculate objective value rapidly are depicted in the following subsections.Algorithm 4:
GVNS_operator.
(
1
)
Input: Initial solution s
0; a set of neighborhood structures
N
k
(
k
=
1
,
.
.
.
,
3
); α
(
2
)
Output: The current best solution s
b found during GVNS
process
(
3
)
Calculate the objective value f
(
s
0
) according to the eval-
uation function in Section 4.1
(
4
)
s
′
←
s
0 /∗s
′ is the current solution ∗/
(
5
)
s
b
←
s
′ /∗s
b is the best solution found so far∗/
(
6
)
d
=
0 /∗d counts the consecutive iterations where s
′ is not
improved ∗/
(
7
)
repeat
(
8
)
Generate a random sequence (SO) to apply three
neighborhood structures
(
9
)
Apply the relevant mechanism (Section 4.5.1) in pre-
determined order specified by SO, update s
′ if a better
configuration is attained
(
10
)
if
f
(
s
′
)
<
f
(
s
b
)
then
(
11
)
s
b
←
s
′
(
12
)
reset the counter d
:
=
0
(
13
)
else
(
14
)
d
:
=
d
+
1
(
15
)
end if
(
16
)
until
d
=
=
α
(
17
)
return
s
b


### 4.5.1. Move and Neighborhood

Three neighborhoodsN
k
(
k
=
1
,
…
,
3
) are adopted in GVNS_MA. The neighborhood N
1 is defined by the swap move operator which swaps two tasks processed by same resource and keeps previous task-to-resource assignment unchanged. As such given a solution s, the swap neighborhood N
1
(
s
) of s is composed of all possible configurations that can be applied with the swap move to s. The neighborhood N
2 is designed on the base of reversion which reverses all the tasks incorporated into two designated random tasks of one resource. As for the neighborhood N
3
(
s
), it is designed by the alter move operator which alters assigned resource from the original to another resource, equipped with demanded skill for one selected randomly task, with a random position in the task sequence of given resource. To efficiently assess the quality of any neighborhood solution, we devise a rapid evaluation technique for neighborhood solutions which is committed greatly to the computational efficiency of the GVNS-MA.


### 4.5.2. Rapid Evaluation Mechanism

Our rapid evaluation technique to neighborhood solutions realizes through effectively calculating the move value (Δ
f) which identifies the change in the evaluation function f (see Section 4.1) of each possible move applicable to the incumbent solution s. It functions in the reduction of computational cost to evaluate any attainable neighborhood solution, inspired by the situation where the starting and finishing times of most tasks will not be changed when neighborhood solutions are generated.ForN
1 and N
2 generated by swap and reversion move, the set of tasks with changed starting and ending times only incorporate the elements ranking next to the isolated first task in the sequence of given resource. Without consideration of deterioration, only the elements located in the position between two picked tasks are influenced. As for N
3 achieved by alter move, all the tasks lined up behind the designated task in the sequence of its initial assigned resource and the new distributed one are included. Attention, for three moves we recalculate the relevant parameters of above-mentioned tasks and the rest are ignored. In addition, the impact that the new solutions is defying the precedence relationships to varying degrees will be respected in terms of M
∗
∑
(
i
,
j
)
∈
E
‍
δ
(
i
,
j
) in evaluation function f (see Section 4.1).


## 4.5.1. Move and Neighborhood

Three neighborhoodsN
k
(
k
=
1
,
…
,
3
) are adopted in GVNS_MA. The neighborhood N
1 is defined by the swap move operator which swaps two tasks processed by same resource and keeps previous task-to-resource assignment unchanged. As such given a solution s, the swap neighborhood N
1
(
s
) of s is composed of all possible configurations that can be applied with the swap move to s. The neighborhood N
2 is designed on the base of reversion which reverses all the tasks incorporated into two designated random tasks of one resource. As for the neighborhood N
3
(
s
), it is designed by the alter move operator which alters assigned resource from the original to another resource, equipped with demanded skill for one selected randomly task, with a random position in the task sequence of given resource. To efficiently assess the quality of any neighborhood solution, we devise a rapid evaluation technique for neighborhood solutions which is committed greatly to the computational efficiency of the GVNS-MA.


## 4.5.2. Rapid Evaluation Mechanism

Our rapid evaluation technique to neighborhood solutions realizes through effectively calculating the move value (Δ
f) which identifies the change in the evaluation function f (see Section 4.1) of each possible move applicable to the incumbent solution s. It functions in the reduction of computational cost to evaluate any attainable neighborhood solution, inspired by the situation where the starting and finishing times of most tasks will not be changed when neighborhood solutions are generated.ForN
1 and N
2 generated by swap and reversion move, the set of tasks with changed starting and ending times only incorporate the elements ranking next to the isolated first task in the sequence of given resource. Without consideration of deterioration, only the elements located in the position between two picked tasks are influenced. As for N
3 achieved by alter move, all the tasks lined up behind the designated task in the sequence of its initial assigned resource and the new distributed one are included. Attention, for three moves we recalculate the relevant parameters of above-mentioned tasks and the rest are ignored. In addition, the impact that the new solutions is defying the precedence relationships to varying degrees will be respected in terms of M
∗
∑
(
i
,
j
)
∈
E
‍
δ
(
i
,
j
) in evaluation function f (see Section 4.1).


## 4.6. Updating population and PairSet

As illustrated in Algorithm1, the population P and thePairSet are updated when an excellent offspring is obtained through thecrossover operator and improved further byGVNS_operator. First of all, if it is better than the worst solution s
w in P, for any improved offspring solution s, the worst configuration s
w is replaced by the offspring solution s. When the population is updated, thePairSet should be updated accordingly: all pairs containing s
w solution are deleted from setPariSet and all pairs generated by combining s solution with others in P are incorporated intoPairSet.


## 5. Computational Experiments and Results

This section plans to assess the proposed method GVNS-MA through having comparisons with the state-of-the-art methods in the literature. For the lack of known benchmark data for handing MS-RCPSPLD, we firstly apply the proposed GVNS-MA to solve the MS-RCPSP on exist benchmark instances in favor of argument its effectiveness. Then, on this basis the GVNS-MA will be examined on the modified problem set.


### 5.1. Benchmark Instances

For the purpose of assessing GVNS-MA fully and comprehensively, computational experiments will be conducted on two sets of instances, where the first set is composed of 30 benchmark instances irrespective of deterioration and its available in Myszkowski et al. [46], which are artificially created in a base of real world, obtained from the Volvo IT Department in Wroclaw. The full information of each instance, including tasks durations, resource capabilities, or precedence between tasks, has been given. As for the other set, it consists of 45 instances generated with some modifications on first set to consider the linear deterioration. The detail will be described in Section 5.4.


### 5.2. Parameter Settings and Experiment Protocol

Our GVNS-MA was programmed in MATLAB R2015b and all the reported computational experiments presented below were executed on a personal computer equipped with an Intel Core i3 processor (3.10 GHz CPU and 2GB RAM) in the environment of Windows 7 OS. To eliminate the randomness as much as possible, twenty replications for each instance are carried out.Table1 shows the descriptions and settings of the parameters adopted in GVNS-MA, determined by preliminary experiments. Our memetic algorithm rests upon only three parameters: the population size p, the depth of general variable neighborhood search α, and the price for a violation to precedence constraint M. For p and α, we follow Lai and Hao [55] and set p
=
10, α
=
50000 while the parameter M is set at 1000 for the first experimental group and 1
×
1
0
7 for the second.Table 1
Settings of important parameters.
Parameters
Section
Description
Values
p
Section4.2
population size forGVNS-MA
10
α
Section4.5
depth of GVNS
50 000
M
Section4.1
penalty value for a violation
1000, 1
×
1
0
7
to precedence constraint


### 5.3. Experimental Results without Deterioration

Our first experimental group aims to evaluate the performance of our GVNS-MA on the set of 30 known instances with at most 200 tasks and 40 renewable resources. Without regard to deterioration, it means that the GVNS-MA will set the deteriorating rates of all tasks at0 when it deals with the relevant computations. Table 2 records the computational results solved by the GVNS-MA with the goal of duration optimization, as well as the results achieved by other reference algorithms in the literature.Table 2
Comparison of the GVNS-MA with other algorithms on known MS-RCPSP dataset [48]. Best results are indicated in italic.
instances
f
p
r
e
b
DEGR
GRASP
GVNS-MA
R
P
D
(
%
)
f
b
e
s
t
f
a
v
g
T
i
m
e
(
s
)
100-10-26-15
236
236
250
237
242.6
191.78
-0.42
100-10-47-9
256
256
263
253
256.8
124.90
1.17
100-10-48-15
247
247
255
245
250.9
175.05
0.81
100-10-64-9
250
250
254
247
257.1
165.36
1.20
100-10-64-15
248
248
256
246
250.6
173.17
0.81
100-20-22-15
134
134
134
133
137.6
149.53
0.75
100-20-46-15
164
164
170
160
163.2
137.70
2.44
100-20-47-9
138
138
180
132
139.4
128.70
4.35
100-20-65-15
213
240
213
193
198.0
103.17
9.39
100-20-65-9
134
134
134
134
140.0
138.93
0.00
100-5-22-15
484
484
503
483
484.0
131.64
0.21
100-5-46-15
529
529
552
528
533.1
189.48
0.19
100-5-48-9
491
491
509
489
490.5
134.45
0.41
100-5-64-15
483
483
501
480
482.3
146.27
0.62
100-5-64-9
475
475
494
474
475.2
162.61
0.21
200-10-128-15
462
462
491
479
499.0
746.32
-3.68
200-10-50-15
488
488
522
488
500.6
895.29
0.00
200-10-50-9
489
489
506
487
493.2
793.34
0.41
200-10-84-9
517
517
526
509
514.0
719.20
1.55
200-10-85-15
479
479
486
477
481.8
561.76
0.42
200-20-145-15
245
245
262
252
271.0
660.08
-2.86
200-20-54-15
270
270
304
291
303.4
847.46
-7.78
200-20-55-9
257
262
257
257
263.0
639.97
0.00
200-20-97-15
336
336
347
334
338.2
724.57
0.60
200-20-97-9
253
253
253
253
258.1
716.20
0.00
200-40-133-15
159
159
163
157
165.0
772.82
1.26
200-40-45-15
164
164
164
159
163.6
565.58
3.05
200-40-45-9
144
168
144
144
152.0
626.53
0.00
200-40-90-9
145
160
145
145
149.4
654.24
0.00
200-40-91-15
153
153
153
153
157.6
624.01
0.00
#B
e
s
t
8
6
26
#T
o
t
a
l
30
30
30
#A
v
e
r
a
g
e
0.50Notice that the instance name (columns 1) contains its full description. Take the instance named 100-10-26-15 as example, the number100 represents the number of tasks included and 10 denotes the quantity of renewable resources provided. As for the number 26 and 15, it illustrates the amount of precedence relationships and the number of different introduced skills. Column 2 of Table 2 indicates the previous minimum objective values (f
p
r
e
b) in the literature which are compiled from the best solutions yield by two recent and best performing algorithms, namely, GRASP [48] and DEGR [49]. Columns 3 to 4 give the best results obtained by DEGR and GRASP. The corresponding results of the GVNS-MA are given in columns 5 to 7, including the minimum objective value (f
b
e
s
t) over 20 independent runs, the average objective value (f
a
v
g), and the average computing time in seconds (Time(s)) to reach f
b
e
s
t. The rowBest indicates a total number of instances where the specific method achieves optimal among three algorithms. The best one is indicated in italic. In addition, to verify whether there exists an essential difference between the best results of GVNS-MA and other reference algorithms, the relative percentage deviation (RPD) is defined by the equation (12)
R
P
D
%
=
f
p
r
e
b
-
f
b
e
s
t
f
p
r
e
b
×
100where a positive value of R
P
D means an improvement of result achieved by GVNS-MA while the negative number represents a worse solution.Table2 discloses that the outcomes from our GVNS-MA are noteworthy compared to the state-of-the-art results in the literature. GVNS-MA improves the previous best known results for 19 instances and matches for 7 cases. Compared with the 8 out of 30 cases solved by DEGR and 6 best solutions achieved by GRASP, these data clearly indicate the superiority of GVNS-MA compared to the previous excellent methods. Additionally, it can be observed that the improvement achieved by GVNS-MA is up to 9.39
%, for instance 100-20-65-15, accompanying that the average R
P
D
(
%
) equals to 0.50
%.


### 5.4. Experimental Results with Linear Deterioration

The previous comparisons and discussions in Section5.3 demonstrate the advantages of GVNS-MA in solving the related issues of MS-RCPSP. In this section, the aforementioned dataset with some modifications is used to assess the capability of GVNS-MA to solve the MS-RCPSPLD. The procedures of generating the testing instances and analysis of the results are described below. To make the benchmark instances meet the considered linear deterioration precisely, the deterioration rate (d
r
i) for task i
,
(
i
∈
V
) is generated randomly from three intervals 0,0.5, [
0.5,1
] and (
0,1
], similar to Cheng et al. [19], to shed light on the influence of the different value range of deterioration rate on its effectiveness.Since the extra included deterioration rate, we provide two additional heuristics for the initial population generation of GVNS-MA. Both the two methods affect the phase of generatingT
Q
j, determining the sequence of tasks assigned to resource j
,
j
∈
K. The first heuristic considers the sequence in descending order of deterioration rate (h) while the other rests upon an ascending order of ratio (a
/
h) of the basic processing time and deterioration rate. The methods adopting the former and latter heuristic to population initialization are dubbedGVNS-
M
A
h andGVNS-
M
A
a
h, respectively.Here, instances with 100 tasks from Myszkowski et al. [46] are isolated to attain the researched objects which fit with the unique nature of the MS-RCPSPLD more. To account for the three intervals from which the deterioration rate is drawn, 3 extended cases are needed to solve for each instance. For convenience, these instances are denoted by adding a suffix for identification to different intervals. For example, 100-10-26-15_1 represents the original case 100-10-26-15 is modified by adding the deterioration rates produced in (
0,0.5
] to the durations of tasks. In total, there are 45
(
3
×
15
) instances randomly generated.Due to zero known results in literature for same dataset, the improved tabu search (ITS) proposed by Dai et al. [54], who discussed the MS-RCPSP under step deterioration, and a path relinking algorithm (PR) [55], based on the population path relinking framework, are programmed as reference algorithms.Table3 reports the computational results achieved by the ITS, PR, GVNS-MA, GVNS-M
A
h, and GVNS-M
A
a
h on the set of 45 benchmark instances. f
b
e
s
t denotes the minimum objective value and f
a
v
g is computed as the average objective value of 20 runs.Table 3
Summary and comparison on the set of 45 new generated instances withn
=
100, of GVNS-MA, GVNS-
M
A
h, GVNS-
M
A
a
h, and the TS heuristic [54] and PR [55]. Best results are indicated in italic.
instances
ITS
PR
GVNS-MA
GVNS-
M
A
h
GVNS-
M
A
a
h
f
b
e
s
t
f
a
v
g
T
i
m
e
(
s
)
f
b
e
s
t
f
a
v
g
T
i
m
e
(
s
)
f
b
e
s
t
f
a
v
g
T
i
m
e
(
s
)
f
b
e
s
t
f
a
v
g
T
i
m
e
(
s
)
f
b
e
s
t
f
a
v
g
T
i
m
e
(
s
)
100-10-26-15_1
655.72
659.81
389.99
636.46
649.26
687.1
632.74
639.23
309.26
619.67
637.97
306.98
626.32
636.29
294.22
100-10-26-15_2
6013.96
6184.16
286.07
6089.71
6254.36
792.83
5871.45
6139.34
374.96
5805.57
6154.74
238.79
5727.94
6151.56
348.26
100-10-26-15_3
1728.56
1841.75
312.36
1646.96
1755.13
597.76
1602.83
1693.6
222.25
1662.21
1712.4
175.41
1638.98
1722.28
346.1
100-10-47-9_1
700.8
720.53
403.04
697.44
712.32
1001.8
694.45
700.98
206.66
676.45
691.57
314.99
696.73
703.9
363.14
100-10-47-9_2
7003.52
7392.87
391.12
7034.39
7211.52
705.63
6722.21
7151.38
241.79
6723.04
6959
206.14
6935.53
7023.69
251.14
100-10-47-9_3
1882.06
1952.06
481.68
1835.8
1908.63
934.63
1741.62
1843.89
300.08
1773.23
1839.58
193.83
1737.08
1833.68
414.32
100-10-48-15_1
658.68
691.41
399.15
670.93
689.08
887.91
648.51
655.26
349.16
632.53
665.95
226.86
647.98
661.02
266.62
100-10-48-15_2
6387.47
6598.09
420.43
6213.57
6587.47
911.61
6186.7
6516.09
411.61
5904.32
6254.62
270.97
6185.07
6346.32
336.55
100-10-48-15_3
1709.99
1742.32
296.59
1718.64
1780.61
733.95
1594.97
1668.87
233.95
1614.83
1663.66
321.69
1635.01
1702.73
270.56
100-10-64-9_1
705.27
757.25
377.03
710.49
769.27
730.24
687.22
709.29
312.87
688.4
712.15
260.24
678.94
696.82
277.56
100-10-64-9_2
7058.06
7447.75
394.15
7040.32
7381.41
627.94
6637.29
7111.14
301.39
6842.1
7191.53
228.06
6967.27
7368.33
399.18
100-10-64-9_3
1938.44
2062.06
311.53
2006.42
2044.03
1089.18
1893.24
1944.5
354.15
1808.42
2008.42
310.4
1938.44
1999.96
318.71
100-10-64-15_1
701.19
714.97
346.26
710.75
727.96
835.43
693.46
700.22
390.97
669.1
691.12
212.49
700.42
707.96
171.16
100-10-64-15_2
6909.64
7447.75
389.98
6725.78
7282.3
616.84
6606.14
6850.85
224.91
6282.3
6829.57
317.84
6263.31
6664.18
237.6
100-10-64-15_3
1938.44
2185.06
318.71
1942.47
2042.35
713.18
1806.92
1860.08
253.36
1871.49
1925.56
454.38
1855.85
1909.57
252.96
100-20-22-15_1
190.89
193.55
296.31
193.6
197.39
551.76
188.83
191.18
222.2
185.72
189.8
214.38
187.8
189.65
247.42
100-20-22-15_2
461.58
477.31
368.54
460.32
467.14
679.26
453.71
460.08
284.55
452.18
466.27
289.26
458.33
463.3
231.24
100-20-22-15_3
263.28
279.81
285.28
272.12
269.73
697.29
259.7
264.19
281.2
255.63
259.18
175.31
255.75
262.54
213.52
100-20-46-15_1
262.43
267.3
334.24
262.14
266.31
603.54
258.62
263.29
411.99
255.11
258.96
121.53
254.76
260.06
174.66
100-20-46-15_2
606.47
662.44
344.08
593.67
635.96
718.78
579.61
616.5
172.16
565.42
594.2
266.96
546.5
592.85
223.13
100-20-46-15_3
324.21
349.09
375.23
335.39
341.79
776.34
316.95
329.09
164.33
316.51
332.63
291.16
328.41
333.49
279.1
100-20-47-9_1
190.07
197.59
290.27
191.63
196.85
577.63
188.64
191.2
283.11
187.47
192.69
273.2
184.55
188.92
307.31
100-20-47-9_2
505.91
534.81
371.19
478.39
514..84
1021.73
480.3
493.19
354.9
462.78
487.64
354.18
449.66
478.93
242.41
100-20-47-9_3
308.02
318.27
457.26
306.31
313.65
699.58
294.37
303.52
578.46
277.12
294.58
297.37
283.99
287.99
275.59
100-20-65-15_1
901.34
924.46
264.13
898.65
905.43
679.57
888.01
900.95
175.05
868.26
895.18
150.52
873.05
893.38
284.3
100-20-65-15_2
2538.99
2606.76
287.18
2501.26
2532.67
587.63
2447.62
2503.16
409.97
2434.49
2475.1
176.59
2423.53
2449.44
257.35
100-20-65-15_3
1105.67
11158.86
274.91
1098.74
1136.85
534.18
1052.15
1092.24
251.38
1085.95
1112.43
159.11
1048.29
1067.76
141.26
100-20-65-9_1
191.13
197.83
412.48
189.57
195.48
795.61
183.69
188.98
305.61
186.97
191.46
189.6
186.94
192.65
309.79
100-20-65-9_2
462.42
477.68
654.69
459.34
474.43
581.12
449.57
462.29
176.8
447.19
459.85
223.24
455.93
465.91
306.06
100-20-65-9_3
280.18
287.76
489.43
275.12
281.08
685.32
271.9
277.21
242.79
265.87
276.91
310.1
264.55
278.45
247.3
100-5-22-15_1
5009.88
5142.85
289.78
5102.85
5050.98
845.26
4865.86
4993.18
435.29
4943.64
5009.88
184.44
4985.67
5102.85
223.35
100-5-22-15_2
1193440
1227080
431.94
1192300
1210150
615.37
1118610
1199248
243.22
1184940
1219514
206.64
1138490
1226780
266.56
100-5-22-15_3
66394.7
70081.8
569.12
66155.3
79262.7
799.76
60632.2
65262.7
106.39
59250.9
62793.04
261.98
64385.6
65975.26
172.67
100-5-46-15_1
6757.39
7497.63
367.97
6527.93
7014.57
1378.62
6350.3
6796.63
507.58
6369.03
6879.41
298.88
6491.64
6719.82
362.02
100-5-46-15_2
1404680
1453430
585.95
1443529
1470970
1085.95
1298430
1370870
265.64
1315940
1360830
235.36
1332210
1399014
241.76
100-5-46-15_3
79566.4
87031.3
506.87
79777.13
8635.67
689.11
74017.8
79651.28
179.24
75586.6
77860.62
168.09
75256.8
80128
187.63
100-5-48-9_1
5637.87
5868.32
312.14
5666.27
783.86
848.07
5520.6
5604.07
241.5
5520.6
5636.64
250.18
5542.99
5665.7
249.52
100-5-48-9_2
1284230
1315720
361.45
1289811
1364650
712.86
1222350
1285020
279.58
1163860
1259332
281.22
1233010
1268572
346.59
100-5-48-9_3
68429.9
69245.3
453.35
66785
71727.92
939.38
65727.9
67622
456.1
66042.6
67091.7
412.86
64822
66721.38
284.46
100-5-64-15_1
5819.16
6273.74
556.61
5765.89
6181.67
1024.15
5544.26
5792.34
351.67
5465.43
5903.52
296.78
5694.2
5801.75
566.19
100-5-64-15_2
1209440
1261510
312.96
1190830
1257643
1235.33
1131450
1183014
405.95
1118430
1151812
463.05
1047250
1158556
333.7
100-5-64-15_3
64226.7
70960.2
349.88
63465.1
68888.9
894.03
61285.7
66578.58
379.85
62677.1
66061.44
459.11
62475.3
67499.62
616.23
100-5-64-9_1
5502.31
5775.24
373.65
5544.81
5667,47
986.93
5281.77
5404.36
339.3
5307.48
5438.95
483.96
5159.84
5367.47
299.32
100-5-64-9_2
1214340
1271610
405.53
1183479
1236750
1199.27
1114060
1155584
415.23
1164010
1201126
402.87
1121650
1159384
272.86
100-5-64-9_3
61035.6
64876.5
363.95
61515.02
63232.3
874.48
60458.6
62103.78
313.63
59451.4
61715.02
305.43
59519.1
62322.3
277.49
#B
e
s
t
0
0
0
0
15
14
17
16
14
15
#T
o
t
a
l
45
45
45
45
45
45
45
45
45
45First, Table3 discloses that the solutions obtained by GVNS-MA, GVNS-M
A
h, and GVNS-M
A
a
h are better than the ITS and PR for any instance from the perspective of both quality of schedule and runtime. To some extent these results demonstrated the differences between linear deterioration and step deterioration and the superiority of memetic algorithm framework. Second, these three methods, differing in the sort order of tasks in initialize phase, behave similarly where GVNS-MA obtains the best 15 out of 45 instances, 17 for GVNS-M
A
h, and 14 for G
V
N
S
a
h in terms of f
b
e
s
t. Specifically, GVNS-MA and GVNS-M
A
h attain the optimal simultaneously for the instance 100-5-48-9-1. From a view point of f
a
v
g and run time, three methods also have a balanced performance. Third, as far as three different intervals to generate deterioration rate are concerned, the phenomenon did not happen that the relevant algorithms display strikingly different behavior. In other words, the performance of the proposed algorithm is not sensitive to the setting of deterioration rate.


### 5.5. Analysis and Discussions

In this section, we study two essential ingredients of the proposed GVNS-MA to get an insight to its performance. One is the rapid evaluation mechanism; the other is the role of the memetic framework.


#### 5.5.1. Importance of Rapid Evaluation Mechanism

GVNS-MA with rapid evaluation mechanism only calculates the relevant parameters of some particular tasks rather than all when the procedure computes the objective value of a neighborhood solution. To highlight the key role of the rapid evaluation mechanism, two sets of comparison experiments are carried out on generated dataset with two algorithms, GVNS-MA and GVNS-M
A
0, including same ingredients with GVNS-MA except for the computation of objective value. When GVNS-M
A
0 figures up the value of a neighborhood solution, it computes all relevant parameters again.Table4 records the experimental results carried out on the dataset [46] without consideration of deterioration, whereas Table 5 shows the comparisons of GVNS-MA and GVNS-M
A
0 about the set of 15 instances generated in Section 5.4 on account of the indiscrimination in three intervals. Column 2 and 5 record the best attained by two algorithms. Column 3 and 6 indicate the minimum time cost to a final feasible schedule with one run of procedure. Note that the best objective value cannot be guaranteed as the output of shortest runtime. As for the parameters in column 4 and 7, they represent the mean runtime. Finally, two parameters D
E
V
s
h
o
r
t
e
s
t and D
E
V
a
v
g are used to disclose the runtime deviation of two methods, defined by equations(13)
D
E
V
s
h
o
r
t
e
s
t
%
=
T
s
h
o
r
t
e
s
t
1
-
T
s
h
o
r
t
e
s
t
2
T
s
h
o
r
t
e
s
t
1
×
100and (14)
D
E
V
a
v
g
%
=
T
a
v
g
1
-
T
a
v
g
2
T
a
v
g
1
×
100respectively. The positive value of D
E
V
s
h
o
r
t
e
s
t
(
%
) and D
E
V
a
v
g
(
%
) means that GVNS-M
A
0 has better performance and negative value tells GVNS-MA is prior to GVNS-M
A
0 in terms of time cost. And the rowsBetter andWorse, respectively, show the number of instances for which the corresponding results of the associated algorithm are better and worse than the other.Table 4
Summary and comparison of GVNS-MA and GVNS-M
A
0 on known MS-RCPSP dataset [46].
instances
GVNS-MA
GVNS-M
A
0
D
E
V
s
h
o
r
t
e
s
t
(
%
)
D
E
V
a
v
g
(
%
)
f
b
e
s
t
T
s
h
o
r
t
e
s
t
1
T
a
v
g
1
f
b
e
s
t
T
s
h
o
r
t
e
s
t
2
T
a
v
g
2
100-10-26-15
237
134.58
191.78
237
155.41
240.93
-15.48
-25.63
100-10-47-9
253
107.90
124.90
253
112.59
155.26
-4.35
-24.31
100-10-48-15
245
148.01
175.05
245
174.61
215.94
-17.97
-23.36
100-10-64-9
247
142.61
165.36
247
162.58
216.63
-14.00
-31.01
100-10-64-15
246
104.49
173.17
246
121.29
222.18
-16.08
-28.30
100-20-22-15
133
129.46
149.53
133
145.47
176.29
-12.37
-17.90
100-20-46-15
160
106.16
137.70
160
121.39
175.66
-14.35
-27.57
100-20-47-9
132
114.82
128.70
132
142.51
174.44
-24.12
-35.54
100-20-65-15
193
97.82
103.17
193
113.01
129.22
-15.53
-25.25
100-20-65-9
134
112.29
138.93
134
126.16
159.56
-12.35
-14.85
100-5-22-15
483
105.73
131.64
483
120.40
167.90
-13.87
-27.54
100-5-46-15
528
160.97
189.48
528
182.98
221.45
-13.67
-16.87
100-5-48-9
489
114.20
134.45
489
134.52
146.37
-17.79
-8.87
100-5-64-15
480
122.67
146.27
480
164.45
202.54
-34.06
-38.47
100-5-64-9
474
124.63
162.61
474
154.10
206.64
-23.65
-27.08
200-10-128-15
479
657.93
746.32
479
801.41
902.58
-21.86
-20.94
200-10-50-15
488
835.5
895.29
488
913.44
984.38
-9.33
-9.95
200-10-50-9
487
744.07
793.34
487
820.27
818.20
-10.24
-3.13
200-10-84-9
509
668.63
719.20
509
725.68
862.85
-8.53
-19.97
200-10-85-15
477
500.61
561.76
477
561.76
688.83
-12.22
-22.62
200-20-145-15
252
534.14
660.08
252
590.08
715.30
-10.47
8.37
200-20-54-15
291
745.02
847.46
291
785.80
967.01
-5.47
-14.11
200-20-55-9
257
577.67
639.97
257
622.39
713.94
-7.74
-11.56
200-20-97-15
334
592.01
724.57
334
666.73
749.14
-12.62
-3.39
200-20-97-9
253
565.37
716.20
253
683.70
809.50
-20.93
13.03
200-40-133-15
157
682.28
772.82
157
720.41
844.72
-5.59
-9.30
200-40-45-15
159
476.09
565.58
159
511.30
615.16
-7.40
-8.77
200-40-45-9
144
571.43
626.53
144
615.48
700.62
-7.71
-11.83
200-40-90-9
145
616.23
654.24
145
683.97
738.17
–10.99
-12.83
200-40-91-15
153
588.02
624.01
153
664.87
760.05
-13.07
-21.80
#B
e
t
t
e
r
30
28
0
2
#W
o
r
s
e
0
2
30
28
#T
o
t
a
l
30
30
30
30
#A
v
e
r
a
g
e
-13.79
-18.80Table 5
Comparison of results of GVNS-MA and GVNS-M
A
0 on the set of 45 new generated instances in Section 5.4.
instances
GVNS-MA
GVNS-M
A
0
D
E
V
s
h
o
r
t
e
s
t
(
%
)
D
E
V
a
v
g
(
%
)
f
b
e
s
t
T
s
h
o
r
t
e
s
t
1
T
a
v
g
1
f
b
e
s
t
T
s
h
o
r
t
e
s
t
2
T
a
v
g
2
100-10-26-15_1
632.74
146.08
274.99
635.08
163.91
309.99
-12.21
-12.73
100-10-47-9_1
694.45
206.66
349.51
696.66
197.36
364.15
4.50
-4.19
100-10-48-15_1
648.51
193.34
286.55
649.11
174.83
244.17
9.57
14.79
100-10-64-9_1
687.22
222.47
312.41
678.09
191.71
348.78
13.83
-11.64
100-10-64-15_1
693.46
192.91
309.49
673.75
190.47
297.09
1.26
4.01
100-20-22-15_1
188.83
161.71
256.15
187.22
146.31
225.34
9.52
12.03
100-20-46-15_1
258.62
154.94
240.39
256.60
142.55
228.86
8.00
4.80
100-20-47-9_1
188.64
222.79
258.72
182.12
252.05
293.80
-13.13
-13.56
100-20-65-15_1
888.01
172.61
207.43
870.85
220.43
187.68
-27.70
9.52
100-20-65-9_1
183.69
237.32
354.53
188.66
264.17
333.25
-11.31
6.00
100-5-22-15_1
4865.86
184.44
270.23
4866.02
224.41
295.76
-21.67
-9.45
100-5-46-15_1
6350.3
264.37
457.83
6720.42
270.03
488.58
-2.14
-6.72
100-5-48-9_1
5520.60
154.46
264.23
5520.60
189.28
311.00
-22.54
-17.70
100-5-64-15_1
5544.26
338.39
413.58
5555.52
322.48
461.02
4.70
-11.47
100-5-64-9_1
5281.77
222.77
323.46
5287.14
200.70
350.71
9.91
-8.42
#B
e
t
t
e
r
7
9
8
6
#W
o
r
s
e
8
6
7
9
#T
o
t
a
l
15
15
15
15
#A
v
e
r
a
g
e
-3.29
-2.98The results summarized in Table4 disclose that the GVNS-MA has an overwhelming advantage over GVNS-M
A
0 in terms of the computation time to solve MS-RCPSP, leaving out the deterioration effect. Indeed, the shortest runtime T
s
h
o
r
t
e
s
t
1 of the GVNS-MA method is better than the shortest runtime T
s
h
o
r
t
e
s
t
2 of GVNS-M
A
0 for 30 out of 30 representative instances, and the average runtime T
a
v
g
1 is better for 28 out of 30 instances. Meanwhile, the average value of D
E
V
s
h
o
r
t
e
s
t
(
%
) equals -13.79%, accompanying with a high of -18.80 percent in D
E
V
a
v
g
(
%
).However, focusing on Table5, the results of two approaches are neck and neck, and GVNS-MA lost its early superiority in MS-RCPSP. In terms of shortest runtime, GVNS-MA successes for 7 out of 15 tested instances while GVNS-M
A
0 reaches optimal for the remain. As for average runtime, GVNS-MA performs better for 9 out of 15 examples and GVNS-M
A
0 achieves reversion in others 6 instances. With these data it will be hard to judge the true benefits of one approach versus the other.To figure out the reason of this phenomenon, we should come back to the inner rationale of rapid evaluation mechanism. When GVNS-MA computes the completion time of a neighborhood solution, it only recalculates the tasks’ related parameters influenced by the particular move. In MS-RCPSP, a move including swap, reverse, and alter will affect just a small number of tasks. But for MS-RCPSPLD instances, any move can cumulatively effect on a large proportion of tasks because of the existing deterioration. Consequently, the runtime saved in computing some unchanged parameters may not make up for the time spent on isolating the changed tasks.These experimental results confirm that although the rapid evaluation mechanism is not so critical for MS-RCPSPLD, it is still quite useful to quickly solve MS-RCPSP instances and constitutes a significant element of the proposed GVNS-MA.


#### 5.5.2. Influence of the Memetic Framework

As shown in Lei et al. [16]; Mladenovićabcd [15], the GVNS approach has shown great performance in a widespread academic application. So it is meaningful to research whether our GVNS-MA has a significant advantage over the originally efficient GVNS algorithm. For this reason, a comparative test between GVNS and GVNS-MA has been carried out. For this experiment, we used the known dataset [46], with 20 times running for each instance. Same with GVNS-MA, the stopping criteria of GVNS is met when the maximum number between two iterations without improvement reaches 5
×
1
0
4. The experimental results of two methods are recorded in Table 6 where D
E
V
(
%
)
=
(
f
-
f
m
i
n
)
/
f
m
i
n
×
100, and the other symbols have same meanings as those of Table 2. As for the f ad f
m
i
n in the equation, they denote the objective value of the best schedule solved by the particular algorithm and the best value attainable until now, respectively. The parameterDEV
(
%
) can visually detect the gap between the current algorithm and the best.Table 6
Summary and comparison of GVNS-MA and GVNS on known MS-RCPSP dataset [46].
instances
GVNS-MA
GVNS
f
b
e
s
t
1
D
e
v
(
%
)
f
b
e
s
t
2
D
e
v
(
%
)
100-10-26-15
237
0.00
260
9.70
100-10-47-9
253
0.00
255
0.79
100-10-48-15
245
0.00
255
4.08
100-10-64-9
247
0.00
257
4.05
100-10-64-15
246
0.00
248
0.81
100-20-22-15
133
0.00
142
6.77
100-20-46-15
160
0.00
161
0.63
100-20-47-9
132
0.00
134
1.52
100-20-65-15
193
0.00
205
6.22
100-20-65-9
134
0.00
142
5.97
100-5-22-15
483
0.00
486
0.62
100-5-46-15
528
0.00
580
9.85
100-5-48-9
489
0.00
493
0.82
100-5-64-15
480
0.00
494
2.92
100-5-64-9
474
0.00
477
0.63
200-10-128-15
479
0.00
501
4.59
200-10-50-15
488
0.00
516
5.74
200-10-50-9
487
0.00
509
4.52
200-10-84-9
509
2.21
498
0.00
200-10-85-15
477
0.00
494
3.56
200-20-145-15
252
0.00
285
13.10
200-20-54-15
291
0.00
303
4.12
200-20-55-9
257
0.00
267
3.89
200-20-97-15
334
0.00
347
3.89
200-20-97-9
253
0.00
282
11.46
200-40-133-15
157
0.00
181
15.29
200-40-45-15
159
0.00
164
3.14
200-40-45-9
144
0.00
176
22.22
200-40-90-9
145
0.00
173
19.31
200-40-91-15
153
0.00
160
4.58
#B
e
t
t
e
r
29
1
#E
q
u
a
l
0
0
#W
o
r
s
e
1
29
#T
o
t
a
l
30
30
#A
v
e
r
a
g
e
0.07
5.83Obviously, Table6 demonstrates that the GVNS-MA significantly outperforms the GVNS algorithm in general. First, compared with the GVNS algorithm, the GVNS-MA obtains better and worse results in terms of the minimum objective value on 29 and 1 instances, respectively. Second, it can be seen that the obtained averageDevs are 0.07% and 5.83%, respectively, for the GVNS-MA and GVNS, implying that there exists a huge difference between two methods. Third, the runtimes of PR are obviously longer than GVNS-MA with worse solutions. These outcomes indicate that the memetic part of the proposed GVNS-MA is very appropriate for solving the related issue of MS-RCPSP.


## 5.1. Benchmark Instances

For the purpose of assessing GVNS-MA fully and comprehensively, computational experiments will be conducted on two sets of instances, where the first set is composed of 30 benchmark instances irrespective of deterioration and its available in Myszkowski et al. [46], which are artificially created in a base of real world, obtained from the Volvo IT Department in Wroclaw. The full information of each instance, including tasks durations, resource capabilities, or precedence between tasks, has been given. As for the other set, it consists of 45 instances generated with some modifications on first set to consider the linear deterioration. The detail will be described in Section 5.4.


## 5.2. Parameter Settings and Experiment Protocol

Our GVNS-MA was programmed in MATLAB R2015b and all the reported computational experiments presented below were executed on a personal computer equipped with an Intel Core i3 processor (3.10 GHz CPU and 2GB RAM) in the environment of Windows 7 OS. To eliminate the randomness as much as possible, twenty replications for each instance are carried out.Table1 shows the descriptions and settings of the parameters adopted in GVNS-MA, determined by preliminary experiments. Our memetic algorithm rests upon only three parameters: the population size p, the depth of general variable neighborhood search α, and the price for a violation to precedence constraint M. For p and α, we follow Lai and Hao [55] and set p
=
10, α
=
50000 while the parameter M is set at 1000 for the first experimental group and 1
×
1
0
7 for the second.Table 1
Settings of important parameters.
Parameters
Section
Description
Values
p
Section4.2
population size forGVNS-MA
10
α
Section4.5
depth of GVNS
50 000
M
Section4.1
penalty value for a violation
1000, 1
×
1
0
7
to precedence constraint


## 5.3. Experimental Results without Deterioration

Our first experimental group aims to evaluate the performance of our GVNS-MA on the set of 30 known instances with at most 200 tasks and 40 renewable resources. Without regard to deterioration, it means that the GVNS-MA will set the deteriorating rates of all tasks at0 when it deals with the relevant computations. Table 2 records the computational results solved by the GVNS-MA with the goal of duration optimization, as well as the results achieved by other reference algorithms in the literature.Table 2
Comparison of the GVNS-MA with other algorithms on known MS-RCPSP dataset [48]. Best results are indicated in italic.
instances
f
p
r
e
b
DEGR
GRASP
GVNS-MA
R
P
D
(
%
)
f
b
e
s
t
f
a
v
g
T
i
m
e
(
s
)
100-10-26-15
236
236
250
237
242.6
191.78
-0.42
100-10-47-9
256
256
263
253
256.8
124.90
1.17
100-10-48-15
247
247
255
245
250.9
175.05
0.81
100-10-64-9
250
250
254
247
257.1
165.36
1.20
100-10-64-15
248
248
256
246
250.6
173.17
0.81
100-20-22-15
134
134
134
133
137.6
149.53
0.75
100-20-46-15
164
164
170
160
163.2
137.70
2.44
100-20-47-9
138
138
180
132
139.4
128.70
4.35
100-20-65-15
213
240
213
193
198.0
103.17
9.39
100-20-65-9
134
134
134
134
140.0
138.93
0.00
100-5-22-15
484
484
503
483
484.0
131.64
0.21
100-5-46-15
529
529
552
528
533.1
189.48
0.19
100-5-48-9
491
491
509
489
490.5
134.45
0.41
100-5-64-15
483
483
501
480
482.3
146.27
0.62
100-5-64-9
475
475
494
474
475.2
162.61
0.21
200-10-128-15
462
462
491
479
499.0
746.32
-3.68
200-10-50-15
488
488
522
488
500.6
895.29
0.00
200-10-50-9
489
489
506
487
493.2
793.34
0.41
200-10-84-9
517
517
526
509
514.0
719.20
1.55
200-10-85-15
479
479
486
477
481.8
561.76
0.42
200-20-145-15
245
245
262
252
271.0
660.08
-2.86
200-20-54-15
270
270
304
291
303.4
847.46
-7.78
200-20-55-9
257
262
257
257
263.0
639.97
0.00
200-20-97-15
336
336
347
334
338.2
724.57
0.60
200-20-97-9
253
253
253
253
258.1
716.20
0.00
200-40-133-15
159
159
163
157
165.0
772.82
1.26
200-40-45-15
164
164
164
159
163.6
565.58
3.05
200-40-45-9
144
168
144
144
152.0
626.53
0.00
200-40-90-9
145
160
145
145
149.4
654.24
0.00
200-40-91-15
153
153
153
153
157.6
624.01
0.00
#B
e
s
t
8
6
26
#T
o
t
a
l
30
30
30
#A
v
e
r
a
g
e
0.50Notice that the instance name (columns 1) contains its full description. Take the instance named 100-10-26-15 as example, the number100 represents the number of tasks included and 10 denotes the quantity of renewable resources provided. As for the number 26 and 15, it illustrates the amount of precedence relationships and the number of different introduced skills. Column 2 of Table 2 indicates the previous minimum objective values (f
p
r
e
b) in the literature which are compiled from the best solutions yield by two recent and best performing algorithms, namely, GRASP [48] and DEGR [49]. Columns 3 to 4 give the best results obtained by DEGR and GRASP. The corresponding results of the GVNS-MA are given in columns 5 to 7, including the minimum objective value (f
b
e
s
t) over 20 independent runs, the average objective value (f
a
v
g), and the average computing time in seconds (Time(s)) to reach f
b
e
s
t. The rowBest indicates a total number of instances where the specific method achieves optimal among three algorithms. The best one is indicated in italic. In addition, to verify whether there exists an essential difference between the best results of GVNS-MA and other reference algorithms, the relative percentage deviation (RPD) is defined by the equation (12)
R
P
D
%
=
f
p
r
e
b
-
f
b
e
s
t
f
p
r
e
b
×
100where a positive value of R
P
D means an improvement of result achieved by GVNS-MA while the negative number represents a worse solution.Table2 discloses that the outcomes from our GVNS-MA are noteworthy compared to the state-of-the-art results in the literature. GVNS-MA improves the previous best known results for 19 instances and matches for 7 cases. Compared with the 8 out of 30 cases solved by DEGR and 6 best solutions achieved by GRASP, these data clearly indicate the superiority of GVNS-MA compared to the previous excellent methods. Additionally, it can be observed that the improvement achieved by GVNS-MA is up to 9.39
%, for instance 100-20-65-15, accompanying that the average R
P
D
(
%
) equals to 0.50
%.


## 5.4. Experimental Results with Linear Deterioration

The previous comparisons and discussions in Section5.3 demonstrate the advantages of GVNS-MA in solving the related issues of MS-RCPSP. In this section, the aforementioned dataset with some modifications is used to assess the capability of GVNS-MA to solve the MS-RCPSPLD. The procedures of generating the testing instances and analysis of the results are described below. To make the benchmark instances meet the considered linear deterioration precisely, the deterioration rate (d
r
i) for task i
,
(
i
∈
V
) is generated randomly from three intervals 0,0.5, [
0.5,1
] and (
0,1
], similar to Cheng et al. [19], to shed light on the influence of the different value range of deterioration rate on its effectiveness.Since the extra included deterioration rate, we provide two additional heuristics for the initial population generation of GVNS-MA. Both the two methods affect the phase of generatingT
Q
j, determining the sequence of tasks assigned to resource j
,
j
∈
K. The first heuristic considers the sequence in descending order of deterioration rate (h) while the other rests upon an ascending order of ratio (a
/
h) of the basic processing time and deterioration rate. The methods adopting the former and latter heuristic to population initialization are dubbedGVNS-
M
A
h andGVNS-
M
A
a
h, respectively.Here, instances with 100 tasks from Myszkowski et al. [46] are isolated to attain the researched objects which fit with the unique nature of the MS-RCPSPLD more. To account for the three intervals from which the deterioration rate is drawn, 3 extended cases are needed to solve for each instance. For convenience, these instances are denoted by adding a suffix for identification to different intervals. For example, 100-10-26-15_1 represents the original case 100-10-26-15 is modified by adding the deterioration rates produced in (
0,0.5
] to the durations of tasks. In total, there are 45
(
3
×
15
) instances randomly generated.Due to zero known results in literature for same dataset, the improved tabu search (ITS) proposed by Dai et al. [54], who discussed the MS-RCPSP under step deterioration, and a path relinking algorithm (PR) [55], based on the population path relinking framework, are programmed as reference algorithms.Table3 reports the computational results achieved by the ITS, PR, GVNS-MA, GVNS-M
A
h, and GVNS-M
A
a
h on the set of 45 benchmark instances. f
b
e
s
t denotes the minimum objective value and f
a
v
g is computed as the average objective value of 20 runs.Table 3
Summary and comparison on the set of 45 new generated instances withn
=
100, of GVNS-MA, GVNS-
M
A
h, GVNS-
M
A
a
h, and the TS heuristic [54] and PR [55]. Best results are indicated in italic.
instances
ITS
PR
GVNS-MA
GVNS-
M
A
h
GVNS-
M
A
a
h
f
b
e
s
t
f
a
v
g
T
i
m
e
(
s
)
f
b
e
s
t
f
a
v
g
T
i
m
e
(
s
)
f
b
e
s
t
f
a
v
g
T
i
m
e
(
s
)
f
b
e
s
t
f
a
v
g
T
i
m
e
(
s
)
f
b
e
s
t
f
a
v
g
T
i
m
e
(
s
)
100-10-26-15_1
655.72
659.81
389.99
636.46
649.26
687.1
632.74
639.23
309.26
619.67
637.97
306.98
626.32
636.29
294.22
100-10-26-15_2
6013.96
6184.16
286.07
6089.71
6254.36
792.83
5871.45
6139.34
374.96
5805.57
6154.74
238.79
5727.94
6151.56
348.26
100-10-26-15_3
1728.56
1841.75
312.36
1646.96
1755.13
597.76
1602.83
1693.6
222.25
1662.21
1712.4
175.41
1638.98
1722.28
346.1
100-10-47-9_1
700.8
720.53
403.04
697.44
712.32
1001.8
694.45
700.98
206.66
676.45
691.57
314.99
696.73
703.9
363.14
100-10-47-9_2
7003.52
7392.87
391.12
7034.39
7211.52
705.63
6722.21
7151.38
241.79
6723.04
6959
206.14
6935.53
7023.69
251.14
100-10-47-9_3
1882.06
1952.06
481.68
1835.8
1908.63
934.63
1741.62
1843.89
300.08
1773.23
1839.58
193.83
1737.08
1833.68
414.32
100-10-48-15_1
658.68
691.41
399.15
670.93
689.08
887.91
648.51
655.26
349.16
632.53
665.95
226.86
647.98
661.02
266.62
100-10-48-15_2
6387.47
6598.09
420.43
6213.57
6587.47
911.61
6186.7
6516.09
411.61
5904.32
6254.62
270.97
6185.07
6346.32
336.55
100-10-48-15_3
1709.99
1742.32
296.59
1718.64
1780.61
733.95
1594.97
1668.87
233.95
1614.83
1663.66
321.69
1635.01
1702.73
270.56
100-10-64-9_1
705.27
757.25
377.03
710.49
769.27
730.24
687.22
709.29
312.87
688.4
712.15
260.24
678.94
696.82
277.56
100-10-64-9_2
7058.06
7447.75
394.15
7040.32
7381.41
627.94
6637.29
7111.14
301.39
6842.1
7191.53
228.06
6967.27
7368.33
399.18
100-10-64-9_3
1938.44
2062.06
311.53
2006.42
2044.03
1089.18
1893.24
1944.5
354.15
1808.42
2008.42
310.4
1938.44
1999.96
318.71
100-10-64-15_1
701.19
714.97
346.26
710.75
727.96
835.43
693.46
700.22
390.97
669.1
691.12
212.49
700.42
707.96
171.16
100-10-64-15_2
6909.64
7447.75
389.98
6725.78
7282.3
616.84
6606.14
6850.85
224.91
6282.3
6829.57
317.84
6263.31
6664.18
237.6
100-10-64-15_3
1938.44
2185.06
318.71
1942.47
2042.35
713.18
1806.92
1860.08
253.36
1871.49
1925.56
454.38
1855.85
1909.57
252.96
100-20-22-15_1
190.89
193.55
296.31
193.6
197.39
551.76
188.83
191.18
222.2
185.72
189.8
214.38
187.8
189.65
247.42
100-20-22-15_2
461.58
477.31
368.54
460.32
467.14
679.26
453.71
460.08
284.55
452.18
466.27
289.26
458.33
463.3
231.24
100-20-22-15_3
263.28
279.81
285.28
272.12
269.73
697.29
259.7
264.19
281.2
255.63
259.18
175.31
255.75
262.54
213.52
100-20-46-15_1
262.43
267.3
334.24
262.14
266.31
603.54
258.62
263.29
411.99
255.11
258.96
121.53
254.76
260.06
174.66
100-20-46-15_2
606.47
662.44
344.08
593.67
635.96
718.78
579.61
616.5
172.16
565.42
594.2
266.96
546.5
592.85
223.13
100-20-46-15_3
324.21
349.09
375.23
335.39
341.79
776.34
316.95
329.09
164.33
316.51
332.63
291.16
328.41
333.49
279.1
100-20-47-9_1
190.07
197.59
290.27
191.63
196.85
577.63
188.64
191.2
283.11
187.47
192.69
273.2
184.55
188.92
307.31
100-20-47-9_2
505.91
534.81
371.19
478.39
514..84
1021.73
480.3
493.19
354.9
462.78
487.64
354.18
449.66
478.93
242.41
100-20-47-9_3
308.02
318.27
457.26
306.31
313.65
699.58
294.37
303.52
578.46
277.12
294.58
297.37
283.99
287.99
275.59
100-20-65-15_1
901.34
924.46
264.13
898.65
905.43
679.57
888.01
900.95
175.05
868.26
895.18
150.52
873.05
893.38
284.3
100-20-65-15_2
2538.99
2606.76
287.18
2501.26
2532.67
587.63
2447.62
2503.16
409.97
2434.49
2475.1
176.59
2423.53
2449.44
257.35
100-20-65-15_3
1105.67
11158.86
274.91
1098.74
1136.85
534.18
1052.15
1092.24
251.38
1085.95
1112.43
159.11
1048.29
1067.76
141.26
100-20-65-9_1
191.13
197.83
412.48
189.57
195.48
795.61
183.69
188.98
305.61
186.97
191.46
189.6
186.94
192.65
309.79
100-20-65-9_2
462.42
477.68
654.69
459.34
474.43
581.12
449.57
462.29
176.8
447.19
459.85
223.24
455.93
465.91
306.06
100-20-65-9_3
280.18
287.76
489.43
275.12
281.08
685.32
271.9
277.21
242.79
265.87
276.91
310.1
264.55
278.45
247.3
100-5-22-15_1
5009.88
5142.85
289.78
5102.85
5050.98
845.26
4865.86
4993.18
435.29
4943.64
5009.88
184.44
4985.67
5102.85
223.35
100-5-22-15_2
1193440
1227080
431.94
1192300
1210150
615.37
1118610
1199248
243.22
1184940
1219514
206.64
1138490
1226780
266.56
100-5-22-15_3
66394.7
70081.8
569.12
66155.3
79262.7
799.76
60632.2
65262.7
106.39
59250.9
62793.04
261.98
64385.6
65975.26
172.67
100-5-46-15_1
6757.39
7497.63
367.97
6527.93
7014.57
1378.62
6350.3
6796.63
507.58
6369.03
6879.41
298.88
6491.64
6719.82
362.02
100-5-46-15_2
1404680
1453430
585.95
1443529
1470970
1085.95
1298430
1370870
265.64
1315940
1360830
235.36
1332210
1399014
241.76
100-5-46-15_3
79566.4
87031.3
506.87
79777.13
8635.67
689.11
74017.8
79651.28
179.24
75586.6
77860.62
168.09
75256.8
80128
187.63
100-5-48-9_1
5637.87
5868.32
312.14
5666.27
783.86
848.07
5520.6
5604.07
241.5
5520.6
5636.64
250.18
5542.99
5665.7
249.52
100-5-48-9_2
1284230
1315720
361.45
1289811
1364650
712.86
1222350
1285020
279.58
1163860
1259332
281.22
1233010
1268572
346.59
100-5-48-9_3
68429.9
69245.3
453.35
66785
71727.92
939.38
65727.9
67622
456.1
66042.6
67091.7
412.86
64822
66721.38
284.46
100-5-64-15_1
5819.16
6273.74
556.61
5765.89
6181.67
1024.15
5544.26
5792.34
351.67
5465.43
5903.52
296.78
5694.2
5801.75
566.19
100-5-64-15_2
1209440
1261510
312.96
1190830
1257643
1235.33
1131450
1183014
405.95
1118430
1151812
463.05
1047250
1158556
333.7
100-5-64-15_3
64226.7
70960.2
349.88
63465.1
68888.9
894.03
61285.7
66578.58
379.85
62677.1
66061.44
459.11
62475.3
67499.62
616.23
100-5-64-9_1
5502.31
5775.24
373.65
5544.81
5667,47
986.93
5281.77
5404.36
339.3
5307.48
5438.95
483.96
5159.84
5367.47
299.32
100-5-64-9_2
1214340
1271610
405.53
1183479
1236750
1199.27
1114060
1155584
415.23
1164010
1201126
402.87
1121650
1159384
272.86
100-5-64-9_3
61035.6
64876.5
363.95
61515.02
63232.3
874.48
60458.6
62103.78
313.63
59451.4
61715.02
305.43
59519.1
62322.3
277.49
#B
e
s
t
0
0
0
0
15
14
17
16
14
15
#T
o
t
a
l
45
45
45
45
45
45
45
45
45
45First, Table3 discloses that the solutions obtained by GVNS-MA, GVNS-M
A
h, and GVNS-M
A
a
h are better than the ITS and PR for any instance from the perspective of both quality of schedule and runtime. To some extent these results demonstrated the differences between linear deterioration and step deterioration and the superiority of memetic algorithm framework. Second, these three methods, differing in the sort order of tasks in initialize phase, behave similarly where GVNS-MA obtains the best 15 out of 45 instances, 17 for GVNS-M
A
h, and 14 for G
V
N
S
a
h in terms of f
b
e
s
t. Specifically, GVNS-MA and GVNS-M
A
h attain the optimal simultaneously for the instance 100-5-48-9-1. From a view point of f
a
v
g and run time, three methods also have a balanced performance. Third, as far as three different intervals to generate deterioration rate are concerned, the phenomenon did not happen that the relevant algorithms display strikingly different behavior. In other words, the performance of the proposed algorithm is not sensitive to the setting of deterioration rate.


## 5.5. Analysis and Discussions

In this section, we study two essential ingredients of the proposed GVNS-MA to get an insight to its performance. One is the rapid evaluation mechanism; the other is the role of the memetic framework.


### 5.5.1. Importance of Rapid Evaluation Mechanism

GVNS-MA with rapid evaluation mechanism only calculates the relevant parameters of some particular tasks rather than all when the procedure computes the objective value of a neighborhood solution. To highlight the key role of the rapid evaluation mechanism, two sets of comparison experiments are carried out on generated dataset with two algorithms, GVNS-MA and GVNS-M
A
0, including same ingredients with GVNS-MA except for the computation of objective value. When GVNS-M
A
0 figures up the value of a neighborhood solution, it computes all relevant parameters again.Table4 records the experimental results carried out on the dataset [46] without consideration of deterioration, whereas Table 5 shows the comparisons of GVNS-MA and GVNS-M
A
0 about the set of 15 instances generated in Section 5.4 on account of the indiscrimination in three intervals. Column 2 and 5 record the best attained by two algorithms. Column 3 and 6 indicate the minimum time cost to a final feasible schedule with one run of procedure. Note that the best objective value cannot be guaranteed as the output of shortest runtime. As for the parameters in column 4 and 7, they represent the mean runtime. Finally, two parameters D
E
V
s
h
o
r
t
e
s
t and D
E
V
a
v
g are used to disclose the runtime deviation of two methods, defined by equations(13)
D
E
V
s
h
o
r
t
e
s
t
%
=
T
s
h
o
r
t
e
s
t
1
-
T
s
h
o
r
t
e
s
t
2
T
s
h
o
r
t
e
s
t
1
×
100and (14)
D
E
V
a
v
g
%
=
T
a
v
g
1
-
T
a
v
g
2
T
a
v
g
1
×
100respectively. The positive value of D
E
V
s
h
o
r
t
e
s
t
(
%
) and D
E
V
a
v
g
(
%
) means that GVNS-M
A
0 has better performance and negative value tells GVNS-MA is prior to GVNS-M
A
0 in terms of time cost. And the rowsBetter andWorse, respectively, show the number of instances for which the corresponding results of the associated algorithm are better and worse than the other.Table 4
Summary and comparison of GVNS-MA and GVNS-M
A
0 on known MS-RCPSP dataset [46].
instances
GVNS-MA
GVNS-M
A
0
D
E
V
s
h
o
r
t
e
s
t
(
%
)
D
E
V
a
v
g
(
%
)
f
b
e
s
t
T
s
h
o
r
t
e
s
t
1
T
a
v
g
1
f
b
e
s
t
T
s
h
o
r
t
e
s
t
2
T
a
v
g
2
100-10-26-15
237
134.58
191.78
237
155.41
240.93
-15.48
-25.63
100-10-47-9
253
107.90
124.90
253
112.59
155.26
-4.35
-24.31
100-10-48-15
245
148.01
175.05
245
174.61
215.94
-17.97
-23.36
100-10-64-9
247
142.61
165.36
247
162.58
216.63
-14.00
-31.01
100-10-64-15
246
104.49
173.17
246
121.29
222.18
-16.08
-28.30
100-20-22-15
133
129.46
149.53
133
145.47
176.29
-12.37
-17.90
100-20-46-15
160
106.16
137.70
160
121.39
175.66
-14.35
-27.57
100-20-47-9
132
114.82
128.70
132
142.51
174.44
-24.12
-35.54
100-20-65-15
193
97.82
103.17
193
113.01
129.22
-15.53
-25.25
100-20-65-9
134
112.29
138.93
134
126.16
159.56
-12.35
-14.85
100-5-22-15
483
105.73
131.64
483
120.40
167.90
-13.87
-27.54
100-5-46-15
528
160.97
189.48
528
182.98
221.45
-13.67
-16.87
100-5-48-9
489
114.20
134.45
489
134.52
146.37
-17.79
-8.87
100-5-64-15
480
122.67
146.27
480
164.45
202.54
-34.06
-38.47
100-5-64-9
474
124.63
162.61
474
154.10
206.64
-23.65
-27.08
200-10-128-15
479
657.93
746.32
479
801.41
902.58
-21.86
-20.94
200-10-50-15
488
835.5
895.29
488
913.44
984.38
-9.33
-9.95
200-10-50-9
487
744.07
793.34
487
820.27
818.20
-10.24
-3.13
200-10-84-9
509
668.63
719.20
509
725.68
862.85
-8.53
-19.97
200-10-85-15
477
500.61
561.76
477
561.76
688.83
-12.22
-22.62
200-20-145-15
252
534.14
660.08
252
590.08
715.30
-10.47
8.37
200-20-54-15
291
745.02
847.46
291
785.80
967.01
-5.47
-14.11
200-20-55-9
257
577.67
639.97
257
622.39
713.94
-7.74
-11.56
200-20-97-15
334
592.01
724.57
334
666.73
749.14
-12.62
-3.39
200-20-97-9
253
565.37
716.20
253
683.70
809.50
-20.93
13.03
200-40-133-15
157
682.28
772.82
157
720.41
844.72
-5.59
-9.30
200-40-45-15
159
476.09
565.58
159
511.30
615.16
-7.40
-8.77
200-40-45-9
144
571.43
626.53
144
615.48
700.62
-7.71
-11.83
200-40-90-9
145
616.23
654.24
145
683.97
738.17
–10.99
-12.83
200-40-91-15
153
588.02
624.01
153
664.87
760.05
-13.07
-21.80
#B
e
t
t
e
r
30
28
0
2
#W
o
r
s
e
0
2
30
28
#T
o
t
a
l
30
30
30
30
#A
v
e
r
a
g
e
-13.79
-18.80Table 5
Comparison of results of GVNS-MA and GVNS-M
A
0 on the set of 45 new generated instances in Section 5.4.
instances
GVNS-MA
GVNS-M
A
0
D
E
V
s
h
o
r
t
e
s
t
(
%
)
D
E
V
a
v
g
(
%
)
f
b
e
s
t
T
s
h
o
r
t
e
s
t
1
T
a
v
g
1
f
b
e
s
t
T
s
h
o
r
t
e
s
t
2
T
a
v
g
2
100-10-26-15_1
632.74
146.08
274.99
635.08
163.91
309.99
-12.21
-12.73
100-10-47-9_1
694.45
206.66
349.51
696.66
197.36
364.15
4.50
-4.19
100-10-48-15_1
648.51
193.34
286.55
649.11
174.83
244.17
9.57
14.79
100-10-64-9_1
687.22
222.47
312.41
678.09
191.71
348.78
13.83
-11.64
100-10-64-15_1
693.46
192.91
309.49
673.75
190.47
297.09
1.26
4.01
100-20-22-15_1
188.83
161.71
256.15
187.22
146.31
225.34
9.52
12.03
100-20-46-15_1
258.62
154.94
240.39
256.60
142.55
228.86
8.00
4.80
100-20-47-9_1
188.64
222.79
258.72
182.12
252.05
293.80
-13.13
-13.56
100-20-65-15_1
888.01
172.61
207.43
870.85
220.43
187.68
-27.70
9.52
100-20-65-9_1
183.69
237.32
354.53
188.66
264.17
333.25
-11.31
6.00
100-5-22-15_1
4865.86
184.44
270.23
4866.02
224.41
295.76
-21.67
-9.45
100-5-46-15_1
6350.3
264.37
457.83
6720.42
270.03
488.58
-2.14
-6.72
100-5-48-9_1
5520.60
154.46
264.23
5520.60
189.28
311.00
-22.54
-17.70
100-5-64-15_1
5544.26
338.39
413.58
5555.52
322.48
461.02
4.70
-11.47
100-5-64-9_1
5281.77
222.77
323.46
5287.14
200.70
350.71
9.91
-8.42
#B
e
t
t
e
r
7
9
8
6
#W
o
r
s
e
8
6
7
9
#T
o
t
a
l
15
15
15
15
#A
v
e
r
a
g
e
-3.29
-2.98The results summarized in Table4 disclose that the GVNS-MA has an overwhelming advantage over GVNS-M
A
0 in terms of the computation time to solve MS-RCPSP, leaving out the deterioration effect. Indeed, the shortest runtime T
s
h
o
r
t
e
s
t
1 of the GVNS-MA method is better than the shortest runtime T
s
h
o
r
t
e
s
t
2 of GVNS-M
A
0 for 30 out of 30 representative instances, and the average runtime T
a
v
g
1 is better for 28 out of 30 instances. Meanwhile, the average value of D
E
V
s
h
o
r
t
e
s
t
(
%
) equals -13.79%, accompanying with a high of -18.80 percent in D
E
V
a
v
g
(
%
).However, focusing on Table5, the results of two approaches are neck and neck, and GVNS-MA lost its early superiority in MS-RCPSP. In terms of shortest runtime, GVNS-MA successes for 7 out of 15 tested instances while GVNS-M
A
0 reaches optimal for the remain. As for average runtime, GVNS-MA performs better for 9 out of 15 examples and GVNS-M
A
0 achieves reversion in others 6 instances. With these data it will be hard to judge the true benefits of one approach versus the other.To figure out the reason of this phenomenon, we should come back to the inner rationale of rapid evaluation mechanism. When GVNS-MA computes the completion time of a neighborhood solution, it only recalculates the tasks’ related parameters influenced by the particular move. In MS-RCPSP, a move including swap, reverse, and alter will affect just a small number of tasks. But for MS-RCPSPLD instances, any move can cumulatively effect on a large proportion of tasks because of the existing deterioration. Consequently, the runtime saved in computing some unchanged parameters may not make up for the time spent on isolating the changed tasks.These experimental results confirm that although the rapid evaluation mechanism is not so critical for MS-RCPSPLD, it is still quite useful to quickly solve MS-RCPSP instances and constitutes a significant element of the proposed GVNS-MA.


### 5.5.2. Influence of the Memetic Framework

As shown in Lei et al. [16]; Mladenovićabcd [15], the GVNS approach has shown great performance in a widespread academic application. So it is meaningful to research whether our GVNS-MA has a significant advantage over the originally efficient GVNS algorithm. For this reason, a comparative test between GVNS and GVNS-MA has been carried out. For this experiment, we used the known dataset [46], with 20 times running for each instance. Same with GVNS-MA, the stopping criteria of GVNS is met when the maximum number between two iterations without improvement reaches 5
×
1
0
4. The experimental results of two methods are recorded in Table 6 where D
E
V
(
%
)
=
(
f
-
f
m
i
n
)
/
f
m
i
n
×
100, and the other symbols have same meanings as those of Table 2. As for the f ad f
m
i
n in the equation, they denote the objective value of the best schedule solved by the particular algorithm and the best value attainable until now, respectively. The parameterDEV
(
%
) can visually detect the gap between the current algorithm and the best.Table 6
Summary and comparison of GVNS-MA and GVNS on known MS-RCPSP dataset [46].
instances
GVNS-MA
GVNS
f
b
e
s
t
1
D
e
v
(
%
)
f
b
e
s
t
2
D
e
v
(
%
)
100-10-26-15
237
0.00
260
9.70
100-10-47-9
253
0.00
255
0.79
100-10-48-15
245
0.00
255
4.08
100-10-64-9
247
0.00
257
4.05
100-10-64-15
246
0.00
248
0.81
100-20-22-15
133
0.00
142
6.77
100-20-46-15
160
0.00
161
0.63
100-20-47-9
132
0.00
134
1.52
100-20-65-15
193
0.00
205
6.22
100-20-65-9
134
0.00
142
5.97
100-5-22-15
483
0.00
486
0.62
100-5-46-15
528
0.00
580
9.85
100-5-48-9
489
0.00
493
0.82
100-5-64-15
480
0.00
494
2.92
100-5-64-9
474
0.00
477
0.63
200-10-128-15
479
0.00
501
4.59
200-10-50-15
488
0.00
516
5.74
200-10-50-9
487
0.00
509
4.52
200-10-84-9
509
2.21
498
0.00
200-10-85-15
477
0.00
494
3.56
200-20-145-15
252
0.00
285
13.10
200-20-54-15
291
0.00
303
4.12
200-20-55-9
257
0.00
267
3.89
200-20-97-15
334
0.00
347
3.89
200-20-97-9
253
0.00
282
11.46
200-40-133-15
157
0.00
181
15.29
200-40-45-15
159
0.00
164
3.14
200-40-45-9
144
0.00
176
22.22
200-40-90-9
145
0.00
173
19.31
200-40-91-15
153
0.00
160
4.58
#B
e
t
t
e
r
29
1
#E
q
u
a
l
0
0
#W
o
r
s
e
1
29
#T
o
t
a
l
30
30
#A
v
e
r
a
g
e
0.07
5.83Obviously, Table6 demonstrates that the GVNS-MA significantly outperforms the GVNS algorithm in general. First, compared with the GVNS algorithm, the GVNS-MA obtains better and worse results in terms of the minimum objective value on 29 and 1 instances, respectively. Second, it can be seen that the obtained averageDevs are 0.07% and 5.83%, respectively, for the GVNS-MA and GVNS, implying that there exists a huge difference between two methods. Third, the runtimes of PR are obviously longer than GVNS-MA with worse solutions. These outcomes indicate that the memetic part of the proposed GVNS-MA is very appropriate for solving the related issue of MS-RCPSP.


## 5.5.1. Importance of Rapid Evaluation Mechanism

GVNS-MA with rapid evaluation mechanism only calculates the relevant parameters of some particular tasks rather than all when the procedure computes the objective value of a neighborhood solution. To highlight the key role of the rapid evaluation mechanism, two sets of comparison experiments are carried out on generated dataset with two algorithms, GVNS-MA and GVNS-M
A
0, including same ingredients with GVNS-MA except for the computation of objective value. When GVNS-M
A
0 figures up the value of a neighborhood solution, it computes all relevant parameters again.Table4 records the experimental results carried out on the dataset [46] without consideration of deterioration, whereas Table 5 shows the comparisons of GVNS-MA and GVNS-M
A
0 about the set of 15 instances generated in Section 5.4 on account of the indiscrimination in three intervals. Column 2 and 5 record the best attained by two algorithms. Column 3 and 6 indicate the minimum time cost to a final feasible schedule with one run of procedure. Note that the best objective value cannot be guaranteed as the output of shortest runtime. As for the parameters in column 4 and 7, they represent the mean runtime. Finally, two parameters D
E
V
s
h
o
r
t
e
s
t and D
E
V
a
v
g are used to disclose the runtime deviation of two methods, defined by equations(13)
D
E
V
s
h
o
r
t
e
s
t
%
=
T
s
h
o
r
t
e
s
t
1
-
T
s
h
o
r
t
e
s
t
2
T
s
h
o
r
t
e
s
t
1
×
100and (14)
D
E
V
a
v
g
%
=
T
a
v
g
1
-
T
a
v
g
2
T
a
v
g
1
×
100respectively. The positive value of D
E
V
s
h
o
r
t
e
s
t
(
%
) and D
E
V
a
v
g
(
%
) means that GVNS-M
A
0 has better performance and negative value tells GVNS-MA is prior to GVNS-M
A
0 in terms of time cost. And the rowsBetter andWorse, respectively, show the number of instances for which the corresponding results of the associated algorithm are better and worse than the other.Table 4
Summary and comparison of GVNS-MA and GVNS-M
A
0 on known MS-RCPSP dataset [46].
instances
GVNS-MA
GVNS-M
A
0
D
E
V
s
h
o
r
t
e
s
t
(
%
)
D
E
V
a
v
g
(
%
)
f
b
e
s
t
T
s
h
o
r
t
e
s
t
1
T
a
v
g
1
f
b
e
s
t
T
s
h
o
r
t
e
s
t
2
T
a
v
g
2
100-10-26-15
237
134.58
191.78
237
155.41
240.93
-15.48
-25.63
100-10-47-9
253
107.90
124.90
253
112.59
155.26
-4.35
-24.31
100-10-48-15
245
148.01
175.05
245
174.61
215.94
-17.97
-23.36
100-10-64-9
247
142.61
165.36
247
162.58
216.63
-14.00
-31.01
100-10-64-15
246
104.49
173.17
246
121.29
222.18
-16.08
-28.30
100-20-22-15
133
129.46
149.53
133
145.47
176.29
-12.37
-17.90
100-20-46-15
160
106.16
137.70
160
121.39
175.66
-14.35
-27.57
100-20-47-9
132
114.82
128.70
132
142.51
174.44
-24.12
-35.54
100-20-65-15
193
97.82
103.17
193
113.01
129.22
-15.53
-25.25
100-20-65-9
134
112.29
138.93
134
126.16
159.56
-12.35
-14.85
100-5-22-15
483
105.73
131.64
483
120.40
167.90
-13.87
-27.54
100-5-46-15
528
160.97
189.48
528
182.98
221.45
-13.67
-16.87
100-5-48-9
489
114.20
134.45
489
134.52
146.37
-17.79
-8.87
100-5-64-15
480
122.67
146.27
480
164.45
202.54
-34.06
-38.47
100-5-64-9
474
124.63
162.61
474
154.10
206.64
-23.65
-27.08
200-10-128-15
479
657.93
746.32
479
801.41
902.58
-21.86
-20.94
200-10-50-15
488
835.5
895.29
488
913.44
984.38
-9.33
-9.95
200-10-50-9
487
744.07
793.34
487
820.27
818.20
-10.24
-3.13
200-10-84-9
509
668.63
719.20
509
725.68
862.85
-8.53
-19.97
200-10-85-15
477
500.61
561.76
477
561.76
688.83
-12.22
-22.62
200-20-145-15
252
534.14
660.08
252
590.08
715.30
-10.47
8.37
200-20-54-15
291
745.02
847.46
291
785.80
967.01
-5.47
-14.11
200-20-55-9
257
577.67
639.97
257
622.39
713.94
-7.74
-11.56
200-20-97-15
334
592.01
724.57
334
666.73
749.14
-12.62
-3.39
200-20-97-9
253
565.37
716.20
253
683.70
809.50
-20.93
13.03
200-40-133-15
157
682.28
772.82
157
720.41
844.72
-5.59
-9.30
200-40-45-15
159
476.09
565.58
159
511.30
615.16
-7.40
-8.77
200-40-45-9
144
571.43
626.53
144
615.48
700.62
-7.71
-11.83
200-40-90-9
145
616.23
654.24
145
683.97
738.17
–10.99
-12.83
200-40-91-15
153
588.02
624.01
153
664.87
760.05
-13.07
-21.80
#B
e
t
t
e
r
30
28
0
2
#W
o
r
s
e
0
2
30
28
#T
o
t
a
l
30
30
30
30
#A
v
e
r
a
g
e
-13.79
-18.80Table 5
Comparison of results of GVNS-MA and GVNS-M
A
0 on the set of 45 new generated instances in Section 5.4.
instances
GVNS-MA
GVNS-M
A
0
D
E
V
s
h
o
r
t
e
s
t
(
%
)
D
E
V
a
v
g
(
%
)
f
b
e
s
t
T
s
h
o
r
t
e
s
t
1
T
a
v
g
1
f
b
e
s
t
T
s
h
o
r
t
e
s
t
2
T
a
v
g
2
100-10-26-15_1
632.74
146.08
274.99
635.08
163.91
309.99
-12.21
-12.73
100-10-47-9_1
694.45
206.66
349.51
696.66
197.36
364.15
4.50
-4.19
100-10-48-15_1
648.51
193.34
286.55
649.11
174.83
244.17
9.57
14.79
100-10-64-9_1
687.22
222.47
312.41
678.09
191.71
348.78
13.83
-11.64
100-10-64-15_1
693.46
192.91
309.49
673.75
190.47
297.09
1.26
4.01
100-20-22-15_1
188.83
161.71
256.15
187.22
146.31
225.34
9.52
12.03
100-20-46-15_1
258.62
154.94
240.39
256.60
142.55
228.86
8.00
4.80
100-20-47-9_1
188.64
222.79
258.72
182.12
252.05
293.80
-13.13
-13.56
100-20-65-15_1
888.01
172.61
207.43
870.85
220.43
187.68
-27.70
9.52
100-20-65-9_1
183.69
237.32
354.53
188.66
264.17
333.25
-11.31
6.00
100-5-22-15_1
4865.86
184.44
270.23
4866.02
224.41
295.76
-21.67
-9.45
100-5-46-15_1
6350.3
264.37
457.83
6720.42
270.03
488.58
-2.14
-6.72
100-5-48-9_1
5520.60
154.46
264.23
5520.60
189.28
311.00
-22.54
-17.70
100-5-64-15_1
5544.26
338.39
413.58
5555.52
322.48
461.02
4.70
-11.47
100-5-64-9_1
5281.77
222.77
323.46
5287.14
200.70
350.71
9.91
-8.42
#B
e
t
t
e
r
7
9
8
6
#W
o
r
s
e
8
6
7
9
#T
o
t
a
l
15
15
15
15
#A
v
e
r
a
g
e
-3.29
-2.98The results summarized in Table4 disclose that the GVNS-MA has an overwhelming advantage over GVNS-M
A
0 in terms of the computation time to solve MS-RCPSP, leaving out the deterioration effect. Indeed, the shortest runtime T
s
h
o
r
t
e
s
t
1 of the GVNS-MA method is better than the shortest runtime T
s
h
o
r
t
e
s
t
2 of GVNS-M
A
0 for 30 out of 30 representative instances, and the average runtime T
a
v
g
1 is better for 28 out of 30 instances. Meanwhile, the average value of D
E
V
s
h
o
r
t
e
s
t
(
%
) equals -13.79%, accompanying with a high of -18.80 percent in D
E
V
a
v
g
(
%
).However, focusing on Table5, the results of two approaches are neck and neck, and GVNS-MA lost its early superiority in MS-RCPSP. In terms of shortest runtime, GVNS-MA successes for 7 out of 15 tested instances while GVNS-M
A
0 reaches optimal for the remain. As for average runtime, GVNS-MA performs better for 9 out of 15 examples and GVNS-M
A
0 achieves reversion in others 6 instances. With these data it will be hard to judge the true benefits of one approach versus the other.To figure out the reason of this phenomenon, we should come back to the inner rationale of rapid evaluation mechanism. When GVNS-MA computes the completion time of a neighborhood solution, it only recalculates the tasks’ related parameters influenced by the particular move. In MS-RCPSP, a move including swap, reverse, and alter will affect just a small number of tasks. But for MS-RCPSPLD instances, any move can cumulatively effect on a large proportion of tasks because of the existing deterioration. Consequently, the runtime saved in computing some unchanged parameters may not make up for the time spent on isolating the changed tasks.These experimental results confirm that although the rapid evaluation mechanism is not so critical for MS-RCPSPLD, it is still quite useful to quickly solve MS-RCPSP instances and constitutes a significant element of the proposed GVNS-MA.


## 5.5.2. Influence of the Memetic Framework

As shown in Lei et al. [16]; Mladenovićabcd [15], the GVNS approach has shown great performance in a widespread academic application. So it is meaningful to research whether our GVNS-MA has a significant advantage over the originally efficient GVNS algorithm. For this reason, a comparative test between GVNS and GVNS-MA has been carried out. For this experiment, we used the known dataset [46], with 20 times running for each instance. Same with GVNS-MA, the stopping criteria of GVNS is met when the maximum number between two iterations without improvement reaches 5
×
1
0
4. The experimental results of two methods are recorded in Table 6 where D
E
V
(
%
)
=
(
f
-
f
m
i
n
)
/
f
m
i
n
×
100, and the other symbols have same meanings as those of Table 2. As for the f ad f
m
i
n in the equation, they denote the objective value of the best schedule solved by the particular algorithm and the best value attainable until now, respectively. The parameterDEV
(
%
) can visually detect the gap between the current algorithm and the best.Table 6
Summary and comparison of GVNS-MA and GVNS on known MS-RCPSP dataset [46].
instances
GVNS-MA
GVNS
f
b
e
s
t
1
D
e
v
(
%
)
f
b
e
s
t
2
D
e
v
(
%
)
100-10-26-15
237
0.00
260
9.70
100-10-47-9
253
0.00
255
0.79
100-10-48-15
245
0.00
255
4.08
100-10-64-9
247
0.00
257
4.05
100-10-64-15
246
0.00
248
0.81
100-20-22-15
133
0.00
142
6.77
100-20-46-15
160
0.00
161
0.63
100-20-47-9
132
0.00
134
1.52
100-20-65-15
193
0.00
205
6.22
100-20-65-9
134
0.00
142
5.97
100-5-22-15
483
0.00
486
0.62
100-5-46-15
528
0.00
580
9.85
100-5-48-9
489
0.00
493
0.82
100-5-64-15
480
0.00
494
2.92
100-5-64-9
474
0.00
477
0.63
200-10-128-15
479
0.00
501
4.59
200-10-50-15
488
0.00
516
5.74
200-10-50-9
487
0.00
509
4.52
200-10-84-9
509
2.21
498
0.00
200-10-85-15
477
0.00
494
3.56
200-20-145-15
252
0.00
285
13.10
200-20-54-15
291
0.00
303
4.12
200-20-55-9
257
0.00
267
3.89
200-20-97-15
334
0.00
347
3.89
200-20-97-9
253
0.00
282
11.46
200-40-133-15
157
0.00
181
15.29
200-40-45-15
159
0.00
164
3.14
200-40-45-9
144
0.00
176
22.22
200-40-90-9
145
0.00
173
19.31
200-40-91-15
153
0.00
160
4.58
#B
e
t
t
e
r
29
1
#E
q
u
a
l
0
0
#W
o
r
s
e
1
29
#T
o
t
a
l
30
30
#A
v
e
r
a
g
e
0.07
5.83Obviously, Table6 demonstrates that the GVNS-MA significantly outperforms the GVNS algorithm in general. First, compared with the GVNS algorithm, the GVNS-MA obtains better and worse results in terms of the minimum objective value on 29 and 1 instances, respectively. Second, it can be seen that the obtained averageDevs are 0.07% and 5.83%, respectively, for the GVNS-MA and GVNS, implying that there exists a huge difference between two methods. Third, the runtimes of PR are obviously longer than GVNS-MA with worse solutions. These outcomes indicate that the memetic part of the proposed GVNS-MA is very appropriate for solving the related issue of MS-RCPSP.


## 6. Conclusions

The proposed general variable neighborhood search-based memetic algorithm (GVNS-MA) for solving the MS-RCPSP and MS-RCPSPLD incorporates an effective neighborhood search procedure and a random crossover operator while applying an original scheme for parent selection. We tested the proposed GVNS-MA on 30 benchmark instances commonly used in the literature and 45 newly generated instances. The computational results of the state-of-the-art algorithms in the literature demonstrate that our algorithm is highly effective for solving MS-RCPSP. Specifically, it improves or matches the previous best known results for all tested instances. As for MS-RCPSPLD, GVNS-MA has a better performance than ITS for any instance in terms of the quality of solution and a considerable shorter runtime compared to PR.The investigations of some essential ingredients of the proposed algorithm shed light on the behavior of the GVNS-MA. First, the rapid evaluation mechanism is particularly suitable to solve MS-RCPSP instances. Second, the population evolution based memetic framework is significantly contributed to the algorithm’s performance.Here we discussed the linear deterioration of the multiskill tasks. It would be interesting to investigate such a scheduling problem in other deterioration mechanisms to meet various actual production conditions.



---

*Source: 9459375-2019-07-04.xml*