# An Effective Hybrid Algorithm Based on Particle Swarm Optimization with Migration Method for Solving the Multiskill Resource-Constrained Project Scheduling Problem

Authors: Huu Dang Quoc; Loc Nguyen The; Cuong Nguyen Doan
Journal: Applied Computational Intelligence and Soft Computing
 (2022)

---

## Abstract

The paper proposed a new algorithm to solve the Multiskill Resource-Constrained Project Scheduling Problem (MS-RCPSP), a combinational optimization problem proved in NP-Hard classification, so it cannot get an optimal solution in polynomial time. The NP-Hard problems can be solved using metaheuristic methods to evolve the population over many generations, thereby finding approximate solutions. However, most metaheuristics have a weakness that can be dropping into local extreme after a number of evolution generations. The new algorithm proposed in this paper will resolve that by detecting local extremes and escaping that by moving the population to new space. That is executed using the Migration technique combined with the Particle Swarm Optimization (PSO) method. The new algorithm is called M-PSO. The experiments were conducted with the iMOPSE benchmark dataset and showed that the M-PSO was more practical than the early algorithms.


---

## Body

## 1. Introduction

Scheduling problems are studied to solve many cases of science and practice, especially big projects which have many tasks. Actually, each real project often has a much larger amount of tasks than the number of renewable resources: people, tools, machines, devices, etc., which can be used to do all of them. Therefore, it is very important to find a good solution to assign resource-to-task efficiently, satisfying the project’s preconstraints. The research to solve this problem has many useful implications such as scheduling of resource coordination in operating systems [1] and scheduling for production lines or applications in subjects of economy and finance [2], military [3], cloud computing [4], fog computing [5], wireless sensor networks [6], etc. Many research results published have shown that this problem is classified into NP-Hard [7–9].Resource-Constrained Project Scheduling Problem (RCPSP) [1, 10, 11] is a project scheduling problem with limited resources, which has been proven to be an NP-Hard problem. The goal is to find a good schedule with minimal time in terms of resource constraints. Currently, this problem is studied and applied in many fields. According to the problem definition, it has two important constraints:(i)
Each renewable resource can only perform a task at a time. Until that task completes, the resource can be used to execute another task.(ii)
When a task has started, it cannot be interrupted until it completes.In each project, tasks have precedence constraints, which means some tasks need to be finished before others.An important problem extended from RCPSP is MS-RCPSP [7, 8, 12] (multiskill RCPSP) that has a new constraint on the skill factor of implementation resources. The new characterization of this problem states that a resource may have more than one skill type, and each skill type has a specific skill level. Each task will have exact requirements about the skill type and skill level of the performing resource. This definition makes the MS-RCPSP more appropriate to real-life projects. The problem is solved by initializing a population of many feasible schedules for the project. The population will evolve step by step through generations to find the best schedule. However, evolution methods often fall into local extremes, so the population cannot run further. This paper proposes a new algorithm using the Migration method combined with PSO traditional to crack the disadvantage when falling into the local extremes.The innovations and main contributions of this paper are described as follows.(i)
Detecting local extremes in the population evolution.(ii)
Proposing the method to escape local extremes by moving the population to a new values space using the Migration.The rest of the paper is separated into six sections. Section2 introduces some early approaches to decoding the MS-RCPSP problem. In Section 3, we raise the mathematical statement of the MS-RCPSP problem. Section 4 presents a new efficient algorithm for finding the approximate solution based on the PSO strategy [2, 13]. In this section, we focus on detailing the Migration technique, which is a major component that makes up the power of the proposed algorithm. To evaluate the algorithm, this section also introduces the particle presentation. Section 5 experiments to demonstrate the efficiency of the proposed algorithm. The examination is conducted on some instances of the iMOPSE benchmark dataset. All experimental results are compared and analyzed with other algorithms to show the effectiveness of the new algorithm. Finally, Section 6 arranges the paper and draws further research directions to enhance the quality of the MS-RCPSP problem.


## 2. Related Works

### 2.1. Approximation Methods for MS-RCPSP

