# Effective Evolutionary Algorithm for Solving the Real-Resource-Constrained Scheduling Problem

Authors: Huu Dang Quoc; Loc Nguyen The; Cuong Nguyen Doan; Naixue Xiong
Journal: Journal of Advanced Transportation
 (2020)

---

## Abstract

This paper defines and introduces the formulation of the Real-RCPSP (Real-Resource-Constrained Project Scheduling Problem), a new variant of the MS-RCPSP (Multiskill Resource-Constrained Project Scheduling Problem). Real-RCPSP is an optimization problem that has been attracting widespread interest from the research community in recent years. Real-RCPSP has become a critical issue in many fields such as resource allocation to perform tasks in Edge Computing or arranging robots at industrial production lines at factories and IoT systems. Compared to the MS-RCPSP, the Real-RCPSP is supplemented with assumptions about the execution time of the task, so it is more realistic. The previous algorithms for solving the MS-RCPSP have only been verified on simulation data, so their results are not completely convincing. In addition, those algorithms are designed only to solve the MS-RCPSP, so they are not completely suitable for solving the new Real-RCPSP. Inspired by the Cuckoo Search approach, this literature proposes an evolutionary algorithm that uses the function Reallocate for fast convergence to the global extremum. In order to verify the proposed algorithm, the experiments were conducted on two datasets: (i) the iMOPSE simulation dataset that previous studies had used and (ii) the actual TNG dataset collected from the textile company TNG. Experimental results on the iMOPSE simulation dataset show that the proposed algorithm achieves better solution quality than the existing algorithms, while the experimental results on the TNG dataset have proved that the proposed algorithm decreases the execution time of current production lines at the TNG company.


---

## Body

## 1. Introduction

Scheduling is used to arrange the resources and tasks in many fields, where scheduling algorithms can have an important impact on the effectiveness and cost. In a logistic system, not only are cargo vehicles characterized by the factors of speed and carrying capacity, but also the skill of the driver is the most important factor in determining the quality of transportation. By taking into account all the factors, especially the driver’s skill one, scheduling algorithms help manage and coordinate the transport system. An intelligent scheduling algorithm helps managers exploit the maximum potential of resources including vehicle and driver to get the project done.In the wireless sensor networks, the node scheduling aims at selecting a set of nodes (i.e., sensors) that provide the data service. This scheduling can effectively reduce the number of nodes and messages and at the same time extend the network lifetime [1–3]. The basic goal of Edge Computing [4] is finding the optimal scheduling for extending the Cloud’s resources such as servers and routers from remote data centers to the edge of the Cloud where they are closer to users, thus overcoming the bottlenecks issue by cloud computing and providing higher performance.Solving the MS-RCPSP [5–7] problem is to find out the schedule to execute the project in the shortest possible time without breaking any constraints. In other words, the scheduling algorithm’s goal is to find a schedule with the smallest execution time while meeting any task and resource constraints. In this paper, the term “makespan” will be used to refer to the distance in time that elapses from the start of work to the end of execution time. MS-RCPSP is among the most commonly investigated optimization problems that have received a lot of attention due to their significant role in network resource scheduling and controlling.MS-RCPSP appears in many practical situations such as logistics and cargo transportation, widely applied to military operations such as sorting missions and determining travel routes [8]. Hosseinian and Baradaran [9] used an evaluation method to make plan decisions with MS-RCPSP. Nazafzad et al. [10] employed a biobjective optimization model for the MS-RCPSP considering shift differential payments and time-of-use electricity tariffs. Their study tried to minimize the cost and the makespan of a given project. Younis and Yang [11] propose the heuristic algorithm to solve a particular case of the MS-RCPSP occurring in grid computing.However, the MS-RCPSP has one serious defect. What often happens in practice is that a resource with a higher skill level has a shorter processing time. This paper presents a new problem, which is a more practical extension of the MS-RCPSP, called the Real-RCPSP. In other words, Real-RCPSP is a specific case of the MS-RCPSP. In the Real-RCPSP, the processing time depends on the skill level of the resource. The real-life nature of Real-RCPSP comes from production lines at the industry factory, where the higher the skill level of a worker is, the faster he can make the product.This paper is organized as follows. The next section presents some previous algorithms for solving the Resource-Constrained Scheduling Problem. This section also briefly introduces the Cuckoo Search strategy [12], one of the most widely used metaheuristics. Section 3 formulates the Real-RCPSP. The proposed algorithm (called R-CSM) is described in the fourth section. Section 4 introduces the most important components of R-CSM, consisting of the function Reallocate, the schedule representation, and a novel schedule measurement model. To verify the performance of the proposed algorithm, in Section 5 and Section 6, we arrange the experiments on the iMOPSE dataset and TNG’s dataset, respectively. In these two sections, the experimental results are analyzed to compare the performance of the proposed algorithm R-CSM with the best previous algorithms such as GreedyDO and GA. Finally, Section 7 ends the paper with the conclusion and future works.


## 2. Related Works

