# DRSCRO: A Metaheuristic Algorithm for Task Scheduling on Heterogeneous Systems

Authors: Yuyi Jiang; Zhiqing Shao; Yi Guo; Huanhuan Zhang; Kun Niu
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

An efficient DAG task scheduling is crucial for leveraging the performance potential of a heterogeneous system and finding a schedule that minimizes themakespan (i.e., the total execution time) of a DAG is known to be NP-complete. A recently proposed metaheuristic method, Chemical Reaction Optimization (CRO), demonstrates its capability for solving NP-complete optimization problems. This paper develops an algorithm named Double-Reaction-Structured Chemical Reaction Optimization (DRSCRO) for DAG scheduling on heterogeneous systems, which modifies the conventional CRO framework and incorporates CRO with the variable neighborhood search (VNS) method. DRSCRO has two reaction phases for super molecule selection and global optimization, respectively. In the molecule selection phase, the CRO as a metaheuristic algorithm is adopted to obtain a super molecule for accelerating convergence. For promoting the intensification capability, in the global optimization phase, the VNS algorithm with a new processor selection model is used as the initialization under the consideration of scheduling order and processor assignment, and the load balance neighborhood structure of VNS is also utilized in the ineffective reaction operator. The experimental results verify the effectiveness and efficiency of DRSCRO in terms ofmakespan and convergence rate.


---

## Body

## 1. Introduction

A large application can be decomposed into several smaller models (i.e., tasks) processed in parallel on heterogeneous computing systems. An efficient task scheduling is crucial for leveraging the performance potential of a heterogeneous system. The problem of the task scheduling on heterogeneous system can be stated as assigning the processors to the tasks for minimizing themakespan (i.e., the total execution time). As one task is required only after all of its predecessors are executed, these tasks with precedence constraints can be modeled as directed acyclic graphs (DAGs), where the nodes and the directed edges represent the tasks and the communications between the tasks, respectively. Finding a schedule that minimizes the execution time of a parallel program is known to be NP-complete [1]. Therefore, two scheduling strategies, heuristic and metaheuristic, are developed for searching a suboptimal solution with lower execution time.Heuristic scheduling strategies focus on identifying a solution by exploiting the heuristics, an important class of algorithms based on which is list scheduling [2–12], such as heterogeneous earliest finish time (HEFT) [3]. List scheduling consists of two basic phases, constructing a scheduling list of tasks order by priority of each task and mapping each task to a processor in priority order according to greedy approach (i.e., a task with the highest-priority is assigned to a processor that allows the earliest finish time). The performance of heuristic-based algorithms relied on the effectiveness of the heuristics in a tremendous manner.Metaheuristic scheduling strategies such as Ant Colony Optimization (ACO) [13], Genetic Algorithms (GA) [14–21], Tabu Search (TS) [22, 23], and Simulated Annealing (SA) [24] search the solution spaces in a direct manner and produce consistent and high quality results on the wide range problems while, in comparison with heuristic-based algorithms, these strategies always cost much more time. The Chemical Reaction Optimization (CRO) is a new metaheuristic method and has shown its efficiency in solving NP-complete problem [25–29]. There are only two CRO-based algorithms [27, 30] for DAG scheduling on heterogeneous system so far according to our knowledge. These two algorithms both focused on the DAG scheduling with the objective of minimizing themakespan. However, as metaheuristic scheduling strategies, CRO-based algorithms for DAG scheduling still have very high time cost and the convergence rates of them also need to be improved. In [30], the concept of super molecule is applied for accelerating convergence and the super molecule is selected by heuristic scheduling strategies. However, the performance of this kind of super molecule selection method is affected by the range of problems.This paper proposes an algorithm, Double-Reaction-Structured CRO (DRSCRO), for DAG task scheduling on heterogeneous systems to aim at obtaining schedules with better quality. In this paper, the conventional CRO framework scheme is modified and two reaction phases, one for super molecule selection and another for global optimization, are developed in DRSCRO. CRO as a metaheuristic algorithm is utilized in the molecule selection phase to obtain a super molecule [31] for better convergence rate. And the variable neighborhood search (VNS) algorithm [32] method with a new processor selection model, as well as its neighborhood structure, is also utilized to promote the intensification capability in the global optimization phase.There are three major contributions of this work:(1)
Developing DRSCRO by modifying the conventional CRO framework and utilizing a metaheuristic method to obtain a super molecule for accelerating convergence.
(2)
Utilizing the VNS [32] algorithm with a new processor selection model as the global optimization phase initialization, which takes into account the optimization of the scheduling order and processor assignment, and applying one of its neighborhood structures in the reaction operator to promote the intensification capability of DRSCRO.
(3)
Conducting simulation experiments to prove the efficiency and effectiveness of DRSCRO in terms ofmakespan and convergence rate.The next section introduces relevant research works on the DAG scheduling problem on heterogeneous systems. Section3 describes the models of the studied problem as formal statement. Section 4 presents the design of the proposed DRSCRO for DAG scheduling. In Section 5, the simulation performance of DRSCRO is analyzed and compared with some existing scheme algorithms. Section 6 draws the conclusions of this paper and the suggestions for future research.


## 2. Literature Review

The DAG scheduling problem, which has been proven to be NP-hard in general [1], can be formulated as the search for an optimal solution to the assignment of the tasks in DAG onto a set of processors, to minimize the total scheduling length (i.e.,makespan). There are two main categories, heuristic (deterministic) and metaheuristic (nondeterministic), of the various scheduling algorithms proposed over the last decade. As metaheuristic methods, CRO-based algorithms for DAG scheduling on heterogeneous systems are based on Chemical Reaction Optimization (CRO) algorithm, which was proposed very recently and has shown its power to deal with NP-complete problems.


### 2.1. Heuristic and Metaheuristic Methods

The heuristic methods are on the basis of the heuristics which are extracted from intuitions, and the most important class of them is list scheduling algorithms [2–12]. The HEFT algorithm, which was proposed by Topcuoglu et al. [3], utilizes the information of execution cost on average of each task as an upward-ranking heuristic to calculate the task priority. At each step of HEFT, the task with the highest value of upward rank is selected and mapped to the processor with a greedy approach (i.e., the assigned processor minimizes the earliest finish time of the selected task). Experimental results prove that HEFT obtains better performance on schedule quality and computational cost than the other list scheduling algorithms. The performance of heuristic-based algorithms heavily relied on the effectiveness of the heuristics. The higher complexity DAG scheduling problems have, the harder greedy heuristics produce consistent results on a wide range of problems. In particular, GA has been widely used to evolve solutions for many task scheduling problems as the most representative metaheuristic method [21]. Different from heuristic-based algorithms, the metaheuristic methods use a guided-random-search-based process for solution searching. They typically require sufficient sampling of candidate solutions in the search space and have shown robust performance on a variety of scheduling problems. For solving DAG scheduling problem successfully, many metaheuristic algorithms have been utilized such as GA [14–21], ACO [13], SA [24], TS [22, 23], CRO [27, 30], VNS [21], and energy-efficient stochastic [33].According to No-Free-Lunch Theorem [34], all well-designed metaheuristic methods have the same performance on searching for optimal solutions when averaged over all possible fitness functions. In comparison with the heuristic methods, the metaheuristic methods, which always have much higher computational cost, can obtain better performance in terms of schedule quality, because the metaheuristic methods can search a wider area of the solution space with the guided-random-search-based processes for solution searching, while the search of the heuristic-based algorithms are narrowed down to a very smaller portion by means of the heuristics.


### 2.2. CRO-Based Algorithms for DAG Scheduling on Heterogeneous Systems

CRO was proposed by Lam and Li very recently [25], and, as far as we know, as metaheuristic methods, Double Molecular Structure-Based Chemical Reaction Optimization (DMSCRO) [27] and Tuple-Based Chemical Reaction Optimization (TMSCRO) [30] are the only two CRO-based algorithms for DAG scheduling on heterogeneous systems. CRO-based algorithms mimic the chemical reaction process, which accords with energy conservation, in a closed container. The molecules with two kinds of energy, potential energy (PE) and kinetic energy (KE), in CRO-based algorithms are the solutions to DAG scheduling problem. The PE value of a molecule is calculated by fitness function, which is equal to the objective value,makespan, of the corresponding solution. And KE is for helping the molecule escape from local optimums and its value is nonnegative. A buffer is also used in CRO-based algorithms for energy interchange and conservation. Moreover, to find the solution with the global minimalmakespan, four types of elementary chemical reactions, on-wall ineffective collision, decomposition, intermolecular ineffective collision, and synthesis, are applied for the intensification and the diversification searches. The typical execution flow of CRO framework adopted in DMSCRO and TMSCRO is as proposed in [25] and the parameters used in CRO are presented in Table 1.Table 1
Parameters used in CRO.
Parameters
Definition
PE
Current potential energy of a molecule
KE
Current kinetic energy of a molecule
InitialKE
Initial kinetic energy of a molecule
θ
Threshold value guides the choice of on-wall collision or decomposition
ϑ
Threshold value guides the choice of intermolecule collision or synthesis
Buffer
Initial energy in the central energy buffer
KELossRate
Loss rate of kinetic energy
MoleColl
Threshold value to determine whether to perform a unimolecule reaction or an intermolecule reaction
PopSize
Size of the molecules
iters
Number of iterationsAs metaheuristic methods, DMSCRO and TMSCRO have better performance in terms of schedule quality than heuristic methods and the reason is as presented in the last paragraph of Section2.1. The experimental results in [27, 30] prove that both of DMSCRO and TMSCRO outperform GA. DMSCRO is the first algorithm by applying CRO proposed by Lam and Li in [25] to solve the DAG scheduling problem, and it enjoys the advantages of both GA and SA. On the one hand, the intermolecular collision and on-wall collision designed in DMSCRO have similar effect to the crossover operation and the mutation operation in GA, respectively. On the other hand, the energy conservation requirement in DMSCRO is able to guide the searching of the optimal solution similarly to the way the Metropolis Algorithm of SA guides the evolution of the solutions in SA. Two additional operations, decomposition and synthesis, give DMSCRO more opportunities to jump out of the local optimum and explore the wider areas in the solution space. This benefit enables DMSCRO to find good solutions faster than GA, which has been widely used to evolve solutions for many task scheduling problems. DMSCRO are not compared with SA in [27, 30], because the underlying principles and philosophies between DMSCRO and SA differ a lot [27]. Typically, metaheuristic algorithms like CRO-based algorithm of GA-based algorithms operating on a population of solutions are able to find good solutions faster than that operating on a single solution like SA-based algorithms. Comparing with DMSCRO, TMSCRO applies constrained earliest finish time algorithm to data pretreatment to take the advantage of the super molecule and constrained critical paths [35], which is, as heuristic information, for accelerating convergence. Moreover, the molecule structure and elementary reaction operators design in TMSCRO are more reasonable than those in DMSCRO on intensification and diversification of searching the solution space.However, for solving the NP problem of DAG scheduling on heterogeneous systems, CRO-based algorithms, TMSCRO and DMSCRO, still have very large time expenditure as metaheuristic scheduling strategies; therefore, the searching capabilities and convergence rates of them need to be improved. There are three deficiencies of TMSCRO and DMSCRO. First, in [30], the concept of super molecule is applied for accelerating convergence and the super molecule is selected by heuristic scheduling strategies, but the performance of this kind of super molecule selection method is affected by the range of problems. Second, in both TMSCRO and DMSCRO, the initial molecules, which are very important for the whole searching process, are randomly created, and the uncertainty of this kind of initialization undermines the searching capabilities of TMSCRO and DMSCRO. Moreover, the intensification capabilities of CRO-based algorithms for DAG scheduling also need to be improved, to obtain better performances of the average results when the iteration stopping criterions are satisfied.Therefore, this paper proposes an algorithm, Double-Reaction-Structured CRO (DRSCRO), for DAG task scheduling on heterogeneous systems to aim at obtaining schedules with better quality. In this paper, the conventional CRO framework scheme is modified and two reaction phases, one for super molecule selection and another for global optimization, are developed in DRSCRO. CRO as a metaheuristic algorithm is utilized in the molecule selection phase to obtain a super molecule [31] for better convergence rate. Moreover, in the global optimization phase, the variable neighborhood search (VNS) algorithm method [21, 32, 36], which is an effective metaheuristic with the utilizations of neighborhood structures and a local search to change the neighborhood systematically, is used to optimize the initial molecule, and one of its neighborhood structures is also adopted in the reaction operator to promote the intensification capability. And there is a new model proposed for processor selection utilized in the neighborhood structures of the VNS algorithm for better effectiveness.Moreover, in [21], VNS was incorporated with GA for DAG scheduling, but the task priority was unchangeable in the VNS algorithm in [21], which reduces the efficiency of VNS to obtain a better solution. So, different from [21], to promote the intensification capability of the whole algorithm, the VNS in DRSCRO is modified under the consideration of the optimization of the scheduling order and the processor assignment both.


## 2.1. Heuristic and Metaheuristic Methods

The heuristic methods are on the basis of the heuristics which are extracted from intuitions, and the most important class of them is list scheduling algorithms [2–12]. The HEFT algorithm, which was proposed by Topcuoglu et al. [3], utilizes the information of execution cost on average of each task as an upward-ranking heuristic to calculate the task priority. At each step of HEFT, the task with the highest value of upward rank is selected and mapped to the processor with a greedy approach (i.e., the assigned processor minimizes the earliest finish time of the selected task). Experimental results prove that HEFT obtains better performance on schedule quality and computational cost than the other list scheduling algorithms. The performance of heuristic-based algorithms heavily relied on the effectiveness of the heuristics. The higher complexity DAG scheduling problems have, the harder greedy heuristics produce consistent results on a wide range of problems. In particular, GA has been widely used to evolve solutions for many task scheduling problems as the most representative metaheuristic method [21]. Different from heuristic-based algorithms, the metaheuristic methods use a guided-random-search-based process for solution searching. They typically require sufficient sampling of candidate solutions in the search space and have shown robust performance on a variety of scheduling problems. For solving DAG scheduling problem successfully, many metaheuristic algorithms have been utilized such as GA [14–21], ACO [13], SA [24], TS [22, 23], CRO [27, 30], VNS [21], and energy-efficient stochastic [33].According to No-Free-Lunch Theorem [34], all well-designed metaheuristic methods have the same performance on searching for optimal solutions when averaged over all possible fitness functions. In comparison with the heuristic methods, the metaheuristic methods, which always have much higher computational cost, can obtain better performance in terms of schedule quality, because the metaheuristic methods can search a wider area of the solution space with the guided-random-search-based processes for solution searching, while the search of the heuristic-based algorithms are narrowed down to a very smaller portion by means of the heuristics.


## 2.2. CRO-Based Algorithms for DAG Scheduling on Heterogeneous Systems

