# Intelligent Differential Evolution Scheme for Network Resources in IoT

Authors: Huu Dang Quoc; Loc Nguyen The; Cuong Nguyen Doan; Toan Phan Thanh; Neal N. Xiong
Journal: Scientific Programming
 (2020)

---

## Abstract

Scheduling is a fundamental factor in managing the network resource of the Internet of things. For IoT systems such as production lines, to operate effectively, it is necessary to find an intelligent management scheme, i.e., schedule, for network resources. In this study, we focus on multiskill resource-constrained project scheduling problem (MS-RCPSP), a combinational optimization problem that has received extensive attention from the research community due to its advantages in network resource management. In recent years, many approaches have been utilized for solving this problem such as genetic algorithm and ant colony optimization. Although these approaches introduce various optimization techniques, premature convergence issue also occurs. Moreover, previous studies have only been verified on simulation data but not on real data of factories. This paper formulated the MS-RCPSP and then proposed a novel algorithm called DEM to solve it. The proposed algorithm was developed based on the differential evolution metaheuristic. Besides, we build the reallocate function to improve the solution quality so that the proposed algorithm converges rapidly to global extremum while also avoiding getting trapped in a local extremum. To evaluate the performance of the proposed algorithm, we conduct the experiment on iMOPSE, the simulated dataset used by previous authors in their research studies. In addition, DEM was verified on real dataset supported by a famous textile industry factory. Experimental results on both simulated data and real data show that the proposed algorithm not only finds a better schedule compared with related works but also can reduce the processing time of the production line currently used at the textile industry factory.


---

## Body

## 1. Introduction

Internet of things systems include not only sensors and automated machines like robots but also intelligent control and management algorithms [1]. Intelligent algorithms for managing network resource play a key role in controlling the operation of automated machines such as robots, enabling them to devote their full capacity to serve users.Multiskill resource-constrained project scheduling problem (MS-RCPSP), a combinational optimization problem, has received extensive attention from the research community in recent years due to its advantages in network resources management and scheduling for Internet of things system. The main purpose of the MS-RCPSP is to find the way for assigning tasks to resources so that the execution time is minimal.In recent years, MS-RCPSP is widely used, and this problem is found not only in critical civilian fields but also in the military setting. MS-RCPSP appears on a broad scale of military operations such as planning an onboard mission or routing an unmanned aerial vehicle (UAV) [2, 3].The rest of the paper is organized as follows. In Section2, we present some related works such as previous approaches to solving the MS-RCPSP. Specifically, the summary of the differential evolution method is included in this section. Differential evolution is a well-known evolutionary algorithm that has been applied effectively to solve NP-hard problems. In this paper, the proposed algorithm is inspired by the differential evolution method. In Section 3, we present the system model and the statement of MS-RCPSP. The formulation of MS-RCPSP is introduced in this section. Section 4 describes the proposed algorithm, which is built on differential evolution strategy [4]. In this section, we focus on presenting the reallocate function, which is the key component that creates the strength of the proposed algorithm. Besides, this section introduces our design for schedule representation and a new measurement model for measuring the difference between two schedules. The proposed algorithm (DEM) is also introduced in this section. Simulation results examining the proposed algorithms along with computational and comparative results are given and analyzed in Section 5. Simulations conducted by using the iMOPSE dataset [5] are presented in this section. In addition, this section describes experiments conducted on the factory’s dataset collected from TNG, a well-known national textile company. Finally, Section 6 concludes the paper and outlines some directions for future work.


## 2. Related Works

### 2.1. Approximation Algorithms for MS-RCPSP

Scheduling problem arises in many practical situations [6–11]. In the general case, the scheduling is proved to be NP-hard. The authors of [5, 12, 13] show that MS-RCPSP, the problem we mentioned in this paper, is an NP-hard scheduling problem. In addition, MS-RCPSP is multimodal or discontinuous and very challenging to solve with traditional optimization methods. In the past few years, various approaches have been proposed to solve MS-RCPSP, thereby finding out intelligent algorithms to allocate and manage network resources in the Internet of things systems [14–17]. Some popular metaheuristic algorithms are the genetic algorithm (GA), ant colony optimization (ACO), and particle swarm optimization [18–22].Su et al. [23] used a mixed-integer model and discrete constraints to solve the problems. Maghsoudlou et al. [24] and Bibiks et al. [25] applied the cuckoo Search algorithm to plan for the multirisk project with three distinct evaluation objectives. Lin et al. [26] proposed a new solution based on GA and some other heuristic algorithms.Myszkowski et al. [5, 13] proposed the hybrid algorithm which is the combination of the differential evolution strategy and the greedy approach for arranging the human resources in product manufacturing projects and calculating time-of-use electricity tariffs and shift differential payments. The authors aimed to achieve the shortest makespan and low cost and gave a new benchmark dataset called iMOPSE [5], an artiﬁcially created dataset based on real-world instances for the MS-RCPSP.The MS-RCPSP is studied and applied in the planning of many practical areas of the Internet of things. Some authors also study new variants of the MS-RCPSP and apply them in different fields. Mejia [3] developed a new variant of the MS-RCPSP to coordinate research activities in the nuclear laboratory. Hosseinian [27] proposed two new algorithms, P-GWO and MOFA, to solve the MS-RCPSP with the deterioration effect and financial constraints (a case study of a gas treating company). In another study, Hosseinian et al. introduced a new mixed-integer formulation for the time-dependent MS-RCPSP considering the learning effect [28].Nemati-Lafmejani et al. [29] developed an integrated biobjective optimization model to deal with multimode RCPSP. The objective of the proposed model is to minimize both the costs and the makespan of the project. Tahrir and Yang [30] proposed a hybrid metaheuristic algorithm that combined ant colony optimization and variable neighbourhood search approaches for job scheduling in grid computing.Several prior research has also been conducted to solve other subproblems of RCPSP, the general problem of MS-RCPSP, to improve the efficiency of network resource management in specific fields of the Internet of things. Ballestin and Leus [31] and Javanmard [32] and their colleagues studied specific cases of RCPSPs such as multiskill stochastic and preemptive problem to calculate project implementation time, i.e., makespan, and build mathematical models for the project resource investment.


### 2.2. Differential Evolution Method

Differential evolution (DE) is a population-based stochastic optimization algorithm introduced by Storn and Price [4]. The advantages of DE lies in its simplicity, efficiency, and speed thanks to the local search method. DE deals with the old generation of the original population by using the mutation operator to create better solutions in the new generation. Until now, DE is clearly recognized to be the approach that has the potential to solve NP-hard [4, 33] problems.Tanabe et al. and Ghosh and Das [34, 35] proposed a DE-based method for scheduling problems in grid computing environment whose purpose is to minimize the execution time and add more parameter adjustment to get high effects.Like other evolutionary approaches, DE performs the evolution of a population by using three kinds of the operator: crossover (recombination), mutation, and selection. The major difference between DE and genetic algorithm, a classical evolutionary algorithm, is due to the mutation operator. DE’s mutation operator uses orientation information to change solutions of the current population as follows.Given the population that is composed of solutions, each of them consists ofD components, and thus a particular solution is represented by a vector xi = (xi,2, xi,2,…, xi,D) where xi,j ∈ R, i = 1, 2, …, N; j = 1, 2, …, D.To create the mutated solutionvi of a given solution xi, DE picks out three random different solutions from the current population: xr1 ≠ xr2 ≠ xr3 ≠ xi, and then the mutation solution vi is determined as follows:(1)vi=xr1+Fxr2−xr3,where the value of the constant F, which plays the role of the mutant factor, is in the range [0, 1]. Because the mutant factor F is used to adjust the size of the directional vector, it is also called the directional hop length.After executing the mutation step, the crossover operation is carried out by combining the parent solutionxi and the mutation solution vi. The crossover operator is performed by selecting a random number CR (CR ∈ [0, 1]) as the probability of crossover. The result of the crossover step is represented by the vector (u1,1, u1,2, ... uN,D) where(2)ui,j=vi,jifrandi,j≤CR ori=Irandxi,jifrandi,j≥CR ori≠Irand.(i)
i = 1, 2, …, N; j = 1, 2,…, D.(ii)
randi,j: mutant factor.(iii)
Irand: a random number varies within the range [1,D]. Thanks to Irand, the mutation solution viis always different from the parent solution xi.Finally, the next generation is created from thexi and the ui as follows:(3)xit+1=uit,iffuit<fxit,xit,in other cases.Since 1997, various versions of DE have been developed by researchers. This paper proposes a variant of the DE algorithm which uses the following terminologies and conventions:(i)
A solution represents a schedule, that is, a plan for performing given tasks(ii)
The number of search space’s dimensions is equal to the number of tasks