Despite the importance of the Real-RCPSP, no one to the best of our knowledge has studied this problem. This paper is the first work that mentions Real-RCPSP; thus this section introduces the existing algorithms to solve another problem that is close to the Real-RCPSP, namely, MS-RCPSP. In Section5 and Section 6, these algorithms will be used as reference algorithms in our experiments.Myszkowski et al. [6] proved that MS-RCPSP is an NP-hard problem, so it is difficult to deal with classical optimization methods. Until now, many different solutions have been introduced for solving the MS-RCPSP; among them, the most successful metaheuristics are the GA [13] and ACO [14].In their research, Maghsoudlou et al. [15] and Bibiks et al. [16] applied the Cuckoo Search algorithm to build multirisk project implementation schedules based on three different evaluation objectives. Zhu et al. [17] proposed an evolutionary algorithm based on the multiverse and several other heuristic algorithms.Myszkowski et al. [6] have built a hybrid algorithm that combined the Difference Evolution and greedy heuristic for managing human and machine resources in factory production projects. The proposed hybrid algorithm tried to minimize makespan and production costs. Besides, iMOPSE [6], a dataset that was generated based on real-world data from the project scheduling problem, was introduced.As a specific case of the MS-RCPCP problem, Real-RCPSP is researched and applied in many fields of the Internet of Things. Hosseinian and Baradaran [18] proposed a greedy heuristic for maximizing the modularity to find high-quality communities of employees and to arrange them to the tasks based on the founded communities. Younis and Yang [11] introduced a hybrid scheduling algorithm for task arrangement in grid computing environment.Some other researchers have also studied the new extension problems of the Constrained Project Scheduling Problem and applied them in many fields of science and finance. Polo-Mejia et al. [19] developed a scheduling algorithm to manage nuclear laboratory operations. To solve the problem of the dense sensors in wireless sensor networks, Wan et al. [20] proposed an energy-saving scheduling algorithm, which arranges some redundant sensors into the sleep mode to reduce the data transmission collision and energy dissipation. Guo et al. [21] developed a PSO-based algorithm that acquired better performance than previous approaches in power efficiency. Cheng et al. [22] have formulated another PSO-based algorithm named DPSO-CA, which is based on the discrete PSO that aims at minimizing the cochannel interference in the network.Previous studies have also been performed to address other subissues of the Constrained Project Scheduling Problem. Barrios et al. [23] and Javanmard et al. [24] studied the Multiskill Stochastic and Preemptive Scheduling Problem to minimize the execution time and proposed the mathematical models for the project’s resource investment.Cuckoo Search (CS) algorithm is a metaheuristic introduced by Yang [25] based on the cuckoo bird behavior. Previous algorithms such as Difference Evolution (DE) [26] and Particle Swarm Optimization (PSO) [21] have been proven to be special cases of the Cuckoo Search algorithm. The efficiency of CS has also been shown to be better than those of DE and PSO in some cases [27]. For the above reasons, in this paper, we have built an algorithm inspired by CS.


## 3. Problem Statement

The Real-RCPSP can be described as follows.A project represented by a graphGV,E has to be realized. Each node of graph G represents a task, while G’s arc represents the relationship between 2 tasks (Figure 1). Specifically, the arci,j means that task i has to be finished by the time when task j is started. Each task has an execution time (or duration) that is calculated by subtracting the start time from the end time. The task must be performed continuously from start to finish and must not be stopped at all.Figure 1
The relationship between tasks.The execution of each task requires some specific resources. Each resource can perform only one task at a time. The task’s execution requires several skills, while each resource possesses its own skills; thus not every resource can perform a given task.The objective of the Real-RCPSP is to shorten the project implementation time to the smallest value while not breaking any constraints. A schedule must be found in which execution will minimize execution time while still meeting the task and resource constraints. As mentioned above, the MS-RCPSP is proved to be NP-hard [5–7], and no polynomial-time algorithm exists, assuming that P≠NP.Real-RCPSP could be stated by using the following notations:(i)
Ci: the set of the parents of task i(ii)
ri: the set of skills required by task i. A certain resource must have an equal or higher skill level of rj to perform task j(iii)
S: the set of all skills; Si: the set of skills belonging to resource i;Si⊆S(iv)
tjk: the time it takes the resource that possesses subset of skill Sk to complete task j(v)
L: the set of resources; Lk: the set of resources that could handle task k; Lk⊆L(vi)
Li: resource i(vii)
W: the set of tasks; Wk: the set of tasks that could be performed by resource k, Wk⊆W(viii)
Wi: task i(ix)
Bk, Ek: starting time and ending time of task k(x)
Au,vi: a Boolean variable; when it equals 1 it means that task u will be executed by resource v at time I; it equals 0 in other cases(xi)
hi: the level of skill i; gi: type of skill i(xii)
rk: a resource must possess skill rk to perform task k(xiii)
m: the period time of the schedule(xiv)
P: a candidate schedule; Pall: the set of candidate schedules(xv)
fP: makespan (execution time) of schedule P(xvi)
y: number of tasks; z: number of resourcesReal-RCPSP could be defined as follows:(1)minimizefP,where(2)fP=maxi∈TEi−mink∈TBk,subject to(3)Sk≠ϕ∀k∈L,(4)Tj≥0∀j∈W,(5)Ej≥0∀j∈W,(6)Ei≤Ej−tj∀j∈W,j≠1,i∈Cj,(7)∀i∈Wk∃r∈Sk:gr=gri,hr≥hri,(8)∀k∈L,∀t∈m:∑i=1nAi,kt≤1,(9)∀j∈W∃!t∈m,!k∈L:Aj,kt=1,(10)Ifhi<hjthentjk>tik∀ri,rj∈Sk×Sv.Note the following:(i)
Formulation (6) forced the parent task to must be finished before the start time of the children task(ii)
Formulation (7) means that, for every task, there is always at least one resource that has enough skill level to handle that task(iii)
Formulation (8) ensures that each resource (k) can only perform at most one task (j) at any time (t)(iv)
Constraint (9) aims to restrict each task to only be executed at most one time. Every task must be performed continuously from start to finish and must not be stopped at all.(v)
Constraint (10) means that the execution time of the higher-skill resources is smaller than the execution time of the lower-skill resources


## 4. Proposed Algorithm

### 4.1. Schedule Representation

We represent a schedule as a row that consists of several elements, and the number of elements denotes the number of tasks. Each element of the row represents the resource that will perform the respective task.


#### 4.1.1. Example 1