CRO was proposed by Lam and Li very recently [25], and, as far as we know, as metaheuristic methods, Double Molecular Structure-Based Chemical Reaction Optimization (DMSCRO) [27] and Tuple-Based Chemical Reaction Optimization (TMSCRO) [30] are the only two CRO-based algorithms for DAG scheduling on heterogeneous systems. CRO-based algorithms mimic the chemical reaction process, which accords with energy conservation, in a closed container. The molecules with two kinds of energy, potential energy (PE) and kinetic energy (KE), in CRO-based algorithms are the solutions to DAG scheduling problem. The PE value of a molecule is calculated by fitness function, which is equal to the objective value,makespan, of the corresponding solution. And KE is for helping the molecule escape from local optimums and its value is nonnegative. A buffer is also used in CRO-based algorithms for energy interchange and conservation. Moreover, to find the solution with the global minimalmakespan, four types of elementary chemical reactions, on-wall ineffective collision, decomposition, intermolecular ineffective collision, and synthesis, are applied for the intensification and the diversification searches. The typical execution flow of CRO framework adopted in DMSCRO and TMSCRO is as proposed in [25] and the parameters used in CRO are presented in Table 1.Table 1
Parameters used in CRO.
Parameters
Definition
PE
Current potential energy of a molecule
KE
Current kinetic energy of a molecule
InitialKE
Initial kinetic energy of a molecule
θ
Threshold value guides the choice of on-wall collision or decomposition
ϑ
Threshold value guides the choice of intermolecule collision or synthesis
Buffer
Initial energy in the central energy buffer
KELossRate
Loss rate of kinetic energy
MoleColl
Threshold value to determine whether to perform a unimolecule reaction or an intermolecule reaction
PopSize
Size of the molecules
iters
Number of iterationsAs metaheuristic methods, DMSCRO and TMSCRO have better performance in terms of schedule quality than heuristic methods and the reason is as presented in the last paragraph of Section2.1. The experimental results in [27, 30] prove that both of DMSCRO and TMSCRO outperform GA. DMSCRO is the first algorithm by applying CRO proposed by Lam and Li in [25] to solve the DAG scheduling problem, and it enjoys the advantages of both GA and SA. On the one hand, the intermolecular collision and on-wall collision designed in DMSCRO have similar effect to the crossover operation and the mutation operation in GA, respectively. On the other hand, the energy conservation requirement in DMSCRO is able to guide the searching of the optimal solution similarly to the way the Metropolis Algorithm of SA guides the evolution of the solutions in SA. Two additional operations, decomposition and synthesis, give DMSCRO more opportunities to jump out of the local optimum and explore the wider areas in the solution space. This benefit enables DMSCRO to find good solutions faster than GA, which has been widely used to evolve solutions for many task scheduling problems. DMSCRO are not compared with SA in [27, 30], because the underlying principles and philosophies between DMSCRO and SA differ a lot [27]. Typically, metaheuristic algorithms like CRO-based algorithm of GA-based algorithms operating on a population of solutions are able to find good solutions faster than that operating on a single solution like SA-based algorithms. Comparing with DMSCRO, TMSCRO applies constrained earliest finish time algorithm to data pretreatment to take the advantage of the super molecule and constrained critical paths [35], which is, as heuristic information, for accelerating convergence. Moreover, the molecule structure and elementary reaction operators design in TMSCRO are more reasonable than those in DMSCRO on intensification and diversification of searching the solution space.However, for solving the NP problem of DAG scheduling on heterogeneous systems, CRO-based algorithms, TMSCRO and DMSCRO, still have very large time expenditure as metaheuristic scheduling strategies; therefore, the searching capabilities and convergence rates of them need to be improved. There are three deficiencies of TMSCRO and DMSCRO. First, in [30], the concept of super molecule is applied for accelerating convergence and the super molecule is selected by heuristic scheduling strategies, but the performance of this kind of super molecule selection method is affected by the range of problems. Second, in both TMSCRO and DMSCRO, the initial molecules, which are very important for the whole searching process, are randomly created, and the uncertainty of this kind of initialization undermines the searching capabilities of TMSCRO and DMSCRO. Moreover, the intensification capabilities of CRO-based algorithms for DAG scheduling also need to be improved, to obtain better performances of the average results when the iteration stopping criterions are satisfied.Therefore, this paper proposes an algorithm, Double-Reaction-Structured CRO (DRSCRO), for DAG task scheduling on heterogeneous systems to aim at obtaining schedules with better quality. In this paper, the conventional CRO framework scheme is modified and two reaction phases, one for super molecule selection and another for global optimization, are developed in DRSCRO. CRO as a metaheuristic algorithm is utilized in the molecule selection phase to obtain a super molecule [31] for better convergence rate. Moreover, in the global optimization phase, the variable neighborhood search (VNS) algorithm method [21, 32, 36], which is an effective metaheuristic with the utilizations of neighborhood structures and a local search to change the neighborhood systematically, is used to optimize the initial molecule, and one of its neighborhood structures is also adopted in the reaction operator to promote the intensification capability. And there is a new model proposed for processor selection utilized in the neighborhood structures of the VNS algorithm for better effectiveness.Moreover, in [21], VNS was incorporated with GA for DAG scheduling, but the task priority was unchangeable in the VNS algorithm in [21], which reduces the efficiency of VNS to obtain a better solution. So, different from [21], to promote the intensification capability of the whole algorithm, the VNS in DRSCRO is modified under the consideration of the optimization of the scheduling order and the processor assignment both.


## 3. Problem Formulation

The DAG scheduling problem is typically with two inputs: a heterogeneous system for task computing in parallel and a parallel program of application (i.e., DAG). In this paper, the heterogeneous system is assumed as a static computing system model presented byP
=
{
p
i
∣
i
=
1
,
2
,
3
,
…
,
P
}, which is a fully connected network of processors. The heterogeneity level in this paper is formulated as (
1
+
h
l
%
)
/
(
1
-
h
l
%
), where the parameter h
l
∈
(
0,1
). In this paper, E
c
C
o
s
t
p
j
(
v
i
) represents the computation cost of a task v
i mapped to the processor p
j and the value of each E
c
C
o
s
t
p
j
(
v
i
) is randomly chosen within the scope of [
1
-
h
l
%
,
1
+
h
l
%
].In general,D
A
G
=
(
V
,
E
) consists of a task (node) set V and an edge set E. E
c
C
o
s
t
p
j
(
v
i
) is as defined in the first paragraph of this section, and the same processor executes a task in the DAG without preemption. The constraint between tasks v
i and v
j is denoted as the edge e
i
,
j
(
e
i
,
j
∈
E
), which means that the execution of task v
j only after the execution result of task v
i has been transmitted to task v
j. Each edge e
i
,
j has a nonnegative weight c
o
m
m
(
v
i
,
v
j
) denoting the communication cost between v
i and v
j. Each task in a DAG can only be executed on one processor and the communication can be performed simultaneously by the processors. In addition, when two communicating tasks are mapped to the same processor, the communication cost of them is zero. Predecessor (v
i) represents the set of the predecessors of v
i, while successor (v
i) represents the set of the successors of v
i. The task with no predecessor is denoted as v
e
n
t
r
y while the task with no successor is denoted as v
e
x
i
t.Consider that there is a DAG withV tasks to be mapped to a heterogeneous system with P processors. Assuming the highest-priority ready task v
i on the processor p
j, the earliest start time of v
i, T
E
S
T
i
m
e
(
v
i
,
p
j
), can be formulated as(1)
T
E
S
T
i
m
e
v
i
,
p
j
=
max
⁡
T
a
v
a
i
l
p
j
,
T
r
e
a
d
y
v
i
,
p
j
,where T
a
v
a
i
l
(
p
j
) can be defined as (2). T
a
v
a
i
l
(
p
j
) is the time when processor p
j is available to the execution of the task v
i:(2)
T
a
v
a
i
l
p
j
=
max
v
k
∈
exec
p
j
⁡
T
A
F
T
i
m
e
v
k
,where e
x
e
c
(
p
j
) represents all the tasks which have already been scheduled on the processor p
j and T
A
F
T
i
m
e
(
v
k
) denotes the actual finish time when the task v
k finishes its execution. T
r
e
a
d
y
(
v
i
,
p
j
) in (1) represents the time when all the data needed for the process of v
k have been transmitted to p
j, which is formulated as(3)
T
r
e
a
d
y
v
i
,
p
j
=
max
v
k
∈
predecessor
v
i
⁡
T
A
F
T
i
m
e
v
k
+
c
o
m
m
v
k
,
v
i
,where T
A
F
T
i
m
e
v
k has the same definition in (2) and predecessor (v
i) denotes the set of all the immediate predecessors of task v
i. c
o
m
m
(
v
k
,
v
i
) is 0 if the task v
k and task v
i are mapped to the same processor p
j.If taskv
i is mapped to the processor p
j with nonpreemptive processing approach, the earliest finish time of task v
i, T
E
F
T
i
m
e
(
v
i
,
p
j
), is formulated as(4)
T
E
F
T
i
m
e
v
i
,
p
j
=
T
E
S
T
i
m
e
v
i
,
p
j
+
E
c
C
o
s
t
p
j
v
i
.After the taskv
i is executed by the processor p
j, T
E
F
T
i
m
e
(
v
i
,
p
j
) is assigned to T
A
F
T
i
m
e
(
v
i
). Themakespan of the entire parallel program is equivalent to the actual finish time of exit task v
e
x
i
t:(5)
m
a
k
e
s
p
a
n
=
max
v
i
∈
V
⁡
T
A
F
T
i
m
e
v
i
=
T
A
F
T
i
m
e
v
e
x
i
t
.The computation of the communication-to-computation ratio (CCR) can be formulated as in(6)
C
C
R
=
∑
e
i
,
j
∈
E
c
o
m
m
v
i
,
v
j
∑
v
i
∈
V
W
v
i
¯
,where W
(
v
i
)
¯ is the average computation cost of task v
i and it can be calculated as follows:(7)
W
v
i
¯
=
∑
k
=
1
P
E
c
C
o
s
t
p
k
v
i
P
.A simple four-task DAG and a heterogeneous computation system with three processors are shown in Figures1(a) and 1(b), respectively. The definition of the notations can be found in Table 2.Table 2
Definitions of notations.
Notations
Definitions
DAG = (V, E)
Input directed acyclic graph withV nodes representing tasks and E edges representing constrained relations among the tasks
P
=
p
i
∣
i
=
1,2
,
3
,
…
,
P
Set of heterogeneous processors in target system
EcCostp
j(v
i)
Execution cost of taskv
i using processor p
j
comm(v
k, v
i)
Communication cost from taskv
k to task v
i
T
ESTime(v
i, p
j)
The earliest start time of taskv
i which is mapped to processor p
j
T
EFTime(v
i, p
j)
The earliest finish time of taskv
i which is mapped to processor p
j
T
avail(p
j)
The time when processorp
j is available
T
ready(v
i, p
j)
The time when all the data needed for the process ofv
i have been transmitted to p
j
T
AFTime(v
k)
Actual finish time when taskv
k finishes its execution
predecessor(v
i)
Set of the predecessors of taskv
i
successor(v
i)
Set of the successors of taskv
i
exec(p
j)
Set of the tasks which have already been scheduled on the processorp
j
W
(
v
)
-
Average computation cost of taskv
CCR
Communication-to-computation ratio
hl
Parameter for adjusting the heterogeneity level in a heterogeneous systemFigure 1
(a) DAG model. (b) Heterogeneous computation system model.
(a)
(b)


## 4. Design of DRSCRO

DRSCRO imitates the molecular interactions in chemical reactions based on the concepts of atoms, molecule, molecular structure, and energy of a molecule. In DRSCRO, a molecule corresponds to a scheduling solution in DAG scheduling, with a unique molecular structure representing the atom positions in a molecule. We utilize the molecular structure of TMSCRO in our work, under the consideration of its capability to represent the constrained relationship between the tasks in a molecule (solution). In addition, the energy of each molecule corresponds to the fitness value of a solution. The molecular interactions try to reconstruct more stable molecular structure with lower energy. There are four kinds of basic chemical reactions, on-wall ineffective collision, decomposition, intermolecular ineffective collision, and synthesis, for molecular interactions in DRSCRO, and each kind of reaction contains two subclasses. These two subclasses of reaction operators are applied in the phase of super molecule selection and the phase of global optimization, respectively.


### 4.1. Framework of DRSCRO

The framework of DRSCRO to schedule a DAG job is as shown in Figure2 with two basic phases, the phase of super molecule selection and the phase of global optimization. In each phase, DRSCRO first initializes the process of a phase, and then the phase process enters iteration.Figure 2
Framework of DRSCRO.In this framework, DRSCRO first executes the phase of super molecule selection to obtain the super molecule (i.e., just the molecule with the global minimalmakespan),  SMole, with other output molecules as the input of the next global optimization phase for the first time (the input of VNS algorithm is the population with  SMole after each iteration in the global optimization phase in the other times), and then DRSCRO performs the phase of global optimization to approach the global optimum solution. The VNS algorithm with a new model for processor selection is adopted as the initialization of the global optimization phase, and it is also utilized as a local search process to promote the intensification capability of DRSCRO. There are four kinds of elementary chemical reaction in DRSCRO, on-wall collision, decomposition, intermolecular collision, and synthesis. And each kind of reaction contains two types of operators which are, respectively, utilized in two phases of DRSCRO. In each iteration, one of the elementary chemical reaction operators is performed to generate new molecules and the PEs of the newly generated molecules (i.e., the fitness function values of the newly generated molecules) will be calculated. In addition,  SMole will be tracked and only participates in on-wall ineffective collision and intermolecular ineffective collision in the global optimization phase to explore as much as possible the solution space in its neighborhoods and the main purpose is to prevent the super molecule from changing dramatically. The iteration of each phase repeats until the stopping criteria (or next phase criteria) are met, and  SMole and its fitness function value are just the final solution andmakespan (i.e., global min point), respectively. In the implementations of the experiments in this paper, the next phase criteria and the stop criteria of DRSCRO are set as when there is nomakespan improvement after 10000 consecutive iterations in the search loop.


### 4.2. Molecular Structure and Fitness Function

This subsection presents the encoding of scheduling solutions (i.e., the molecular structure) and the statement of the fitness function in DRSCRO.


#### 4.2.1. Molecular Structure

In this paper, an atom with three elements can be denoted as a tuple(
v
i
,
f
i
,
p
i
) and the molecular structure M with an array of tuples can be formulated as in (8) to represent a solution to the DAG scheduling problem. The order of the tuples in M represents the priority of each DAG task v
i with the allocated processor p
i, and V
=
(
v
1
,
v
2
,
…
,
v
V
) is a topological sequence of DAG, which is with the hypothetical entry task (with no predecessors) v
1 and exit task (with no successors) v
V, respectively, representing the beginning and end of execution. Moreover, if tuple A is before tuple B and v
A is the predecessor of v
B in DAG, the second integer of tuple  B, f
B, will be 1, and vice versa(8)
m
=
v
1
,
f
1
,
p
1
,
v
2
,
f
2
,
p
2
,
…
,
v
V
,
f
V
,
p
V
.


#### 4.2.2. Fitness Function

Potential energy (PE) is defined as the fitness function value of the corresponding solution represented byS. The overall schedule length of the entire DAG, namely,makespan, is the largest finish time among all tasks, which is equivalent to the actual finish time of the exit node in DAG. In this paper, the goal of DAG scheduling problem by DRSCRO is to obtain the scheduling that minimizesmakespan and ensure that the precedence of the tasks is not violated. Hence, each fitness function value is defined as (9)
F
i
t
m
=
P
E
m
=
m
a
k
e
s
p
a
n
.Algorithm1 presents how to calculate the value of the optimization fitness function F
i
t
(
m
).Algorithm 1:Fit(m) calculating the fitness value of a molecule and the processor allocation optimization.
(1)makespan = 0;
(2)for each node v
k in m = ((v
1, f
1, p
1), (v
2, f
2, p
2
)
,
…
,
(
v
V, f
V, p
V)) do
(3)  calculate the actual finish time ofv
k (i.e. T
AFTime
(
v
k
))
(4)if  m
a
k
e
s
p
a
n
<
T
AFTime
(
v
k
)
(5)   updatemakespan
(6)makespan = T
AFTime
(
v
k
)
(7)end if
(8)end for
(9)return
makespan;


### 4.3. Super Molecule Selection Phase

#### 4.3.1. Initialization

There are two kinds of initial molecule generator, one used in the phase of super molecule selection and the other used in the phase of global optimization, to generate the initial solutions for DRSCRO to manipulate. The tuples of the first moleculem used in the initialization of the phase of super molecule selection are ascendingly ordered by the upward rank value [27] of their v
i, and element three p
i of each tuple is generated by a random perturbation. The upward rank value can be calculated by(10)
R
a
n
k
v
i
=
W
v
i
¯
+
max
v
j
∈
successor
v
i
⁡
c
o
m
m
v
i
,
v
j
+
R
a
n
k
v
j
.A detailed description of the initial molecule generator of the super molecule selection phase is given in Algorithm2. For the first input molecule  m, p
x in each tuple in m is set as p
1.Algorithm 2:InitMoleSMS(m) generating the initial population for the super molecule selection phase.
(1)M
o
l
e
N = 1;
(2)while  MoleN  ≤  PopSize do
(3)for each p
i in molecule m to randomly change;
(4)   changep
i randomly
(5)end for
(6)  generate a new moleculem
′;
(7)MoleN = MoleN + 1;
(8)end while