## 2.1. Approximation Algorithms for MS-RCPSP

Scheduling problem arises in many practical situations [6–11]. In the general case, the scheduling is proved to be NP-hard. The authors of [5, 12, 13] show that MS-RCPSP, the problem we mentioned in this paper, is an NP-hard scheduling problem. In addition, MS-RCPSP is multimodal or discontinuous and very challenging to solve with traditional optimization methods. In the past few years, various approaches have been proposed to solve MS-RCPSP, thereby finding out intelligent algorithms to allocate and manage network resources in the Internet of things systems [14–17]. Some popular metaheuristic algorithms are the genetic algorithm (GA), ant colony optimization (ACO), and particle swarm optimization [18–22].Su et al. [23] used a mixed-integer model and discrete constraints to solve the problems. Maghsoudlou et al. [24] and Bibiks et al. [25] applied the cuckoo Search algorithm to plan for the multirisk project with three distinct evaluation objectives. Lin et al. [26] proposed a new solution based on GA and some other heuristic algorithms.Myszkowski et al. [5, 13] proposed the hybrid algorithm which is the combination of the differential evolution strategy and the greedy approach for arranging the human resources in product manufacturing projects and calculating time-of-use electricity tariffs and shift differential payments. The authors aimed to achieve the shortest makespan and low cost and gave a new benchmark dataset called iMOPSE [5], an artiﬁcially created dataset based on real-world instances for the MS-RCPSP.The MS-RCPSP is studied and applied in the planning of many practical areas of the Internet of things. Some authors also study new variants of the MS-RCPSP and apply them in different fields. Mejia [3] developed a new variant of the MS-RCPSP to coordinate research activities in the nuclear laboratory. Hosseinian [27] proposed two new algorithms, P-GWO and MOFA, to solve the MS-RCPSP with the deterioration effect and financial constraints (a case study of a gas treating company). In another study, Hosseinian et al. introduced a new mixed-integer formulation for the time-dependent MS-RCPSP considering the learning effect [28].Nemati-Lafmejani et al. [29] developed an integrated biobjective optimization model to deal with multimode RCPSP. The objective of the proposed model is to minimize both the costs and the makespan of the project. Tahrir and Yang [30] proposed a hybrid metaheuristic algorithm that combined ant colony optimization and variable neighbourhood search approaches for job scheduling in grid computing.Several prior research has also been conducted to solve other subproblems of RCPSP, the general problem of MS-RCPSP, to improve the efficiency of network resource management in specific fields of the Internet of things. Ballestin and Leus [31] and Javanmard [32] and their colleagues studied specific cases of RCPSPs such as multiskill stochastic and preemptive problem to calculate project implementation time, i.e., makespan, and build mathematical models for the project resource investment.


## 2.2. Differential Evolution Method

Differential evolution (DE) is a population-based stochastic optimization algorithm introduced by Storn and Price [4]. The advantages of DE lies in its simplicity, efficiency, and speed thanks to the local search method. DE deals with the old generation of the original population by using the mutation operator to create better solutions in the new generation. Until now, DE is clearly recognized to be the approach that has the potential to solve NP-hard [4, 33] problems.Tanabe et al. and Ghosh and Das [34, 35] proposed a DE-based method for scheduling problems in grid computing environment whose purpose is to minimize the execution time and add more parameter adjustment to get high effects.Like other evolutionary approaches, DE performs the evolution of a population by using three kinds of the operator: crossover (recombination), mutation, and selection. The major difference between DE and genetic algorithm, a classical evolutionary algorithm, is due to the mutation operator. DE’s mutation operator uses orientation information to change solutions of the current population as follows.Given the population that is composed of solutions, each of them consists ofD components, and thus a particular solution is represented by a vector xi = (xi,2, xi,2,…, xi,D) where xi,j ∈ R, i = 1, 2, …, N; j = 1, 2, …, D.To create the mutated solutionvi of a given solution xi, DE picks out three random different solutions from the current population: xr1 ≠ xr2 ≠ xr3 ≠ xi, and then the mutation solution vi is determined as follows:(1)vi=xr1+Fxr2−xr3,where the value of the constant F, which plays the role of the mutant factor, is in the range [0, 1]. Because the mutant factor F is used to adjust the size of the directional vector, it is also called the directional hop length.After executing the mutation step, the crossover operation is carried out by combining the parent solutionxi and the mutation solution vi. The crossover operator is performed by selecting a random number CR (CR ∈ [0, 1]) as the probability of crossover. The result of the crossover step is represented by the vector (u1,1, u1,2, ... uN,D) where(2)ui,j=vi,jifrandi,j≤CR ori=Irandxi,jifrandi,j≥CR ori≠Irand.(i)
i = 1, 2, …, N; j = 1, 2,…, D.(ii)
randi,j: mutant factor.(iii)
Irand: a random number varies within the range [1,D]. Thanks to Irand, the mutation solution viis always different from the parent solution xi.Finally, the next generation is created from thexi and the ui as follows:(3)xit+1=uit,iffuit<fxit,xit,in other cases.Since 1997, various versions of DE have been developed by researchers. This paper proposes a variant of the DE algorithm which uses the following terminologies and conventions:(i)
A solution represents a schedule, that is, a plan for performing given tasks(ii)
The number of search space’s dimensions is equal to the number of tasks


## 3. System Model and Definitions

### 3.1. RCPSP

MS-RCPSP is just a special case of RCPSP. Before the outline of the multiskill RCPSP, the description of the classical RCPSP would be introduced as follows.(i)
Assume a given project represented by a directed noncyclical graphG (V, E), where each node depicts a task and the arc represents finish-to-start precedence relationship between two tasks. The arc (u, v) ∈ E shows that the task u must be completed before task vbegins (Figure 1).(ii)
Without any difference, two empty tasks were added to the project. The first one is placed at the beginning of the project as the predecessor of every other task, whereas the second empty task is placed at the end of the process as the successor of other tasks.(iii)
The duration (also called execution time) of a certain task is calculated from the beginning time to the ending time of that task.(iv)
The execution progress of every task cannot be stopped until it is done.(v)
Each task needs an amount of resources for its execution.Figure 1
The relationship between tasks.The goal of the RCPSP is to find out a schedule of the task such that the precedence and resource constraints are satisfied and the makespan is minimized. RCPSP has been proved to be NP-hard [12]. Throughout the paper, we use the term “makespan” to refer to the execution time of the project, also called project duration. In the process of looking for the optimal schedule, both priority constraint between operations and resource constraint have to be met.


### 3.2. MS-RCPSP Formulation