Suppose that we have 10 tasksW=1,2,3,4,5,6,7,8,9,10 and 3 resources L=1,2,3. Assume the following:(i)
Sk=S,∀k∈L; every resource has an equal skill set(ii)
Lk=L,∀k∈W; any resource can perform any task(iii)
The execution times of the tasks are presented in Table1Table 1
Execution times of the tasks.
TaskW1W2W3W4W5W6W7W8W9W10Execution time3234343626We also assume that the constraint to prioritize the performance of the tasks is shown in Figure1, specifically:(i)
Task 1 has to be performed firstly(ii)
Task 6 has to be performed after task 2(iii)
Tasks 7 and 9 have to be performed after task 3(iv)
Task 5 has to be performed after task 4(v)
Task 8 has to be performed after task 5(vi)
Task 10 has to be performed after tasks 6, 7, and 9With the above assumptions and constraints, a possible schedule is shown in Figure2. Table 2 shows how that schedule assigns 3 resources to perform 10 tasks in detail.Figure 2
A possible schedule.Table 2
The assignment of a possible schedule.
TaskW1W2W3W4W5W6W7W8W9W10ResourceL2L1L2L3L2L1L3L2L3L3As described in Table2, resource 1 executes task 2 and task 6; resource 2 handles tasks 1, 3, 5, and 8; resource 3 executes tasks 4, 7, 9, and 10.


### 4.2. Measurement Model

Cuckoo Search algorithm is an optimization scheme dealing with real functions such as the Gaussian probability distribution function, whereas Real-RCPSP is the optimization problem of discrete functions. Therefore, in order to apply the Cuckoo Search algorithm to the Real-RCPSP, it is necessary to build a model for schedules measuring. The following will present our proposed measurement model in detail:(i)
V=v1,v2,…,vn is called “unit vector,” where vi=100/zi−1: zi is the number of resources that possess set of skills qi.(ii)
VectorK=k1,k2,…,kn is the distance between schedule P=p1,p2,…,pn and schedule Q=q1,q2,…,qn. This leads to K=P−Q.Meanwhile, if scheduleQ=q1,q2,…,qn is added with a difference K=k1,k2,…,kn, schedule P=p1,p2,…,pn is obtained, where we have the following:(iii)
pi=positionroundqi+ki and position (i) presents the respective resource(iv)
ki=vi×orderpi−orderqiorderpi: the place ofpi in the Li


#### 4.2.1. Example 2

Suppose thatL1=L1,L3,L4,L9,L10. We have z1=5; v1=100/5−1=25.Similarly, suppose thatL1=L6,L7,L8,L10. We have z2=4; v2=100/4−1=33.33.Table3 depicts the order of resources.Table 3
The order of resources.
Order01234ResourceL1L3L4L9L10ResourceL6L7L8L10ScheduleP=1,8 and schedule Q=4,7 are shown in Table 4.Table 4
The assignment of schedulesP and Q.
ScheduleTask12PL1L8QL4L7Consider the distanceK=P−Q=k1,k2 where k1=v1×absorderp1−orderq1=25abs0−2=25.k2=v2×absorderp2−orderq2=33.33×abs2−1=33.33.This leads toK=50,33.33.GivenKP=0,66.66, we have Z=P+K⟶KP+K⟶4,10 (Table 5).Table 5
Measurement value.
Task12PL1L8KP066.66K5033.33KP+K5099.99Z=KP+KL4L10


### 4.3. Proposed Algorithm R-CSM

The proposed Algorithm1 R-CSM is represented as follows.Algorithm 1:R-CSM algorithm.
input: maxGenerationiMOPSE datasetsoutput: makespan of project(1)
Begin(2)
t⟵0(3)
Size ⟵ number of individuals (i.e. possible schedules)(4)
pt ⟵ the first population(5)
ft ⟵ the fitness, b_plan(bestnest), makespan(6)
pa=0.25(7)
While (t < max_gen)(8)
n_plan ⟵ create new nest by Lévy Flight(9)
r_plan ⟵ Select random nest fromPt(10)
If (f(n_plan) < (r_plan))(11)
r_plan = n_plan(12)
End if(13)
Pt ⟵ Remove pa worst nest and replace by new nests, new nests created by Lévy Flight(14)
Ft ⟵ the fitness, b_plan, makespan(15)
b_plan ⟵ Reallocate(b_plan)//scheduleb_plan is improved by the//function Reallocate(), which is described in the next subsection in details.(16)
t⟵t+1(17)
End while(18)
returnmakespan(19)
Endf is objective function.Note that, in line number 16, functionReallocate() improves the quality of b_plan, as analyzed in the next subsection.


### 4.4. Function Reallocate

c_plan is the most appropriate feasible schedule until now.Lb is the last resource to finish. Function Late() will find out the value of Rb.Size() is the size of a set or an array.N_makespan is execution time of the new resource-task arrangementLine 12 and line 13 show that the new schedule (n_plan) is always equal to or better than the old schedule (c_plan) in terms of the makespan.The function Reallocate() (Figure3) generates the new schedule from the best schedule, so it inherits and promotes the advantages of the current population (Algorithm 2).Figure 3
Function Reallocate.Algorithm 2:Function Reallocate.
Input: b_plan//the best feasible schedule that the algorithm has found until nowOutput://the feasible schedule which is better than the input(1)
Begin(2)
makespan =f(b_plan)(3)
n_plan =b_plan;//the best resource-task assignment plan so far(4)
Lb ← Late(n_plan)//the resource finish its execution latest(5)
Wb←set of tasks is performed by resource Lb(6)
Fori = 1 to sizeWb//examine the set of tasks performed by resource Lb(7)
Wi=Wbi;(8)
Li←L−LbLi←L − Lb//set of resource can perform the task i except Lb(9)
Forj = 1 to sizeLi(10)
Wj=Wj+Wi//task i will perform the resource Lj(11)
Wb=Wb+Wi//task i is eliminated from Lb(12)
n_makespan =f(n_plan)(13)
If n_makespan < makespan(14)
Makespan = n_makespan(15)
Return b_best;(16)
End if(17)
b_plan = n_plan;(18)
End for(19)
End for(20)
Return n_plan(21)
End Function


#### 4.4.1. Example 3