In recent years, researching good methods to solve the MS-RCPSP [7, 12, 14] problem has become important in deploying it into many domains. Since this is a combinatorial optimization problem belonging to the NP-Hard [11, 15, 16] classification, we cannot find an optimal solution in polynomial time, so the objective of methods is to find an approximate result based on metaheuristic techniques. Authors usually use evolutionary approaches as GA [17, 18], PSO [19–22], Greedy, Min-Max, etc. to solve and get out the approximate solutions. Some of the outstanding related works are shown in Table 1.Table 1
Summary of early work.
No.YearAuthorMethodDataset12017Javanmard [47], [51]GA, PSOPS-LIB22013–2019Myszkowski và cộng sự [31], [42], [43], [44], [45]GA, Ant, Greedy,…iMOPSE32018Hosseinian [4], [5], [6], [7]GA, PSOProGen, iMOPSE42019H. Davari-Ardakani [21]Min-MaxiMOPSEMyszkowski et al. [8, 9, 23] have researched this problem for many years, and they have many quality publication papers presented regarding that. The authors proposed algorithms based on evaluation methods such as Tabu Search [8], Ant colony, GA [9, 24, 25], etc. Most of them are traditional methods, so they usually have limited effective results. However, the best contribution of Myszkowski is to build and publish the standard dataset used to experiment with the new algorithms for the MS-RCPSP. It is called the iMOPSE dataset [9].Hosseinian and Baradaran [7, 26] have many published papers about MS-RCPSP too. In 2018, Hosseinian and Baradaran published a paper [7] on the Multimode MS-RCSPSP (MMSRCPSP), a subclass of the MS-RCPSP problem. MMSRCPSP has added constraints where each task can only be executed in a few predefined modes. When the mode is selected, it cannot be changed. The authors suggested a method to make individuals in the next generation, which is built from the GA algorithm combined with the decision-making method based on Shanon-entropy data measure. Experiments were carried out on randomly generated datasets by ProGen software. After that, in 2019, the authors published a paper [26] on the Dandelion Algorithm [27]. In 2020, this group of authors continued to publish an article that solves the multiobjective MS-RCPSP problem with two objectives: total time and cost to complete a project. The authors use the Pareto-based Gray Wolf Optimizer algorithm and continue to test the results on the iMOPSE standard dataset [9].In 2017, Javanmard et al. used two traditional evolutionary algorithms, GA and PSO, to schedule multiskill resources (actually workers and engineers) to minimize the total cost in the chemical industry [28]. The proposed algorithms are tried on the PSPLIB dataset [29] not fully suitable for scheduling problems because of no cost parameter objectives. Moreover, the authors cannot compare their traditional algorithms with newer ones at the experimental stage but only compare them.Also studying multiobjective problems such as Hosseinian et al., Davari-Ardakani [30] proposed a multiobjective variant of the MS-RCPSP problem to minimize the time and cost of the current project. The proposed issue is called MSPSP, which is limited to projects with the following two characteristics:(i)
The timing of implementation is arbitrary; for example, the project can be done in the evenings or on weekends(ii)
Energy costs are very high, comparable to wages paid to employees.However, the authors only gave the problem model without any new solution method to solve it. They only conducted experiments with the Max-Min method, a very traditional method.


### 2.2. PSO Method

Particle Swarm Optimization (PSO) [31–35] is an evolutionary algorithm. Similar to other evolutionary algorithms, PSO will perform a population-based search; initially the population is randomly initialized with a certain number of individuals. However, PSO differs from other evolutionary algorithms in that each individual in the population is determined by two basic parameters, the position vector (representing the individual’s experience over generations) and the velocity vector (representing the population’s experience over generations). Each individual will move in the solution space at a particular velocity. After each generation, the individuals will move towards the best position of the individual in the past and the best position of the population and after each generation, the instances will move towards better search regions in the search space. In the process of finding individuals, the displacement vector and the position vector will be updated according to the best value of that individual in the past and the best position of the population according to the following formula.An effective algorithm suggested by Kennedy and Eberhart [32] in 1995 in the evaluation optimization method is PSO (Particle Swarm Optimization). In the PSO, each particle in each generation is evaluated from two values containing position and velocity where the position is calculated as follows:(1)vik+1=ωvik+c1rand1×pbesti−xik+c2rand2×gbesti−xik,xik+1=xik+vik,where(i)
vik, vik+1 are velocity of particle i at generation k and k + 1.(ii)
xik, xik+1 are position of the particle i at generation k and k + 1.(iii)
ω is inertia weight; c1, c2 are speedup coefficients.(iv)
rand1, rand2 are the values between 0 and 1 randomly generated.(v)
pbesti is the best position of particle i.(vi)
gbest: the best particle position in a population.


## 2.1. Approximation Methods for MS-RCPSP

In recent years, researching good methods to solve the MS-RCPSP [7, 12, 14] problem has become important in deploying it into many domains. Since this is a combinatorial optimization problem belonging to the NP-Hard [11, 15, 16] classification, we cannot find an optimal solution in polynomial time, so the objective of methods is to find an approximate result based on metaheuristic techniques. Authors usually use evolutionary approaches as GA [17, 18], PSO [19–22], Greedy, Min-Max, etc. to solve and get out the approximate solutions. Some of the outstanding related works are shown in Table 1.Table 1
Summary of early work.
No.YearAuthorMethodDataset12017Javanmard [47], [51]GA, PSOPS-LIB22013–2019Myszkowski và cộng sự [31], [42], [43], [44], [45]GA, Ant, Greedy,…iMOPSE32018Hosseinian [4], [5], [6], [7]GA, PSOProGen, iMOPSE42019H. Davari-Ardakani [21]Min-MaxiMOPSEMyszkowski et al. [8, 9, 23] have researched this problem for many years, and they have many quality publication papers presented regarding that. The authors proposed algorithms based on evaluation methods such as Tabu Search [8], Ant colony, GA [9, 24, 25], etc. Most of them are traditional methods, so they usually have limited effective results. However, the best contribution of Myszkowski is to build and publish the standard dataset used to experiment with the new algorithms for the MS-RCPSP. It is called the iMOPSE dataset [9].Hosseinian and Baradaran [7, 26] have many published papers about MS-RCPSP too. In 2018, Hosseinian and Baradaran published a paper [7] on the Multimode MS-RCSPSP (MMSRCPSP), a subclass of the MS-RCPSP problem. MMSRCPSP has added constraints where each task can only be executed in a few predefined modes. When the mode is selected, it cannot be changed. The authors suggested a method to make individuals in the next generation, which is built from the GA algorithm combined with the decision-making method based on Shanon-entropy data measure. Experiments were carried out on randomly generated datasets by ProGen software. After that, in 2019, the authors published a paper [26] on the Dandelion Algorithm [27]. In 2020, this group of authors continued to publish an article that solves the multiobjective MS-RCPSP problem with two objectives: total time and cost to complete a project. The authors use the Pareto-based Gray Wolf Optimizer algorithm and continue to test the results on the iMOPSE standard dataset [9].In 2017, Javanmard et al. used two traditional evolutionary algorithms, GA and PSO, to schedule multiskill resources (actually workers and engineers) to minimize the total cost in the chemical industry [28]. The proposed algorithms are tried on the PSPLIB dataset [29] not fully suitable for scheduling problems because of no cost parameter objectives. Moreover, the authors cannot compare their traditional algorithms with newer ones at the experimental stage but only compare them.Also studying multiobjective problems such as Hosseinian et al., Davari-Ardakani [30] proposed a multiobjective variant of the MS-RCPSP problem to minimize the time and cost of the current project. The proposed issue is called MSPSP, which is limited to projects with the following two characteristics:(i)
The timing of implementation is arbitrary; for example, the project can be done in the evenings or on weekends(ii)
Energy costs are very high, comparable to wages paid to employees.However, the authors only gave the problem model without any new solution method to solve it. They only conducted experiments with the Max-Min method, a very traditional method.