In this paper, MS-RCPSP [5, 13, 36] was chosen because it is more practical than its general problem, RCPSP. MS-RCPSP uses the additional attribute, skill, in the problem formulation. Each task requires particular skills at the given levels to be executed, whereas each resource has some skills with given levels. Thus, the resource A is capable of performing the task B if A has skills required by B at the identical or higher level.Before deepening the study of MS-RCPSP, we take a look at some notations as follows:(i)
dj: the duration of task j; Pj: subset of the predecessors of task j(ii)
qj: subset of skills required by task j(iii)
Qk: the subset of skills owned by the resource k(iv)
Q: the set of skills, Qk ⊆ Q(v)
RS: the set of resources(vi)
T: the set of tasks(vii)
Tk: the set of tasks that resource k can perform, Tk ⊆ T(viii)
RSk: the set of resources that can perform task k, RSk ⊆ RS(ix)
Sj, Fj: start time and ﬁnish time of task j(x)
Uj,kt: Uj,kt = 1 in case of resource k is assigned to task j at given time t; Uj,kt = 0 in other cases(xi)
lq: the level of the given skill q; hq: type of the skill q(xii)
qj: the skill required by task j(xiii)
τ: duration of a schedule(xiv)
PS: a feasible schedule(xv)
PSall: the set of all feasible schedules(xvi)
f(PS): makespan of schedule PSEach schedule (PS) is responsible for coordinatingn tasks and m resources.Formally, MS-RCPSP could be stated as follows:(4)fPS⟶min,where(5)fPS=maxFi∈TFi−minFk∈TFk,(6)Qk≠Ø∀k∈RS,(7)dj≥0∀j∈T,(8)Fj≥0∀j∈T,(9)Fi≤Fj∀j∈T,j≠1,i∈Pj,(10)∀i∈Tk∃q∈Qk:hq=hqiandlq≥lqi,(11)∀k∈RS,∀t∈τ:∑i=1nUi,kt≤1,(12)∀j∈T∃!t∈τ,!k∈RS:Uj,kt=1,whereUj,kt∈0;1.


## 3.1. RCPSP

MS-RCPSP is just a special case of RCPSP. Before the outline of the multiskill RCPSP, the description of the classical RCPSP would be introduced as follows.(i)
Assume a given project represented by a directed noncyclical graphG (V, E), where each node depicts a task and the arc represents finish-to-start precedence relationship between two tasks. The arc (u, v) ∈ E shows that the task u must be completed before task vbegins (Figure 1).(ii)
Without any difference, two empty tasks were added to the project. The first one is placed at the beginning of the project as the predecessor of every other task, whereas the second empty task is placed at the end of the process as the successor of other tasks.(iii)
The duration (also called execution time) of a certain task is calculated from the beginning time to the ending time of that task.(iv)
The execution progress of every task cannot be stopped until it is done.(v)
Each task needs an amount of resources for its execution.Figure 1
The relationship between tasks.The goal of the RCPSP is to find out a schedule of the task such that the precedence and resource constraints are satisfied and the makespan is minimized. RCPSP has been proved to be NP-hard [12]. Throughout the paper, we use the term “makespan” to refer to the execution time of the project, also called project duration. In the process of looking for the optimal schedule, both priority constraint between operations and resource constraint have to be met.


## 3.2. MS-RCPSP Formulation

In this paper, MS-RCPSP [5, 13, 36] was chosen because it is more practical than its general problem, RCPSP. MS-RCPSP uses the additional attribute, skill, in the problem formulation. Each task requires particular skills at the given levels to be executed, whereas each resource has some skills with given levels. Thus, the resource A is capable of performing the task B if A has skills required by B at the identical or higher level.Before deepening the study of MS-RCPSP, we take a look at some notations as follows:(i)
dj: the duration of task j; Pj: subset of the predecessors of task j(ii)
qj: subset of skills required by task j(iii)
Qk: the subset of skills owned by the resource k(iv)
Q: the set of skills, Qk ⊆ Q(v)
RS: the set of resources(vi)
T: the set of tasks(vii)
Tk: the set of tasks that resource k can perform, Tk ⊆ T(viii)
RSk: the set of resources that can perform task k, RSk ⊆ RS(ix)
Sj, Fj: start time and ﬁnish time of task j(x)
Uj,kt: Uj,kt = 1 in case of resource k is assigned to task j at given time t; Uj,kt = 0 in other cases(xi)
lq: the level of the given skill q; hq: type of the skill q(xii)
qj: the skill required by task j(xiii)
τ: duration of a schedule(xiv)
PS: a feasible schedule(xv)
PSall: the set of all feasible schedules(xvi)
f(PS): makespan of schedule PSEach schedule (PS) is responsible for coordinatingn tasks and m resources.Formally, MS-RCPSP could be stated as follows:(4)fPS⟶min,where(5)fPS=maxFi∈TFi−minFk∈TFk,(6)Qk≠Ø∀k∈RS,(7)dj≥0∀j∈T,(8)Fj≥0∀j∈T,(9)Fi≤Fj∀j∈T,j≠1,i∈Pj,(10)∀i∈Tk∃q∈Qk:hq=hqiandlq≥lqi,(11)∀k∈RS,∀t∈τ:∑i=1nUi,kt≤1,(12)∀j∈T∃!t∈τ,!k∈RS:Uj,kt=1,whereUj,kt∈0;1.


## 4. Proposed Algorithm

### 4.1. Schedule Representation

In this study, every schedule or solution is represented by a vector that consists of elements; the number of elements (size of the vector) and the number of tasks are the same. The value of a certain element depicts the resource that can execute the corresponding task.Example 1.
Given a set of taskT = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} and a set of resource RS = {1, 2, 3}. The MS-RCPSP’s goal is to find out a schedule in which the makespan can be minimized while meeting priority constraints between tasks (Figure 1).
Consider a set of taskT = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} and set of resource RS = {1, 2, 3}. Priority constraints between tasks are depicted in Figure 1, whereby task 1 is the predecessor of task 2, and thus task 2 cannot be performed until task 1 is finished: S2 ≥ F1. There is no relation between task 3 and task 4; therefore, they are executed concurrently or sequentially.
Besides, in this example, we assume that(i)
sk = si ∀k, i ∈ RS(ii)
Qk = Q ∀k ∈ RS(iii)
RSk = RS ∀k ∈ RS
The duration of the tasks is given in Table1.
A feasible schedule for the project is demonstrated in Figure2, where it can be seen that the makespan is 15.
The above schedule is demonstrated in Table2, where resource 1 performed tasks number 1, 2, 6, 8, and 9; resource 2 is assigned to execute tasks number 3 and 7; resource 3 deals with the remaining tasks.Table 1
Task duration.
Task12345678910Duration2435225342Figure 2
A feasible schedule.Table 2
Resource-task assignment.
Task12345678910Resource1123312113


### 4.2. Measurement Model

The differential evolution algorithm was primarily designed for real-valued data. However, like most of the other scheduling problems, MS-RCPSP deals with discrete values, and thus there is a need for the discrete variant of DE. In addition, this discrete DE algorithm needs a model for representing the MS-RCPSP’s factors such as the difference between two schedules. In this paper, we build a new measurement model for measuring the difference between the two schedules as follows:(i)
Unit vectorP=(p1, p2, ..., pn); pi = 100/(k i − 1), where ki is the number of resources that can execute task i(ii)
The difference between scheduleX=(x1, x2, ..., xn) and schedule Y=(y1, y2, ..., yn) is denoted by the differential vector D = X – Y=(d1, d2, ..., dn)where(13)di=pi×orderxi−orderyi,order (xi): the position of the resource (xi) in the RSi(iii)
The sum of the scheduleY and differential vector D is the schedule X=(x1, x2, ..., xn)where(14)xi=positionroundyi+di,position (i): the resource corresponding to the position iExample 2.
Assume that there are 6 resources that could handle task 1: RS1 = {R1, R3, R4, R5, R9, R10}. Thus, k1 = 6; p1 = 100/(6–1) = 20. Assume that there are 5 resources that could handle task 2: RS2 = {R3, R5, R7, R8, R10 }. Thus, k2 = 5; p2 = 100/(5–1) = 25. The resource order in measurement model is presented in Table 3.
Consider 2 schedules:X=(3, 5); Y=(5, 10). The task assignment is shown in Table 4.
D = X–Y=(d1, d2), where d1 = p1. Abs (order (x1)−order (y1)) = 20. Abs (1–3) = 40.
d2 = p2. Abs (order (x2)−order (y2)) = 25. Abs (1–4) = 75. Thus, D=(40, 75). Consider D’=(35.71, 5.23). As shown in Table 5, we have Z = X+ D’=(5, 8).Table 3
Resource order in measurement model.
Order012345ResourceR1R3R4R5R9R10ResourceR3R5R7R8R10Table 4
Schedule’s task-resource assignment.
ScheduleTask12XR3R5YR5R10Table 5
Measurement value.
Task12XR3R5D′35.715.23Pi. order (xi)2060X + D′55.7165.23Z = X+ D′R5R8