Suppose thatW=1,2,3,4,5,6,7,8,9,10; L=1,2,3.We also assume that resource 1 can handle tasks 1, 2, 3, 4, 6, 8, 9, and 10; resource 2 can execute tasks 1, 3, 7, and 9; resource 3 can perform tasks 1, 4, 5, 8, 9, and 10.The constraint regarding the task order is illustrated in Figure1, and the task’s execution time is shown in Table 1.Table6 depicts the schedule P; its makespan is equal to 18 as shown in Figure 4 in detail.Table 6
Resource-task assignment ofP.
TaskW1W2W3W4W5W6W7W8W9W10ResourceL1L1L2L3L3L1L2L1L3L3Figure 4
The schedule changes as a result of the function Reallocate.The function Reallocate uses schedule P as the input and arranges task 9 to resource 1 (see Table7) instead of resource 3 as before.Table 7
Resource-task assignment of newP.
TaskW1W2W3W4W5W6W7W8W9W10ResourceL1L1L2L3L3L1L2L1L1L3The results point out that functionReallocate decreases the makespan from 18 to 17, as described in Figure 4.


## 4.1. Schedule Representation

We represent a schedule as a row that consists of several elements, and the number of elements denotes the number of tasks. Each element of the row represents the resource that will perform the respective task.


### 4.1.1. Example 1

Suppose that we have 10 tasksW=1,2,3,4,5,6,7,8,9,10 and 3 resources L=1,2,3. Assume the following:(i)
Sk=S,∀k∈L; every resource has an equal skill set(ii)
Lk=L,∀k∈W; any resource can perform any task(iii)
The execution times of the tasks are presented in Table1Table 1
Execution times of the tasks.
TaskW1W2W3W4W5W6W7W8W9W10Execution time3234343626We also assume that the constraint to prioritize the performance of the tasks is shown in Figure1, specifically:(i)
Task 1 has to be performed firstly(ii)
Task 6 has to be performed after task 2(iii)
Tasks 7 and 9 have to be performed after task 3(iv)
Task 5 has to be performed after task 4(v)
Task 8 has to be performed after task 5(vi)
Task 10 has to be performed after tasks 6, 7, and 9With the above assumptions and constraints, a possible schedule is shown in Figure2. Table 2 shows how that schedule assigns 3 resources to perform 10 tasks in detail.Figure 2
A possible schedule.Table 2
The assignment of a possible schedule.
TaskW1W2W3W4W5W6W7W8W9W10ResourceL2L1L2L3L2L1L3L2L3L3As described in Table2, resource 1 executes task 2 and task 6; resource 2 handles tasks 1, 3, 5, and 8; resource 3 executes tasks 4, 7, 9, and 10.


## 4.1.1. Example 1

Suppose that we have 10 tasksW=1,2,3,4,5,6,7,8,9,10 and 3 resources L=1,2,3. Assume the following:(i)
Sk=S,∀k∈L; every resource has an equal skill set(ii)
Lk=L,∀k∈W; any resource can perform any task(iii)
The execution times of the tasks are presented in Table1Table 1
Execution times of the tasks.
TaskW1W2W3W4W5W6W7W8W9W10Execution time3234343626We also assume that the constraint to prioritize the performance of the tasks is shown in Figure1, specifically:(i)
Task 1 has to be performed firstly(ii)
Task 6 has to be performed after task 2(iii)
Tasks 7 and 9 have to be performed after task 3(iv)
Task 5 has to be performed after task 4(v)
Task 8 has to be performed after task 5(vi)
Task 10 has to be performed after tasks 6, 7, and 9With the above assumptions and constraints, a possible schedule is shown in Figure2. Table 2 shows how that schedule assigns 3 resources to perform 10 tasks in detail.Figure 2
A possible schedule.Table 2
The assignment of a possible schedule.
TaskW1W2W3W4W5W6W7W8W9W10ResourceL2L1L2L3L2L1L3L2L3L3As described in Table2, resource 1 executes task 2 and task 6; resource 2 handles tasks 1, 3, 5, and 8; resource 3 executes tasks 4, 7, 9, and 10.


## 4.2. Measurement Model

Cuckoo Search algorithm is an optimization scheme dealing with real functions such as the Gaussian probability distribution function, whereas Real-RCPSP is the optimization problem of discrete functions. Therefore, in order to apply the Cuckoo Search algorithm to the Real-RCPSP, it is necessary to build a model for schedules measuring. The following will present our proposed measurement model in detail:(i)
V=v1,v2,…,vn is called “unit vector,” where vi=100/zi−1: zi is the number of resources that possess set of skills qi.(ii)
VectorK=k1,k2,…,kn is the distance between schedule P=p1,p2,…,pn and schedule Q=q1,q2,…,qn. This leads to K=P−Q.Meanwhile, if scheduleQ=q1,q2,…,qn is added with a difference K=k1,k2,…,kn, schedule P=p1,p2,…,pn is obtained, where we have the following:(iii)
pi=positionroundqi+ki and position (i) presents the respective resource(iv)
ki=vi×orderpi−orderqiorderpi: the place ofpi in the Li


### 4.2.1. Example 2

Suppose thatL1=L1,L3,L4,L9,L10. We have z1=5; v1=100/5−1=25.Similarly, suppose thatL1=L6,L7,L8,L10. We have z2=4; v2=100/4−1=33.33.Table3 depicts the order of resources.Table 3
The order of resources.
Order01234ResourceL1L3L4L9L10ResourceL6L7L8L10ScheduleP=1,8 and schedule Q=4,7 are shown in Table 4.Table 4
The assignment of schedulesP and Q.
ScheduleTask12PL1L8QL4L7Consider the distanceK=P−Q=k1,k2 where k1=v1×absorderp1−orderq1=25abs0−2=25.k2=v2×absorderp2−orderq2=33.33×abs2−1=33.33.This leads toK=50,33.33.GivenKP=0,66.66, we have Z=P+K⟶KP+K⟶4,10 (Table 5).Table 5
Measurement value.
Task12PL1L8KP066.66K5033.33KP+K5099.99Z=KP+KL4L10