## 2.2. PSO Method

Particle Swarm Optimization (PSO) [31–35] is an evolutionary algorithm. Similar to other evolutionary algorithms, PSO will perform a population-based search; initially the population is randomly initialized with a certain number of individuals. However, PSO differs from other evolutionary algorithms in that each individual in the population is determined by two basic parameters, the position vector (representing the individual’s experience over generations) and the velocity vector (representing the population’s experience over generations). Each individual will move in the solution space at a particular velocity. After each generation, the individuals will move towards the best position of the individual in the past and the best position of the population and after each generation, the instances will move towards better search regions in the search space. In the process of finding individuals, the displacement vector and the position vector will be updated according to the best value of that individual in the past and the best position of the population according to the following formula.An effective algorithm suggested by Kennedy and Eberhart [32] in 1995 in the evaluation optimization method is PSO (Particle Swarm Optimization). In the PSO, each particle in each generation is evaluated from two values containing position and velocity where the position is calculated as follows:(1)vik+1=ωvik+c1rand1×pbesti−xik+c2rand2×gbesti−xik,xik+1=xik+vik,where(i)
vik, vik+1 are velocity of particle i at generation k and k + 1.(ii)
xik, xik+1 are position of the particle i at generation k and k + 1.(iii)
ω is inertia weight; c1, c2 are speedup coefficients.(iv)
rand1, rand2 are the values between 0 and 1 randomly generated.(v)
pbesti is the best position of particle i.(vi)
gbest: the best particle position in a population.


## 3. Problem Definitions

The MS-RCPSP [7, 8, 12, 14] is a subproblem of RCPSP (Resource-Constrained Project Scheduling Problem) that added the skill domain to the renewable resources. The objective of this problem is to find the minimum makespan, i.e., the minimum time to complete the full project. In the running time, each task requires a particular skill, where skill level is equal to or greater than the task’s requirement.To define formulations of the MS-RCPSP, we need a notation system presented in Table2.Table 2
The notations.
CiThe set of tasks need to be completed before taski can be executedSThe set of all resource’s skillsSi: the subset of skills owned by the resource i, Si ⊆ SSiThe skillitjThe duration of taskjLThe resources used to execute tasks of the projectLkThe subset of the resources which can perform taskk; Lk ⊆ LLiThe resourceiWThe tasks that the project needs to doWkThe subset of task which can be executed by the resourcek, Wk ⊆ WWiThe taskiriThe subset of the skill required by taski. A resource has the same skill and skill level equal to or greater than the requirement that can be performedBk, EkThe begin time and end time of the taskkAu,vtThe variable to identify the resourcev is running task u at time t; 1: yes, 0: nohiThe skill leveligiType of skillimMakespan of the schedulePThe feasible solutionPallThe set of all solutionf(P)The function to calculate the makespan ofP solutionnTask numberzResource numberUsing the notations presented in Table2, we can construct the mathematical model for the MS-RCPSP as follows.(2)fP⟶min,subject to(3)Sk≠∅,∀Lk∈L,(4)tj≥0,∀Wj∈W,(5)Ej≥0,∀Wj∈W,(6)Ei≤Ej−tj,∀Wj∈W,j≠1,Wi∈Cj(7)∀Wi∈Wk,∃Sq∈Sk,gSq=griandhSq≥hri,(8)∀Lk∈L,∀q∈m:∑i=1nAi,kq≤1,(9)∀Wj∈W,∃!q∈0,m,!Lk∈L:Aj,kq=1;withAj,kq∈0;1,where we have the following:(i)
Constraint (3): a resource must have one or more skills.(ii)
Constraints (4) and (5): the duration of any task must be equal to or greater than zero (in fact, any real task’s duration is a positive number; only two dummy tasks have the duration equal to 0, which shows the start and finish time of the project).(iii)
Constraint (6): the parent task (task i) must be finished before the child task (task j) starts. When task i ends are denoted Ei, the time when subtask j starts is Ej − tj.(iv)
Constraint (7): any task i ∈ Wk, having skill S ∈ Sk satisfied to gS=gSi shows that the skill of r is the save with skill of Li. hSq≥hri: skill level of using the resource is equal to or greater than the task’s requirement.(v)
Constraint (8): at any time, each resource can execute only one task. To check the availability of the resource, we use the expression ∑i=1nAi,kq; if it results in 0 value, the k resource cannot be assigned to do any task, else k is used.(vi)
Constraint (9): each task is executed by only one resource.In the MS-RCPSP problem, the resource must meet the skill type and skill level to perform a task. Accordingly, a resource can commit the task if its skill is the same as the task’s required, and the skill level must be equal to or greater than the tasks needed. The resource-to-task assignment can be presented as a matrix illustrated in Figure1.Figure 1
The relation matrix of resources-tasks assignment.In Figure1, Si.j denotes Si skill type and it has j skill level. Tasks that require execution resources must meet a specific skill type and skill level. The feasible resource should have the same skill type and skill level greater than or equal to the required skill level.Example 1.
Figure1 presents a project with four tasks and four renewable resources. The resources have skill types from S1 to S2, and each of them can have a skill level from 1 to 3. According to MS-RCPSP constraint, to do task W1, the resource must meet the task’s requirement that means the resource has to have skill type S2 and skill level equal to or greater than 2. Looking into the resource list, we determine that resource L1 has skill type S2 and skill level is 2, so L1 can be allocated to execute W1.