### 4.3. Proposed DEM Algorithm

The proposed algorithm (differential evolution multiskill, or DEM) is described in Algorithm1:(i)
Stop criterion: the loopwhile-end while would be stopped if the difference between makespan of some continuous generations is smaller than a threshold(ii)
Size: number of solutions in the population(iii)
F: parameter of the mutation operator(iv)
CR: crossover probability(v)
n: number of tasksAlgorithm 1: DEM algorithm.
(1)
Begin(2)
Load and validate iMOPSE dataset(3)
t⟵0(4)
Size⟵size of the population(5)
P(t)⟵Initial population(6)
f(t)⟵Calculate the fitness and makespan(7)
while (Stop criterion)(8)
for (inti = 0; i < Size; i++)(9)
xr1≠xr2≠xr3≠xi⟵rand (1,Size)(10)
F⟵rand (0, 1)(11)
vi(t) ⟵ xr1 + F×(xr−xr3)// parameter of the mutation operator(12)
for (j = 0; j < n; j++)(13)
ui,j=vi,jifrandi,j≤CR ori=Irandxi,jifrandi,j≥CR ori≠Irand(14)
end for(15)
if (f (ui (t)) ≤ f(xi(t)))(16)
xi (t+1) = ui(t)(17)
else(18)
xi (t+1) = xi (t)(19)
end if(20)
end for(21)
Calculate the fitness and bestnest(22)
If (makespan > min (fitness))(23)
makespan = min (fitness)(24)
End if(25)
bestnest ⟵ Reallocate (bestnest)(26)
t ⟵ t + 1(27)
end while(28)
return makespan(29)
EndAs shown in line 25, after classical DE steps such as mutation and selection are executed, functionReallocate() is called to reduce the makespan of the candidate schedule bestnest. Procedures of this function will be dealt with in more detail in the next section (Algorithm 2):currentBest: the best schedule among the population of the current generation.Rb : According to the arrangement of schedule newbest (line 3), Rb is the last resource that finishes its job. In Figure 3, before the reallocate function was called, Rb is resource 1.maxResource(): the function which returns the last resource to finish (line 3).size(): the function which returns the number of elements of the given set or array (line 5).newmakespan: makespan of the new schedule (line 11), which is obtained from the old schedule by reassigning taski. The task i is moved from resource Rb (line 9) to resource Ri[j] (line 10).Algorithm 2: Function reallocate.
Input: currentBest //the best schedule among the current populationOutput: //the improved schedule(1) Begin(2) makespan =f(best)(3) newbest = currentBest;(4)Rb ⟵ maxResource (newbest) //the last resource to finish its job(5)Tb ⟵ set of tasks is performed by resource Rb(6) Fori = 1 to size(Tb) // Consider each task in Tb, the set of tasks performed by resource Rb(7)Ti = Tb [i];(8)Ri ⟵ set of resource that are skilled enough to execute the task i except Rb(9)  Forj = 1 to size (Ri) // Consider each resource in turn(10)Ri[j] = Ri[j] + {i} // Reassign task i to resource Ri[j](11)Rb = Rb – {i} // Remove task i from the task list of Rb(12)   newmakespan =f(newbest) // The makespan of the new schedule(13)   If newmakespan < makespan(14)   makespan = newmakespan(15)   Return newbest; // Successful Reallocate, return the new and better schedule(16)   End if(17)   newbest = currentBest; // Unsuccessful Reallocate, reuse the original schedule for the next iteration(18)   End for(19)  End for(20) Return best(21) End FunctionFigure 3
Function reallocate.


### 4.4. Function Reallocate

Line 12 and 13 demonstrate that the new schedule (newbest) is better than the old schedule (currentBest) in terms of makespan, which means that the functionReallocate certainly returns a better schedule. Moreover, the function Reallocate guides DEM algorithm in the right direction by finding a new schedule (newbest) based on the best solution (currentBest); therefore, it inherits the advanced genomes of the population as well as the old schedule.Example 3.
Given set of taskT = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, set of resource RS = {1, 2, 3}. Resource 1 can execute tasks 1, 2, 3, 4, 6, 8, 9, and 10; resource 2 can perform tasks 1, 3, 7, and 9; resource 3 can handle tasks 1, 4, 5, 8, 9, and 10. The relationship between tasks is depicted in Figure 1, and the duration of the tasks is given in Table 1.
Consider a schedule (PS) as shown in Table6. From observation, Figure 4 shows that makespan f(PS) = 17.
New schedule, the result of the functionReallocate, is described in Table 7.
Figure4 illustrates that function Reallocate converts the schedule PS into the new schedule by assigning task 9 to resource 2 instead of resource 1 as before. Thanks to this allocation, the new schedule achieves better makespan (15) compared to the old schedule (17).Table 6
Resource-task assignment of PS.
Task12345678910Resource1123312133Figure 4
Gantt diagram of schedule before and after functionReallocate.Table 7
Resource-task assignment of new schedule.
Task12345678910Resource1123312113


## 4.1. Schedule Representation

In this study, every schedule or solution is represented by a vector that consists of elements; the number of elements (size of the vector) and the number of tasks are the same. The value of a certain element depicts the resource that can execute the corresponding task.Example 1.
Given a set of taskT = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} and a set of resource RS = {1, 2, 3}. The MS-RCPSP’s goal is to find out a schedule in which the makespan can be minimized while meeting priority constraints between tasks (Figure 1).
Consider a set of taskT = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} and set of resource RS = {1, 2, 3}. Priority constraints between tasks are depicted in Figure 1, whereby task 1 is the predecessor of task 2, and thus task 2 cannot be performed until task 1 is finished: S2 ≥ F1. There is no relation between task 3 and task 4; therefore, they are executed concurrently or sequentially.
Besides, in this example, we assume that(i)
sk = si ∀k, i ∈ RS(ii)
Qk = Q ∀k ∈ RS(iii)
RSk = RS ∀k ∈ RS
The duration of the tasks is given in Table1.
A feasible schedule for the project is demonstrated in Figure2, where it can be seen that the makespan is 15.
The above schedule is demonstrated in Table2, where resource 1 performed tasks number 1, 2, 6, 8, and 9; resource 2 is assigned to execute tasks number 3 and 7; resource 3 deals with the remaining tasks.Table 1
Task duration.
Task12345678910Duration2435225342Figure 2
A feasible schedule.Table 2
Resource-task assignment.
Task12345678910Resource1123312113


## 4.2. Measurement Model

The differential evolution algorithm was primarily designed for real-valued data. However, like most of the other scheduling problems, MS-RCPSP deals with discrete values, and thus there is a need for the discrete variant of DE. In addition, this discrete DE algorithm needs a model for representing the MS-RCPSP’s factors such as the difference between two schedules. In this paper, we build a new measurement model for measuring the difference between the two schedules as follows:(i)
Unit vectorP=(p1, p2, ..., pn); pi = 100/(k i − 1), where ki is the number of resources that can execute task i(ii)
The difference between scheduleX=(x1, x2, ..., xn) and schedule Y=(y1, y2, ..., yn) is denoted by the differential vector D = X – Y=(d1, d2, ..., dn)where(13)di=pi×orderxi−orderyi,order (xi): the position of the resource (xi) in the RSi(iii)
The sum of the scheduleY and differential vector D is the schedule X=(x1, x2, ..., xn)where(14)xi=positionroundyi+di,position (i): the resource corresponding to the position iExample 2.
Assume that there are 6 resources that could handle task 1: RS1 = {R1, R3, R4, R5, R9, R10}. Thus, k1 = 6; p1 = 100/(6–1) = 20. Assume that there are 5 resources that could handle task 2: RS2 = {R3, R5, R7, R8, R10 }. Thus, k2 = 5; p2 = 100/(5–1) = 25. The resource order in measurement model is presented in Table 3.
Consider 2 schedules:X=(3, 5); Y=(5, 10). The task assignment is shown in Table 4.
D = X–Y=(d1, d2), where d1 = p1. Abs (order (x1)−order (y1)) = 20. Abs (1–3) = 40.
d2 = p2. Abs (order (x2)−order (y2)) = 25. Abs (1–4) = 75. Thus, D=(40, 75). Consider D’=(35.71, 5.23). As shown in Table 5, we have Z = X+ D’=(5, 8).Table 3
Resource order in measurement model.
Order012345ResourceR1R3R4R5R9R10ResourceR3R5R7R8R10Table 4
Schedule’s task-resource assignment.
ScheduleTask12XR3R5YR5R10Table 5
Measurement value.
Task12XR3R5D′35.715.23Pi. order (xi)2060X + D′55.7165.23Z = X+ D′R5R8