## 4.2.1. Example 2

Suppose thatL1=L1,L3,L4,L9,L10. We have z1=5; v1=100/5−1=25.Similarly, suppose thatL1=L6,L7,L8,L10. We have z2=4; v2=100/4−1=33.33.Table3 depicts the order of resources.Table 3
The order of resources.
Order01234ResourceL1L3L4L9L10ResourceL6L7L8L10ScheduleP=1,8 and schedule Q=4,7 are shown in Table 4.Table 4
The assignment of schedulesP and Q.
ScheduleTask12PL1L8QL4L7Consider the distanceK=P−Q=k1,k2 where k1=v1×absorderp1−orderq1=25abs0−2=25.k2=v2×absorderp2−orderq2=33.33×abs2−1=33.33.This leads toK=50,33.33.GivenKP=0,66.66, we have Z=P+K⟶KP+K⟶4,10 (Table 5).Table 5
Measurement value.
Task12PL1L8KP066.66K5033.33KP+K5099.99Z=KP+KL4L10


## 4.3. Proposed Algorithm R-CSM

The proposed Algorithm1 R-CSM is represented as follows.Algorithm 1:R-CSM algorithm.
input: maxGenerationiMOPSE datasetsoutput: makespan of project(1)
Begin(2)
t⟵0(3)
Size ⟵ number of individuals (i.e. possible schedules)(4)
pt ⟵ the first population(5)
ft ⟵ the fitness, b_plan(bestnest), makespan(6)
pa=0.25(7)
While (t < max_gen)(8)
n_plan ⟵ create new nest by Lévy Flight(9)
r_plan ⟵ Select random nest fromPt(10)
If (f(n_plan) < (r_plan))(11)
r_plan = n_plan(12)
End if(13)
Pt ⟵ Remove pa worst nest and replace by new nests, new nests created by Lévy Flight(14)
Ft ⟵ the fitness, b_plan, makespan(15)
b_plan ⟵ Reallocate(b_plan)//scheduleb_plan is improved by the//function Reallocate(), which is described in the next subsection in details.(16)
t⟵t+1(17)
End while(18)
returnmakespan(19)
Endf is objective function.Note that, in line number 16, functionReallocate() improves the quality of b_plan, as analyzed in the next subsection.


## 4.4. Function Reallocate

c_plan is the most appropriate feasible schedule until now.Lb is the last resource to finish. Function Late() will find out the value of Rb.Size() is the size of a set or an array.N_makespan is execution time of the new resource-task arrangementLine 12 and line 13 show that the new schedule (n_plan) is always equal to or better than the old schedule (c_plan) in terms of the makespan.The function Reallocate() (Figure3) generates the new schedule from the best schedule, so it inherits and promotes the advantages of the current population (Algorithm 2).Figure 3
Function Reallocate.Algorithm 2:Function Reallocate.
Input: b_plan//the best feasible schedule that the algorithm has found until nowOutput://the feasible schedule which is better than the input(1)
Begin(2)
makespan =f(b_plan)(3)
n_plan =b_plan;//the best resource-task assignment plan so far(4)
Lb ← Late(n_plan)//the resource finish its execution latest(5)
Wb←set of tasks is performed by resource Lb(6)
Fori = 1 to sizeWb//examine the set of tasks performed by resource Lb(7)
Wi=Wbi;(8)
Li←L−LbLi←L − Lb//set of resource can perform the task i except Lb(9)
Forj = 1 to sizeLi(10)
Wj=Wj+Wi//task i will perform the resource Lj(11)
Wb=Wb+Wi//task i is eliminated from Lb(12)
n_makespan =f(n_plan)(13)
If n_makespan < makespan(14)
Makespan = n_makespan(15)
Return b_best;(16)
End if(17)
b_plan = n_plan;(18)
End for(19)
End for(20)
Return n_plan(21)
End Function


### 4.4.1. Example 3

Suppose thatW=1,2,3,4,5,6,7,8,9,10; L=1,2,3.We also assume that resource 1 can handle tasks 1, 2, 3, 4, 6, 8, 9, and 10; resource 2 can execute tasks 1, 3, 7, and 9; resource 3 can perform tasks 1, 4, 5, 8, 9, and 10.The constraint regarding the task order is illustrated in Figure1, and the task’s execution time is shown in Table 1.Table6 depicts the schedule P; its makespan is equal to 18 as shown in Figure 4 in detail.Table 6
Resource-task assignment ofP.
TaskW1W2W3W4W5W6W7W8W9W10ResourceL1L1L2L3L3L1L2L1L3L3Figure 4
The schedule changes as a result of the function Reallocate.The function Reallocate uses schedule P as the input and arranges task 9 to resource 1 (see Table7) instead of resource 3 as before.Table 7
Resource-task assignment of newP.
TaskW1W2W3W4W5W6W7W8W9W10ResourceL1L1L2L3L3L1L2L1L1L3The results point out that functionReallocate decreases the makespan from 18 to 17, as described in Figure 4.


## 4.4.1. Example 3

Suppose thatW=1,2,3,4,5,6,7,8,9,10; L=1,2,3.We also assume that resource 1 can handle tasks 1, 2, 3, 4, 6, 8, 9, and 10; resource 2 can execute tasks 1, 3, 7, and 9; resource 3 can perform tasks 1, 4, 5, 8, 9, and 10.The constraint regarding the task order is illustrated in Figure1, and the task’s execution time is shown in Table 1.Table6 depicts the schedule P; its makespan is equal to 18 as shown in Figure 4 in detail.Table 6
Resource-task assignment ofP.
TaskW1W2W3W4W5W6W7W8W9W10ResourceL1L1L2L3L3L1L2L1L3L3Figure 4
The schedule changes as a result of the function Reallocate.The function Reallocate uses schedule P as the input and arranges task 9 to resource 1 (see Table7) instead of resource 3 as before.Table 7
Resource-task assignment of newP.
TaskW1W2W3W4W5W6W7W8W9W10ResourceL1L1L2L3L3L1L2L1L1L3The results point out that functionReallocate decreases the makespan from 18 to 17, as described in Figure 4.