#### 4.3.2. Elementary Chemical Reaction Operators

In DRSCRO, the operators for super molecule selection just randomly changep
i of each tuple in a molecule as the intensification searches or the diversification searches [25] to optimize the processor mapping of a solution. Figures 3, 4, 5, and 6, respectively, show the examples of four operators for super molecule selection, in which the molecules correspond to the DAG as shown in Figure 1(a). And the white blocks in these examples denote the tuples that do not change during the reaction operation calculations.Figure 3
Example of OnWallSMS.Figure 4
Example of DecompSMS.Figure 5
Example of IntermoleSMS.Figure 6
Example of SynthSMS.As shown in Figure3, the operator, OnWallSMS, is used to generate a new molecule m
′ from a given reaction molecule m for optimization. OnWallSMS works as follows: (1) The operator randomly chooses a tuple (v
i, f
i, p
i) in  m. (2) The operator changes p
i randomly. In the end, the operator generates a new molecule m
′ from m as an intensification search.As shown in Figure4, the operator, DecompSMS, is used to generate new molecules m
′
1 and m
′
2 from a given reaction molecule m. DecompSMS works as follows: (1) The operator generates two molecules m
′
1
=
m and m
′
2
=
m. (2) The operator keeps the tuples in m
′
1, which is at the odd position in  m and then changes the remaining p
x’s of tuples in m
′
1, randomly. (3) The operator retains the tuples in m
′
2, which is at the even position in  m, and then changes the remaining p
x’s of tuples in m
′
2 randomly. In the end, the operator generates two new molecules m
′
1 and m
′
2 from m as a diversification search.As shown in Figure5, the operator, IntermoleSMS, is used to generate new molecules m
′
1 and m
′
2 from given molecules  m
1 and  m
2. This operator first uses the steps in OnWallSMS to generate m
′
1 from m
1, and then the operator generates the other new molecule m
′
2 from m
2 in the similar fashion. In the end, the operator generates two new molecules m
′
1 and m
′
2 from  m
1 and  m
2 as an intensification search.As shown in Figure6, the operator, SynthSMS, is used to generate a new molecule m
′ from given molecules m
1 and m
2. SynthSMS works as follows: The operator keeps the tuples in m
′, which is at the same position in m
1 and m
2 with the same p
x’s, and then changes the remaining p
y’s in m
′, randomly. As a result, the operator generates m
′ from m
1 and m
2 as a diversification search.


### 4.4. Global Optimization Phase

#### 4.4.1. Initialization

VNS is utilized by our proposed algorithm as the initialization of the global optimization phase and it is also as a local search process to promote the intensification capability of DRSCRO during the running of the whole algorithm.Algorithms3 and 4, respectively, present the subset generator of the phase output and the main steps of the whole VNS algorithm (i.e., the initialization of the global optimization phase). In DRSCRO, the VNS algorithm only processes the subset of the population with the super molecule,  SMole, after each iteration in the global optimization phase (the output of super molecule selection phase is the input of VNS for the first time). As presented in Algorithm 3, if thepop_set (i.e., the set of population) is the output of the super molecule selection phase, the tuple orders and p
is of its elements will be adjusted.pop_subset is the subset of population andpop_subset_num is the number of the elements inpop_subset, which is set asPopSize × 50% in this paper.Algorithm 3:InitVNS(pop_set, pop_subset_num) initializing the subset of the population pop_set for undergoing the VNS algorithm.
(1)tempSet = pop_set;
(2)pop_subset = ∅;
(3)if  pop_set is the input of the VNS algorithm for the first time (i.e. the output of the super molecule selection phase)
(4)for each t
e
m
p
S in tempSet except S
M
o
l
e
(5)   choose a tuple (v
i, f
i, p
i) in t
e
m
p
S, where f
i
=
0, randomly;
(6)   generate a random numberr
n
d
∈
(
0,1
);
(7)if  rnd≥ 0.5
(8)    find the first predecessorv
j = Pred(v
i) from v
i to the begin in molecule t
e
m
p
S;
(9)    interchanged position of (v
i, f
i, p
i) and (v
j
+
1, f
j
+
1, p
j
+
1) in molecule t
e
m
p
S;
(10)update f
i, f
i
+
1 and f
j
+
1 as defined in the last paragraph of Section 4.2.1.
(11) end if
(12)
for each p
i in molecule t
e
m
p
S to randomly change;
(13)  change p
i randomly
(14) end for
(15) if Fit(t
e
m
p
S) < Fit(S
M
o
l
e)
(16)  S
M
o
l
e = t
e
m
p
S;
(17) end if
(18)
end for
(19)end if
(20)pop_subset adds S
M
o
l
e;
(21)pop_subset adds the molecules in tempSet with tuple order different from S
M
o
l
e;
(22)while  p
o
p
_
s
u
b
s
e
t
≠
p
o
p
_
s
u
b
s
e
t
_
n
u
m  do
(23)pop_subset add a molecules in pop_set which do not exist in pop_subset;
(24)end whileAlgorithm 4:InitMoleGOVNS(pop_set) generating the initial population of the global optimization phase.
(1)pop_subset = InitVNS(pop_set);
(2) Select the set of neighborhood structuresN
e
i
g
h
d (d = 1,2
,
3
,
…
,
d
max
⁡);
(3)for each individual m in the pop_subset  do
(4)d = 1;
(5)while  d
<
d
max
⁡  do
(6)   Randomly generate a moleculem
1 from the dth neighborhood of m;
(7)   Apply some local search method withm
1 as the initial molecule (the local optimum presented by m
2);
(8)If  m
2 is better than m
(9)m
=
m
2;
(10)
d
=
1;
(11) else
(12)d = d + 1;
(13)
end if
(14)
end while
(15)until the termination condition is satisfied
(16)end for
(17) execute the combination strategy;In Algorithm4, different from the VNS proposed in [21], the task priority was changeable in the VNS algorithm used in DRSCRO, the reason for which is that the unchangeable task priority in the VNS reduces its efficiency to obtain a better solution. Therefore, under the consideration of the optimization of the scheduling order and the processor assignment both, the input molecules of VNS can be with different tuple order (i.e., task priority) as presented in Algorithm 3 in each iteration. d
m
a
x is set to 2 as presented in [37]. As the essential factor of VNS, two neighborhood structures, load balance and communication reduction neighborhood structures, which demonstrate their power in solving DAG scheduling problem on heterogeneous systems as presented in [21], are adopted by the VNS algorithm in DRSCRO for their high efficiency. In this paper, a new model is also proposed for processor selection of these two neighborhood structures. As presented in [21], there are two intuitions used to construct the neighborhood structures. One is that balancing load among various processors usually helps minimizing themakespan, especially when most tasks are allocated to only a few processors; the other is that reducing communication overhead and idle waiting time of processors always results in a more effective schedule, especially given a relatively high unit communication. However, there is a contradiction between these two intuitions, because reducing communication overhead and idle waiting time of processors always means that some processors are with most tasks. So, different from the original ones in [21], we develop a new model for processor selection. Let T
C
l
o
a
d
(
p
i
) be all the task execution cost of processor p
i, and T
C
c
o
m
m
(
p
i
) is the communication cost overhead of processor p
i as defined in [21]. The values of T
C
l
o
a
d
(
p
i
) and T
C
c
o
m
m
(
p
i
) are the tendencies of load balancing and communication reducing, respectively (i.e., the tendency of task reducing or increasing). The greater T
C
l
o
a
d
(
p
i
) is the stronger tendency of reducing tasks on p
i is, and the greater T
C
c
o
m
m
(
p
i
) is the stronger tendency of increasing tasks on p
i is. Therefore, a parameter Tend(p
i) is developed to measure the tendency with the combination of T
C
l
o
a
d
(
p
i
) and T
C
c
o
m
m
(
p
i
) as (11). The neighborhood structure computation processes of load balance and communication reduction are as presented in Algorithms 5 and 6, respectively. The proposed model is under the comprehensive consideration of both intuitions and can make the VNS algorithm more effective than the original one:(11)
T
e
n
d
p
i
=
1
1
+
e
-
T
C
l
o
a
d
p
i
/
T
C
c
o
m
m
p
i
.Algorithm 5:GenNeighborhoodofLoadBalance(ω).
(1)for each processor p
i in the solution ω  do
(2)  Compute Tend(p
i);
(3)end for
(4) Choose the processorp
max
⁡ with the largest Tend(p
max
⁡);
(5) Randomly choose a taskv
random from exec(p
max
⁡);
(6) Randomly choose a processorp
random different from p
max
⁡;
(7) Reallocatev
random to the processor p
random;
(8) Encode and reschedule the changed solutionω
′;
(9)return  ω
′;Algorithm 6:GenNeighborhoodofCommReduction(ω).
(1)for each processor p
i in the solution ω  do
(2)  Compute Tend(p
i);
(3)end for
(4) Choose the processorp
min
⁡ with the smallest Tend(p
min
⁡);
(5) Set the candidate set,cand, empty;
(6)for each task v
i in the set exec(p
min
⁡) do
(7) Compute the set predecessor(v
i);
(8) Update predecessor(v
i) with predecessor(v
i) = predecessor(v
i) − exec(p
min
⁡);
(9)cand = cand + predecessor(v
i);
(10)end for
(11) Randomly choose a taskv
random from cand;
(12) Reallocatev
random to the processor p
min
⁡;
(13) Encode and reschedule the changed solutionω
′;
(14)return  ω
′;The VNS algorithm in DRSCRO utilizes the dual termination criteria. The termination criterion 1 sets the upper bound of the local search iterations to 20, and the termination criterion 2 sets the maximum iteration number without improvement to 3. The VNS algorithm will stop if either criterion is satisfied. To form a new initial population, a combination strategy is utilized for combining the current population and the VNS output after the VNS algorithm outputs the subset of the population. The current population and the VNS output are first merged and sorted by increasingmakespan; then the firstPopSize molecules are selected to generate the new initial population.


#### 4.4.2. Elementary Chemical Reaction Operators

The operators for global optimization not only varyp
i of each tuple but also interchange the positions of the tuples in a molecule as the intensification searches or the diversification searches [25] to optimize the whole solution.On-wall ineffective collision (as an intensification search), decomposition (as a diversification search), and synthesis (as a diversification search) are as presented in [30], and we do not repeat them here to focus on our main work. In [30], the function of the ineffective collision operator is similar to that of the on-wall ineffective collision operator. Therefore, different from [30], a modified ineffective collision operator is proposed in this paper, and it utilized the load balance neighborhood structure used in the VNS mentioned before, to promote the intensification capability of DRSCRO and avoid the function duplication.The operator, IntermoleGO (i.e., the ineffective collision operator), is used to generate new moleculesm
′
1 and m
′
2 from given molecules m
1 and m
2. This operator first uses the steps in OnWallGO to generate m
′
1 from m
1, and then the operator generate the other new molecule m
′
2 from m
2 in the similar fashion. In the end, the operator generates two new molecules m
′
1 and m
′
2 from m
1 and m
2 as an intensification search. The detailed executions are presented in Algorithm 7. Figure 7 shows the example of the IntermoleGO, in which the molecules correspond to the DAG as shown in Figure 1(a).Algorithm 7:IntermoleGO(m
1, m
2).
(1) choose randomly a tuple (v
i, f
i, p
i) in m
1 where f
i = 0;
(2) exchange the positions of (v
i, f
i, p
i) and (v
i
-
1,f
i
-
1, p
i
-
1);
(3) modifyf
i
-
1, f
i and f
i
+
1 in m
1 as defined in the last paragraph of Section 4.2.1;
(4) generate a new moleculem
′
1 = GenLBNeighborhood(m
1);
(5) choose randomly a tuple (v
i, f
i, p
i) in m
2 where f
j = 0;
(6) exchange the positions of (v
i, f
i, p
i) and (v
j
-
1, f
j
-
1, p
j
-
1);
(7) modifyf
j
-
1, f
j and f
j
+
1 in m
2 as defined in the last paragraph of Section 4.2.1;
(8) generate a new moleculem
′
2 = GenLBNeighborhood(m
2);Figure 7
Example of IntermoleGO.


### 4.5. Illustrative Example

Consider the example shown in Figure1(a). Its edges are labeled with the communication costs, whereas the execution costs are shown in Table 3.Table 3
Execution cost of DAG tasks by each processor.
Tasks
p
1
p
2
p
3
v
1
7
8
9
v
2
12
14
16
v
3
14
15
16
v
4
13
3
14Initially, the path (v
1, v
2, v
4, v
3) is found based on the upward rank value of each task in DAG, and the first molecule,  m = ((v
1, 0, p
1), (v
2, 1, p
1), (v
4, 0, p
1), and (v
3, 1, p
1)), can be obtained. Algorithm 2, InitMoleSMS, is then executed to generate the initial population with 10 elements (i.e.,PopSize is set as 10) for super molecule selection phase. The initial population molecules are operated during the iterations in the super molecule selection phase as presented in the framework of DRSCRO in Section 4.1, and the super molecule,  SMole = ((v
1, 0, p
3), (v
2, 1, p
1), (v
4, 0, p
2), and (v
3, 1, p
1)), can be obtained.In the global optimization phase, Algorithm4, InitMoleGOVNS, is then executed to generate (or to update) the initial population after each iteration as presented in Section 4.1. The molecules are operated during the iterations in the global optimization phase as presented in the framework of DRSCRO in Section 4.1, and the global minimalmakespan = 40 is finally obtained, for which the corresponding solution (i.e., molecule) is ((v
1, 0, p
2), (v
4, 1, p
2), (v
2, 0, p
2), and (v
3, 1, p
2)).


### 4.6. Analysis of DRSCRO

As a new metaheuristic strategy, the CRO-based methods for DAG scheduling which is proposed very recently have demonstrated the capability for solving this kind of NP-hard optimization problems. By analyzing the framework, molecular structure, chemical reaction operators, and the operational environment in DRSCRO, it can be shown to some extent that DRSCRO scheme has the advantage of three points in comparison with other CRO-based algorithms for DAG scheduling.First, to some degree, super molecule in DRSCRO is similar toInitS in TMSCRO [30] or the “elite” in GA [31]. However, the “elite” in GA is usually generated from two chromosomes, while super molecule is approached by executing the first phase of DRSCRO. Moreover, in comparison with TMSCRO, DRSCRO uses a metaheuristic strategy (CRO) to get a better super molecule. It is because, as intelligent random-search algorithm, CRO used in the phase of DRSCRO for super molecule selection searches a wider area of the solution space than CEFT applied in TMSCRO, which narrow the search down to a very small portion of the solution space. As a result, a better super molecule may contribute to a better global optimum solution and accelerates convergence. Second, DAG scheduling problem has two complex aspects including task sequence optimization and processor assignment optimization, which lead to a very large and complicated solution space. So, for a better capability of intensification search than other CRO-based algorithms for DAG scheduling on heterogeneous systems, DRSCRO applied VNS algorithm as the initialization of the global optimization phase, which is also as a local search process during the running of DRSCRO, and one of the neighborhood structures of VNS is also utilized in the ineffective reaction operator. Moreover, during the running of DRSCRO, the task priority is changeable in our adopted VNS algorithm and a new model for processor selection is also utilized in the neighborhood structures for promoting efficiency of VNS, different from the VNS proposed in [22]. All of three advantages as previously mentioned enhance the ability to get better rapidity of convergence and better search result in the whole solution space, which is demonstrated by the experimental results in Sections 5.3 and 5.4. The time complexity of DRSCRO is O
i
t
e
r
×
2
×
V
+
4
×
E
×
P
+
d
m
a
x
×
s
u
b
p
o
p
N
u
m.


## 4.1. Framework of DRSCRO