## 4.3. Proposed DEM Algorithm

The proposed algorithm (differential evolution multiskill, or DEM) is described in Algorithm1:(i)
Stop criterion: the loopwhile-end while would be stopped if the difference between makespan of some continuous generations is smaller than a threshold(ii)
Size: number of solutions in the population(iii)
F: parameter of the mutation operator(iv)
CR: crossover probability(v)
n: number of tasksAlgorithm 1: DEM algorithm.
(1)
Begin(2)
Load and validate iMOPSE dataset(3)
t⟵0(4)
Size⟵size of the population(5)
P(t)⟵Initial population(6)
f(t)⟵Calculate the fitness and makespan(7)
while (Stop criterion)(8)
for (inti = 0; i < Size; i++)(9)
xr1≠xr2≠xr3≠xi⟵rand (1,Size)(10)
F⟵rand (0, 1)(11)
vi(t) ⟵ xr1 + F×(xr−xr3)// parameter of the mutation operator(12)
for (j = 0; j < n; j++)(13)
ui,j=vi,jifrandi,j≤CR ori=Irandxi,jifrandi,j≥CR ori≠Irand(14)
end for(15)
if (f (ui (t)) ≤ f(xi(t)))(16)
xi (t+1) = ui(t)(17)
else(18)
xi (t+1) = xi (t)(19)
end if(20)
end for(21)
Calculate the fitness and bestnest(22)
If (makespan > min (fitness))(23)
makespan = min (fitness)(24)
End if(25)
bestnest ⟵ Reallocate (bestnest)(26)
t ⟵ t + 1(27)
end while(28)
return makespan(29)
EndAs shown in line 25, after classical DE steps such as mutation and selection are executed, functionReallocate() is called to reduce the makespan of the candidate schedule bestnest. Procedures of this function will be dealt with in more detail in the next section (Algorithm 2):currentBest: the best schedule among the population of the current generation.Rb : According to the arrangement of schedule newbest (line 3), Rb is the last resource that finishes its job. In Figure 3, before the reallocate function was called, Rb is resource 1.maxResource(): the function which returns the last resource to finish (line 3).size(): the function which returns the number of elements of the given set or array (line 5).newmakespan: makespan of the new schedule (line 11), which is obtained from the old schedule by reassigning taski. The task i is moved from resource Rb (line 9) to resource Ri[j] (line 10).Algorithm 2: Function reallocate.
Input: currentBest //the best schedule among the current populationOutput: //the improved schedule(1) Begin(2) makespan =f(best)(3) newbest = currentBest;(4)Rb ⟵ maxResource (newbest) //the last resource to finish its job(5)Tb ⟵ set of tasks is performed by resource Rb(6) Fori = 1 to size(Tb) // Consider each task in Tb, the set of tasks performed by resource Rb(7)Ti = Tb [i];(8)Ri ⟵ set of resource that are skilled enough to execute the task i except Rb(9)  Forj = 1 to size (Ri) // Consider each resource in turn(10)Ri[j] = Ri[j] + {i} // Reassign task i to resource Ri[j](11)Rb = Rb – {i} // Remove task i from the task list of Rb(12)   newmakespan =f(newbest) // The makespan of the new schedule(13)   If newmakespan < makespan(14)   makespan = newmakespan(15)   Return newbest; // Successful Reallocate, return the new and better schedule(16)   End if(17)   newbest = currentBest; // Unsuccessful Reallocate, reuse the original schedule for the next iteration(18)   End for(19)  End for(20) Return best(21) End FunctionFigure 3
Function reallocate.


## 4.4. Function Reallocate

Line 12 and 13 demonstrate that the new schedule (newbest) is better than the old schedule (currentBest) in terms of makespan, which means that the functionReallocate certainly returns a better schedule. Moreover, the function Reallocate guides DEM algorithm in the right direction by finding a new schedule (newbest) based on the best solution (currentBest); therefore, it inherits the advanced genomes of the population as well as the old schedule.Example 3.
Given set of taskT = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, set of resource RS = {1, 2, 3}. Resource 1 can execute tasks 1, 2, 3, 4, 6, 8, 9, and 10; resource 2 can perform tasks 1, 3, 7, and 9; resource 3 can handle tasks 1, 4, 5, 8, 9, and 10. The relationship between tasks is depicted in Figure 1, and the duration of the tasks is given in Table 1.
Consider a schedule (PS) as shown in Table6. From observation, Figure 4 shows that makespan f(PS) = 17.
New schedule, the result of the functionReallocate, is described in Table 7.
Figure4 illustrates that function Reallocate converts the schedule PS into the new schedule by assigning task 9 to resource 2 instead of resource 1 as before. Thanks to this allocation, the new schedule achieves better makespan (15) compared to the old schedule (17).Table 6
Resource-task assignment of PS.
Task12345678910Resource1123312133Figure 4
Gantt diagram of schedule before and after functionReallocate.Table 7
Resource-task assignment of new schedule.
Task12345678910Resource1123312113


## 5. Experiment

Experiments were conducted on the simulated dataset and the real dataset to evaluate the performance of proposed algorithms in comparison with previous algorithms such as GreedyDO and GA. We first utilize the simulated iMOPSE dataset, a collection of project instances that are artificially created based on a database obtained from the international company, to evaluate the performance of the proposed algorithm.


### 5.1. Simulation on Simulated Dataset

#### 5.1.1. iMOPSE Dataset

The simulated dataset iMOPSE [5] has been used to investigate existing algorithms GreedyDO  and GA [13, 36]; therefore, we conduct simulations on iMOPSE dataset to fairly compare between DEM and those algorithms.As shown in Table8, iMOPSE’s instances are classified into 15 categories according to the following attributes:(i)
The number of tasks and resources(ii)
The number of precedence relations between tasks(iii)
The number of skillsTable 8
MS-RCPSP d36 iMOPSE dataset.
Dataset instanceTasksResourcesPrecedence relationsSkills100_5_48_91005489100_5_64_1510056415100_5_64_91005649100_10_64_910010649100_10_65_15100106515100_20_65_15100206515100_20_65_910020659200_10_84_920010849200_10_85_15200108515200_20_55_920020559200_20_97_15200209715200_20_97_920020979200_40_45_920040459200_40_90_920040909200_40_91_15200409115All simulations were run on a PC with Intel Core i5-CPU 2.2 GHz, 6 GB RAM, and operating system Windows 10. All of iMOPSE instances used by our simulations are listed in Table8.


#### 5.1.2. Parameters and System Settings

The simulation is conducted by using the following:(i)
Simulation environment: Matlab ver. 2014(ii)
Simulation tool: the performance of previous algorithms such as GA is fairly evaluated by using GARunner [13]; the simulation tool was provided by the author of those algorithms(iii)
Input data: 15 iMOPSE instances that are described in Table8(iv)
Number of solution in the populationNp: 100(v)
Number of generationsNg: 50,000(vi)
Since all of the considered algorithms are approximate, we run on each instance 35 times to get average value, the standard deviation value, and the best value