## 5. Simulation with iMOPSE Dataset

### 5.1. Simulation Settings

To verify the performance of the R-CSM, the simulations are conducted by using iMOPSE dataset [6], which has been used by previous studies to examine algorithms such as GreedyDO and GA [28]. iMOPSE’s instances have the following fields:(i)
Number of tasks and resources(ii)
The constraint regarding the task order(iii)
Set of resource’s skillsThis paper arranges the simulations on iMOPSE’s instances listed in Table8. All of our simulations were run on a machine with Intel® Core i7 CPU at 2.2 GHz, 6 GB RAM, running Windows 10. Our R-CSM algorithm was programmed in Matlab. Simulation results are described in Table 9.Table 8
d36 iMOPSE dataset.
Dataset instanceTasksResourcesPrecedence 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_15200409115Table 9
Makespan of algorithms (in hour).
Dataset instanceGreedyDOGAR-CSMAvgBestStdAvgBestStd100_5_22_1563052451754854841.41100_5_46_1569358758455415382.55100_5_48_9779535528104934902.16100_5_64_1564053052724964904.55100_5_64_9597521508104794743.68100_10_26_1537029429222382370.94100_10_47_954929929632562532.36100_10_48_1534428227932452422.25100_10_64_953330529672492435.32100_10_65_1542629028652472451.25100_20_22_1535316916361271243.4100_20_46_1539420719771671642.85100_20_47_939018618501461431.89100_20_65_1531024324022132102.05100_20_65_940818718151331284.5200_10_128_1578058357754714682.94200_10_50_15763577553174894853.3200_10_50_981758958554844840.47200_10_84_9999583567115095053.91200_10_85_1570655554954764741.32200_20_145_1548032832622442403.48200_20_54_15488385363212612573.19200_20_55_999931831242512482.87200_20_97_15680438424103353341.89200_20_97_981632632162492443.42200_40_133_1551222221561541484.19200_40_45_1561621020161651613.68200_40_45_982121320931591528.06200_40_90_996321521131521483.72200_40_91_1551920520031411354.92Each simulation was set up with parameters as follows:(i)
Dataset: 30 iMOPSE’s instances that are described above(ii)
Number of individuals in populationNp=100(iii)
The program execution process consists of 50,000 generationsNg=50,000(iv)
Each instance was repeatedly executed 30 times


### 5.2. Simulation Results

To show the efficiency of the proposed algorithm, we compare R-CSM with two existing algorithms, which are GreedyDO and GA [28]. Myszkowski did not provide the tool for GreedyDO; thus Table 9 just lists the best value of the algorithm GreedyDO that was published in the author’s literature. Meanwhile algorithm GA is reprogrammed using the GARunner, the tool provided by the authors in [6, 28]; thus Table 9 lists the average value, the best value, and the standard deviation value of the algorithm GA’s makespan.Table9 and Figure 5 demonstrated that the makespan of the R-CSM’s schedules is smaller than the makespan of GreedyDO and GA. The comparison between algorithms is discussed as follows in detail:(i)
Compared with the original CS, the R-CSM algorithm is equipped with function Reallocate, which makes R-CSM capable of fast convergence. This ability is clearly demonstrated by the comparison of R-CSM with the previous most powerful algorithms. R-CSM’s best value is smaller than GreedyDO from 21% to 85% and faster than GA from 6% to 33%. The average value of the R-CSM’s makespan is better than the GA from 6% to 33%.(ii)
Thanks to the function Reallocate and the proposed measurement model, the process of finding the optimal schedule of the R-CSM is not only fast but also stable. This is demonstrated by the experimental results in Table9. The total value of R-CSM’s standard deviation is 92.52 only, whereas the total value of GA’s standard deviation is equal to 180. This result shows that the R-CSM algorithm is more stable than the GA algorithm.Figure 5
The comparison of performance between R-CSM and GA.


## 5.1. Simulation Settings

To verify the performance of the R-CSM, the simulations are conducted by using iMOPSE dataset [6], which has been used by previous studies to examine algorithms such as GreedyDO and GA [28]. iMOPSE’s instances have the following fields:(i)
Number of tasks and resources(ii)
The constraint regarding the task order(iii)
Set of resource’s skillsThis paper arranges the simulations on iMOPSE’s instances listed in Table8. All of our simulations were run on a machine with Intel® Core i7 CPU at 2.2 GHz, 6 GB RAM, running Windows 10. Our R-CSM algorithm was programmed in Matlab. Simulation results are described in Table 9.Table 8
d36 iMOPSE dataset.
Dataset instanceTasksResourcesPrecedence 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_15200409115Table 9
Makespan of algorithms (in hour).
Dataset instanceGreedyDOGAR-CSMAvgBestStdAvgBestStd100_5_22_1563052451754854841.41100_5_46_1569358758455415382.55100_5_48_9779535528104934902.16100_5_64_1564053052724964904.55100_5_64_9597521508104794743.68100_10_26_1537029429222382370.94100_10_47_954929929632562532.36100_10_48_1534428227932452422.25100_10_64_953330529672492435.32100_10_65_1542629028652472451.25100_20_22_1535316916361271243.4100_20_46_1539420719771671642.85100_20_47_939018618501461431.89100_20_65_1531024324022132102.05100_20_65_940818718151331284.5200_10_128_1578058357754714682.94200_10_50_15763577553174894853.3200_10_50_981758958554844840.47200_10_84_9999583567115095053.91200_10_85_1570655554954764741.32200_20_145_1548032832622442403.48200_20_54_15488385363212612573.19200_20_55_999931831242512482.87200_20_97_15680438424103353341.89200_20_97_981632632162492443.42200_40_133_1551222221561541484.19200_40_45_1561621020161651613.68200_40_45_982121320931591528.06200_40_90_996321521131521483.72200_40_91_1551920520031411354.92Each simulation was set up with parameters as follows:(i)
Dataset: 30 iMOPSE’s instances that are described above(ii)
Number of individuals in populationNp=100(iii)
The program execution process consists of 50,000 generationsNg=50,000(iv)
Each instance was repeatedly executed 30 times