## 4. Proposed Algorithm

### 4.1. Schedule Representation

In the scheduling algorithm, a schedule is represented as a vector and the vector’s item number is equal to the task number of the project. The value of each item shows the resource index to perform it. The corresponding resource has to meet the requirement constraint of the task.Example 2.
Consider a project that has 10 tasks and 2 resources.(i)
The set of tasks:W = {W1, W2, W3, W4, W5, W6, W7, W8, W9, W10}.(ii)
The set of resources:L = {L1, L2}.
The priority graph of the tasks is shown in Figure2.
The duration of tasks (in hours) is shown in Table3.
Figure3 shows the assigning of resources to execute tasks of the project. The resource to perform the task needs to meet the priority constraints of the problem containing the skill requirements and skill level.
A vector can present the schedule shown in Figure3 as Table 4.
Table4 presents the task-resource assignment of the project, where the resource L1 performs tasks: W1, W4, W5, W, W7, W10; the resource L2 is assigned to execute tasks: W2, W3, W8, W9.Figure 2
The priority graph of the project.Table 3
The duration of task.
TaskW1W2W3W4W5W6W7W8W9W10Duration2435225342Figure 3
The Gantt diagram of the resource-task assignment.Table 4
The task-resource assignment of schedule.
TaskW1W2W3W4W5W6W7W8W9W10Resource1221111221


### 4.2. Migration Method

To find a feasible solution with the minimum makespan for the MS-RCPSP problem, we study the Migration method combined with the PSO [32–34]; the new algorithm is named M-PSO.


#### 4.2.1. Migration Method

The PSO algorithm tends to fall into the local extreme when performing evolution. The Migration method moves the population from the local extreme to new space while expanding the search space.Definition 1.
A population is said to be not successfully evaluated if the makespan of the population is still fixed between two continuous generations.
The Migration method runs over steps as follows:Step 1: detecting the local extremes:To detect local extremes, we use a variablenf to count the number of times the population has failed to evolve consecutively; if this value is greater than a specified threshold (nmax), then the population has fallen into the local extreme. Equation (10) shows how to evaluate nf.(10)nf=nf+1,ifnewmakespan=oldmakespan,0,ifnewmakespan≠oldmakespan,Step 2: moving the population to a new space:
To move the population staying local extreme to new space, we continue with some next steps:(i)
Consider each particle of the population.(ii)
For each taski of the particle, find the set Li of resources that can perform task i, sorting the resources in Li by the index of each resource.(iii)
Replace the current resource used to doi task by resource staying at the opposite position in Li sorted. Equation (11) represents this step.(11)Li=L1,L2,…,Lm,m≤n,∀Wi∈W,j∈1,m:Lj←Lm−j.
Figure4 illustrates the Migration method by changing execution resources. Specifically, the task being performed by resource L2 will be assigned to Lm − 1 and the task being performed by resource Lm will be allocated to L1.
The new assigning resource-to-task has to ensure the problem’s constraints. After all the particles of the population are moved, we will get a new population that is migrated to a new space, which means the population is escaping to the local extreme.
The Migration pseudocode is implemented as follows (Algorithm 1):Algorithm 1: Migration.
Input:Pall–the current populationOutput:Pnew–the population after movingBegin(1)
Pnew = {}(2)
Fori = 1 to size(P)(3)
Pi ← Pall[i];(4)
Forj = 1 to n(5)
Li ← the subset of resource can be performed the task Li(6)
Li ← Sort(Li)(7)
idx ← index of resource executed the taski(8)
idx = size(Li) – idx + 1(9)
Li = Li[idx](10)
End for //j(11)
Pnew = Pnew + {Pi}(12)
End for //i(13)
ReturnPnew;End FunctionFigure 4
Changing task execution resources.


### 4.3. The M-PSO Algorithm