#### 5.1.3. Simulation Results

Simulation results are shown in Tables9 and 10, where the makespan of the best solutions found by GreedyDO, GA, and the proposed algorithm (DEM) is illustrated (in hours). Table 9 shows that the makespans acquired by GA are always better than those acquired by GreedyDO.Table 9
The makespan of the best solutions found by GreedyDO and GA.
Dataset instanceGreedyDOGA100_5_48_9779528100_5_64_15640527100_5_64_9597508100_10_64_9533296100_10_65_15426286100_20_65_15310240100_20_65_9408181200_10_84_9999567200_10_85_15706549200_20_55_9999312200_20_97_15680424200_20_97_9816321200_40_45_9821209200_40_90_9963211200_40_91_15519200Table 10
The average value, the best value, and the standard deviation of makespan obtained from GA and DEM.
Dataset instanceGADEMAvgBestStdAvgBestStd100_5_48_95355289.74984920.50100_5_64_155305272.55105041.50100_5_64_95215089.94884851.00100_10_64_93052966.62642571.50100_10_65_152902865.02632580.50100_20_65_152402400.02112100.50100_20_65_91871814.51731581.00200_10_84_958356711.45375273.00200_10_85_155555494.94924900.50200_20_55_93183124.23102900.50200_20_97_154384249.73363300.00200_20_97_93263216.23143063.00200_40_45_92132092.92172071.50200_40_90_92152113.12172061.00200_40_91_152052003.42051913.50Table10 illustrates the average value, the best value, and the standard deviation of the makespan found by GA and the proposed DEM algorithm.From the observation, the result in Tables9 and 10 shows that(i)
The solutions found by DEM are better than Greedy from 16% to 78% and GA from 0% to 21%.(ii)
Regarding the average value (Table9): DEM is better than Greedy from 15% to 77.5% and GA from 0.7% to 20.8%.(iii)
Inspired by the differential evolution strategy, the proposed algorithm uses two parameters to guide the generation of the solution generated in the next generation: (i) the experience vector of both the population and (ii) the experience vector of the solution across different generations. DEM not only inherits those advantages of differential evolution approach but also utilizes the function reallocate, which improves its performance. Therefore, DEM has faster convergence and greater stability, which is shown by the standard deviation in Table9 (column Std). The total standard deviation of DEM is 19.5 while the value of GA is 55.7; this result proves that the stability of DEM algorithm is better than GA.(iv)
In addition, the use of a scale to represent solutions helps DEM calculate the deviations between solutions more accurately and create better solutions in the next generations.


### 5.2. Simulation on Real Dataset

#### 5.2.1. TNG Dataset

Experiments conducted on the simulated dataset are sometimes inaccurate and unsatisfactory. To overcome this drawback, we collected the dataset of TNG Investment and Trading Joint Stock Company [37], a well-known national textile company. TNG dataset instances have the following characteristics and parameters:(i)
The company has product sewing contracts under the business partners' contracts; each order places a sample of a product in large quantities(ii)
Each product has a certain number of stages, each of which requires a certain time to complete(iii)
Each order will be assigned to a group of workers(iv)
Each group consists of many workers(v)
Each worker's skills are rated based on his rankThe above parameters of the dataset have been converted to a suitable format as shown in Table11.Table 11
Parameters conversion.
Real factor or parameterThe roleOrderProjectStage of the productTaskTime to execute the stageDuration of the given taskWorkerResourceThe worker gradeSkill level of the resourceThe order in which the tasks are executedThe priority of the tasksOrder execution timeThe total time of project implementation, i.e., the makespanTable11 demonstrates that the TNG dataset parameters will be represented as follows:(i)
The order from the business partners’ is represented by a project(ii)
The stage of the product is represented by a task(iii)
A worker in the factory is represented by a resource in the problem formulation(iv)
The worker grade is represented by the skill level of the resource(v)
The order in which the tasks are executed is represented by the priority of the tasks(vi)
Order execution time is represented by the total time of project implementation, i.e., the makespanAfter the conversion, the dataset is shown in Table12Table 12
TNG dataset.
Dataset instanceNumber of tasksNumber of resourcesPrecedence relationsSkill levelsProject timeTNG1713710266409TNG2713910266325TNG3714110266296TNG4714510266392TNG513737189461174TNG613739189461052TNG71374118946871TNG81374518946996


#### 5.2.2. Parameters and System Settings

Experiment setting:(i)
Input data: 8 instances that are listed in Table12(ii)
Number of the solution in the populationNp: 100(iii)
Number of generationsNg: 50,000(iv)
Like simulation on the simulated dataset, we run on each TNG dataset instance 35 times to get the best value


#### 5.2.3. Simulation Results

To prove the effectiveness of the proposed algorithm (DEM), we carry out experiments by using the real-world dataset collected from the TNG company. DEM will be compared with other algorithms from previous research studies, GreedyDO and GA. The performance of these algorithms is recorded and observed by using GARunner, the tool created by Myszkowski et al. [13].Table13 contains the makespan (measured in hours) of the best solution achieved by GreedyDO, GA, and DEM. In addition, the performing intervals of the actual projects at the TNG factory are shown in column TNG.Table13 proves that schedules found by DEM are better than those acquired by GA and GreedyDO. Table 13 and Figure 5 also highlight that the schedules found by evolutionary algorithms are always shorter than the execution time of the actual projects at the TNG factory.Table 13
Comparison between the makespan of real TNG project and makespan of schedule found by GreedyDO, GA, and DEM.
Dataset instanceTNGGreedyDOGADEMTNG1409236201165TNG2325243198166TNG3296258212166TNG4392248176165TNG51174972751712TNG61052963791712TNG7871834810728TNG8996906720675Figure 5
The comparison of makespan between DEM, GA, and TNG’s solution.Compared to the execution time at the TNG factory, the GreedyDO and GA algorithms reduce the makespan by 4%–42% and 7%–51%, respectively, while DEM has the best results of 16%–61%. This result is understandable because so far all projects have been manually scheduled based on the scheduler's experience.This statistical analysis of the experimental result proves that DEM achieved better solutions than the previous algorithms. Thanks to the directed nature, DEM not only ensures fast convergence but also averts getting trapped in local extrema. In experiments conducted on the TNG dataset, DEM reduces the makespan from 16% to 61% compared to the current factory schedule.


## 5.1. Simulation on Simulated Dataset

### 5.1.1. iMOPSE Dataset

The simulated dataset iMOPSE [5] has been used to investigate existing algorithms GreedyDO  and GA [13, 36]; therefore, we conduct simulations on iMOPSE dataset to fairly compare between DEM and those algorithms.As shown in Table8, iMOPSE’s instances are classified into 15 categories according to the following attributes:(i)
The number of tasks and resources(ii)
The number of precedence relations between tasks(iii)
The number of skillsTable 8
MS-RCPSP d36 iMOPSE dataset.
Dataset instanceTasksResourcesPrecedence relationsSkills100_5_48_91005489100_5_64_1510056415100_5_64_91005649100_10_64_910010649100_10_65_15100106515100_20_65_15100206515100_20_65_910020659200_10_84_920010849200_10_85_15200108515200_20_55_920020559200_20_97_15200209715200_20_97_920020979200_40_45_920040459200_40_90_920040909200_40_91_15200409115All simulations were run on a PC with Intel Core i5-CPU 2.2 GHz, 6 GB RAM, and operating system Windows 10. All of iMOPSE instances used by our simulations are listed in Table8.


### 5.1.2. Parameters and System Settings

The simulation is conducted by using the following:(i)
Simulation environment: Matlab ver. 2014(ii)
Simulation tool: the performance of previous algorithms such as GA is fairly evaluated by using GARunner [13]; the simulation tool was provided by the author of those algorithms(iii)
Input data: 15 iMOPSE instances that are described in Table8(iv)
Number of solution in the populationNp: 100(v)
Number of generationsNg: 50,000(vi)
Since all of the considered algorithms are approximate, we run on each instance 35 times to get average value, the standard deviation value, and the best value