The framework of DRSCRO to schedule a DAG job is as shown in Figure2 with two basic phases, the phase of super molecule selection and the phase of global optimization. In each phase, DRSCRO first initializes the process of a phase, and then the phase process enters iteration.Figure 2
Framework of DRSCRO.In this framework, DRSCRO first executes the phase of super molecule selection to obtain the super molecule (i.e., just the molecule with the global minimalmakespan),  SMole, with other output molecules as the input of the next global optimization phase for the first time (the input of VNS algorithm is the population with  SMole after each iteration in the global optimization phase in the other times), and then DRSCRO performs the phase of global optimization to approach the global optimum solution. The VNS algorithm with a new model for processor selection is adopted as the initialization of the global optimization phase, and it is also utilized as a local search process to promote the intensification capability of DRSCRO. There are four kinds of elementary chemical reaction in DRSCRO, on-wall collision, decomposition, intermolecular collision, and synthesis. And each kind of reaction contains two types of operators which are, respectively, utilized in two phases of DRSCRO. In each iteration, one of the elementary chemical reaction operators is performed to generate new molecules and the PEs of the newly generated molecules (i.e., the fitness function values of the newly generated molecules) will be calculated. In addition,  SMole will be tracked and only participates in on-wall ineffective collision and intermolecular ineffective collision in the global optimization phase to explore as much as possible the solution space in its neighborhoods and the main purpose is to prevent the super molecule from changing dramatically. The iteration of each phase repeats until the stopping criteria (or next phase criteria) are met, and  SMole and its fitness function value are just the final solution andmakespan (i.e., global min point), respectively. In the implementations of the experiments in this paper, the next phase criteria and the stop criteria of DRSCRO are set as when there is nomakespan improvement after 10000 consecutive iterations in the search loop.


## 4.2. Molecular Structure and Fitness Function

This subsection presents the encoding of scheduling solutions (i.e., the molecular structure) and the statement of the fitness function in DRSCRO.


### 4.2.1. Molecular Structure

In this paper, an atom with three elements can be denoted as a tuple(
v
i
,
f
i
,
p
i
) and the molecular structure M with an array of tuples can be formulated as in (8) to represent a solution to the DAG scheduling problem. The order of the tuples in M represents the priority of each DAG task v
i with the allocated processor p
i, and V
=
(
v
1
,
v
2
,
…
,
v
V
) is a topological sequence of DAG, which is with the hypothetical entry task (with no predecessors) v
1 and exit task (with no successors) v
V, respectively, representing the beginning and end of execution. Moreover, if tuple A is before tuple B and v
A is the predecessor of v
B in DAG, the second integer of tuple  B, f
B, will be 1, and vice versa(8)
m
=
v
1
,
f
1
,
p
1
,
v
2
,
f
2
,
p
2
,
…
,
v
V
,
f
V
,
p
V
.


### 4.2.2. Fitness Function

Potential energy (PE) is defined as the fitness function value of the corresponding solution represented byS. The overall schedule length of the entire DAG, namely,makespan, is the largest finish time among all tasks, which is equivalent to the actual finish time of the exit node in DAG. In this paper, the goal of DAG scheduling problem by DRSCRO is to obtain the scheduling that minimizesmakespan and ensure that the precedence of the tasks is not violated. Hence, each fitness function value is defined as (9)
F
i
t
m
=
P
E
m
=
m
a
k
e
s
p
a
n
.Algorithm1 presents how to calculate the value of the optimization fitness function F
i
t
(
m
).Algorithm 1:Fit(m) calculating the fitness value of a molecule and the processor allocation optimization.
(1)makespan = 0;
(2)for each node v
k in m = ((v
1, f
1, p
1), (v
2, f
2, p
2
)
,
…
,
(
v
V, f
V, p
V)) do
(3)  calculate the actual finish time ofv
k (i.e. T
AFTime
(
v
k
))
(4)if  m
a
k
e
s
p
a
n
<
T
AFTime
(
v
k
)
(5)   updatemakespan
(6)makespan = T
AFTime
(
v
k
)
(7)end if
(8)end for
(9)return
makespan;


## 4.2.1. Molecular Structure

In this paper, an atom with three elements can be denoted as a tuple(
v
i
,
f
i
,
p
i
) and the molecular structure M with an array of tuples can be formulated as in (8) to represent a solution to the DAG scheduling problem. The order of the tuples in M represents the priority of each DAG task v
i with the allocated processor p
i, and V
=
(
v
1
,
v
2
,
…
,
v
V
) is a topological sequence of DAG, which is with the hypothetical entry task (with no predecessors) v
1 and exit task (with no successors) v
V, respectively, representing the beginning and end of execution. Moreover, if tuple A is before tuple B and v
A is the predecessor of v
B in DAG, the second integer of tuple  B, f
B, will be 1, and vice versa(8)
m
=
v
1
,
f
1
,
p
1
,
v
2
,
f
2
,
p
2
,
…
,
v
V
,
f
V
,
p
V
.


## 4.2.2. Fitness Function

Potential energy (PE) is defined as the fitness function value of the corresponding solution represented byS. The overall schedule length of the entire DAG, namely,makespan, is the largest finish time among all tasks, which is equivalent to the actual finish time of the exit node in DAG. In this paper, the goal of DAG scheduling problem by DRSCRO is to obtain the scheduling that minimizesmakespan and ensure that the precedence of the tasks is not violated. Hence, each fitness function value is defined as (9)
F
i
t
m
=
P
E
m
=
m
a
k
e
s
p
a
n
.Algorithm1 presents how to calculate the value of the optimization fitness function F
i
t
(
m
).Algorithm 1:Fit(m) calculating the fitness value of a molecule and the processor allocation optimization.
(1)makespan = 0;
(2)for each node v
k in m = ((v
1, f
1, p
1), (v
2, f
2, p
2
)
,
…
,
(
v
V, f
V, p
V)) do
(3)  calculate the actual finish time ofv
k (i.e. T
AFTime
(
v
k
))
(4)if  m
a
k
e
s
p
a
n
<
T
AFTime
(
v
k
)
(5)   updatemakespan
(6)makespan = T
AFTime
(
v
k
)
(7)end if
(8)end for
(9)return
makespan;


## 4.3. Super Molecule Selection Phase

### 4.3.1. Initialization

There are two kinds of initial molecule generator, one used in the phase of super molecule selection and the other used in the phase of global optimization, to generate the initial solutions for DRSCRO to manipulate. The tuples of the first moleculem used in the initialization of the phase of super molecule selection are ascendingly ordered by the upward rank value [27] of their v
i, and element three p
i of each tuple is generated by a random perturbation. The upward rank value can be calculated by(10)
R
a
n
k
v
i
=
W
v
i
¯
+
max
v
j
∈
successor
v
i
⁡
c
o
m
m
v
i
,
v
j
+
R
a
n
k
v
j
.A detailed description of the initial molecule generator of the super molecule selection phase is given in Algorithm2. For the first input molecule  m, p
x in each tuple in m is set as p
1.Algorithm 2:InitMoleSMS(m) generating the initial population for the super molecule selection phase.
(1)M
o
l
e
N = 1;
(2)while  MoleN  ≤  PopSize do
(3)for each p
i in molecule m to randomly change;
(4)   changep
i randomly
(5)end for
(6)  generate a new moleculem
′;
(7)MoleN = MoleN + 1;
(8)end while


### 4.3.2. Elementary Chemical Reaction Operators

In DRSCRO, the operators for super molecule selection just randomly changep
i of each tuple in a molecule as the intensification searches or the diversification searches [25] to optimize the processor mapping of a solution. Figures 3, 4, 5, and 6, respectively, show the examples of four operators for super molecule selection, in which the molecules correspond to the DAG as shown in Figure 1(a). And the white blocks in these examples denote the tuples that do not change during the reaction operation calculations.Figure 3
Example of OnWallSMS.Figure 4
Example of DecompSMS.Figure 5
Example of IntermoleSMS.Figure 6
Example of SynthSMS.As shown in Figure3, the operator, OnWallSMS, is used to generate a new molecule m
′ from a given reaction molecule m for optimization. OnWallSMS works as follows: (1) The operator randomly chooses a tuple (v
i, f
i, p
i) in  m. (2) The operator changes p
i randomly. In the end, the operator generates a new molecule m
′ from m as an intensification search.As shown in Figure4, the operator, DecompSMS, is used to generate new molecules m
′
1 and m
′
2 from a given reaction molecule m. DecompSMS works as follows: (1) The operator generates two molecules m
′
1
=
m and m
′
2
=
m. (2) The operator keeps the tuples in m
′
1, which is at the odd position in  m and then changes the remaining p
x’s of tuples in m
′
1, randomly. (3) The operator retains the tuples in m
′
2, which is at the even position in  m, and then changes the remaining p
x’s of tuples in m
′
2 randomly. In the end, the operator generates two new molecules m
′
1 and m
′
2 from m as a diversification search.As shown in Figure5, the operator, IntermoleSMS, is used to generate new molecules m
′
1 and m
′
2 from given molecules  m
1 and  m
2. This operator first uses the steps in OnWallSMS to generate m
′
1 from m
1, and then the operator generates the other new molecule m
′
2 from m
2 in the similar fashion. In the end, the operator generates two new molecules m
′
1 and m
′
2 from  m
1 and  m
2 as an intensification search.As shown in Figure6, the operator, SynthSMS, is used to generate a new molecule m
′ from given molecules m
1 and m
2. SynthSMS works as follows: The operator keeps the tuples in m
′, which is at the same position in m
1 and m
2 with the same p
x’s, and then changes the remaining p
y’s in m
′, randomly. As a result, the operator generates m
′ from m
1 and m
2 as a diversification search.


## 4.3.1. Initialization

There are two kinds of initial molecule generator, one used in the phase of super molecule selection and the other used in the phase of global optimization, to generate the initial solutions for DRSCRO to manipulate. The tuples of the first moleculem used in the initialization of the phase of super molecule selection are ascendingly ordered by the upward rank value [27] of their v
i, and element three p
i of each tuple is generated by a random perturbation. The upward rank value can be calculated by(10)
R
a
n
k
v
i
=
W
v
i
¯
+
max
v
j
∈
successor
v
i
⁡
c
o
m
m
v
i
,
v
j
+
R
a
n
k
v
j
.A detailed description of the initial molecule generator of the super molecule selection phase is given in Algorithm2. For the first input molecule  m, p
x in each tuple in m is set as p
1.Algorithm 2:InitMoleSMS(m) generating the initial population for the super molecule selection phase.
(1)M
o
l
e
N = 1;
(2)while  MoleN  ≤  PopSize do
(3)for each p
i in molecule m to randomly change;
(4)   changep
i randomly
(5)end for
(6)  generate a new moleculem
′;
(7)MoleN = MoleN + 1;
(8)end while


## 4.3.2. Elementary Chemical Reaction Operators

In DRSCRO, the operators for super molecule selection just randomly changep
i of each tuple in a molecule as the intensification searches or the diversification searches [25] to optimize the processor mapping of a solution. Figures 3, 4, 5, and 6, respectively, show the examples of four operators for super molecule selection, in which the molecules correspond to the DAG as shown in Figure 1(a). And the white blocks in these examples denote the tuples that do not change during the reaction operation calculations.Figure 3
Example of OnWallSMS.Figure 4
Example of DecompSMS.Figure 5
Example of IntermoleSMS.Figure 6
Example of SynthSMS.As shown in Figure3, the operator, OnWallSMS, is used to generate a new molecule m
′ from a given reaction molecule m for optimization. OnWallSMS works as follows: (1) The operator randomly chooses a tuple (v
i, f
i, p
i) in  m. (2) The operator changes p
i randomly. In the end, the operator generates a new molecule m
′ from m as an intensification search.As shown in Figure4, the operator, DecompSMS, is used to generate new molecules m
′
1 and m
′
2 from a given reaction molecule m. DecompSMS works as follows: (1) The operator generates two molecules m
′
1
=
m and m
′
2
=
m. (2) The operator keeps the tuples in m
′
1, which is at the odd position in  m and then changes the remaining p
x’s of tuples in m
′
1, randomly. (3) The operator retains the tuples in m
′
2, which is at the even position in  m, and then changes the remaining p
x’s of tuples in m
′
2 randomly. In the end, the operator generates two new molecules m
′
1 and m
′
2 from m as a diversification search.As shown in Figure5, the operator, IntermoleSMS, is used to generate new molecules m
′
1 and m
′
2 from given molecules  m
1 and  m
2. This operator first uses the steps in OnWallSMS to generate m
′
1 from m
1, and then the operator generates the other new molecule m
′
2 from m
2 in the similar fashion. In the end, the operator generates two new molecules m
′
1 and m
′
2 from  m
1 and  m
2 as an intensification search.As shown in Figure6, the operator, SynthSMS, is used to generate a new molecule m
′ from given molecules m
1 and m
2. SynthSMS works as follows: The operator keeps the tuples in m
′, which is at the same position in m
1 and m
2 with the same p
x’s, and then changes the remaining p
y’s in m
′, randomly. As a result, the operator generates m
′ from m
1 and m
2 as a diversification search.


## 4.4. Global Optimization Phase

### 4.4.1. Initialization