The M-PSO algorithm is improved from the PSO algorithm integrated with the Migration method to improve the efficiency of results. The detail of M-PSO is described in Algorithm 2 as follows:Algorithm 2: M-PSO.
Input:nmax: the threshold to find local extremal, tmax: number of evolution generations.Output: the best solution gbest(1)
Begin(2)
Pall ← Init data from iMOPSE dataset and create population.(3)
t = 0(4)
nf = 0(5)
while (t < tmax)(6)
t = t + 1(7)
fori = 1 to size (Pall) do(8)
Calculate the objective value:f (Pi)(9)
end for(10)
fori = 1 to size (Pall) do(11)
iff (Pi) < f (fitnessi) then(12)
pbesti = Pi(13)
f (pbesti) = f (Pi)(14)
end if(15)
end for(16)
for i = 1 to size (Pall) do(17)
if (f (Pi) < f (gbest)) then(18)
gbest = Pi(19)
f (gbest) = f (Pi)(20)
end if(21)
if f(Pi)! = f(Pi-1) then(22)
nf = 0(23)
else(24)
nf + = 1(25)
end if(26)
end for(27)
for i = 1 to size (Pall) do(28)
update velocity vector(29)
update position vector(30)
end for(31)
if (nf = nmax)(32)
Pall ← Migration (Pall)(33)
nf = 0(34)
end if(35)
end while(36)
return gbest(37)
endf: objective functionLines 21 to 25 show the way to find out the local extreme.Lines 31 to 34 check the threshold and call Migration function to move the population to a new space, making the population escape the current local extremum area and expand finding space.


## 4.1. Schedule Representation

In the scheduling algorithm, a schedule is represented as a vector and the vector’s item number is equal to the task number of the project. The value of each item shows the resource index to perform it. The corresponding resource has to meet the requirement constraint of the task.Example 2.
Consider a project that has 10 tasks and 2 resources.(i)
The set of tasks:W = {W1, W2, W3, W4, W5, W6, W7, W8, W9, W10}.(ii)
The set of resources:L = {L1, L2}.
The priority graph of the tasks is shown in Figure2.
The duration of tasks (in hours) is shown in Table3.
Figure3 shows the assigning of resources to execute tasks of the project. The resource to perform the task needs to meet the priority constraints of the problem containing the skill requirements and skill level.
A vector can present the schedule shown in Figure3 as Table 4.
Table4 presents the task-resource assignment of the project, where the resource L1 performs tasks: W1, W4, W5, W, W7, W10; the resource L2 is assigned to execute tasks: W2, W3, W8, W9.Figure 2
The priority graph of the project.Table 3
The duration of task.
TaskW1W2W3W4W5W6W7W8W9W10Duration2435225342Figure 3
The Gantt diagram of the resource-task assignment.Table 4
The task-resource assignment of schedule.
TaskW1W2W3W4W5W6W7W8W9W10Resource1221111221


## 4.2. Migration Method

To find a feasible solution with the minimum makespan for the MS-RCPSP problem, we study the Migration method combined with the PSO [32–34]; the new algorithm is named M-PSO.


### 4.2.1. Migration Method

The PSO algorithm tends to fall into the local extreme when performing evolution. The Migration method moves the population from the local extreme to new space while expanding the search space.Definition 1.
A population is said to be not successfully evaluated if the makespan of the population is still fixed between two continuous generations.
The Migration method runs over steps as follows:Step 1: detecting the local extremes:To detect local extremes, we use a variablenf to count the number of times the population has failed to evolve consecutively; if this value is greater than a specified threshold (nmax), then the population has fallen into the local extreme. Equation (10) shows how to evaluate nf.(10)nf=nf+1,ifnewmakespan=oldmakespan,0,ifnewmakespan≠oldmakespan,Step 2: moving the population to a new space:
To move the population staying local extreme to new space, we continue with some next steps:(i)
Consider each particle of the population.(ii)
For each taski of the particle, find the set Li of resources that can perform task i, sorting the resources in Li by the index of each resource.(iii)
Replace the current resource used to doi task by resource staying at the opposite position in Li sorted. Equation (11) represents this step.(11)Li=L1,L2,…,Lm,m≤n,∀Wi∈W,j∈1,m:Lj←Lm−j.
Figure4 illustrates the Migration method by changing execution resources. Specifically, the task being performed by resource L2 will be assigned to Lm − 1 and the task being performed by resource Lm will be allocated to L1.
The new assigning resource-to-task has to ensure the problem’s constraints. After all the particles of the population are moved, we will get a new population that is migrated to a new space, which means the population is escaping to the local extreme.
The Migration pseudocode is implemented as follows (Algorithm 1):Algorithm 1: Migration.
Input:Pall–the current populationOutput:Pnew–the population after movingBegin(1)
Pnew = {}(2)
Fori = 1 to size(P)(3)
Pi ← Pall[i];(4)
Forj = 1 to n(5)
Li ← the subset of resource can be performed the task Li(6)
Li ← Sort(Li)(7)
idx ← index of resource executed the taski(8)
idx = size(Li) – idx + 1(9)
Li = Li[idx](10)
End for //j(11)
Pnew = Pnew + {Pi}(12)
End for //i(13)
ReturnPnew;End FunctionFigure 4
Changing task execution resources.


## 4.2.1. Migration Method