### 5.1.3. Simulation Results

Simulation results are shown in Tables9 and 10, where the makespan of the best solutions found by GreedyDO, GA, and the proposed algorithm (DEM) is illustrated (in hours). Table 9 shows that the makespans acquired by GA are always better than those acquired by GreedyDO.Table 9
The makespan of the best solutions found by GreedyDO and GA.
Dataset instanceGreedyDOGA100_5_48_9779528100_5_64_15640527100_5_64_9597508100_10_64_9533296100_10_65_15426286100_20_65_15310240100_20_65_9408181200_10_84_9999567200_10_85_15706549200_20_55_9999312200_20_97_15680424200_20_97_9816321200_40_45_9821209200_40_90_9963211200_40_91_15519200Table 10
The average value, the best value, and the standard deviation of makespan obtained from GA and DEM.
Dataset instanceGADEMAvgBestStdAvgBestStd100_5_48_95355289.74984920.50100_5_64_155305272.55105041.50100_5_64_95215089.94884851.00100_10_64_93052966.62642571.50100_10_65_152902865.02632580.50100_20_65_152402400.02112100.50100_20_65_91871814.51731581.00200_10_84_958356711.45375273.00200_10_85_155555494.94924900.50200_20_55_93183124.23102900.50200_20_97_154384249.73363300.00200_20_97_93263216.23143063.00200_40_45_92132092.92172071.50200_40_90_92152113.12172061.00200_40_91_152052003.42051913.50Table10 illustrates the average value, the best value, and the standard deviation of the makespan found by GA and the proposed DEM algorithm.From the observation, the result in Tables9 and 10 shows that(i)
The solutions found by DEM are better than Greedy from 16% to 78% and GA from 0% to 21%.(ii)
Regarding the average value (Table9): DEM is better than Greedy from 15% to 77.5% and GA from 0.7% to 20.8%.(iii)
Inspired by the differential evolution strategy, the proposed algorithm uses two parameters to guide the generation of the solution generated in the next generation: (i) the experience vector of both the population and (ii) the experience vector of the solution across different generations. DEM not only inherits those advantages of differential evolution approach but also utilizes the function reallocate, which improves its performance. Therefore, DEM has faster convergence and greater stability, which is shown by the standard deviation in Table9 (column Std). The total standard deviation of DEM is 19.5 while the value of GA is 55.7; this result proves that the stability of DEM algorithm is better than GA.(iv)
In addition, the use of a scale to represent solutions helps DEM calculate the deviations between solutions more accurately and create better solutions in the next generations.


## 5.1.1. iMOPSE Dataset

The simulated dataset iMOPSE [5] has been used to investigate existing algorithms GreedyDO  and GA [13, 36]; therefore, we conduct simulations on iMOPSE dataset to fairly compare between DEM and those algorithms.As shown in Table8, iMOPSE’s instances are classified into 15 categories according to the following attributes:(i)
The number of tasks and resources(ii)
The number of precedence relations between tasks(iii)
The number of skillsTable 8
MS-RCPSP d36 iMOPSE dataset.
Dataset instanceTasksResourcesPrecedence relationsSkills100_5_48_91005489100_5_64_1510056415100_5_64_91005649100_10_64_910010649100_10_65_15100106515100_20_65_15100206515100_20_65_910020659200_10_84_920010849200_10_85_15200108515200_20_55_920020559200_20_97_15200209715200_20_97_920020979200_40_45_920040459200_40_90_920040909200_40_91_15200409115All simulations were run on a PC with Intel Core i5-CPU 2.2 GHz, 6 GB RAM, and operating system Windows 10. All of iMOPSE instances used by our simulations are listed in Table8.


## 5.1.2. Parameters and System Settings

The simulation is conducted by using the following:(i)
Simulation environment: Matlab ver. 2014(ii)
Simulation tool: the performance of previous algorithms such as GA is fairly evaluated by using GARunner [13]; the simulation tool was provided by the author of those algorithms(iii)
Input data: 15 iMOPSE instances that are described in Table8(iv)
Number of solution in the populationNp: 100(v)
Number of generationsNg: 50,000(vi)
Since all of the considered algorithms are approximate, we run on each instance 35 times to get average value, the standard deviation value, and the best value


## 5.1.3. Simulation Results

Simulation results are shown in Tables9 and 10, where the makespan of the best solutions found by GreedyDO, GA, and the proposed algorithm (DEM) is illustrated (in hours). Table 9 shows that the makespans acquired by GA are always better than those acquired by GreedyDO.Table 9
The makespan of the best solutions found by GreedyDO and GA.
Dataset instanceGreedyDOGA100_5_48_9779528100_5_64_15640527100_5_64_9597508100_10_64_9533296100_10_65_15426286100_20_65_15310240100_20_65_9408181200_10_84_9999567200_10_85_15706549200_20_55_9999312200_20_97_15680424200_20_97_9816321200_40_45_9821209200_40_90_9963211200_40_91_15519200Table 10
The average value, the best value, and the standard deviation of makespan obtained from GA and DEM.
Dataset instanceGADEMAvgBestStdAvgBestStd100_5_48_95355289.74984920.50100_5_64_155305272.55105041.50100_5_64_95215089.94884851.00100_10_64_93052966.62642571.50100_10_65_152902865.02632580.50100_20_65_152402400.02112100.50100_20_65_91871814.51731581.00200_10_84_958356711.45375273.00200_10_85_155555494.94924900.50200_20_55_93183124.23102900.50200_20_97_154384249.73363300.00200_20_97_93263216.23143063.00200_40_45_92132092.92172071.50200_40_90_92152113.12172061.00200_40_91_152052003.42051913.50Table10 illustrates the average value, the best value, and the standard deviation of the makespan found by GA and the proposed DEM algorithm.From the observation, the result in Tables9 and 10 shows that(i)
The solutions found by DEM are better than Greedy from 16% to 78% and GA from 0% to 21%.(ii)
Regarding the average value (Table9): DEM is better than Greedy from 15% to 77.5% and GA from 0.7% to 20.8%.(iii)
Inspired by the differential evolution strategy, the proposed algorithm uses two parameters to guide the generation of the solution generated in the next generation: (i) the experience vector of both the population and (ii) the experience vector of the solution across different generations. DEM not only inherits those advantages of differential evolution approach but also utilizes the function reallocate, which improves its performance. Therefore, DEM has faster convergence and greater stability, which is shown by the standard deviation in Table9 (column Std). The total standard deviation of DEM is 19.5 while the value of GA is 55.7; this result proves that the stability of DEM algorithm is better than GA.(iv)
In addition, the use of a scale to represent solutions helps DEM calculate the deviations between solutions more accurately and create better solutions in the next generations.


## 5.2. Simulation on Real Dataset

### 5.2.1. TNG Dataset

Experiments conducted on the simulated dataset are sometimes inaccurate and unsatisfactory. To overcome this drawback, we collected the dataset of TNG Investment and Trading Joint Stock Company [37], a well-known national textile company. TNG dataset instances have the following characteristics and parameters:(i)
The company has product sewing contracts under the business partners' contracts; each order places a sample of a product in large quantities(ii)
Each product has a certain number of stages, each of which requires a certain time to complete(iii)
Each order will be assigned to a group of workers(iv)
Each group consists of many workers(v)
Each worker's skills are rated based on his rankThe above parameters of the dataset have been converted to a suitable format as shown in Table11.Table 11
Parameters conversion.
Real factor or parameterThe roleOrderProjectStage of the productTaskTime to execute the stageDuration of the given taskWorkerResourceThe worker gradeSkill level of the resourceThe order in which the tasks are executedThe priority of the tasksOrder execution timeThe total time of project implementation, i.e., the makespanTable11 demonstrates that the TNG dataset parameters will be represented as follows:(i)
The order from the business partners’ is represented by a project(ii)
The stage of the product is represented by a task(iii)
A worker in the factory is represented by a resource in the problem formulation(iv)
The worker grade is represented by the skill level of the resource(v)
The order in which the tasks are executed is represented by the priority of the tasks(vi)
Order execution time is represented by the total time of project implementation, i.e., the makespanAfter the conversion, the dataset is shown in Table12Table 12
TNG dataset.
Dataset instanceNumber of tasksNumber of resourcesPrecedence relationsSkill levelsProject timeTNG1713710266409TNG2713910266325TNG3714110266296TNG4714510266392TNG513737189461174TNG613739189461052TNG71374118946871TNG81374518946996