## 5.2. Simulation Results

To show the efficiency of the proposed algorithm, we compare R-CSM with two existing algorithms, which are GreedyDO and GA [28]. Myszkowski did not provide the tool for GreedyDO; thus Table 9 just lists the best value of the algorithm GreedyDO that was published in the author’s literature. Meanwhile algorithm GA is reprogrammed using the GARunner, the tool provided by the authors in [6, 28]; thus Table 9 lists the average value, the best value, and the standard deviation value of the algorithm GA’s makespan.Table9 and Figure 5 demonstrated that the makespan of the R-CSM’s schedules is smaller than the makespan of GreedyDO and GA. The comparison between algorithms is discussed as follows in detail:(i)
Compared with the original CS, the R-CSM algorithm is equipped with function Reallocate, which makes R-CSM capable of fast convergence. This ability is clearly demonstrated by the comparison of R-CSM with the previous most powerful algorithms. R-CSM’s best value is smaller than GreedyDO from 21% to 85% and faster than GA from 6% to 33%. The average value of the R-CSM’s makespan is better than the GA from 6% to 33%.(ii)
Thanks to the function Reallocate and the proposed measurement model, the process of finding the optimal schedule of the R-CSM is not only fast but also stable. This is demonstrated by the experimental results in Table9. The total value of R-CSM’s standard deviation is 92.52 only, whereas the total value of GA’s standard deviation is equal to 180. This result shows that the R-CSM algorithm is more stable than the GA algorithm.Figure 5
The comparison of performance between R-CSM and GA.


## 6. Experiment with TNG Dataset

### 6.1. Experimental Setting

In general, the major disadvantage of verifying on simulation datasets, such as iMOPSE, is that sometimes the results do not match what is actually happening. In order to make the experiment more convincing, we have collected and used the dataset of Investment and Trading Joint Stock Company (TNG) [29]. At TNG textile factory, the dataset construction is carried out as follows:(i)
The company TNG contracts with business partners, whereby each order corresponds to a product sample with a large quantity(ii)
A given order will be performed by a subset of employees(iii)
A product consists of several components, and each component takes an execution time(iv)
The skills of each worker are evaluated based on that worker’s rankConducting experiments on a simulation dataset is always convenient because the parameters of the dataset are set by the experimenter; therefore these parameters are completely consistent with the problem formulation.In contrast, the parameters of a real dataset are factory-defined, so they are not compatible with the conventions in the problem formulation. For this reason, before conducting experiments with TNG’s dataset, the parameters of this dataset need to be converted to a format that matches the Real-RCPSP formulation.This conversion is conducted as follows:(i)
Order is demonstrated by the project(ii)
Product’s stage is depicted by a task(iii)
An employee is depicted by a resource(iv)
Employee’s grade is depicted by the resource’s skill level(v)
The manufacture sequence is denoted by the task’s relationship(vi)
The execution time of the order is demonstrated by the makespanThe TNG dataset is described in Table10.Table 10
TNG dataset.
Dataset instanceNameTasksResourcesPrecedence relationsSkill levelsProject time71_37_1026_1TNG171371026640971_39_1026_1TNG271391026632571_41_1026_1TNG371411026629671_45_1026_1TNG4714510266392137_37_1894_1TNG513737189461174137_39_1894_1TNG613739189461052137_41_1894_1TNG71374118946871137_45_1894_1TNG81374518946996Experiment setting is as follows:(i)
Dataset: 8 TNG’s instances that are listed in Table10(ii)
Number of individuals in populationNp=100(iii)
The program execution process consists of 50,000 generationsNg=50,000(iv)
Each instance was repeatedly executed 35 times


### 6.2. Experimental Results

The experiments in this section were conducted on the TNG dataset to prove that the proposed algorithm is more efficient than existing algorithms not only when they are operating on the simulated dataset such as iMOPSE but also when operating on the actual dataset.Experimental results (listed in Table11) demonstrated that the proposed algorithm R-CSM is not only more efficient than previous algorithms such as GreedyDO and GA but also more efficient than the actual production plan at the TNG factory, which is presented in column TNG.Table 11
Makespan of GreedyDO, GA, and R-CSM (in hour).
Dataset instanceTNGGreedyDOGAR-CSMTNG1409236201166TNG2325243198165TNG3296258212168TNG4392248176175TNG51174972751710TNG61052963791715TNG7871834810727TNG8996906720677As depicted in Table11, compared to the execution time of the actual production plan at the factory TNG,the GA and GreedyDO algorithms reduce the makespan by 7%–55% and 4%–42%, respectively, while R-CSM has the best results of 17%–59%.As the best current evolutionary algorithms, GreedyDO and GA are both better than the actual production plan at the factory TNG. However, neither of these algorithms is as good as the proposed algorithm R-CSM. In experiments on the TNG datasets, R-CSM lessens the makespan from 17% to 59% compared to the current factory schedule. To sum up, the proposed algorithm R-CSM has been proven to be overall more effective compared to existing approaches such as GreedyDO, GA, and the current factory schedule.Applying the R-CSM algorithm on the data from table Table11 to solve the Real-RCPSP, we get the results shown in Table 12.Table 12
Experimental results with Real-RCPSP.
Dataset instanceTNG (A)MS-RCPSP (1)Real-RCPSP (2)(2) vs. (1)Bestvs. (A) (%)Bestvs. (A) (%)Hours%TNG140916659131683521.1TNG232516549133593219.4TNG329616843132553621.4TNG439217555127684827.4TNG51174710405725113819.4TNG6105271532626408912.4TNG7871727175693515821.7TNG8996677325604411717.3Experimental results in Table12 show that, thanks to the application of the R-CSM algorithm to the actual problem with data on the textile production of TNG, the production time is reduced from 12.4% to 27%. These results also show that the greater the difference between the skill levels of workers, the more efficient the R-CSM algorithm.Figure6 shows the effectiveness of algorithm R-CSM when it is applied to solve the MS-RCPSP and the Real-RCPSP on the textile dataset of TNG textile company.Figure 6
R-CSM to solve MS-RCPSP and Real-RCPSP.