The PSO algorithm tends to fall into the local extreme when performing evolution. The Migration method moves the population from the local extreme to new space while expanding the search space.Definition 1.
A population is said to be not successfully evaluated if the makespan of the population is still fixed between two continuous generations.
The Migration method runs over steps as follows:Step 1: detecting the local extremes:To detect local extremes, we use a variablenf to count the number of times the population has failed to evolve consecutively; if this value is greater than a specified threshold (nmax), then the population has fallen into the local extreme. Equation (10) shows how to evaluate nf.(10)nf=nf+1,ifnewmakespan=oldmakespan,0,ifnewmakespan≠oldmakespan,Step 2: moving the population to a new space:
To move the population staying local extreme to new space, we continue with some next steps:(i)
Consider each particle of the population.(ii)
For each taski of the particle, find the set Li of resources that can perform task i, sorting the resources in Li by the index of each resource.(iii)
Replace the current resource used to doi task by resource staying at the opposite position in Li sorted. Equation (11) represents this step.(11)Li=L1,L2,…,Lm,m≤n,∀Wi∈W,j∈1,m:Lj←Lm−j.
Figure4 illustrates the Migration method by changing execution resources. Specifically, the task being performed by resource L2 will be assigned to Lm − 1 and the task being performed by resource Lm will be allocated to L1.
The new assigning resource-to-task has to ensure the problem’s constraints. After all the particles of the population are moved, we will get a new population that is migrated to a new space, which means the population is escaping to the local extreme.
The Migration pseudocode is implemented as follows (Algorithm 1):Algorithm 1: Migration.
Input:Pall–the current populationOutput:Pnew–the population after movingBegin(1)
Pnew = {}(2)
Fori = 1 to size(P)(3)
Pi ← Pall[i];(4)
Forj = 1 to n(5)
Li ← the subset of resource can be performed the task Li(6)
Li ← Sort(Li)(7)
idx ← index of resource executed the taski(8)
idx = size(Li) – idx + 1(9)
Li = Li[idx](10)
End for //j(11)
Pnew = Pnew + {Pi}(12)
End for //i(13)
ReturnPnew;End FunctionFigure 4
Changing task execution resources.


## 4.3. The M-PSO Algorithm

The M-PSO algorithm is improved from the PSO algorithm integrated with the Migration method to improve the efficiency of results. The detail of M-PSO is described in Algorithm 2 as follows:Algorithm 2: M-PSO.
Input:nmax: the threshold to find local extremal, tmax: number of evolution generations.Output: the best solution gbest(1)
Begin(2)
Pall ← Init data from iMOPSE dataset and create population.(3)
t = 0(4)
nf = 0(5)
while (t < tmax)(6)
t = t + 1(7)
fori = 1 to size (Pall) do(8)
Calculate the objective value:f (Pi)(9)
end for(10)
fori = 1 to size (Pall) do(11)
iff (Pi) < f (fitnessi) then(12)
pbesti = Pi(13)
f (pbesti) = f (Pi)(14)
end if(15)
end for(16)
for i = 1 to size (Pall) do(17)
if (f (Pi) < f (gbest)) then(18)
gbest = Pi(19)
f (gbest) = f (Pi)(20)
end if(21)
if f(Pi)! = f(Pi-1) then(22)
nf = 0(23)
else(24)
nf + = 1(25)
end if(26)
end for(27)
for i = 1 to size (Pall) do(28)
update velocity vector(29)
update position vector(30)
end for(31)
if (nf = nmax)(32)
Pall ← Migration (Pall)(33)
nf = 0(34)
end if(35)
end while(36)
return gbest(37)
endf: objective functionLines 21 to 25 show the way to find out the local extreme.Lines 31 to 34 check the threshold and call Migration function to move the population to a new space, making the population escape the current local extremum area and expand finding space.


## 5. Experiment

To estimate the efficiency of our proposed method, we developed the simulator on the Matlab environment conducted on the benchmark iMOPSE dataset. The test results are compared with GA-M [9] and GRASP [9, 23], showing that M-PSO has a positive effect.


### 5.1. The Benchmark Dataset

In the simulated program, we use the iMOPSE [9] installers to investigate many existing algorithms as GRASP, GA-M, etc. The iMOPSE dataset has the following characteristics:(i)
Number of project tasks.(ii)
Number of resources used to implement the project.(iii)
Number of precedence constraints performed between tasks.(iv)
The number of skills of the resources in the project.Table4 shows 12 iMOPSE’s instances to experiment with our algorithms.The simulation is run on a PC with Intel Core i5-CPU 2.2 GHz, 6 GB RAM, and using the Windows 10 OS. The dataset used in our simulator is listed in Table5.Table 5
iMOPSE benchmark dataset.
NameTasksResourcesPrecedence relationsSkills100_5_22_1510052215100_5_46_1510054615100_5_48_91005489100_5_64_1510056415100_5_64_91005649100_10_26_15100102615100_10_47_910010479100_10_48_15100104815100_10_64_910010649100_10_65_15100106515100_20_22_15100202215100_20_46_15100204615100_20_47_910020479100_20_65_15100206515100_20_65_910020659200_10_128_152001012815200_10_50_15200105015200_10_50_920010509200_10_84_920010849200_10_85_15200108515200_20_145_152002014515200_20_54_15200205415200_20_55_920020559200_20_97_15200209715200_20_97_920020979200_40_133_152004013315200_40_45_15200404515200_40_45_920040459200_40_90_920040909200_40_91_15200409115The input parameters and initial values are the following:(i)
The experiment environment: Matlab.(ii)
Data: 30 iMOPSE installers that are shown in Table5.(iii)
Number of particles in the populationNp: 100.(iv)
Number of evolutionary generationsNg: 50,000.(v)
Number of executing times for a data install: 35.All result data contains average, standard deviation, and best values.