VNS is utilized by our proposed algorithm as the initialization of the global optimization phase and it is also as a local search process to promote the intensification capability of DRSCRO during the running of the whole algorithm.Algorithms3 and 4, respectively, present the subset generator of the phase output and the main steps of the whole VNS algorithm (i.e., the initialization of the global optimization phase). In DRSCRO, the VNS algorithm only processes the subset of the population with the super molecule,  SMole, after each iteration in the global optimization phase (the output of super molecule selection phase is the input of VNS for the first time). As presented in Algorithm 3, if thepop_set (i.e., the set of population) is the output of the super molecule selection phase, the tuple orders and p
is of its elements will be adjusted.pop_subset is the subset of population andpop_subset_num is the number of the elements inpop_subset, which is set asPopSize × 50% in this paper.Algorithm 3:InitVNS(pop_set, pop_subset_num) initializing the subset of the population pop_set for undergoing the VNS algorithm.
(1)tempSet = pop_set;
(2)pop_subset = ∅;
(3)if  pop_set is the input of the VNS algorithm for the first time (i.e. the output of the super molecule selection phase)
(4)for each t
e
m
p
S in tempSet except S
M
o
l
e
(5)   choose a tuple (v
i, f
i, p
i) in t
e
m
p
S, where f
i
=
0, randomly;
(6)   generate a random numberr
n
d
∈
(
0,1
);
(7)if  rnd≥ 0.5
(8)    find the first predecessorv
j = Pred(v
i) from v
i to the begin in molecule t
e
m
p
S;
(9)    interchanged position of (v
i, f
i, p
i) and (v
j
+
1, f
j
+
1, p
j
+
1) in molecule t
e
m
p
S;
(10)update f
i, f
i
+
1 and f
j
+
1 as defined in the last paragraph of Section 4.2.1.
(11) end if
(12)
for each p
i in molecule t
e
m
p
S to randomly change;
(13)  change p
i randomly
(14) end for
(15) if Fit(t
e
m
p
S) < Fit(S
M
o
l
e)
(16)  S
M
o
l
e = t
e
m
p
S;
(17) end if
(18)
end for
(19)end if
(20)pop_subset adds S
M
o
l
e;
(21)pop_subset adds the molecules in tempSet with tuple order different from S
M
o
l
e;
(22)while  p
o
p
_
s
u
b
s
e
t
≠
p
o
p
_
s
u
b
s
e
t
_
n
u
m  do
(23)pop_subset add a molecules in pop_set which do not exist in pop_subset;
(24)end whileAlgorithm 4:InitMoleGOVNS(pop_set) generating the initial population of the global optimization phase.
(1)pop_subset = InitVNS(pop_set);
(2) Select the set of neighborhood structuresN
e
i
g
h
d (d = 1,2
,
3
,
…
,
d
max
⁡);
(3)for each individual m in the pop_subset  do
(4)d = 1;
(5)while  d
<
d
max
⁡  do
(6)   Randomly generate a moleculem
1 from the dth neighborhood of m;
(7)   Apply some local search method withm
1 as the initial molecule (the local optimum presented by m
2);
(8)If  m
2 is better than m
(9)m
=
m
2;
(10)
d
=
1;
(11) else
(12)d = d + 1;
(13)
end if
(14)
end while
(15)until the termination condition is satisfied
(16)end for
(17) execute the combination strategy;In Algorithm4, different from the VNS proposed in [21], the task priority was changeable in the VNS algorithm used in DRSCRO, the reason for which is that the unchangeable task priority in the VNS reduces its efficiency to obtain a better solution. Therefore, under the consideration of the optimization of the scheduling order and the processor assignment both, the input molecules of VNS can be with different tuple order (i.e., task priority) as presented in Algorithm 3 in each iteration. d
m
a
x is set to 2 as presented in [37]. As the essential factor of VNS, two neighborhood structures, load balance and communication reduction neighborhood structures, which demonstrate their power in solving DAG scheduling problem on heterogeneous systems as presented in [21], are adopted by the VNS algorithm in DRSCRO for their high efficiency. In this paper, a new model is also proposed for processor selection of these two neighborhood structures. As presented in [21], there are two intuitions used to construct the neighborhood structures. One is that balancing load among various processors usually helps minimizing themakespan, especially when most tasks are allocated to only a few processors; the other is that reducing communication overhead and idle waiting time of processors always results in a more effective schedule, especially given a relatively high unit communication. However, there is a contradiction between these two intuitions, because reducing communication overhead and idle waiting time of processors always means that some processors are with most tasks. So, different from the original ones in [21], we develop a new model for processor selection. Let T
C
l
o
a
d
(
p
i
) be all the task execution cost of processor p
i, and T
C
c
o
m
m
(
p
i
) is the communication cost overhead of processor p
i as defined in [21]. The values of T
C
l
o
a
d
(
p
i
) and T
C
c
o
m
m
(
p
i
) are the tendencies of load balancing and communication reducing, respectively (i.e., the tendency of task reducing or increasing). The greater T
C
l
o
a
d
(
p
i
) is the stronger tendency of reducing tasks on p
i is, and the greater T
C
c
o
m
m
(
p
i
) is the stronger tendency of increasing tasks on p
i is. Therefore, a parameter Tend(p
i) is developed to measure the tendency with the combination of T
C
l
o
a
d
(
p
i
) and T
C
c
o
m
m
(
p
i
) as (11). The neighborhood structure computation processes of load balance and communication reduction are as presented in Algorithms 5 and 6, respectively. The proposed model is under the comprehensive consideration of both intuitions and can make the VNS algorithm more effective than the original one:(11)
T
e
n
d
p
i
=
1
1
+
e
-
T
C
l
o
a
d
p
i
/
T
C
c
o
m
m
p
i
.Algorithm 5:GenNeighborhoodofLoadBalance(ω).
(1)for each processor p
i in the solution ω  do
(2)  Compute Tend(p
i);
(3)end for
(4) Choose the processorp
max
⁡ with the largest Tend(p
max
⁡);
(5) Randomly choose a taskv
random from exec(p
max
⁡);
(6) Randomly choose a processorp
random different from p
max
⁡;
(7) Reallocatev
random to the processor p
random;
(8) Encode and reschedule the changed solutionω
′;
(9)return  ω
′;Algorithm 6:GenNeighborhoodofCommReduction(ω).
(1)for each processor p
i in the solution ω  do
(2)  Compute Tend(p
i);
(3)end for
(4) Choose the processorp
min
⁡ with the smallest Tend(p
min
⁡);
(5) Set the candidate set,cand, empty;
(6)for each task v
i in the set exec(p
min
⁡) do
(7) Compute the set predecessor(v
i);
(8) Update predecessor(v
i) with predecessor(v
i) = predecessor(v
i) − exec(p
min
⁡);
(9)cand = cand + predecessor(v
i);
(10)end for
(11) Randomly choose a taskv
random from cand;
(12) Reallocatev
random to the processor p
min
⁡;
(13) Encode and reschedule the changed solutionω
′;
(14)return  ω
′;The VNS algorithm in DRSCRO utilizes the dual termination criteria. The termination criterion 1 sets the upper bound of the local search iterations to 20, and the termination criterion 2 sets the maximum iteration number without improvement to 3. The VNS algorithm will stop if either criterion is satisfied. To form a new initial population, a combination strategy is utilized for combining the current population and the VNS output after the VNS algorithm outputs the subset of the population. The current population and the VNS output are first merged and sorted by increasingmakespan; then the firstPopSize molecules are selected to generate the new initial population.


### 4.4.2. Elementary Chemical Reaction Operators

The operators for global optimization not only varyp
i of each tuple but also interchange the positions of the tuples in a molecule as the intensification searches or the diversification searches [25] to optimize the whole solution.On-wall ineffective collision (as an intensification search), decomposition (as a diversification search), and synthesis (as a diversification search) are as presented in [30], and we do not repeat them here to focus on our main work. In [30], the function of the ineffective collision operator is similar to that of the on-wall ineffective collision operator. Therefore, different from [30], a modified ineffective collision operator is proposed in this paper, and it utilized the load balance neighborhood structure used in the VNS mentioned before, to promote the intensification capability of DRSCRO and avoid the function duplication.The operator, IntermoleGO (i.e., the ineffective collision operator), is used to generate new moleculesm
′
1 and m
′
2 from given molecules m
1 and m
2. This operator first uses the steps in OnWallGO to generate m
′
1 from m
1, and then the operator generate the other new molecule m
′
2 from m
2 in the similar fashion. In the end, the operator generates two new molecules m
′
1 and m
′
2 from m
1 and m
2 as an intensification search. The detailed executions are presented in Algorithm 7. Figure 7 shows the example of the IntermoleGO, in which the molecules correspond to the DAG as shown in Figure 1(a).Algorithm 7:IntermoleGO(m
1, m
2).
(1) choose randomly a tuple (v
i, f
i, p
i) in m
1 where f
i = 0;
(2) exchange the positions of (v
i, f
i, p
i) and (v
i
-
1,f
i
-
1, p
i
-
1);
(3) modifyf
i
-
1, f
i and f
i
+
1 in m
1 as defined in the last paragraph of Section 4.2.1;
(4) generate a new moleculem
′
1 = GenLBNeighborhood(m
1);
(5) choose randomly a tuple (v
i, f
i, p
i) in m
2 where f
j = 0;
(6) exchange the positions of (v
i, f
i, p
i) and (v
j
-
1, f
j
-
1, p
j
-
1);
(7) modifyf
j
-
1, f
j and f
j
+
1 in m
2 as defined in the last paragraph of Section 4.2.1;
(8) generate a new moleculem
′
2 = GenLBNeighborhood(m
2);Figure 7
Example of IntermoleGO.


## 4.4.1. Initialization

VNS is utilized by our proposed algorithm as the initialization of the global optimization phase and it is also as a local search process to promote the intensification capability of DRSCRO during the running of the whole algorithm.Algorithms3 and 4, respectively, present the subset generator of the phase output and the main steps of the whole VNS algorithm (i.e., the initialization of the global optimization phase). In DRSCRO, the VNS algorithm only processes the subset of the population with the super molecule,  SMole, after each iteration in the global optimization phase (the output of super molecule selection phase is the input of VNS for the first time). As presented in Algorithm 3, if thepop_set (i.e., the set of population) is the output of the super molecule selection phase, the tuple orders and p
is of its elements will be adjusted.pop_subset is the subset of population andpop_subset_num is the number of the elements inpop_subset, which is set asPopSize × 50% in this paper.Algorithm 3:InitVNS(pop_set, pop_subset_num) initializing the subset of the population pop_set for undergoing the VNS algorithm.
(1)tempSet = pop_set;
(2)pop_subset = ∅;
(3)if  pop_set is the input of the VNS algorithm for the first time (i.e. the output of the super molecule selection phase)
(4)for each t
e
m
p
S in tempSet except S
M
o
l
e
(5)   choose a tuple (v
i, f
i, p
i) in t
e
m
p
S, where f
i
=
0, randomly;
(6)   generate a random numberr
n
d
∈
(
0,1
);
(7)if  rnd≥ 0.5
(8)    find the first predecessorv
j = Pred(v
i) from v
i to the begin in molecule t
e
m
p
S;
(9)    interchanged position of (v
i, f
i, p
i) and (v
j
+
1, f
j
+
1, p
j
+
1) in molecule t
e
m
p
S;
(10)update f
i, f
i
+
1 and f
j
+
1 as defined in the last paragraph of Section 4.2.1.
(11) end if
(12)
for each p
i in molecule t
e
m
p
S to randomly change;
(13)  change p
i randomly
(14) end for
(15) if Fit(t
e
m
p
S) < Fit(S
M
o
l
e)
(16)  S
M
o
l
e = t
e
m
p
S;
(17) end if
(18)
end for
(19)end if
(20)pop_subset adds S
M
o
l
e;
(21)pop_subset adds the molecules in tempSet with tuple order different from S
M
o
l
e;
(22)while  p
o
p
_
s
u
b
s
e
t
≠
p
o
p
_
s
u
b
s
e
t
_
n
u
m  do
(23)pop_subset add a molecules in pop_set which do not exist in pop_subset;
(24)end whileAlgorithm 4:InitMoleGOVNS(pop_set) generating the initial population of the global optimization phase.
(1)pop_subset = InitVNS(pop_set);
(2) Select the set of neighborhood structuresN
e
i
g
h
d (d = 1,2
,
3
,
…
,
d
max
⁡);
(3)for each individual m in the pop_subset  do
(4)d = 1;
(5)while  d
<
d
max
⁡  do
(6)   Randomly generate a moleculem
1 from the dth neighborhood of m;
(7)   Apply some local search method withm
1 as the initial molecule (the local optimum presented by m
2);
(8)If  m
2 is better than m
(9)m
=
m
2;
(10)
d
=
1;
(11) else
(12)d = d + 1;
(13)
end if
(14)
end while
(15)until the termination condition is satisfied
(16)end for
(17) execute the combination strategy;In Algorithm4, different from the VNS proposed in [21], the task priority was changeable in the VNS algorithm used in DRSCRO, the reason for which is that the unchangeable task priority in the VNS reduces its efficiency to obtain a better solution. Therefore, under the consideration of the optimization of the scheduling order and the processor assignment both, the input molecules of VNS can be with different tuple order (i.e., task priority) as presented in Algorithm 3 in each iteration. d
m
a
x is set to 2 as presented in [37]. As the essential factor of VNS, two neighborhood structures, load balance and communication reduction neighborhood structures, which demonstrate their power in solving DAG scheduling problem on heterogeneous systems as presented in [21], are adopted by the VNS algorithm in DRSCRO for their high efficiency. In this paper, a new model is also proposed for processor selection of these two neighborhood structures. As presented in [21], there are two intuitions used to construct the neighborhood structures. One is that balancing load among various processors usually helps minimizing themakespan, especially when most tasks are allocated to only a few processors; the other is that reducing communication overhead and idle waiting time of processors always results in a more effective schedule, especially given a relatively high unit communication. However, there is a contradiction between these two intuitions, because reducing communication overhead and idle waiting time of processors always means that some processors are with most tasks. So, different from the original ones in [21], we develop a new model for processor selection. Let T
C
l
o
a
d
(
p
i
) be all the task execution cost of processor p
i, and T
C
c
o
m
m
(
p
i
) is the communication cost overhead of processor p
i as defined in [21]. The values of T
C
l
o
a
d
(
p
i
) and T
C
c
o
m
m
(
p
i
) are the tendencies of load balancing and communication reducing, respectively (i.e., the tendency of task reducing or increasing). The greater T
C
l
o
a
d
(
p
i
) is the stronger tendency of reducing tasks on p
i is, and the greater T
C
c
o
m
m
(
p
i
) is the stronger tendency of increasing tasks on p
i is. Therefore, a parameter Tend(p
i) is developed to measure the tendency with the combination of T
C
l
o
a
d
(
p
i
) and T
C
c
o
m
m
(
p
i
) as (11). The neighborhood structure computation processes of load balance and communication reduction are as presented in Algorithms 5 and 6, respectively. The proposed model is under the comprehensive consideration of both intuitions and can make the VNS algorithm more effective than the original one:(11)
T
e
n
d
p
i
=
1
1
+
e
-
T
C
l
o
a
d
p
i
/
T
C
c
o
m
m
p
i
.Algorithm 5:GenNeighborhoodofLoadBalance(ω).
(1)for each processor p
i in the solution ω  do
(2)  Compute Tend(p
i);
(3)end for
(4) Choose the processorp
max
⁡ with the largest Tend(p
max
⁡);
(5) Randomly choose a taskv
random from exec(p
max
⁡);
(6) Randomly choose a processorp
random different from p
max
⁡;
(7) Reallocatev
random to the processor p
random;
(8) Encode and reschedule the changed solutionω
′;
(9)return  ω
′;Algorithm 6:GenNeighborhoodofCommReduction(ω).
(1)for each processor p
i in the solution ω  do
(2)  Compute Tend(p
i);
(3)end for
(4) Choose the processorp
min
⁡ with the smallest Tend(p
min
⁡);
(5) Set the candidate set,cand, empty;
(6)for each task v
i in the set exec(p
min
⁡) do
(7) Compute the set predecessor(v
i);
(8) Update predecessor(v
i) with predecessor(v
i) = predecessor(v
i) − exec(p
min
⁡);
(9)cand = cand + predecessor(v
i);
(10)end for
(11) Randomly choose a taskv
random from cand;
(12) Reallocatev
random to the processor p
min
⁡;
(13) Encode and reschedule the changed solutionω
′;
(14)return  ω
′;The VNS algorithm in DRSCRO utilizes the dual termination criteria. The termination criterion 1 sets the upper bound of the local search iterations to 20, and the termination criterion 2 sets the maximum iteration number without improvement to 3. The VNS algorithm will stop if either criterion is satisfied. To form a new initial population, a combination strategy is utilized for combining the current population and the VNS output after the VNS algorithm outputs the subset of the population. The current population and the VNS output are first merged and sorted by increasingmakespan; then the firstPopSize molecules are selected to generate the new initial population.


## 4.4.2. Elementary Chemical Reaction Operators

The operators for global optimization not only varyp
i of each tuple but also interchange the positions of the tuples in a molecule as the intensification searches or the diversification searches [25] to optimize the whole solution.On-wall ineffective collision (as an intensification search), decomposition (as a diversification search), and synthesis (as a diversification search) are as presented in [30], and we do not repeat them here to focus on our main work. In [30], the function of the ineffective collision operator is similar to that of the on-wall ineffective collision operator. Therefore, different from [30], a modified ineffective collision operator is proposed in this paper, and it utilized the load balance neighborhood structure used in the VNS mentioned before, to promote the intensification capability of DRSCRO and avoid the function duplication.The operator, IntermoleGO (i.e., the ineffective collision operator), is used to generate new moleculesm
′
1 and m
′
2 from given molecules m
1 and m
2. This operator first uses the steps in OnWallGO to generate m
′
1 from m
1, and then the operator generate the other new molecule m
′
2 from m
2 in the similar fashion. In the end, the operator generates two new molecules m
′
1 and m
′
2 from m
1 and m
2 as an intensification search. The detailed executions are presented in Algorithm 7. Figure 7 shows the example of the IntermoleGO, in which the molecules correspond to the DAG as shown in Figure 1(a).Algorithm 7:IntermoleGO(m
1, m
2).
(1) choose randomly a tuple (v
i, f
i, p
i) in m
1 where f
i = 0;
(2) exchange the positions of (v
i, f
i, p
i) and (v
i
-
1,f
i
-
1, p
i
-
1);
(3) modifyf
i
-
1, f
i and f
i
+
1 in m
1 as defined in the last paragraph of Section 4.2.1;
(4) generate a new moleculem
′
1 = GenLBNeighborhood(m
1);
(5) choose randomly a tuple (v
i, f
i, p
i) in m
2 where f
j = 0;
(6) exchange the positions of (v
i, f
i, p
i) and (v
j
-
1, f
j
-
1, p
j
-
1);
(7) modifyf
j
-
1, f
j and f
j
+
1 in m
2 as defined in the last paragraph of Section 4.2.1;
(8) generate a new moleculem
′
2 = GenLBNeighborhood(m
2);Figure 7
Example of IntermoleGO.