## 6.1. Experimental Setting

In general, the major disadvantage of verifying on simulation datasets, such as iMOPSE, is that sometimes the results do not match what is actually happening. In order to make the experiment more convincing, we have collected and used the dataset of Investment and Trading Joint Stock Company (TNG) [29]. At TNG textile factory, the dataset construction is carried out as follows:(i)
The company TNG contracts with business partners, whereby each order corresponds to a product sample with a large quantity(ii)
A given order will be performed by a subset of employees(iii)
A product consists of several components, and each component takes an execution time(iv)
The skills of each worker are evaluated based on that worker’s rankConducting experiments on a simulation dataset is always convenient because the parameters of the dataset are set by the experimenter; therefore these parameters are completely consistent with the problem formulation.In contrast, the parameters of a real dataset are factory-defined, so they are not compatible with the conventions in the problem formulation. For this reason, before conducting experiments with TNG’s dataset, the parameters of this dataset need to be converted to a format that matches the Real-RCPSP formulation.This conversion is conducted as follows:(i)
Order is demonstrated by the project(ii)
Product’s stage is depicted by a task(iii)
An employee is depicted by a resource(iv)
Employee’s grade is depicted by the resource’s skill level(v)
The manufacture sequence is denoted by the task’s relationship(vi)
The execution time of the order is demonstrated by the makespanThe TNG dataset is described in Table10.Table 10
TNG dataset.
Dataset instanceNameTasksResourcesPrecedence relationsSkill levelsProject time71_37_1026_1TNG171371026640971_39_1026_1TNG271391026632571_41_1026_1TNG371411026629671_45_1026_1TNG4714510266392137_37_1894_1TNG513737189461174137_39_1894_1TNG613739189461052137_41_1894_1TNG71374118946871137_45_1894_1TNG81374518946996Experiment setting is as follows:(i)
Dataset: 8 TNG’s instances that are listed in Table10(ii)
Number of individuals in populationNp=100(iii)
The program execution process consists of 50,000 generationsNg=50,000(iv)
Each instance was repeatedly executed 35 times


## 6.2. Experimental Results

The experiments in this section were conducted on the TNG dataset to prove that the proposed algorithm is more efficient than existing algorithms not only when they are operating on the simulated dataset such as iMOPSE but also when operating on the actual dataset.Experimental results (listed in Table11) demonstrated that the proposed algorithm R-CSM is not only more efficient than previous algorithms such as GreedyDO and GA but also more efficient than the actual production plan at the TNG factory, which is presented in column TNG.Table 11
Makespan of GreedyDO, GA, and R-CSM (in hour).
Dataset instanceTNGGreedyDOGAR-CSMTNG1409236201166TNG2325243198165TNG3296258212168TNG4392248176175TNG51174972751710TNG61052963791715TNG7871834810727TNG8996906720677As depicted in Table11, compared to the execution time of the actual production plan at the factory TNG,the GA and GreedyDO algorithms reduce the makespan by 7%–55% and 4%–42%, respectively, while R-CSM has the best results of 17%–59%.As the best current evolutionary algorithms, GreedyDO and GA are both better than the actual production plan at the factory TNG. However, neither of these algorithms is as good as the proposed algorithm R-CSM. In experiments on the TNG datasets, R-CSM lessens the makespan from 17% to 59% compared to the current factory schedule. To sum up, the proposed algorithm R-CSM has been proven to be overall more effective compared to existing approaches such as GreedyDO, GA, and the current factory schedule.Applying the R-CSM algorithm on the data from table Table11 to solve the Real-RCPSP, we get the results shown in Table 12.Table 12
Experimental results with Real-RCPSP.
Dataset instanceTNG (A)MS-RCPSP (1)Real-RCPSP (2)(2) vs. (1)Bestvs. (A) (%)Bestvs. (A) (%)Hours%TNG140916659131683521.1TNG232516549133593219.4TNG329616843132553621.4TNG439217555127684827.4TNG51174710405725113819.4TNG6105271532626408912.4TNG7871727175693515821.7TNG8996677325604411717.3Experimental results in Table12 show that, thanks to the application of the R-CSM algorithm to the actual problem with data on the textile production of TNG, the production time is reduced from 12.4% to 27%. These results also show that the greater the difference between the skill levels of workers, the more efficient the R-CSM algorithm.Figure6 shows the effectiveness of algorithm R-CSM when it is applied to solve the MS-RCPSP and the Real-RCPSP on the textile dataset of TNG textile company.Figure 6
R-CSM to solve MS-RCPSP and Real-RCPSP.


## 7. Conclusion

This article aims to announce and survey Real-RCPSP, a new combinatorial optimization problem that appears in many fields such as Edge Computing, industrial production, and IoT systems. The new problem is stated, and then a new algorithm named R-CSM is proposed. Inspired by the Cuckoo Search strategy, the proposed algorithm has been upgraded by using function Reallocate; thus it achieved high performance.The experimental results show that the proposed algorithm R-CSM is better than the previous algorithms such as GreedyDO and GA at 21%–85% and 6%–33%, respectively. At the same time, the proposed algorithm converged to the optimal solution faster than previous approaches.In the near future, we are going to continue researching on Real-RCPSP in order to improve the solution quality and the speed of the convergence. Multifactorial optimization seems to be one of the promising approaches to this problem.



---

*Source: 8897710-2020-10-14.xml*