### 5.2.2. Parameters and System Settings

Experiment setting:(i)
Input data: 8 instances that are listed in Table12(ii)
Number of the solution in the populationNp: 100(iii)
Number of generationsNg: 50,000(iv)
Like simulation on the simulated dataset, we run on each TNG dataset instance 35 times to get the best value


### 5.2.3. Simulation Results

To prove the effectiveness of the proposed algorithm (DEM), we carry out experiments by using the real-world dataset collected from the TNG company. DEM will be compared with other algorithms from previous research studies, GreedyDO and GA. The performance of these algorithms is recorded and observed by using GARunner, the tool created by Myszkowski et al. [13].Table13 contains the makespan (measured in hours) of the best solution achieved by GreedyDO, GA, and DEM. In addition, the performing intervals of the actual projects at the TNG factory are shown in column TNG.Table13 proves that schedules found by DEM are better than those acquired by GA and GreedyDO. Table 13 and Figure 5 also highlight that the schedules found by evolutionary algorithms are always shorter than the execution time of the actual projects at the TNG factory.Table 13
Comparison between the makespan of real TNG project and makespan of schedule found by GreedyDO, GA, and DEM.
Dataset instanceTNGGreedyDOGADEMTNG1409236201165TNG2325243198166TNG3296258212166TNG4392248176165TNG51174972751712TNG61052963791712TNG7871834810728TNG8996906720675Figure 5
The comparison of makespan between DEM, GA, and TNG’s solution.Compared to the execution time at the TNG factory, the GreedyDO and GA algorithms reduce the makespan by 4%–42% and 7%–51%, respectively, while DEM has the best results of 16%–61%. This result is understandable because so far all projects have been manually scheduled based on the scheduler's experience.This statistical analysis of the experimental result proves that DEM achieved better solutions than the previous algorithms. Thanks to the directed nature, DEM not only ensures fast convergence but also averts getting trapped in local extrema. In experiments conducted on the TNG dataset, DEM reduces the makespan from 16% to 61% compared to the current factory schedule.


## 5.2.1. TNG Dataset

Experiments conducted on the simulated dataset are sometimes inaccurate and unsatisfactory. To overcome this drawback, we collected the dataset of TNG Investment and Trading Joint Stock Company [37], a well-known national textile company. TNG dataset instances have the following characteristics and parameters:(i)
The company has product sewing contracts under the business partners' contracts; each order places a sample of a product in large quantities(ii)
Each product has a certain number of stages, each of which requires a certain time to complete(iii)
Each order will be assigned to a group of workers(iv)
Each group consists of many workers(v)
Each worker's skills are rated based on his rankThe above parameters of the dataset have been converted to a suitable format as shown in Table11.Table 11
Parameters conversion.
Real factor or parameterThe roleOrderProjectStage of the productTaskTime to execute the stageDuration of the given taskWorkerResourceThe worker gradeSkill level of the resourceThe order in which the tasks are executedThe priority of the tasksOrder execution timeThe total time of project implementation, i.e., the makespanTable11 demonstrates that the TNG dataset parameters will be represented as follows:(i)
The order from the business partners’ is represented by a project(ii)
The stage of the product is represented by a task(iii)
A worker in the factory is represented by a resource in the problem formulation(iv)
The worker grade is represented by the skill level of the resource(v)
The order in which the tasks are executed is represented by the priority of the tasks(vi)
Order execution time is represented by the total time of project implementation, i.e., the makespanAfter the conversion, the dataset is shown in Table12Table 12
TNG dataset.
Dataset instanceNumber of tasksNumber of resourcesPrecedence relationsSkill levelsProject timeTNG1713710266409TNG2713910266325TNG3714110266296TNG4714510266392TNG513737189461174TNG613739189461052TNG71374118946871TNG81374518946996


## 5.2.2. Parameters and System Settings

Experiment setting:(i)
Input data: 8 instances that are listed in Table12(ii)
Number of the solution in the populationNp: 100(iii)
Number of generationsNg: 50,000(iv)
Like simulation on the simulated dataset, we run on each TNG dataset instance 35 times to get the best value


## 5.2.3. Simulation Results

To prove the effectiveness of the proposed algorithm (DEM), we carry out experiments by using the real-world dataset collected from the TNG company. DEM will be compared with other algorithms from previous research studies, GreedyDO and GA. The performance of these algorithms is recorded and observed by using GARunner, the tool created by Myszkowski et al. [13].Table13 contains the makespan (measured in hours) of the best solution achieved by GreedyDO, GA, and DEM. In addition, the performing intervals of the actual projects at the TNG factory are shown in column TNG.Table13 proves that schedules found by DEM are better than those acquired by GA and GreedyDO. Table 13 and Figure 5 also highlight that the schedules found by evolutionary algorithms are always shorter than the execution time of the actual projects at the TNG factory.Table 13
Comparison between the makespan of real TNG project and makespan of schedule found by GreedyDO, GA, and DEM.
Dataset instanceTNGGreedyDOGADEMTNG1409236201165TNG2325243198166TNG3296258212166TNG4392248176165TNG51174972751712TNG61052963791712TNG7871834810728TNG8996906720675Figure 5
The comparison of makespan between DEM, GA, and TNG’s solution.Compared to the execution time at the TNG factory, the GreedyDO and GA algorithms reduce the makespan by 4%–42% and 7%–51%, respectively, while DEM has the best results of 16%–61%. This result is understandable because so far all projects have been manually scheduled based on the scheduler's experience.This statistical analysis of the experimental result proves that DEM achieved better solutions than the previous algorithms. Thanks to the directed nature, DEM not only ensures fast convergence but also averts getting trapped in local extrema. In experiments conducted on the TNG dataset, DEM reduces the makespan from 16% to 61% compared to the current factory schedule.


## 6. Conclusion and Future Work

This paper proposes to investigate the MS-RCPSP, one of the combinatorial optimization problems that have a wide range of practical applications in science, technology, and life. The MS-RCPSP is formulated and presented as a mathematical model, and then a novel algorithm called DEM which is based on differential evolution strategy is proposed.The MS-RCPSP, which is the subject of the investigation in this paper, has significant meaning for network resource management in the Internet of things. The MS-RCPSP we study takes into account the resource’s skill level, an important factor of the practical projects. Inspired by differential evolution metaheuristic, we have devised a new evolutionary algorithm that has the ability to outperform all the previous approaches. We build a function called reallocate, which is the key component that creates the strength of the proposed algorithm. This function avoids the idle time intervals in a given schedule, improving the solution quality.To analyze the efficiency of the proposed algorithm, various simulations are conducted and compared with the previous algorithms. Besides the simulated dataset, the real dataset supported by the TNG company has also been utilized for the assessment. The simulation result shows that our developed algorithm is more effective than existing algorithms. DEM achieves not only better quality solution but also faster convergence to global extremum in comparison with the prior algorithms.In the next steps, we are planning to improve DEM algorithm by using a blended random walk and the Gauss statistical function. We will implement local search operations to further improve the quality of the solutions. At the same time, we will integrate the Gaussian probability distribution to improve the search direction modification in the solution space. Thanks to that improvement, we expect that the proposed algorithm will not fall into the local extreme trap.In the future, we will utilize the DE metaheuristic with the integration of the Gauss distribution and Gauss statistical function [38, 39] to improve the effectiveness of the searching for the optimum solution and avoid the local extreme trap.



---

*Source: 8860384-2020-07-14.xml*