## 4.5. Illustrative Example

Consider the example shown in Figure1(a). Its edges are labeled with the communication costs, whereas the execution costs are shown in Table 3.Table 3
Execution cost of DAG tasks by each processor.
Tasks
p
1
p
2
p
3
v
1
7
8
9
v
2
12
14
16
v
3
14
15
16
v
4
13
3
14Initially, the path (v
1, v
2, v
4, v
3) is found based on the upward rank value of each task in DAG, and the first molecule,  m = ((v
1, 0, p
1), (v
2, 1, p
1), (v
4, 0, p
1), and (v
3, 1, p
1)), can be obtained. Algorithm 2, InitMoleSMS, is then executed to generate the initial population with 10 elements (i.e.,PopSize is set as 10) for super molecule selection phase. The initial population molecules are operated during the iterations in the super molecule selection phase as presented in the framework of DRSCRO in Section 4.1, and the super molecule,  SMole = ((v
1, 0, p
3), (v
2, 1, p
1), (v
4, 0, p
2), and (v
3, 1, p
1)), can be obtained.In the global optimization phase, Algorithm4, InitMoleGOVNS, is then executed to generate (or to update) the initial population after each iteration as presented in Section 4.1. The molecules are operated during the iterations in the global optimization phase as presented in the framework of DRSCRO in Section 4.1, and the global minimalmakespan = 40 is finally obtained, for which the corresponding solution (i.e., molecule) is ((v
1, 0, p
2), (v
4, 1, p
2), (v
2, 0, p
2), and (v
3, 1, p
2)).


## 4.6. Analysis of DRSCRO

As a new metaheuristic strategy, the CRO-based methods for DAG scheduling which is proposed very recently have demonstrated the capability for solving this kind of NP-hard optimization problems. By analyzing the framework, molecular structure, chemical reaction operators, and the operational environment in DRSCRO, it can be shown to some extent that DRSCRO scheme has the advantage of three points in comparison with other CRO-based algorithms for DAG scheduling.First, to some degree, super molecule in DRSCRO is similar toInitS in TMSCRO [30] or the “elite” in GA [31]. However, the “elite” in GA is usually generated from two chromosomes, while super molecule is approached by executing the first phase of DRSCRO. Moreover, in comparison with TMSCRO, DRSCRO uses a metaheuristic strategy (CRO) to get a better super molecule. It is because, as intelligent random-search algorithm, CRO used in the phase of DRSCRO for super molecule selection searches a wider area of the solution space than CEFT applied in TMSCRO, which narrow the search down to a very small portion of the solution space. As a result, a better super molecule may contribute to a better global optimum solution and accelerates convergence. Second, DAG scheduling problem has two complex aspects including task sequence optimization and processor assignment optimization, which lead to a very large and complicated solution space. So, for a better capability of intensification search than other CRO-based algorithms for DAG scheduling on heterogeneous systems, DRSCRO applied VNS algorithm as the initialization of the global optimization phase, which is also as a local search process during the running of DRSCRO, and one of the neighborhood structures of VNS is also utilized in the ineffective reaction operator. Moreover, during the running of DRSCRO, the task priority is changeable in our adopted VNS algorithm and a new model for processor selection is also utilized in the neighborhood structures for promoting efficiency of VNS, different from the VNS proposed in [22]. All of three advantages as previously mentioned enhance the ability to get better rapidity of convergence and better search result in the whole solution space, which is demonstrated by the experimental results in Sections 5.3 and 5.4. The time complexity of DRSCRO is O
i
t
e
r
×
2
×
V
+
4
×
E
×
P
+
d
m
a
x
×
s
u
b
p
o
p
N
u
m.


## 5. Experimental Details

In this section, the simulation experiment and comparative evaluation of HEFT, DMSCRO, TMSCRO, and proposed DRSCRO are presented. As presented in [27, 30], by theory analysis and experimental results, TMSCRO and DMSCRO proved to have better performance than GA; therefore, our work is the further study of CRO-based algorithms for DAG scheduling on heterogeneous systems, and, for DRSCRO as a metaheuristic algorithm, we focus on the performance of our proposed algorithm itself and the comparison between DRSCRO and other similar kinds of algorithms.First, two extensive sets of graphs as the test beds for comparative study are described. Next, the parameter settings which are used in the simulation experiments are presented. The results and analysis of the experiment, includingmakespan test and convergence rate test, are given in the final part.


### 5.1. Test Bed

As presented in [27, 30], two extensive sets of DAGs, real-world application and randomly generated application graphs, are considered as the test beds in the experiments to enhance the comparability of various algorithms. The first extensive test bed is two real-world problem DAGs, molecular dynamics code [38] and Gaussian elimination [8]. Molecular dynamics are a computer simulation of physical movements of the molecules and atoms, which are allowed to interact for a period of time, in the context of N-body simulation. Molecular dynamics code DAG is shown in Figure 8. Gaussian elimination is used to calculate the solution for a linear equation system, which is applied systematically to convert row operations on a set of linear equations to the upper triangular form. As shown in Figure 9, the total number of tasks in the Gaussian elimination DAG with the matrix size of 7 is 27, and the largest task number at the same level is 6. The reason of the utilization of these two application graphs as a test bed is not only to enhance the comparability of various algorithms but also to show the function application of our proposed algorithm as an illustrative demonstration without loss of generality. The second extensive test bed for comparative study is the DAGs of random graphs. A random graph generator presented in [39] is implemented to generate random graphs in the simulation experiment. It allows the user to generate a variety of random graphs with different characteristics, such as CCR, the amount of calculation of a task, the successor number of a task, and the total number of tasks in a random graph. It is also assumed that all tasks and communication links have the same computation cost and communication cost, respectively.Figure 8
A molecular dynamics code DAG.Figure 9
A Gaussian elimination DAG for a matrix of size 7.As shown in Figure2, the next phase criteria and stopping criteria of DRSCRO are that themakespan stays unchanged for 5000 consecutive iterations in the search loop. And the stopping criterion of TMSCRO and DMSCRO is that themakespan remains the same for 10000 consecutive iterations.


### 5.2. Parameter Setting

In the experiments, a parameterh
l is set to represent the heterogeneity level as presented in the first paragraph of Section 3. It complies with the MHM model assumption and results in the fact that speeds of a computing processor are different for different tasks. In doing so, the heterogeneity level (
1
+
h
l
%
)
/
(
1
-
h
l
%
) is equal to the biggest possible ratio of the best processor speed to the worst processor speed for each task. h
l is set as the value to make the heterogeneity level 2 unless otherwise specified in this paper.The details of parameter setting are shown in Table4. The parameters 6–12, which are the CRO-based algorithms tested in the simulation, are set as presented in [25].Table 4
Parameter values for simulation experiment.
Parameter
Value
CCR
0.1, 0.2, 1, 2, 5
Number of processors
4, 8, 16, 32
hl
0.333
Successor number of a task in a random graph
1, 2, 3, 4
Total number of tasks in a random graph
10, 20, 50
InitialKE
1000
θ
500
ϑ
10
Buffer
200
KELossRate
0.2
MoleColl
0.2
PopSize
10


### 5.3. Makespan Tests

The performance of the proposed algorithm is compared with two state-of-the-art CRO-based scheduling algorithms, DMSCRO and TMSCRO, and a heuristic algorithm HEFT. Eachmakespan value plotted in the graphs is the average value of a number of independent runs. In the first extensive test bed, themakespan is averaged over 10 independent runs (HEFT is run only once as a deterministic algorithm.), while in the second extensive test bed themakespan is averaged over 30 different random graph running instances. Moreover, to prove the robustness of DRSCRO, the best final value achieved in all these runs, the worst final value, and the related standard deviation or variance are also presented.


#### 5.3.1. Real-World Application Graphs

Figures10–13 show the simulation experiment results of DRSCRO, DMSCRO, TMSCRO, and HEFT on the real-world application graphs, and Tables 4–7 list the detail of the experimental results.Table 5
Experiment results for the molecular dynamics code, CCR = 1.0.
The number of processors
HEFT(average makespan)
DMSCRO(average makespan)
TMSCRO(average makespan)
DRSCRO(average makespan)
DRSCRO(best
makespan)
DRSCRO(worst makespan)
DRSCRO(variance)
4
120.086
117.624
116.993
116.759
114.365
119.589
2.487
8
120.074
116.633
116.007
115.775
113.402
118.582
2.466
16
120.031
116.101
115.478
115.247
112.885
118.041
2.455
32
119.993
115.476
114.856
114.529
112.182
117.306
2.440Table 6
Experiment results for Gaussian elimination graph, CCR = 0.2.
The number of processors
HEFT(average makespan)
DMSCRO(average makespan)
TMSCRO(average makespan)
DRSCRO(average makespan)
DRSCRO(best
makespan)
DRSCRO(worst makespan)
DRSCRO(variance)
4
126.852
124.252
123.585
123.337
122.042
126.327
1.769
8
96.952
94.965
94.455
94.266
92.333
96.551
2.008
16
82.356
80.668
80.235
80.074
78.433
82.015
1.706
32
75.630
74.080
73.682
73.535
72.027
75.317
1.566Table 7
Experiment results for the molecular dynamics code; the processors number is 16.
The value of CCR
HEFT(average makespan)
DMSCRO(average makespan)
TMSCRO(average makespan)
DRSCRO(average makespan)
DRSCRO(best
makespan)
DRSCRO(worst makespan)
DRSCRO(variance)
0.1
111.782
109.491
108.903
108.685
106.457
111.320
2.315
0.2
112.034
109.737
109.148
108.930
106.697
111.571
2.320
1
120.031
116.101
115.478
115.247
112.885
118.041
2.455
2
160.760
157.465
156.619
156.306
153.102
158.532
3.034
5
414.581
406.082
403.902
403.095
400.878
404.805
2.125Figure 10
Average makespan for the molecular dynamics code, CCR = 1.0.Figure 11
Average makespan for Gaussian elimination, CCR = 0.2.Figure 12
Average makespan for the molecular dynamics code; the processors number is 16.Figure 13
Average makespan for Gaussian elimination; the processors number is 8.As shown in Figures10 and 11, it can be observed that the averagemakespan decreases as the processor number increases. The results also show that DRSCRO, TMSCRO, and DMSCRO achieve very similar performance, which are all metaheuristic methods. It is because, according to No-Free-Lunch Theorem, all well-designed metaheuristic methods have the same performance on searching for optimal solutions when averaged over all possible fitness functions. The TMSCRO and DMSCRO used in the simulation are well-designed and taken from the literature. Therefore it proved that DRSCRO developed in our work is also well-designed.A close observation of the results in Tables10 and 11 shows that DRSCRO outperforms TMSCRO and DMSCRO on average slightly. The reason is only because DRSCRO has better capability of intensification search by applying VNS and the utilization of one of its neighborhood structures in the ineffective reaction operator, as presented in the last paragraph of Section 4.6. Therefore the performance of the average results obtained by DRSCRO is better than that obtained by TMSCRO and DMSCRO, when the stopping criterion is satisfied. Moreover, DRSCRO, TMSCRO, and DMSCRO typically outperform HEFT because they search a wider area of the solution space as metaheuristic methods, while the search of HEFT is narrowed down to a very smaller portion by means of the heuristics.Figures12 and 13 and the results in Tables 7 and 8 show the performance of the experimental results of these four algorithms with CCR value increasing. It can be seen that themakespan on average increases with the CCR value increasing. It is because the heterogeneous processors are in the idle state for longer, as a result of the DAGs becoming more communication-intensive. It also can be observed that DRSCRO, TMSCRO, and DMSCRO outperform HEFT and the advantage becomes more significant with the value of CCR increasing, which suggest that heuristic algorithm like HEFT has less consistent performance in a wide scheduling scenario range, and metaheuristic algorithm performs more effectively for communication-intensive DAGs.Table 8
Experiment results for Gaussian elimination graph; the processors number is 8.
The value of CCR
HEFT(average makespan)
DMSCRO(average makespan)
TMSCRO(average makespan)
DRSCRO(average makespan)
DRSCRO(best
makespan)
DRSCRO(worst makespan)
DRSCRO(variance)
0.1
96.612
94.632
94.124
93.935
92.010
96.212
2.001
0.2
96.952
94.965
94.455
94.266
92.333
96.551
2.008
1
131.094
128.407
127.717
127.462
124.849
130.552
2.715
2
222.635
218.071
216.900
216.467
214.194
219.550
2.456
5
403.600
395.327
393.204
392.418
390.260
394.083
2.069


#### 5.3.2. Randomly Generated Application Graphs

As shown in Figures14–16, randomly generated DAGs are used to evaluate the performance of DRSCRO, TMSCRO, DMSCRO, and HEFT in these experiments. And the details of these experimental results are listed in Tables 9–11.Table 9
Experiment results for random graphs under different processor numbers; task number is 50 and CCR = 0.2.
The number of processors
HEFT(average makespan)
DMSCRO(average makespan)
TMSCRO(average makespan)
DRSCRO(average makespan)
DRSCRO(best
makespan)
DRSCRO(worst makespan)
DRSCRO(variance)
4
149.400
146.337
145.552
145.261
142.283
148.782
3.094
8
119.511
117.061
116.433
116.200
113.818
119.017
2.475
16
119.473
117.024
116.396
116.163
113.782
118.979
2.474
32
119.468
115.550
114.929
114.700
112.348
117.480
2.443Table 10
Experiment results for random graphs under different task numbers; processors number is 32 and CCR = 10.
The number of tasks
HEFT(average makespan)
DMSCRO(average makespan)
TMSCRO(average makespan)
DRSCRO(average makespan)
DRSCRO(best
makespan)
DRSCRO(worst makespan)
DRSCRO(variance)
10
714.484
706.149
699.100
690.708
688.982
693.638
2.025
20
1100.918
1089.685
1080.428
1069.082
1066.410
1071.479
2.619
50
1666.373
1662.543
1649.988
1634.230
1633.415
1636.261
1.165Table 11
Experiment results of DRSCRO for the random graph under different CCRs; the task number is 50.
Value of CCR
Processors number is 4
Processors number is 8
Processors number is 16
Processors number is 32
0.1
145.093
116.068
116.058
114.592
0.2
145.261
116.200
116.163
114.700
1
153.248
120.228
119.511
118.534
2
194.401
166.014
164.246
162.292
5
508.759
498.427
492.049
487.830Figure 14
Average makespan for random graphs under different processor numbers; task number is 50 and CCR = 0.2.Figure 15
Average makespan for random graphs under different task numbers; processors number is 32 and CCR = 10.Figure 16
Average makespan of DRSCRO for the random graph under different CCRs; the task number is 50.Figure14 shows the performance on the experimental results of these four algorithms with the processor number increasing. As shown in Figure 14, DRSCRO always outperforms TMSCRO, DMSCRO, and HEFT as the number of processors increases. Figure 15 shows that DMSCRO has better performance than the other three algorithms as the task number increases. The reasons for these are similar to those explained in the third paragraph of Section 5.3.1. Figure 16 shows themakespan on average with CCR values increasing. It can be seem that the averagemakespan increases rapidly with the increasing of the value of CCR. As shown in Figure 16, themakespan on average increases rapidly when the value of CCR rises. It is the fact that the DAG becomes more communication-intensive with CCR increasing which leads to the processors staying in the idle state for longer.


### 5.4. Convergence Tests