### 5.2. Experiment Results

The results of the M-PSO are presented in Table6; this table also shows the values of GA-M and GRASP algorithms published together with the iMOPSE dataset.Table 6
The experiment results on the iMOPSE dataset.
DatasetGA-MGRASPM-PSOBestAvgStdBestAvgStdBestAvgStd100_5_22_155175245.35035041.24854861.7100_5_46_155845874.75525563.95305310.5100_5_48_95285359.75105100.34904921.6100_5_64_155275302.55015021.24784791.3100_5_64_95085219.94944940.24714742.5100_10_26_152922920.02512587.12332330.4100_10_47_92962960.02632640.92572613.7100_10_48_152792822.92562571.22442450.6100_10_64_92963056.62552572.12402465.9100_10_65_152862905.02562603.82442451.3100_20_22_151631695.81341373.71281313.1100_20_46_151972076.91701743.91621652.9100_20_47_91851860.51331406.81241283.6100_20_65_152402400.52132130.12282301.8100_20_65_91811874.51351350.41251250.3200_10_128_155775834.94914965.24614642.7200_10_50_1555357717.55245283.84864870.7200_10_50_95855895.05065081.94844883.7200_10_84_956758311.45265270.85085102.1200_10_85_155495554.94964981.74734762.5200_20_145_153263282.02622718.52362371.4200_20_54_1536338520.83043083.72562560.3200_20_55_93123184.22572580.62512553.5200_20_97_154244389.734734703343373.3200_20_97_93213266.22532563.82552560.9200_40_133_152152226.21631706.51471514.1200_40_45_152012106.31641640.31631674200_40_45_92092132.91441473.21521629.5200_40_90_92112153.11481534.91451527.1200_40_91_152002053.41531595.71351438.3In Table6, GA-M and GRASP are proposed algorithms of Myszkowski which are executed on the iMOPSE dataset.These values are calculated after conducting experiments on the corresponding installers, including(i)
BEST: the best makespan value.(ii)
AVG: the average makespan value.(iii)
STD: the standard deviation value.Comparing the M-PSO with GA-M, we have the following:(i)
Regarding BEST and AVG values: M-PSO is better than GA-M in all instances, in which BEST value is better than GA-M from 6.2% to 32.97%, and AVG value is better than GA-M from 4.3% to 33.56%.(ii)
Regarding STD, the total standard deviation of GA-M is 173.3 and of M-PSO is 83.6. It denotes that the M-PSO algorithm is more efficient and more stable than the GA-M algorithm.Comparing the M-PSO with GRASP, we have the following:(i)
The results of M-PSO have better results than GRASP in most cases, specifically better than GRASP 27/30 instances (from 0.6% to 15.8%) with the BEST value and 27/30 instances data with AVG value (from 0% to 16.9%).The M-PSO can detect local extremes and escape them using the Migration technique, achieving higher efficiency than other comparison algorithms. The experiment results also show that the more the tasks in the project are, the more the M-PSO becomes satisfactory. The superiority of M-PSO in comparison with two competitors are shown in the figures, specifically as follows:(i)
The BEST values present in Figures5 and 6.(ii)
The AVG values present in Figures7 and 8.(iii)
The STD values present in Figures9 and 10.Figure 5
Comparing BEST values between GA-M, GRASP, and M-PSO of 100 tasks projects.Figure 6
Comparing BEST values between GA-M, GRASP, and M-PSO of 200 tasks projects.Figure 7
Comparing AVG values between GA-M, GRASP, and M-PSO of 100 tasks projects.Figure 8
Comparing AVG values between GA-M, GRASP, and M-PSO of 200 tasks projects.Figure 9
Comparing STD values between GA-M, GRASP, and M-PSO of 100 tasks projects.Figure 10
Comparing STD values between GA-M, GRASP, and M-PSO of 200 tasks projects.


## 5.1. The Benchmark Dataset

In the simulated program, we use the iMOPSE [9] installers to investigate many existing algorithms as GRASP, GA-M, etc. The iMOPSE dataset has the following characteristics:(i)
Number of project tasks.(ii)
Number of resources used to implement the project.(iii)
Number of precedence constraints performed between tasks.(iv)
The number of skills of the resources in the project.Table4 shows 12 iMOPSE’s instances to experiment with our algorithms.The simulation is run on a PC with Intel Core i5-CPU 2.2 GHz, 6 GB RAM, and using the Windows 10 OS. The dataset used in our simulator is listed in Table5.Table 5
iMOPSE benchmark dataset.
NameTasksResourcesPrecedence relationsSkills100_5_22_1510052215100_5_46_1510054615100_5_48_91005489100_5_64_1510056415100_5_64_91005649100_10_26_15100102615100_10_47_910010479100_10_48_15100104815100_10_64_910010649100_10_65_15100106515100_20_22_15100202215100_20_46_15100204615100_20_47_910020479100_20_65_15100206515100_20_65_910020659200_10_128_152001012815200_10_50_15200105015200_10_50_920010509200_10_84_920010849200_10_85_15200108515200_20_145_152002014515200_20_54_15200205415200_20_55_920020559200_20_97_15200209715200_20_97_920020979200_40_133_152004013315200_40_45_15200404515200_40_45_920040459200_40_90_920040909200_40_91_15200409115The input parameters and initial values are the following:(i)
The experiment environment: Matlab.(ii)
Data: 30 iMOPSE installers that are shown in Table5.(iii)
Number of particles in the populationNp: 100.(iv)
Number of evolutionary generationsNg: 50,000.(v)
Number of executing times for a data install: 35.All result data contains average, standard deviation, and best values.