In this section, the convergence experiments are conducted to show the change ofmakespan among DRSCRO, TMSCRO, and DMSCRO. The convergence traces and significant tests are to further reveal the differences between DRSCRO and the other two algorithms. In these experiments, as suggested in [27], the stopping criteria of these three algorithms are that the total running time reaches a setting value (e.g., 180 s). Under the consideration of comparability, the beginning of the time counting of DRSCRO is set as the start of the global optimization phase processing. In the first extensive test bed, themakespan is averaged over 10 independent runs, while in the second extensive test bed themakespan is averaged over 30 different random graph running instances.


#### 5.4.1. Convergence Trace

The convergence traces of DRSCRO, TMSCRO, and DMSCRO for processing the molecular dynamics code and Gaussian elimination are plotted in Figures17 and 18, respectively. Figures 19–21 show the convergence traces when processing the randomly generated DAG sets, of which each contains 10, 20, and 50 tasks, respectively. As shown in Figures 17–21, it can be observed that the convergence traces of these three algorithms have obvious differences. And the DRSCRO converges faster than the other two algorithms in every case. The reason for the better rate of convergence of DRSCRO is as presented in the last paragraph of Section 4.6 (i.e., DRSCRO takes the advantage of its double-reaction structure to obtain a better super molecule for accelerating convergence). Even though the VNS algorithm adds the time cost in each iteration, the enhanced optimization capability of DRSCRO also makes it obtain a better coverage rate than TMSCRO and DMSCRO. The simulation experimental results show that DRSCRO converges faster than TMSCRO by 19.4% on average (by 29.3% in the best case) and faster than DMSCRO by 33.9% on average (by 41.2% in the best case).Figure 17
Convergence trace for the molecular dynamics code; CCR = 1 and the number of processors is 16.Figure 18
Convergence trace for Gaussian elimination; CCR = 0.2 and the number of processors is 8.Figure 19
Convergence trace for the set of the randomly generated DAGs with 10 tasks.Figure 20
Convergence trace for the set of the randomly generated DAGs with 20 tasks.Figure 21
Convergence trace for the set of the randomly generated DAGs with 50 tasks.Moreover, the statistical analysis based on the average values achieved is also presented in Section5.4.2, to prove that DRSCRO outperforms the other CRO-based algorithms for DAG scheduling from a statistical point of view.


#### 5.4.2. Significant Tests

Statistical analysis is necessary for the average coverage rates obtained in all cases by DRSCRO, TMSCRO, and DMSCRO, which are metaheuristic methods, in order to find significant differences among these results. Nonparametric tests according to the recommendations in [40] are specifically considered to be used, since the experimental results may present neither normal distribution nor variance homogeneity. Therefore, the Friedman test and the Quade test are applied to check whether significant differences exist in the performance between these three algorithms. A significance level α = 0.05 is used in all statistical tests.Tables12 and 13, respectively, list the test results of the Friedman test and the Quade test, which both reject the null hypothesis of equivalent performance. In both of these two tests, our proposed DRSCRO is not only compared against all the algorithms but also compared against the remaining ones as the control method. The results in Tables 12 and 13 validate the significant differences α in the performance of DRSCRO, TMSCRO, and DMSCRO.Table 12
Results of Friedman tests,α
=
0.05.
Method
Algorithm
p value
Hypothesis
Friedman test
DRSCRO, DMSCRO
2.53
E
-
02
Rejected
DRSCRO, TMSCRO
2.53
E
-
02
Rejected
DRSCRO, DMSCRO, TMSCRO
6.70
E
-
03
RejectedTable 13
Results of Quade tests,α
=
0.05.
Method
Algorithm
p value
Hypothesis
Quade test
DRSCRO, DMSCRO
1.32
E
-
02
Rejected
DRSCRO, TMSCRO
1.32
E
-
02
Rejected
DRSCRO, DMSCRO, TMSCRO
1.09
E
-
03
RejectedIn sum, it could be concluded that DRSCRO, which is the control algorithm, statistically outperforms the other CRO-based DAG scheduling algorithm on coverage rate with a significant level of 0.05.


## 5.1. Test Bed

As presented in [27, 30], two extensive sets of DAGs, real-world application and randomly generated application graphs, are considered as the test beds in the experiments to enhance the comparability of various algorithms. The first extensive test bed is two real-world problem DAGs, molecular dynamics code [38] and Gaussian elimination [8]. Molecular dynamics are a computer simulation of physical movements of the molecules and atoms, which are allowed to interact for a period of time, in the context of N-body simulation. Molecular dynamics code DAG is shown in Figure 8. Gaussian elimination is used to calculate the solution for a linear equation system, which is applied systematically to convert row operations on a set of linear equations to the upper triangular form. As shown in Figure 9, the total number of tasks in the Gaussian elimination DAG with the matrix size of 7 is 27, and the largest task number at the same level is 6. The reason of the utilization of these two application graphs as a test bed is not only to enhance the comparability of various algorithms but also to show the function application of our proposed algorithm as an illustrative demonstration without loss of generality. The second extensive test bed for comparative study is the DAGs of random graphs. A random graph generator presented in [39] is implemented to generate random graphs in the simulation experiment. It allows the user to generate a variety of random graphs with different characteristics, such as CCR, the amount of calculation of a task, the successor number of a task, and the total number of tasks in a random graph. It is also assumed that all tasks and communication links have the same computation cost and communication cost, respectively.Figure 8
A molecular dynamics code DAG.Figure 9
A Gaussian elimination DAG for a matrix of size 7.As shown in Figure2, the next phase criteria and stopping criteria of DRSCRO are that themakespan stays unchanged for 5000 consecutive iterations in the search loop. And the stopping criterion of TMSCRO and DMSCRO is that themakespan remains the same for 10000 consecutive iterations.


## 5.2. Parameter Setting

In the experiments, a parameterh
l is set to represent the heterogeneity level as presented in the first paragraph of Section 3. It complies with the MHM model assumption and results in the fact that speeds of a computing processor are different for different tasks. In doing so, the heterogeneity level (
1
+
h
l
%
)
/
(
1
-
h
l
%
) is equal to the biggest possible ratio of the best processor speed to the worst processor speed for each task. h
l is set as the value to make the heterogeneity level 2 unless otherwise specified in this paper.The details of parameter setting are shown in Table4. The parameters 6–12, which are the CRO-based algorithms tested in the simulation, are set as presented in [25].Table 4
Parameter values for simulation experiment.
Parameter
Value
CCR
0.1, 0.2, 1, 2, 5
Number of processors
4, 8, 16, 32
hl
0.333
Successor number of a task in a random graph
1, 2, 3, 4
Total number of tasks in a random graph
10, 20, 50
InitialKE
1000
θ
500
ϑ
10
Buffer
200
KELossRate
0.2
MoleColl
0.2
PopSize
10


## 5.3. Makespan Tests

The performance of the proposed algorithm is compared with two state-of-the-art CRO-based scheduling algorithms, DMSCRO and TMSCRO, and a heuristic algorithm HEFT. Eachmakespan value plotted in the graphs is the average value of a number of independent runs. In the first extensive test bed, themakespan is averaged over 10 independent runs (HEFT is run only once as a deterministic algorithm.), while in the second extensive test bed themakespan is averaged over 30 different random graph running instances. Moreover, to prove the robustness of DRSCRO, the best final value achieved in all these runs, the worst final value, and the related standard deviation or variance are also presented.


### 5.3.1. Real-World Application Graphs

Figures10–13 show the simulation experiment results of DRSCRO, DMSCRO, TMSCRO, and HEFT on the real-world application graphs, and Tables 4–7 list the detail of the experimental results.Table 5
Experiment results for the molecular dynamics code, CCR = 1.0.
The number of processors
HEFT(average makespan)
DMSCRO(average makespan)
TMSCRO(average makespan)
DRSCRO(average makespan)
DRSCRO(best
makespan)
DRSCRO(worst makespan)
DRSCRO(variance)
4
120.086
117.624
116.993
116.759
114.365
119.589
2.487
8
120.074
116.633
116.007
115.775
113.402
118.582
2.466
16
120.031
116.101
115.478
115.247
112.885
118.041
2.455
32
119.993
115.476
114.856
114.529
112.182
117.306
2.440Table 6
Experiment results for Gaussian elimination graph, CCR = 0.2.
The number of processors
HEFT(average makespan)
DMSCRO(average makespan)
TMSCRO(average makespan)
DRSCRO(average makespan)
DRSCRO(best
makespan)
DRSCRO(worst makespan)
DRSCRO(variance)
4
126.852
124.252
123.585
123.337
122.042
126.327
1.769
8
96.952
94.965
94.455
94.266
92.333
96.551
2.008
16
82.356
80.668
80.235
80.074
78.433
82.015
1.706
32
75.630
74.080
73.682
73.535
72.027
75.317
1.566Table 7
Experiment results for the molecular dynamics code; the processors number is 16.
The value of CCR
HEFT(average makespan)
DMSCRO(average makespan)
TMSCRO(average makespan)
DRSCRO(average makespan)
DRSCRO(best
makespan)
DRSCRO(worst makespan)
DRSCRO(variance)
0.1
111.782
109.491
108.903
108.685
106.457
111.320
2.315
0.2
112.034
109.737
109.148
108.930
106.697
111.571
2.320
1
120.031
116.101
115.478
115.247
112.885
118.041
2.455
2
160.760
157.465
156.619
156.306
153.102
158.532
3.034
5
414.581
406.082
403.902
403.095
400.878
404.805
2.125Figure 10
Average makespan for the molecular dynamics code, CCR = 1.0.Figure 11
Average makespan for Gaussian elimination, CCR = 0.2.Figure 12
Average makespan for the molecular dynamics code; the processors number is 16.Figure 13
Average makespan for Gaussian elimination; the processors number is 8.As shown in Figures10 and 11, it can be observed that the averagemakespan decreases as the processor number increases. The results also show that DRSCRO, TMSCRO, and DMSCRO achieve very similar performance, which are all metaheuristic methods. It is because, according to No-Free-Lunch Theorem, all well-designed metaheuristic methods have the same performance on searching for optimal solutions when averaged over all possible fitness functions. The TMSCRO and DMSCRO used in the simulation are well-designed and taken from the literature. Therefore it proved that DRSCRO developed in our work is also well-designed.A close observation of the results in Tables10 and 11 shows that DRSCRO outperforms TMSCRO and DMSCRO on average slightly. The reason is only because DRSCRO has better capability of intensification search by applying VNS and the utilization of one of its neighborhood structures in the ineffective reaction operator, as presented in the last paragraph of Section 4.6. Therefore the performance of the average results obtained by DRSCRO is better than that obtained by TMSCRO and DMSCRO, when the stopping criterion is satisfied. Moreover, DRSCRO, TMSCRO, and DMSCRO typically outperform HEFT because they search a wider area of the solution space as metaheuristic methods, while the search of HEFT is narrowed down to a very smaller portion by means of the heuristics.Figures12 and 13 and the results in Tables 7 and 8 show the performance of the experimental results of these four algorithms with CCR value increasing. It can be seen that themakespan on average increases with the CCR value increasing. It is because the heterogeneous processors are in the idle state for longer, as a result of the DAGs becoming more communication-intensive. It also can be observed that DRSCRO, TMSCRO, and DMSCRO outperform HEFT and the advantage becomes more significant with the value of CCR increasing, which suggest that heuristic algorithm like HEFT has less consistent performance in a wide scheduling scenario range, and metaheuristic algorithm performs more effectively for communication-intensive DAGs.Table 8
Experiment results for Gaussian elimination graph; the processors number is 8.
The value of CCR
HEFT(average makespan)
DMSCRO(average makespan)
TMSCRO(average makespan)
DRSCRO(average makespan)
DRSCRO(best
makespan)
DRSCRO(worst makespan)
DRSCRO(variance)
0.1
96.612
94.632
94.124
93.935
92.010
96.212
2.001
0.2
96.952
94.965
94.455
94.266
92.333
96.551
2.008
1
131.094
128.407
127.717
127.462
124.849
130.552
2.715
2
222.635
218.071
216.900
216.467
214.194
219.550
2.456
5
403.600
395.327
393.204
392.418
390.260
394.083
2.069


### 5.3.2. Randomly Generated Application Graphs

As shown in Figures14–16, randomly generated DAGs are used to evaluate the performance of DRSCRO, TMSCRO, DMSCRO, and HEFT in these experiments. And the details of these experimental results are listed in Tables 9–11.Table 9
Experiment results for random graphs under different processor numbers; task number is 50 and CCR = 0.2.
The number of processors
HEFT(average makespan)
DMSCRO(average makespan)
TMSCRO(average makespan)
DRSCRO(average makespan)
DRSCRO(best
makespan)
DRSCRO(worst makespan)
DRSCRO(variance)
4
149.400
146.337
145.552
145.261
142.283
148.782
3.094
8
119.511
117.061
116.433
116.200
113.818
119.017
2.475
16
119.473
117.024
116.396
116.163
113.782
118.979
2.474
32
119.468
115.550
114.929
114.700
112.348
117.480
2.443Table 10
Experiment results for random graphs under different task numbers; processors number is 32 and CCR = 10.
The number of tasks
HEFT(average makespan)
DMSCRO(average makespan)
TMSCRO(average makespan)
DRSCRO(average makespan)
DRSCRO(best
makespan)
DRSCRO(worst makespan)
DRSCRO(variance)
10
714.484
706.149
699.100
690.708
688.982
693.638
2.025
20
1100.918
1089.685
1080.428
1069.082
1066.410
1071.479
2.619
50
1666.373
1662.543
1649.988
1634.230
1633.415
1636.261
1.165Table 11
Experiment results of DRSCRO for the random graph under different CCRs; the task number is 50.
Value of CCR
Processors number is 4
Processors number is 8
Processors number is 16
Processors number is 32
0.1
145.093
116.068
116.058
114.592
0.2
145.261
116.200
116.163
114.700
1
153.248
120.228
119.511
118.534
2
194.401
166.014
164.246
162.292
5
508.759
498.427
492.049
487.830Figure 14
Average makespan for random graphs under different processor numbers; task number is 50 and CCR = 0.2.Figure 15
Average makespan for random graphs under different task numbers; processors number is 32 and CCR = 10.Figure 16
Average makespan of DRSCRO for the random graph under different CCRs; the task number is 50.Figure14 shows the performance on the experimental results of these four algorithms with the processor number increasing. As shown in Figure 14, DRSCRO always outperforms TMSCRO, DMSCRO, and HEFT as the number of processors increases. Figure 15 shows that DMSCRO has better performance than the other three algorithms as the task number increases. The reasons for these are similar to those explained in the third paragraph of Section 5.3.1. Figure 16 shows themakespan on average with CCR values increasing. It can be seem that the averagemakespan increases rapidly with the increasing of the value of CCR. As shown in Figure 16, themakespan on average increases rapidly when the value of CCR rises. It is the fact that the DAG becomes more communication-intensive with CCR increasing which leads to the processors staying in the idle state for longer.


## 5.3.1. Real-World Application Graphs

Figures10–13 show the simulation experiment results of DRSCRO, DMSCRO, TMSCRO, and HEFT on the real-world application graphs, and Tables 4–7 list the detail of the experimental results.Table 5
Experiment results for the molecular dynamics code, CCR = 1.0.
The number of processors
HEFT(average makespan)
DMSCRO(average makespan)
TMSCRO(average makespan)
DRSCRO(average makespan)
DRSCRO(best
makespan)
DRSCRO(worst makespan)
DRSCRO(variance)
4
120.086
117.624
116.993
116.759
114.365
119.589
2.487
8
120.074
116.633
116.007
115.775
113.402
118.582
2.466
16
120.031
116.101
115.478
115.247
112.885
118.041
2.455
32
119.993
115.476
114.856
114.529
112.182
117.306
2.440Table 6
Experiment results for Gaussian elimination graph, CCR = 0.2.
The number of processors
HEFT(average makespan)
DMSCRO(average makespan)
TMSCRO(average makespan)
DRSCRO(average makespan)
DRSCRO(best
makespan)
DRSCRO(worst makespan)
DRSCRO(variance)
4
126.852
124.252
123.585
123.337
122.042
126.327
1.769
8
96.952
94.965
94.455
94.266
92.333
96.551
2.008
16
82.356
80.668
80.235
80.074
78.433
82.015
1.706
32
75.630
74.080
73.682
73.535
72.027
75.317
1.566Table 7
Experiment results for the molecular dynamics code; the processors number is 16.
The value of CCR
HEFT(average makespan)
DMSCRO(average makespan)
TMSCRO(average makespan)
DRSCRO(average makespan)
DRSCRO(best
makespan)
DRSCRO(worst makespan)
DRSCRO(variance)
0.1
111.782
109.491
108.903
108.685
106.457
111.320
2.315
0.2
112.034
109.737
109.148
108.930
106.697
111.571
2.320
1
120.031
116.101
115.478
115.247
112.885
118.041
2.455
2
160.760
157.465
156.619
156.306
153.102
158.532
3.034
5
414.581
406.082
403.902
403.095
400.878
404.805
2.125Figure 10
Average makespan for the molecular dynamics code, CCR = 1.0.Figure 11
Average makespan for Gaussian elimination, CCR = 0.2.Figure 12
Average makespan for the molecular dynamics code; the processors number is 16.Figure 13
Average makespan for Gaussian elimination; the processors number is 8.As shown in Figures10 and 11, it can be observed that the averagemakespan decreases as the processor number increases. The results also show that DRSCRO, TMSCRO, and DMSCRO achieve very similar performance, which are all metaheuristic methods. It is because, according to No-Free-Lunch Theorem, all well-designed metaheuristic methods have the same performance on searching for optimal solutions when averaged over all possible fitness functions. The TMSCRO and DMSCRO used in the simulation are well-designed and taken from the literature. Therefore it proved that DRSCRO developed in our work is also well-designed.A close observation of the results in Tables10 and 11 shows that DRSCRO outperforms TMSCRO and DMSCRO on average slightly. The reason is only because DRSCRO has better capability of intensification search by applying VNS and the utilization of one of its neighborhood structures in the ineffective reaction operator, as presented in the last paragraph of Section 4.6. Therefore the performance of the average results obtained by DRSCRO is better than that obtained by TMSCRO and DMSCRO, when the stopping criterion is satisfied. Moreover, DRSCRO, TMSCRO, and DMSCRO typically outperform HEFT because they search a wider area of the solution space as metaheuristic methods, while the search of HEFT is narrowed down to a very smaller portion by means of the heuristics.Figures12 and 13 and the results in Tables 7 and 8 show the performance of the experimental results of these four algorithms with CCR value increasing. It can be seen that themakespan on average increases with the CCR value increasing. It is because the heterogeneous processors are in the idle state for longer, as a result of the DAGs becoming more communication-intensive. It also can be observed that DRSCRO, TMSCRO, and DMSCRO outperform HEFT and the advantage becomes more significant with the value of CCR increasing, which suggest that heuristic algorithm like HEFT has less consistent performance in a wide scheduling scenario range, and metaheuristic algorithm performs more effectively for communication-intensive DAGs.Table 8
Experiment results for Gaussian elimination graph; the processors number is 8.
The value of CCR
HEFT(average makespan)
DMSCRO(average makespan)
TMSCRO(average makespan)
DRSCRO(average makespan)
DRSCRO(best
makespan)
DRSCRO(worst makespan)
DRSCRO(variance)
0.1
96.612
94.632
94.124
93.935
92.010
96.212
2.001
0.2
96.952
94.965
94.455
94.266
92.333
96.551
2.008
1
131.094
128.407
127.717
127.462
124.849
130.552
2.715
2
222.635
218.071
216.900
216.467
214.194
219.550
2.456
5
403.600
395.327
393.204
392.418
390.260
394.083
2.069


## 5.3.2. Randomly Generated Application Graphs

As shown in Figures14–16, randomly generated DAGs are used to evaluate the performance of DRSCRO, TMSCRO, DMSCRO, and HEFT in these experiments. And the details of these experimental results are listed in Tables 9–11.Table 9
Experiment results for random graphs under different processor numbers; task number is 50 and CCR = 0.2.
The number of processors
HEFT(average makespan)
DMSCRO(average makespan)
TMSCRO(average makespan)
DRSCRO(average makespan)
DRSCRO(best
makespan)
DRSCRO(worst makespan)
DRSCRO(variance)
4
149.400
146.337
145.552
145.261
142.283
148.782
3.094
8
119.511
117.061
116.433
116.200
113.818
119.017
2.475
16
119.473
117.024
116.396
116.163
113.782
118.979
2.474
32
119.468
115.550
114.929
114.700
112.348
117.480
2.443Table 10
Experiment results for random graphs under different task numbers; processors number is 32 and CCR = 10.
The number of tasks
HEFT(average makespan)
DMSCRO(average makespan)
TMSCRO(average makespan)
DRSCRO(average makespan)
DRSCRO(best
makespan)
DRSCRO(worst makespan)
DRSCRO(variance)
10
714.484
706.149
699.100
690.708
688.982
693.638
2.025
20
1100.918
1089.685
1080.428
1069.082
1066.410
1071.479
2.619
50
1666.373
1662.543
1649.988
1634.230
1633.415
1636.261
1.165Table 11
Experiment results of DRSCRO for the random graph under different CCRs; the task number is 50.
Value of CCR
Processors number is 4
Processors number is 8
Processors number is 16
Processors number is 32
0.1
145.093
116.068
116.058
114.592
0.2
145.261
116.200
116.163
114.700
1
153.248
120.228
119.511
118.534
2
194.401
166.014
164.246
162.292
5
508.759
498.427
492.049
487.830Figure 14
Average makespan for random graphs under different processor numbers; task number is 50 and CCR = 0.2.Figure 15
Average makespan for random graphs under different task numbers; processors number is 32 and CCR = 10.Figure 16
Average makespan of DRSCRO for the random graph under different CCRs; the task number is 50.Figure14 shows the performance on the experimental results of these four algorithms with the processor number increasing. As shown in Figure 14, DRSCRO always outperforms TMSCRO, DMSCRO, and HEFT as the number of processors increases. Figure 15 shows that DMSCRO has better performance than the other three algorithms as the task number increases. The reasons for these are similar to those explained in the third paragraph of Section 5.3.1. Figure 16 shows themakespan on average with CCR values increasing. It can be seem that the averagemakespan increases rapidly with the increasing of the value of CCR. As shown in Figure 16, themakespan on average increases rapidly when the value of CCR rises. It is the fact that the DAG becomes more communication-intensive with CCR increasing which leads to the processors staying in the idle state for longer.


## 5.4. Convergence Tests

In this section, the convergence experiments are conducted to show the change ofmakespan among DRSCRO, TMSCRO, and DMSCRO. The convergence traces and significant tests are to further reveal the differences between DRSCRO and the other two algorithms. In these experiments, as suggested in [27], the stopping criteria of these three algorithms are that the total running time reaches a setting value (e.g., 180 s). Under the consideration of comparability, the beginning of the time counting of DRSCRO is set as the start of the global optimization phase processing. In the first extensive test bed, themakespan is averaged over 10 independent runs, while in the second extensive test bed themakespan is averaged over 30 different random graph running instances.


### 5.4.1. Convergence Trace

The convergence traces of DRSCRO, TMSCRO, and DMSCRO for processing the molecular dynamics code and Gaussian elimination are plotted in Figures17 and 18, respectively. Figures 19–21 show the convergence traces when processing the randomly generated DAG sets, of which each contains 10, 20, and 50 tasks, respectively. As shown in Figures 17–21, it can be observed that the convergence traces of these three algorithms have obvious differences. And the DRSCRO converges faster than the other two algorithms in every case. The reason for the better rate of convergence of DRSCRO is as presented in the last paragraph of Section 4.6 (i.e., DRSCRO takes the advantage of its double-reaction structure to obtain a better super molecule for accelerating convergence). Even though the VNS algorithm adds the time cost in each iteration, the enhanced optimization capability of DRSCRO also makes it obtain a better coverage rate than TMSCRO and DMSCRO. The simulation experimental results show that DRSCRO converges faster than TMSCRO by 19.4% on average (by 29.3% in the best case) and faster than DMSCRO by 33.9% on average (by 41.2% in the best case).Figure 17
Convergence trace for the molecular dynamics code; CCR = 1 and the number of processors is 16.Figure 18
Convergence trace for Gaussian elimination; CCR = 0.2 and the number of processors is 8.Figure 19
Convergence trace for the set of the randomly generated DAGs with 10 tasks.Figure 20
Convergence trace for the set of the randomly generated DAGs with 20 tasks.Figure 21
Convergence trace for the set of the randomly generated DAGs with 50 tasks.Moreover, the statistical analysis based on the average values achieved is also presented in Section5.4.2, to prove that DRSCRO outperforms the other CRO-based algorithms for DAG scheduling from a statistical point of view.


### 5.4.2. Significant Tests

Statistical analysis is necessary for the average coverage rates obtained in all cases by DRSCRO, TMSCRO, and DMSCRO, which are metaheuristic methods, in order to find significant differences among these results. Nonparametric tests according to the recommendations in [40] are specifically considered to be used, since the experimental results may present neither normal distribution nor variance homogeneity. Therefore, the Friedman test and the Quade test are applied to check whether significant differences exist in the performance between these three algorithms. A significance level α = 0.05 is used in all statistical tests.Tables12 and 13, respectively, list the test results of the Friedman test and the Quade test, which both reject the null hypothesis of equivalent performance. In both of these two tests, our proposed DRSCRO is not only compared against all the algorithms but also compared against the remaining ones as the control method. The results in Tables 12 and 13 validate the significant differences α in the performance of DRSCRO, TMSCRO, and DMSCRO.Table 12
Results of Friedman tests,α
=
0.05.
Method
Algorithm
p value
Hypothesis
Friedman test
DRSCRO, DMSCRO
2.53
E
-
02
Rejected
DRSCRO, TMSCRO
2.53
E
-
02
Rejected
DRSCRO, DMSCRO, TMSCRO
6.70
E
-
03
RejectedTable 13
Results of Quade tests,α
=
0.05.
Method
Algorithm
p value
Hypothesis
Quade test
DRSCRO, DMSCRO
1.32
E
-
02
Rejected
DRSCRO, TMSCRO
1.32
E
-
02
Rejected
DRSCRO, DMSCRO, TMSCRO
1.09
E
-
03
RejectedIn sum, it could be concluded that DRSCRO, which is the control algorithm, statistically outperforms the other CRO-based DAG scheduling algorithm on coverage rate with a significant level of 0.05.


## 5.4.1. Convergence Trace

The convergence traces of DRSCRO, TMSCRO, and DMSCRO for processing the molecular dynamics code and Gaussian elimination are plotted in Figures17 and 18, respectively. Figures 19–21 show the convergence traces when processing the randomly generated DAG sets, of which each contains 10, 20, and 50 tasks, respectively. As shown in Figures 17–21, it can be observed that the convergence traces of these three algorithms have obvious differences. And the DRSCRO converges faster than the other two algorithms in every case. The reason for the better rate of convergence of DRSCRO is as presented in the last paragraph of Section 4.6 (i.e., DRSCRO takes the advantage of its double-reaction structure to obtain a better super molecule for accelerating convergence). Even though the VNS algorithm adds the time cost in each iteration, the enhanced optimization capability of DRSCRO also makes it obtain a better coverage rate than TMSCRO and DMSCRO. The simulation experimental results show that DRSCRO converges faster than TMSCRO by 19.4% on average (by 29.3% in the best case) and faster than DMSCRO by 33.9% on average (by 41.2% in the best case).Figure 17
Convergence trace for the molecular dynamics code; CCR = 1 and the number of processors is 16.Figure 18
Convergence trace for Gaussian elimination; CCR = 0.2 and the number of processors is 8.Figure 19
Convergence trace for the set of the randomly generated DAGs with 10 tasks.Figure 20
Convergence trace for the set of the randomly generated DAGs with 20 tasks.Figure 21
Convergence trace for the set of the randomly generated DAGs with 50 tasks.Moreover, the statistical analysis based on the average values achieved is also presented in Section5.4.2, to prove that DRSCRO outperforms the other CRO-based algorithms for DAG scheduling from a statistical point of view.


## 5.4.2. Significant Tests

Statistical analysis is necessary for the average coverage rates obtained in all cases by DRSCRO, TMSCRO, and DMSCRO, which are metaheuristic methods, in order to find significant differences among these results. Nonparametric tests according to the recommendations in [40] are specifically considered to be used, since the experimental results may present neither normal distribution nor variance homogeneity. Therefore, the Friedman test and the Quade test are applied to check whether significant differences exist in the performance between these three algorithms. A significance level α = 0.05 is used in all statistical tests.Tables12 and 13, respectively, list the test results of the Friedman test and the Quade test, which both reject the null hypothesis of equivalent performance. In both of these two tests, our proposed DRSCRO is not only compared against all the algorithms but also compared against the remaining ones as the control method. The results in Tables 12 and 13 validate the significant differences α in the performance of DRSCRO, TMSCRO, and DMSCRO.Table 12
Results of Friedman tests,α
=
0.05.
Method
Algorithm
p value
Hypothesis
Friedman test
DRSCRO, DMSCRO
2.53
E
-
02
Rejected
DRSCRO, TMSCRO
2.53
E
-
02
Rejected
DRSCRO, DMSCRO, TMSCRO
6.70
E
-
03
RejectedTable 13
Results of Quade tests,α
=
0.05.
Method
Algorithm
p value
Hypothesis
Quade test
DRSCRO, DMSCRO
1.32
E
-
02
Rejected
DRSCRO, TMSCRO
1.32
E
-
02
Rejected
DRSCRO, DMSCRO, TMSCRO
1.09
E
-
03
RejectedIn sum, it could be concluded that DRSCRO, which is the control algorithm, statistically outperforms the other CRO-based DAG scheduling algorithm on coverage rate with a significant level of 0.05.


## 6. Discussion

The experimental results ofmakespan tests show that the performance of DRSCRO is very similar to the other similar kinds of metaheuristic algorithms because when averaged over all possible fitness functions, each well-designed metaheuristic algorithm has the same performance for searching optimal solutions, according to No-Free-Lunch Theorem. However, the proposed DRSCRO can achieve better performance and find good solutions faster than the other similar kinds of metaheuristic algorithms as the experimental results of convergence tests, and the reason for it, as the analysis in the last paragraph in Section 4.6, is that DRSCRO has a better super molecule creation by metaheuristic method, and under the consideration of the optimization of scheduling order and processor assignment, DRSCRO takes the advantages of VNS algorithm in the global optimization phase to improve the optimization capability. A load balance neighborhood structure is also applied in the ineffective reaction operator for a better intensification capability. The new processor selection model utilized in the neighborhood structures also promotes the efficiency of VNS algorithm.


## 7. Conclusion and Future Study

An algorithm named Double-Reaction-Structured CRO (DRSCRO) is developed for DAG scheduling on heterogeneous systems in this paper. DRSCRO includes two reaction phases, one for super molecule selection and another for global optimization. The phase of super molecule selection is used to obtain a super molecule by the metaheuristic method for better convergence rate, different from other CRO-based algorithms for DAG scheduling on heterogeneous systems. In addition, to promote the intersection capability of DRSCRO, the VNS algorithm, which is with a new model for processor selection utilized in the neighborhood structures, is used as the initialization of global optimization phase, and the load balance neighborhood structure of VNS is also applied in the ineffective reaction operator. The experimental results show that DRSCRO can also achieve a higher speedup than the other CRO-based algorithms as far as we know. And DRSCRO algorithm can also obtain better performance on averagemakespan in some cases.In future work, we will analyze the parameter sensitivity of DRSCRO for promoting its activeness. Moreover, to make the proposed algorithm more practical, DRSCRO will be also extended to aim at two main objectives, such as (1) minimization of schedule length (time domain) and (2) minimization of number of used processors (resource domain).



---

*Source: 396582-2015-12-28.xml*