## 5.2. Experiment Results

The results of the M-PSO are presented in Table6; this table also shows the values of GA-M and GRASP algorithms published together with the iMOPSE dataset.Table 6
The experiment results on the iMOPSE dataset.
DatasetGA-MGRASPM-PSOBestAvgStdBestAvgStdBestAvgStd100_5_22_155175245.35035041.24854861.7100_5_46_155845874.75525563.95305310.5100_5_48_95285359.75105100.34904921.6100_5_64_155275302.55015021.24784791.3100_5_64_95085219.94944940.24714742.5100_10_26_152922920.02512587.12332330.4100_10_47_92962960.02632640.92572613.7100_10_48_152792822.92562571.22442450.6100_10_64_92963056.62552572.12402465.9100_10_65_152862905.02562603.82442451.3100_20_22_151631695.81341373.71281313.1100_20_46_151972076.91701743.91621652.9100_20_47_91851860.51331406.81241283.6100_20_65_152402400.52132130.12282301.8100_20_65_91811874.51351350.41251250.3200_10_128_155775834.94914965.24614642.7200_10_50_1555357717.55245283.84864870.7200_10_50_95855895.05065081.94844883.7200_10_84_956758311.45265270.85085102.1200_10_85_155495554.94964981.74734762.5200_20_145_153263282.02622718.52362371.4200_20_54_1536338520.83043083.72562560.3200_20_55_93123184.22572580.62512553.5200_20_97_154244389.734734703343373.3200_20_97_93213266.22532563.82552560.9200_40_133_152152226.21631706.51471514.1200_40_45_152012106.31641640.31631674200_40_45_92092132.91441473.21521629.5200_40_90_92112153.11481534.91451527.1200_40_91_152002053.41531595.71351438.3In Table6, GA-M and GRASP are proposed algorithms of Myszkowski which are executed on the iMOPSE dataset.These values are calculated after conducting experiments on the corresponding installers, including(i)
BEST: the best makespan value.(ii)
AVG: the average makespan value.(iii)
STD: the standard deviation value.Comparing the M-PSO with GA-M, we have the following:(i)
Regarding BEST and AVG values: M-PSO is better than GA-M in all instances, in which BEST value is better than GA-M from 6.2% to 32.97%, and AVG value is better than GA-M from 4.3% to 33.56%.(ii)
Regarding STD, the total standard deviation of GA-M is 173.3 and of M-PSO is 83.6. It denotes that the M-PSO algorithm is more efficient and more stable than the GA-M algorithm.Comparing the M-PSO with GRASP, we have the following:(i)
The results of M-PSO have better results than GRASP in most cases, specifically better than GRASP 27/30 instances (from 0.6% to 15.8%) with the BEST value and 27/30 instances data with AVG value (from 0% to 16.9%).The M-PSO can detect local extremes and escape them using the Migration technique, achieving higher efficiency than other comparison algorithms. The experiment results also show that the more the tasks in the project are, the more the M-PSO becomes satisfactory. The superiority of M-PSO in comparison with two competitors are shown in the figures, specifically as follows:(i)
The BEST values present in Figures5 and 6.(ii)
The AVG values present in Figures7 and 8.(iii)
The STD values present in Figures9 and 10.Figure 5
Comparing BEST values between GA-M, GRASP, and M-PSO of 100 tasks projects.Figure 6
Comparing BEST values between GA-M, GRASP, and M-PSO of 200 tasks projects.Figure 7
Comparing AVG values between GA-M, GRASP, and M-PSO of 100 tasks projects.Figure 8
Comparing AVG values between GA-M, GRASP, and M-PSO of 200 tasks projects.Figure 9
Comparing STD values between GA-M, GRASP, and M-PSO of 100 tasks projects.Figure 10
Comparing STD values between GA-M, GRASP, and M-PSO of 200 tasks projects.


## 6. Conclusion and Future Work

In this paper, we have presented the MS-RCPSP problem, a combinatorial optimization problem with many scientific and practical applications. It has described the mathematical model of the problem and proposes a new algorithm to find a feasible solution for the MS-RCPSP problem. The proposed algorithm is M-PSO, which is improved from the PSO algorithm combined with the migration method to escape the local extremes and expand the searching space. The conduction evaluated the effectiveness of our proposed algorithm on the iMOPSE dataset (standard dataset used for MS-RCPSP problem). All experiment results were collected and compared with other algorithms such as GA-M and GRASP. Experimental results show that M-PSO’s results are better than previous algorithms, specifically better than GA-M from 6.2% to 32.97% and GRASP from 0.6% to 15.8%.In the future, the authors will continue to research and improve the algorithm based on other approximation methods, using random moves based on Gauss, Cauchy, etc. to improve the suggested effectiveness of the algorithm.



---

*Source: 6230145-2022-02-15.xml*