A Multiobjective Computation Offloading Algorithm

for Mobile Edge Computing

Fuhong Song, Huanlai Xing, Shouxi Luo, Dawei Zhan, Penglin Dai, Rong Qu

Abstract—In mobile edge computing (MEC), smart mobile becoming increasingly powerful in terms of computing
devices (SMDs) with limited computation resources and battery capability, they are, however, still not able to support
lifetime can offload their computing-intensive tasks to MEC computing-intensive applications. On the one hand, SMDs
servers, thus to enhance the computing capability and reduce the with limited computing capability may cause high latency,
energy consumption of SMDs. Nevertheless, offloading tasks to
the edge incurs additional transmission time and thus higher thus failing to meet the required quality of service (QoS)
execution delay. This paper studies the trade-off between the demand. On the other hand, high battery consumption by
completion time of applications and the energy consumption of computing-intensive applications may also significantly
SMDs in MEC networks. The problem is formulated as a degrade the quality of experience (QoE) for end users.
multiobjective computation offloading problem (MCOP), where With more computing and storage resources in cloud
the task precedence, i.e. ordering of tasks in SMD applications, is servers, mobile cloud computing (MCC) [3] has been
introduced as a new constraint in the MCOP. An improved
multiobjective evolutionary algorithm based on decomposition envisioned as a potential solution to deal with the above
(MOEA/D) with two performance enhancing schemes is proposed. mentioned problems. MCC migrates computational tasks to
1) The problem-specific population initialization scheme uses a cloud servers, thus to reduce the computational burden and
latency-based execution location initialization method to initialize energy consumption of local SMDs. This is referred to as the
the execution location (i.e. either local SMD or MEC server) for computation offloading problem (COP). Nevertheless, cloud
each task. 2) The dynamic voltage and frequency scaling based servers are usually geographically faraway from SMDs,
energy conservation scheme helps to decrease the energy
consumption without increasing the completion time of resulting into high transmission delay and low response speed.
applications. The simulation results clearly demonstrate that the Obviously, MCC is not suitable for scenarios involving
proposed algorithm outperforms a number of state-of-the-art delay-sensitive applications, as QoE cannot be properly
heuristics and meta-heuristics in terms of the convergence and guaranteed. Actually, the computation offloading in MCC is
diversity of the obtained nondominated solutions. only suitable for delay-tolerant and computation-intensive
applications, such as online social networks, mobile
Index Terms—Computation offloading, dynamic voltage and e-commerce, remote learning, etc. On the other hand, MEC
frequency scaling, mobile edge computing, multiobjective relocates cloud computing resources to the edge of networks
evolutionary algorithm.
in close proximity to SMDs, ensuring lower end-to-end delay
and faster response [4][5][6]. The computation offloading in
I. INTRODUCTION
MEC is more appropriate for supporting delay-sensitive and

W ITH the rapid development of mobile communication

technologies, smart mobile devices (SMDs) including
smartphones, tablets, laptops and smartwatches have become
computation-intensive applications, such as virtual reality,
autonomous driving, and interactive online games and so on.
With the demand for delay-sensitive applications ever
the main platforms to support various mobile applications increasing, it is hence more practical to study the COP
such as banking, education, healthcare, travel, business, games, problem in MEC.
face recognition, augmented reality, and natural language In general, MEC servers are lightweight regarding the
processing, etc. [1][2]. Nowadays, although SMDs are computing capability, because their economic and scalable
deployment should be considered. It is thus not feasible to
offload all computational tasks from SMDs to the MEC severs.
Manuscript received December 7, 2019; This work was supported in part by
China Postdoctoral Science Foundation (2019M663552), National Natural More data transmission over communication channels also
Science Foundation of China (No. 61802319), the Fundamental Research leads to higher transmission delay. To avoid overloading,
Funds for the Central Universities, China Scholarship Council, P. R. China, SMDs should offload appropriate amount of computational
and University of Nottingham, United Kingdom. (Corresponding author:
tasks to MEC servers, which also helps to reduce the battery
Huanlai Xing.)
F. Song, H. Xing, S. Luo, D. Zhan, and P. Dai are with the School of consumption of SMDs.
Information Science and Technology, Southwest Jiaotong University, In MEC, the completion time of applications and the energy
Chengdu 611756, China (e-mail: [email protected]; consumption of SMDs conflict with each other. In other words,
[email protected]; [email protected]; [email protected];
improving one of them would deteriorate the other. The
[email protected]).
R. Qu is with the School of Computer Science, University of Nottingham, computational problem of reasonably offloading tasks between
Nottingham NG8 1BB, United Kingdom (e-mail: [email protected]). SMDs and MEC servers, i.e. COP, has become one of the most
challenging research topics in the area of MEC.
 In this paper, we model the computation offloading in MEC process to determine execution locations for tasks. A
as a multiobjective computation offloading problem (MCOP). transmission policy was devised based on the queueing state
A multiobjective evolutionary algorithm based on of task buffer, the transmission unit state and the local
decomposition (MOEA/D) is adopted for solving it [7]. processing unit state. The average completion time of tasks
The main contributions are summarized as follows: was minimized by an efficient one-dimensional search
1) A MCOP problem in MEC environment is modeled, algorithm. Mao et al. [10] developed a green MEC system
where the average completion time of applications and with energy harvesting and proposed a low complexity online
the average energy consumption of SMDs are defined algorithm, i.e. Lyapunov optimization based dynamic
as two objectives. On each SMD, only one application, computation offloading algorithm (LODCO) to reduce the
with an ordered list of tasks, runs at a time. To our execution latency by jointly determining the offloading
knowledge, this is the first model in MEC considering decision, the CPU-cycle frequency and the transmission power.
the task-precedence constraints within each application Yang et al. [11] investigated the scheduling problem of
in MCOP. multi-user computing partitioning and cloud resource
2) An improved MOEA/D algorithm with two computing offloading. The average completion time of
performance-enhancing schemes, namely multiple users, rather than a single user, was minimized by an
MOEA/D-MCOP, is proposed. The first scheme, a offline heuristic algorithm. Dinh et al. [12] took both fixed and
problem-specific population initialization scheme elastic CPU frequencies of SMDs into account. A semidefinite
generates a set of high-quality solutions to MCOP, relaxation (SDR) based approach was proposed to minimize
where a latency-based execution location initialization the execution time of all tasks.
(LELI) method is designed to determine the initial Energy consumption of SMDs is also a main concern in
execution location (i.e. local SMD or MEC server) for COP. Muñoz et al. [13] proposed a framework to jointly
each task, guiding the exploration towards promising optimize the usage of computational and radio resources,
regions in the search space. The second scheme, a where multiple antennas were used in SMDs and femto access
dynamic voltage and frequency scaling based energy points. The energy consumption was minimized by optimizing
conservation scheme, aims at reducing the energy the communication time and the amount of data offloaded to a
consumption of SMDs. femto access point. Tong et al. [14] aimed at obtaining a
3) For the new MCOP built in this paper, there exists no trade-off between energy consumption of SMDs and QoS of
benchmark instance in the literature. A set of test applications. An application-aware wireless transmission
instances are thus generated to verify the performance scheduling algorithm was presented to minimize the energy
of the proposed MOEA/D-MCOP, and presented to the consumption, subject to the application deadline. Masoudi et
research community for further investigations on this al. [15] considered three practical constraints, i.e. the backhaul
emerging topic. The simulation results clearly capacity, the maximum tolerable delay, and the interference
demonstrate that the proposed algorithm obtains level. They proposed a joint power allocation and
high-quality nondominated solutions and outperforms decision-making algorithm to minimize the power
a number of state-of-the-art MOEAs and heuristic consumption of SMDs. Wang et al. [16] presented an
algorithms against several evaluation criteria. integrated framework for computation offloading and
The remainder of this paper is organized as follows. The interference management, where the physical resource block,
related work is introduced in Section II. In Section III, we the computation offloading decision and the computation
present the MEC system model and formulate the bi-objective resource allocation were taken into consideration for reducing
MCOP problem. Section IV briefly reviews the multiobjective energy consumption. Mahmoodi et al. [17] modeled the COP
optimization problem and the original MOEA/D. The as a linear optimization problem on energy consumption,
proposed MOEA/D-MCOP is explained in Section V. The where the communication delay, the overall application
simulations and performance analysis are discussed in Section execution time and the component precedence ordering were
VI. Section VII presents the conclusions and future work. taken into account. Xu et al. [18] proposed an energy-aware
computation offloading scheme, where simple additive
II. RELATED WORK weighting and multiple criteria decision marking were used to
The COP problem has received an increasing research determine an optimal solution. In [19], an energy-efficient
attention from both academia and industry [8]. In general, COP problem in 5G MEC was investigated, considering
completion time and energy consumption are considered as fronthaul and backhaul links. The overall energy consumption
typical criteria for COP performance evaluation, i.e. as was minimized by an artificial fish swarm algorithm, subject
objectives of minimizing the completion time, minimizing the to the completion time demand. In [20], a security and energy
energy consumption, and minimizing both of them at the same efficient computation offloading scheme based on genetic
time. algorithm was presented. Guo et al. [21] formulated a
When a SMD offloads computing-intensive tasks to a MEC cloud-MEC collaborative computation offloading problem.
server, the completion time is one of the important criteria for The authors presented an approximation collaborative
QoE evaluation. Liu et al. [9] adopted Markov decision computation offloading scheme to minimize the energy
consumption of all mobile devices. Zhang et al. [22] proposed
a collaborative task execution scheduling algorithm to solve This presents a practical constraint in many applications. For
the delay-constrained workflow scheduling problem in MCC. example, in any face recognition system, object detection
The energy consumption of SMDs was minimized, with the cannot be launched before the completion of video/image
application delay deadline satisfied. Guo et al. [23] studied an collection. This motivates us to model a new MCOP with a
energy-efficient computation offloading management scheme realistic task precedence constraint.
in MEC with small cell networks. A hierarchical GA and Most of the existing algorithms for MCOP evaluate
PSO-based computation algorithm was developed to minimize solutions using weighted sum of multiple objectives. The fact
the energy consumption of all mobile devices. Kuang et al. [24] that the objectives conflict with each other in MCOP has been
formulated a multi-user offloading game problem in the omitted, thus a single solution cannot be optimized against all
OFDMA communication system. The authors presented an objectives. In research, NSGA-II has thus been employed to
offloading game mechanism to maximize the number of solve MCOP [30]. As a multiobjective evolutionary algorithm
energy-saving devices, including a beneficial offloading (MOEA), NSGA-II has unveiled promising advantage, i.e.
threshold algorithm and a beneficial offloading group providing a set of nondominated solutions for decision making
algorithm. It minimized the energy cost while considering the in a single run. Nevertheless, as we observe in this paper,
application’s deadline and risk probability. Lin et al. [25] NSGA-II not only is likely to be stuck into local optima, but
applied dynamic voltage and frequency scaling (DVFS) to also converges slowly. MOEA/D decomposes a multiobjective
minimize SMD energy consumption in MCC environment, optimization problem (MOP) into a number of scalar
where task precedence requirements within any application optimization subproblems and solves each of them at the same
were satisfied. However, the authors assumed that there was a time. It has been reported that MOEA/D achieves better
single SMD in their MCC system, which was impractical. In optimization performance with lower computational overhead,
real world applications, multiple SMDs are active at the same compared with NSGA-II [31][32][33]. This motivates us to
time, and some of them may offload their computation tasks to investigate MOEA/D to address the newly modeled MCOP in
cloud. this paper.
On the one hand, a smaller completion time requires more
tasks to be executed on local SMDs, which leads to higher III. SYSTEM MODEL AND PROBLEM FORMULATION
battery consumption. On the other hand, to keep the battery
consumption at a lower level requires more computations to be A. System Overview
offloaded to the edge. Some researchers hence treated the A MEC system consists of one macro eNodeB node (MeNB)
completion time of applications and the energy consumption and a set of small eNodeB nodes (SeNBs) [26], as shown in
of SMDs as equally important, i.e. minimizing them Fig. 1. MeNB is equipped with a MEC server capable of
simultaneously. Zhang et al. [26] considered single and executing multiple computing-intensive tasks in parallel. The
multicell MEC network scenarios, and proposed an integrated MEC server can dynamically allocate its computing resources
framework for computation offloading and resource allocation. to execute tasks offloaded from different SMDs. All SeNBs
An iterative search algorithm was developed to strike a are connected to MeNB via wired lines. Each SeNB forms a
balance between execution time and energy consumption. small cell, connecting to a set of SMDs via wireless channels.
Peng et al. [27] developed an optimal task scheduling scheme Each task in an application can be run either on local SMDs
for SMDs using the DVFS technology and the whale or the MEC server. Computation offloading incurs when some
optimization algorithm. Considering the operating CPU-cycle tasks are offloaded from SMDs to the MEC server, and the
frequency, the task execution position and sequence, this data delivery relies on relay of SeNB and MeNB.
scheme could optimize both of the objectives simultaneously.
Guo et al. [28] studied energy-efficient COP subject to the
application execution latency. An energy-efficient dynamic
offloading and resource scheduling (eDors) scheme was
proposed to reduce the execution latency and the energy
consumption. Wang et al. [29] modeled an energy-efficient
M/M/n-based COP with both of the objectives. A distributed
algorithm considering transmission power allocation, strategy
selection and clock frequency control was proposed. Cui et al.
[30] investigated the tradeoff between the completion time and
the energy consumption subject to end user requirements, and
presented an improved fast and elitist nondominated sorting
genetic algorithm (NSGA-II).
In summary, considering the completion time and energy
consumption as two objectives represents one of the main
streams in the current research on MEC computation Fig. 1. An example MEC system.
offloading. To the best of our knowledge, however, task
precedence has not been considered in the existing MCOPs.
 generated by all its immediate predecessors in pre(vi,j,k). The
main notations used in this paper are summarized in Table I.

TABLE I
SUMMARY OF THE MAIN NOTATIONS
Notation Definition
Btotal Total bandwidth offered by the MEC system
ci,j,k Number of CPU cycles required to perform task vi,j,k
di,j,k Input data size of task vi,j,k
e(vi,j,k, vi,j,l) Task-precedence constraint from task vi,j,k to task vi,j,l
Ei,j Set of the task precedence constraints of application Gi,j
F Computing capability of the MEC server
f i ,actual
j ,h Actual computing frequency on the h-th core of SMD Ui,j
Fig. 2. An example DAG of an application.
f max Maximum computing frequency on the h-th core of SMD
i , j ,h
Ui,j
There are two commonly used structural representation Gi,j Application (task graph) to be executed on SMD Ui,j
methods to denote an application, namely the graph-based gi,j Channel gain between SMD Ui,j and SeNB  i
method [34] and the language-based method [35]. In particular, H Number of heterogeneous cores of a SMD
the graph-based method includes directed acyclic graph (DAG) Ii,j Interference at the SMD Ui,j
Li,j Execution location vector associated with application Gi,j
[20][25][27][28][36] and Petri Net [37]. DAG based model is
loci,j,k Execution location of task vi,j,k
one of the most popular methods. Therefore, each application M Number of the computing frequency levels on a core
on a SMD is modeled as a DAG task structure. Fig. 2 shows Number of SMDs in the i-th small cell associated with
N iSMD
an example DAG of an application. SeNB i
SMD
In this paper, time sharing is adopted in the MEC system N total Total number of SMDs in the MEC system
and the minimum time unit is referred to as time interval (e.g. N task
total Total number of tasks in the MEC system
several seconds). We assume that in any time interval, for any Nchannel Number of channels offered by the MEC system
SMD, there is only one application being executed. However, Ni,j Total number of tasks in application Gi,j
any SMD is allowed to run different applications in different Oi,j Execution order vector associated with application Gi,j
oi,j,k Output data size of task vi,j,k
time intervals, enabling co-existence of multiple applications.
ui,j,k The k-th task to be executed in Oi,j
piactual
, j ,h Actual power consumption of the h-th core of SMD Ui,j
B. System Model
p max Maximum power consumption of the h-th core of SMD
For the MeNB, its associated MEC server is with a i , j ,h
Ui,j
computing capability of F. Denote the i-th SeNB as i, i = pirxd
,j Power consumption when SMD Ui,j receives data
1,…,S, where S is the number of SeNBs. Let N iSMD and Ui,j be p txd
i, j Power consumption when SMD Ui,j offloads tasks
the number of SMDs and the j-th SMD in the i-th small cell pre(vi,j,k) Set of the immediate predecessors of task vi,j,k
associated with i, respectively. Ri,j Achievable uplink transmission rate of SMD Ui,j
S Number of SeNBs in the MEC system
Denote the application to be executed on SMD Ui,j by a
Computation offloading solution associated with
DAG Gi,j = (Vi,j, Ei,j), where Vi,j and Ei,j are the task and SOL(Gi,j)
application Gi,j
precedence constraint sets, respectively, i = 1,…,S, and j = SOL(i) Computation offloading solution associated with SeNB i
1,…, N iSMD . An application is also referred to as a task graph suc(vi,j,k) Set of the immediate successors of task vi,j,k
The j-th SMD in the i-th small cell associated with SeNB
Gi,j, which is composed of Ni,j tasks, where Ni,j = |Vi,j|. Let vi,j,k Ui,j
i
∈ Vi,j be the k-th task in task set Vi,j, k = 1,…,Ni,j. Edge e(vi,j,k, Vi,j Set of the tasks in application Gi,j
vi,j,l) ∈ Ei,j defines the task-precedence constraint from task vi,j,k vi,j,k The k-th task in application Gi,j
x A solution to the MCOP
to task vi,j,l, meaning vi,j,l cannot be executed until vi,j,k is αt The t-th frequency scaling factor
completed. i The i-th SeNB in the MEC system
Let pre(vi,j,k) and suc(vi,j,k) be the sets of the immediate σ2 Noise power
predecessors and successors of task vi,j,k, respectively. For a ω Bandwidth of a wireless channel
task graph Gi,j, denote the start and end tasks by vi,j,start and
vi,j,end, respectively. Taking the task graph in Fig. 2 as an
example, for task v6, its associated sets of immediate C. Communication Model
predecessors and successors are pre(v6) = {v2, v3, v4} and When a task is selected for offloading, its associated input
suc(v6) = {v7}; v1 and v7 are the start and end tasks, data is transmitted to the MEC server via SeNB and MeNB.
respectively. The transmission delay from SeNB to MEC server via wired
Each task vi,j,k is modeled as a 3-tuple set vi,j,k = (ci,j,k, di,j,k, connections is usually trivial, thus is ignored. The
oi,j,k), where ci,j,k is the number of CPU cycles required to transmission delay between the corresponding SMD and
perform vi,j,k, and di,j,k and oi,j,k are the input and output data SeNB is considered in the model.
sizes of vi,j,k, respectively. The input data of vi,j,k includes the Let Btotal and Nchannel be the total bandwidth and the number
input parameters, the program code, and the output data of channels offered by the MEC system, respectively. Each
channel is of a bandwidth ω = Btotal / Nchannel. Each SMD uses tasks, and pirxd
,j is the power consumption of Ui,j when
one of the Nchannel channels for data offloading. To guarantee
receiving data from its associated SeNB.
that all SMDs within the same small cell can perform
Assume there are M frequency scaling factors, i.e. α1,…,αM,
independent computation offloading, it is assumed that Nchannel
for an arbitrary core in an arbitrary SMD, where
is no less than the maximum number of SMDs allowed in a
0<α1<…<αt<…<αM = 1 [25]. The actual computing frequency
small cell. If two SMDs from neighboring small cells use the
that the h-th core of SMD Ui,j is working at can be defined as
same channel to transmit data, interference occurs and the
transmission rate is reduced. f i ,actual
j,h   t  f i ,max
j , h , t = 1,…,M. The actual power consumption
actual 
According to the Shannon-Harley theorem, it is possible of the h-th core of Ui,j, piactual
, j , h , is equal to ai , j , h  ( f i , j , h ) ,
that no errors occur in a channel with limited bandwidth and
where γ is a constant in the range of [2, 3] and ai , j , h is a
Gaussian white noise interference if transmitting information
at the theoretical maximum transmission rate. In this paper, we coefficient associated with the chip structure.
min
set the achievable uplink transmission rate in a channel to the Let TSMD , h (vi , j , k ) denote the minimum execution time of
theoretical maximum transmission rate of that channel. task vi,j,k if vi,j,k is executed on the h-th core of SMD Ui,j, at the
Assume each wireless channel is symmetric, i.e. the maximum computing frequency f i ,max min
j , h . TSMD , h (vi , j , k ) depends
achievable uplink and downlink transmission rates are the
same. When SMD Ui,j offloads tasks to the MEC server, the on the number of CPU cycles required to perform vi,j,k, ci,j,k,
achievable uplink transmission rate Ri,j is calculated using Eq. and the maximum computing frequency, f i ,max
j , h . Then, the

(1). actual execution time of vi,j,k on the h-th core TSMD , h (vi , j , k ) is
 pitxd  obtained using Eq. (3) [25].
, j gi , j
Ri , j   log 2 1  2  (1)
   Ii, j min
  TSMD , h (vi , j , k )  TSMD , h (vi , j , k ) /  t

c (3)
where ω is the channel bandwidth. pitxd
,j is the power  max
i, j,k

f i, j,h  t
consumption of Ui,j when tasks are offloaded to the MEC
server. gi,j is the channel gain between SMD Ui,j and SeNB i. If task vi,j,k is executed locally on the h-th core of SMD Ui,j,
σ2 is the noise power. Ii,j is the interference parameter its actual energy consumption ESMD actual
, h (vi , j , k ) is obtained via
associated with SMD Ui,j indicating how severe the channel
sharing is, as defined in Eq. (2). Eq. (4), according to [25].
actual actual
S NlSMD ESMD , h (vi , j , k )  pi , j , h  TSMD , h (vi , j , k )
txd
Ii, j   
l 1, l  i k 1
( i , j ),( l , k ) p gi ,(l , k )
l,k (2)
 ai , j , h  ( f i ,actual  min
j , h )  (TSMD , h (vi , j , k ) /  t )

 ai , j , h  ( t  fi ,max min
j , h )  (TSMD , h (vi , j , k ) /  t )
where λ(i,j),(l,k) ∈ {0,1} is a channel sharing coefficient. λ(i,j),(l,k) (4)
= 1 represents that the same channel is being shared by both  ( t ) 1  ai , j , h  ( f i ,max  min
j , h )  TSMD , h (vi , j , k )
Ui,j and Ul,k, and λ(i,j),(l,k) = 0 otherwise. pltxd
, k is the power  ( t ) 1  ESMD
max
, h (vi , j , k )
consumption of Ul,k when offloading tasks, and gi,(l,k) is the
 ( t ) 1  pimax min
, j , h  TSMD , h (vi , j , k )
channel gain between Ul,k and i, where Ul,k is associated with
SeNB l, l, i ∈ {1,…,S} and l ≠ i. max
where ESMD , h (vi , j , k ) is the maximum energy consumption if

task vi,j,k is executed on the h-th core of SMD Ui,j at the

D. Local Computing
maximum computing frequency.
In this paper, the local computing model is based on the Before executing task vi,j,k, execution of all its immediate
local scheduling model in MCC [25], where the DVFS predecessors must be completed. If vi,j,k is to be launched on a
technique is enabled. For each SMD in the MEC system, core of SMD Ui,j, the ready time for executing it is related to
assume there are H heterogeneous cores in its processor. This the completion times of its immediate predecessors in pre(vi,j,k).
enables the processor execute its tasks in parallel if there are That is, the ready time for executing vi,j,k, RTSMD exe
(vi , j , k ) ,
no task-precedence constraints among them. All cores are
DVFS enabled, allowing each core to run at different depends on the maximum completion time of all tasks in
frequency levels at different times. An arbitrary SMD Ui,j can pre(vi,j,k). Assume vi,j,l ∈ pre(vi,j,k) is an immediate predecessor
be defined as a 4-tuple set U i , j  ( f i ,max max txd rxd of vi,j,k which can be executed on either the local SMD or the
j , h , pi , j , h , pi , j , pi , j ) , exe
MEC server. Let CTSMD (vi , j ,l ) be the completion time of task
where f i ,max
j , h is the maximum computing frequency on the rxd
vi,j,l if it is executed on SMD Ui,j. Let CTSMD (vi , j ,l ) be the
h-th core of Ui,j, h = 1,…,H, pimax
, j , h is the maximum power
completion time that Ui,j finishes receiving the output data of
consumption when the h-th core is working at frequency vi,j,l from wireless channel if vi,j,l is executed on the MEC
txd
f i ,max
j , h , pi , j is the power consumption of Ui,j when offloading
exe
server. The definition of RTSMD (vi , j , k ) is expressed in Eq. (5).
 exe exe
RTSMD (vi , j , k )  Let CTMEC (vi , j ,l ) be the completion time of vi,j,l ∈ pre(vi,j,k)
(5) if vi,j,l is executed on the MEC server. The ready time for
max max CTSMD
exe rxd
(vi , j ,l ), CTSMD (vi , j ,l )
vi , j ,l  pre ( vi , j ,k ) exe
executing vi,j,k on the MEC server, RTMEC (vi , j , k ) , is defined in
exe
where CTSMD (vi , j ,l )  0 means vi,j,l is offloaded to the MEC Eq. (9).
rxd exe
server and CTSMD (vi , j ,l )  0 means vi,j,l is executed locally. So, RTMEC (vi , j , k ) 
exe rxd txd exe (9)
in any case, between CTSMD (vi , j ,l ) and CTSMD (vi , j ,l ) , one of max{CTSMD (vi , j , k ), max CTMEC (vi , j ,l )}
vi , j ,l  pre ( vi , j ,k )
them is set to 0.
exe
If task vi,j,k is selected to run on a core of Ui,j, its execution Let TMEC (vi , j , k ) denote the execution time of vi,j,k on the
exe
cannot start before its ready time RTSMD (vi , j , k ) . It is possible MEC server, as defined in Eq. (10).
that vi,j,k is executed sometime after RT exe
(vi , j , k ) , because exe
ci , j , k
SMD TMEC (vi , j , k )  (10)
that core may be busy with executing other tasks at that time. F
exe where ci,j,k is the number of CPU cycles required to execute
Let the start time for executing vi,j,k denoted by STSMD (vi , j , k ) ,
vi,j,k, and F is the computing capability of the MEC server.
exe exe
STSMD (vi , j , k )  RTSMD (vi , j , k ) [25]. The MEC server can start to transmit the output data of vi,j,k
back to Ui,j, immediately after the completion of vi,j,k. Let
txd
E. Edge Computing RTMEC (vi , j , k ) be the ready time for the MEC server to
The edge computing model in this paper is based on the transmit back the output data of vi,j,k, as defined in Eq. (11).
cloud scheduling model in [25]. However, the authors assume txd exe
RTMEC (vi , j , k )  CTMEC (vi , j , k ) (11)
there is only one active SMD in the MCC network, which is
not realistic. We assume there are multiple SMDs in the MEC Let the time duration required to receive the output data of
system, which mimics the demands from the real world. rxd
vi,j,k from the MEC server, denoted by TSMD (vi , j , k ) , as defined
To model the offloading task vi,j,k to the MEC server, let
txd
RTSMD (vi , j , k ) be the ready time for transmitting vi,j,k from Ui,j in Eq. (12).

via wireless channel. If vi,j,k is to be offloaded to the MEC rxd

oi , j , k
txd
TSMD (vi , j , k )  (12)
server, the ready time for transmitting it, RTSMD (vi , j , k ) , Ri , j
depends on the maximum completion time of all tasks in
txd where oi,j,k is the output data size after the execution of vi,j,k.
pre(vi,j,k). Let CTSMD (vi , j ,l ) be the completion time that Ui,j In [25], the cloud scheduling model does not consider the
finishes transmitting vi,j,l ∈ pre(vi,j,k) to the MEC server. The energy consumption of SMD Ui,j incurred when receiving the
txd
expression of RTSMD (vi , j , k ) is presented in Eq. (6) [25]. output data of task vi,j,k, which is not practical. In contrast, our
edge computing model takes the energy consumption of
txd
RTSMD (vi , j , k )  receiving the output data from MEC server into consideration,
(6) which helps to accurately estimate the energy consumption.
max max CTSMD
exe txd
(vi , j ,l ), CTSMD (vi , j ,l ) The energy consumption of Ui,j for receiving the output data of
vi , j ,l  pre ( vi , j ,k )
rxd
vi,j,k, ESMD (vi , j , k ) , is defined in Eq. (13), according to
exe
where CTSMD (vi , j ,l )  0 if vi,j,l is offloaded to the MEC server
[22][38].
txd
and CTSMD (vi , j ,l )  0 if vi,j,l is executed locally. rxd
ESMD (vi , j , k )  pirxd rxd
, j  TSMD (vi , j , k ) (13)
Let the time duration required to transmit vi,j,k to the MEC
txd
server be TSMD (vi , j , k ) , as defined in Eq. (7). Taking the task graph in Fig. 2 as an example, we briefly
explain the process of local and edge computing. In the MEC
txd
di , j , k system, there is one SeNB, namely 1, and one SMD
TSMD (vi , j , k )  (7)
Ri , j associated with 1, namely U1,1. The application G1,1 has seven
tasks, i.e. v1,1,k, k = 1,…,7, to be run on U1,1. Suppose U1,1
where di,j,k and Ri,j are the input data size of vi,j,k and the owns three cores (i.e. h = 1,2,3). Table II shows the execution
achievable uplink transmission rate, respectively. time of each task on different cores and the actual execution
If task vi,j,k is offloaded to the MEC server, the energy locations of all tasks. Let loc1,1,k ∈ {1,2,3,4} be the execution
txd
consumption of Ui,j for transmitting this task, ESMD (vi , j , k ) , is location of v1,1,k, k = 1,…,7. If 1 ≤ loc1,1,k ≤ 3, v1,1,k is executed
expressed in Eq. (8). on the loc1,1,k-th core of U1,1. If loc1,1,k = 4, v1,1,k is offloaded to
the MEC server. For simplicity, we set the time duration
txd
ESMD (vi , j , k )  pitxd txd
, j  TSMD (vi , j , k ) (8) required to transmit each task to the MEC server,
txd
TSMD (v1,1, k )  3 , the time duration required to receive the
 rxd
output data of each task from the MEC server , TSMD (v1,1, k )  1 , offloaded to the MEC server, CT (Gi , j ) equals to the time
and the execution time of each task on the MEC server, when the output data of vi,j,end is fully received. Otherwise,
exe
TMEC (v1,1, k )  1 , k = 1,…,7. CT (Gi , j ) equals to the time when the execution of vi,j,end is
over.
TABLE II
EXECUTION TIMES AND LOCATIONS OF ALL TASKS CT (Gi , j ) 
min min min exe rxd
(14)
Task TSMD ,1 TSMD ,2 TSMD ,3 Location  i , j ,end  CT (vi , j , end )  (1   i , j ,end )  CTSMD (vi , j , end )
SMD
v1 1 3 4 3
v2 3 4 5 1 With the obtained completion times of all applications on
v3 1 2 4 4
all SMDs, the average completion time (ACT) of applications
v4 3 5 7 1
v5 2 5 6 2 in the MEC system can be calculated using Eq. (15).
v6 2 4 6 3 SMD
S Ni
v7 1 3 4 4 1
ACT  SMD
N total
  CT (G
i 1 j 1
i, j ) (15)

SMD S
where N total   i 1 NiSMD is the total number of SMDs in the
MEC system.
The average energy consumption (AEC) of all SMDs in the
MEC system can be obtained by Eq. (16).
SMD N
S Ni
1 i, j

AEC  task
N total
   E (v
i 1 j 1 k =1
i, j ,k ) (16)

where
actual
E (vi , j , k )   i , j , k  ESMD , h (vi , j , k ) 
txd rxd
(17)
(1   i , j , k )  ( ESMD (vi , j ,k )  ESMD (vi , j , k ))

task S N SMD
N total   i 1  j i 1 Ni , j is the total number of tasks in the
MEC system. i,j,k = 1 if vi,j,k is executed on SMD Ui,j; i,j,k = 0,
otherwise.
Fig. 3. Task scheduling plan.
The MCOP can be defined as a bi-objective MOP problem,
minimizing ACT in Eq. (15) and AEC in Eq. (16) subject to all
Fig. 3 shows the task scheduling plan according to Table II. task precedence constraints as defined in Eq. (18).
The start time and completion time of task v6 are
exe exe Minimize ( ACT , AEC )
STSMD (v6 )  10 and CTSMD (v6 )  16 , respectively. The Li , j , Oi , j
rxd
completion time of G1,1 , CT (G1,1 )  CT SMD (v7 ) , is 21. s.t.
C1: order (vi , j , k )  order (vi , j ,l ), if e(vi , j , k , vi , j ,l )  Ei , j
F. Problem Formulation exe exe
C2 : CTSMD (vi , j ,l )  RTSMD (vi , j , k ), vi , j ,l  pre(vi , j , k )
The new MCOP model aims to simultaneously minimize rxd exe
the average completion time of applications and the average C3 : CTSMD (vi , j ,l )  RTSMD (vi , j , k ), vi , j ,l  pre(vi , j , k )
energy consumption of SMDs in the above MEC system. txd exe (18)
C4 : CTSMD (vi , j , k )  RTMEC (vi , j , k )
exe rxd
Let CTSMD (v i , j ,end ) and CTSMD (v i , j ,end ) be the completion exe exe
C5 : max CTMEC (vi , j ,l )  RTMEC (vi , j , k )
vi , j ,l  pre ( vi , j ,k )
time for executing the end task vi,j,end in application Gi,j on
SMD Ui,j and that for receiving the output data of vi,j,end via C6 : loci , j , k  {0,1,..., H }, i, j , k
wireless channel, respectively. Let  i , j , end be a binary
where, constraint C1 is the execution order constraint between
variable indicating if vi,j,end is executed on Ui,j or the MEC two tasks, i.e. if e(vi , j , k , vi , j ,l )  Ei , j , task vi , j ,l cannot be
server.  i , j ,end  1 means vi,j,end is executed on Ui,j, and
executed before the completion of task vi , j , k . Constraints C2
 i , j ,end  0 otherwise. The completion time of application Gi,j
and C3 are the local task-precedence constraints, ensuring that
on SMD Ui,j, CT (Gi , j ) , is defined in Eq. (14), which is equal vi , j , k cannot be executed before all its immediate
to the completion time of the end task vi,j,end in Gi,j. If vi,j,end is predecessors are completed. Constraints C4 and C5 are the
edge task-precedence constraints, indicating that vi , j , k cannot B. Original MOEA/D
be executed before it is completely offloaded to the MEC MOEA/D has been applied to various MOPs due to its high
server and all its immediate predecessors are completed on the effectiveness yet low computational cost [31][32][33][40][43]
MEC server. Constraint C6 is a computation offloading [44]. MOEA/D decomposes a MOP into a number of scalar
execution location constraint, specifying where vi , j , k is optimization subproblems (SOSPs) that are simultaneously
optimized in a collaborative and time efficient manner. It
executed, i.e. which core of U i , j or the MEC server.
employs genetic operators to generate new solutions and
obtain a set of nondominated solutions through an evolution
IV. OVERVIEW OF MOP AND MOEA/D process. Three basic methods have been employed in the
literature for decomposition, among which the Tchebycheff
A. MOP method is the mostly used, and adopted in our proposed
A MOP can be defined as Eq. (19). algorithm.
Let  1 ,...,  N P be a set of uniformly spread weighted
 Minimize F ( x )  ( f1 ( x ),..., f m ( x ))T
 (19) vectors, where NP is the number of SOSPs.  i  (1i ,..., mi )
Subject to x   is the weight vector associated with the i-th SOSP, i = 1,…,NP,
m
where x = ( x1 ,..., xn ) is an n-dimension decision vector in where m is the number of objectives, and  j 1
 ij  1 . Let
search space Ω. There are m objective functions in objective z *  ( z1* ,..., z m* ) be the reference point,
vector F(x), where f1(x),…,fm(x) conflict with each other [39]. *
where z  min{ f j ( x ) | x  } , and j = 1,…,m. Based on the
Given two different solutions x1, x2 ∈ Ω, x1 is said to j

dominate x2, if fi(x1) ≤ fi(x2) for all i ∈ {1,…,m}, and fj(x1) < Tchebycheff method, the i-th SOSP is defined by Eq. (20).
fj(x2) for at least one j ∈ {1,…,m}. A solution x* ∈ Ω is known
 Minimize g te ( x |  i , z * )  max{ ij | f j ( x )  z *j |}
as Pareto optimal if no other solution in Ω dominates it. The  1 j  m
(20)
set of all Pareto optimal solutions is known as the Pareto Subject to x  
optimal set, of which the mapping in the objective space is
known as the Pareto optimal front (PF).
There are mainly two methods to handle a MOP. One is to
convert it to a single-objective optimization problem (SOP) by V. THE PROPOSED MOEA/D FOR MCOP
objective aggregation. In this case, the commonly used This paper proposes an improved MOEA/D to address the
method is weighted sum, where each objective, e.g. the ACT new MCOP, namely MOEA/D-MCOP. This section first
and AEC in this paper, is assigned a weight. However, weight introduces the solution representation and evaluation. Two
values should be set in advance. Heuristics and metaheuristics specially devised performance enhancing schemes, i.e. a
(including EAs) are often used to address a SOP. By running problem-specific population initialization scheme, and a
them once, a single solution is output. If system demands DVFS-based energy conservation scheme are then explained.
change, the weight values need to be re-set. Hence, the first Then, the overall procedure of MOEA/D-MCOP is given in
method only obtains a compromised solution, which cannot detail. The complexity of MOEA/D-MCOP is analyzed at last.
reflect the conflicting features between objectives. The other
method to tackle MOP is to use MOEAs. Any MOEA is A. Solution Representation and Evaluation
capable of obtaining a set of nondominated solutions in a
single run. These solutions reflect the Pareto-dominance As mentioned in Section III, for application Gi,j on SMD Ui,j,
relation among them. This is what a decision maker expects to the execution locations and the execution orders of all tasks in
know. Even if the system demands change, the nondominated Gi,j need to be determined in the MCOP. Let
solutions obtained by MOEAs are still valid. This is why Vi , j  {vi , j ,1 ,..., vi , j , Ni , j } denote the set of tasks in Gi,j. Let
MOEAs are more appropriate to address the MCOP problem. L i , j  (loci , j ,1 ,..., loci , j , k ,..., loci , j , Ni , j ) denote the execution
Currently, MOEAs have attracted increasingly more
location vector of all tasks in Gi,j, where
research attention and been successfully applied to address
loci , j , k  {1,..., H , H  1} is the execution location of task vi,j,k,
various MOP problems, such as computation offloading
[27][30], workflow scheduling [20], function optimization and H is the number of cores in Ui,j. If 1  loci , j , k  H , vi,j,k is
[7][40], feature selection [41], and job shop scheduling [42]. executed on the loci,j,k-th core of Ui,j. If loci , j , k  H  1 , vi,j,k is
Pareto-dominance based MOEAs are the mainstream
optimizers in the literature, such as, NSGA-II. Nevertheless, offloaded to the MEC server. Let
they usually suffer from prematurity and local optima. On the O i , j  (ui , j ,1 ,..., ui , j , k ,..., ui , j , Ni , j ) denote the execution order
other hand, compared with them, MOEA/D has been reported vector of all tasks in Gi,j, where ui , j , k  Vi , j denotes the k-th
to achieve better global exploration ability with lower
task to be executed in O i , j , e.g. ui , j ,1  vi , j , start and
computational overhead [31][40]. This motivates us to adapt
MOEA/D for the new MCOP. ui , j , Ni , j  vi , j , end .
 computing time if it is executed on SMD, and its task
offloading time if it is executed on the MEC server. As
aforementioned, a solution to the MCOP problem, x, contains
all execution locations of all tasks in the MEC system and the
execution orders among them. By reducing the completion
time of each task in a greedy manner, this method reduces the
completion time of each application, which also helps to
reduce the average completion time of all applications in the
MEC system, i.e. ACT.
avg ofld
Let TSMD (vi , j , k ) and TMEC (vi , j , k ) be the average execution
time and the task offloading time of vi,j,k, respectively. For an
arbitrary application Gi,j, the procedure to determine the
execution locations of all tasks is described as below.
Fig. 4. Solution representation in the MCOP. avg ofld
For each vi,j,k in Gi,j, TSMD (vi , j , k ) and TMEC (vi , j , k ) are
ofld txd
calculated. TMEC (vi , j , k ) is the summation of TSMD (vi , j ,k ) ,
Let SOL(Gi , j )  ( Li , j , Oi , j ) be a computation offloading exe rxd
TMEC (vi , j ,k ) and TSMD (vi , j ,k ) (see Eqs. (7), (10) and (12)). If
solution (SOL) for application Gi,j, i = 1,…,S, j  1,..., N iSMD . avg ofld
TSMD (vi , j , k )  TMEC (vi , j , k ) , vi,j,k is executed on a randomly
Let SOL( i )  ( SOL(Gi ,1 ),..., SOL(Gi , N SMD )) be a SOL for all
i
selected core of Ui,j; otherwise, vi,j,k is offloaded to the MEC
applications on all SMDs associated with SeNB πi, i = 1,…,S. server. The execution location initialization for all tasks in Gi,j
A solution to the MCOP, x  ( SOL ( 1 ),..., SOL( S )) , consists is shown in Algorithm 1, where randInt(1, H) is an integer
of all SOLs associated with all SeNBs in the MEC system. Fig. randomly generated in the range [1, H].
4 shows an example solution to the MCOP.
Given a solution x, its objective function values, F(x) = Algorithm 1. Latency-Based Execution Location Initialization
(fACT(x), fAEC(x)), can be calculated using Eqs. (15) and (16) in Input: application Gi,j.
Section III-F. Output: execution location vector Li , j .
1. Initialize vector Li , j  (loci , j ,1 ,..., loci , j , Ni , j ) ;
B. Problem-Specific Population Intialization Scheme 2. for k = 1 to Ni,j do
avg H
The problem-specific population initialization scheme is 3. Calculate TSMD (vi , j ,k )  (1 / H )   h1 ci , j ,k / f i ,max
j ,h ;

based on two methods, including a latency-based execution 4. ofld

Calculate TMEC txd
(vi , j ,k )  TSMD exe
(vi , j ,k )  TMEC rxd
(vi , j ,k )  TSMD (vi , j ,k ) ;
location initialization method and a commonly used execution avg ofld
5. if TSMD (vi , j ,k )  TMEC (vi , j ,k ) then
order initialization method.
6. Generate a random integer randInt(1, H);
1) Latency-Based Execution Location Initialization 7. Set loci , j ,k = randInt(1, H); // local computing
Initial population usually has a significant impact on the 8. else
optimization performance of a MOEA. An effective 9. Set loci , j ,k = H + 1;. // edge computing
population initialization scheme helps to guide a MOEA
towards promising areas in the search space [40]. Randomly
generated initial population may have better diversity, they are, 2) Random-Selection-Based Execution Order Initialization
however, not always helpful for the search to quickly locate In [20], an efficient execution order initialization method
areas with high-quality solutions in exponential search spaces. based on random selection is proposed, i.e.
In particular, for highly constrained optimization problems, random-selection-based execution order initialization (RSEOI),
misleading search directions of a MOEA might lead to serious where a task set, Ψ, maintains all those tasks which are not
deterioration on the optimization performance [31]. sorted but their immediate predecessors are sorted. A task vi,j,r
To the best of our knowledge, most of EAs for COP is randomly selected from Ψ and added to the end of execution
problems initialize execution locations for all tasks in a order vector Oi,j. After that, vi,j,r is removed from Ψ, and its
random manner [20][27]. For most of small scale COP immediate successors, whose immediate predecessors are all
problems, random location generation helps to diversify the sorted, are inserted into Ψ. Once all tasks in Gi,j are sorted, the
population and has a positive influence on the optimization task selection process stops and Oi,j is returned as the output.
performance. However, this method is no longer applicable to By running the RSEOI method multiple times, a set of
the highly constrained large scale MCOP problem concerned different execution order vectors for Gi,j can be obtained.
in this paper, due to the large number of tasks involved and the RSEOI is thus incorporated into the PSPI scheme to diversify
task precedence constraints. the initial population. The execution order initialization for all
The proposed latency-based execution location initialization tasks in Gi,j is shown in Algorithm 2.
(LELI) method decides if a task is executed locally or
offloaded to the MEC server by comparing its average
 Algorithm 2. Random-Selection-Based Execution Order Initialization applying DVFS to COP and MCOP problems in mobile edge
Input: application Gi,j. computing. As mentioned in Section III-D, there are H
Output: execution order vector Oi , j . heterogeneous cores in each SMD, where each core can run at
1. Initialize vector Oi , j  (ui , j ,1 ,..., ui , j , Ni , j ) ; M different computing frequency levels. This paper introduces
2. Set the sortable task set Ψ = ∅; a DVFS-based energy conservation (DVFS-EC) scheme in the
3. Set the sorted task set Ζ = ∅; proposed algorithm to further decrease the energy
4. Set Γ = Vi,j – {vi,j,start }; consumption of SMDs.
5. Set ui,j,1 = vi,j,start and Ζ = Ζ ∪ {vi,j,start};
6. Set index = 1; // index of the current task in Oi,j
In [25], a DVFS algorithm is presented for a COP in mobile
7. while Γ ≠ ∅ do cloud computing. By dynamically tuning the computing
8. for vi,j,k ∈ Γ do frequency level of each core, this algorithm can significantly
9. if pre(vi,j,k) ⊂ Z and vi,j,k ∉ Ψ then reduce the energy consumption of the associated mobile
10. Set Ψ = Ψ ∪ {vi,j,k};
device.
11. Randomly select a task vi,j,r from Ψ;
12. Set Ψ = Ψ – {vi,j,r}, Z = Z ∪ {vi,j,r} and Γ = Γ – {vi,j,r};
13. Set index = index + 1 and ui,j,index = vi,j,r; Algorithm 3. DVFS Based on SOL(Gi,j)
Input: task scheduling plan associated with SOL(Gi,j).
Output: new task scheduling plan with new computing
3) Overall Procedure of the Problem-Specific Population frequency level assignment for local tasks.
Initialization Scheme 1. for k = 1 to Ni,j do
2. if 1 ≤ loci,j,k ≤ H then // local tasks
The problem-specific population initialization (PSPI) 3. Set flag = 0 and t = 1;
scheme is based on LELI and RSEOI. The pseudocode of 4. while flag == 0 and t < M do
PSPI is shown in Fig. 5, where randInt(1, H+1) is an integer 5. exe ,new
Calculate a new completion time CTSMD (vi , j ,k ) if
randomly generated in the range [1, H+1]. vi,j,k is executed using the t-th computing frequency level;
The execution locations of all tasks are initialized by 6. if there exists next task vi , j ,next on the same core then
random execution location generation in half of the initial exe
7. Set limit1 = STSMD (vi , j ,next ) ;
population, and LELI (i.e. Algorithm 1) for the other half of
the initial population. The random execution location 8. else if vi,j,k is the last task on this core then
9. Set limit1 = CT(Gi,j);
generation introduces certain level of population diversity 10. if vi,j,k is not end task then
while LELI provides high-quality solutions for the evolution. 11. Set limit2 = min exe
STSMD (vi , j ,l ) ;
The execution order vector associated with each application vi , j ,l suc ( vi , j ,k )

Gi,j is initialized by Algorithm 2. 12. else Set limit2 = CT(Gi,j);

exe ,new exe ,new
13. if CTSMD (vi , j ,k ) ≤ limit1 and CTSMD (vi , j ,k ) ≤ limit2 then
1. Set POP = ∅ and index = 1; // POP: population 14. Assign the t-th computing frequency level to vi,j,k;
2. while index ≤ NP do // NP: population size 15. Set flag = 1;
3. Initialize solution xindex = (SOL(π1),…,SOL(πS)); 16. Set t = t+1;
4. for i = 1 to S do // for each SOL(πi)
5. for j = 1 to N iSMD do // for each SOL(Gi,j)
The DVFS algorithm in [25] is adapted for the MCOP
6. if index ≤ NP/2 then formulated in this paper, as shown in Algorithm 3. Given
7. for k = 1 to Ni,j do
8. Generate a random integer randInt(1, H+1); application Gi,j with its computation offloading solution
9. Set loci,j,k = randInt(1, H+1); SOL(Gi,j), the associated computation offloading is calculated,
10. else Obtain Li,j by Algorithm 1; including the start time and the completion time of vi,j,k,
11. Obtain Oi,j by Algorithm 2; exe exe
12. Set SOL(Gi,j) = (Li,j, Oi,j);
STSMD (vi , j , k ) and CTSMD (vi , j , k ) , and the completion time of
13. Set POP = POP ∪ xindex and index = index + 1; Gi,j, CT(Gi,j), according to Sections III-D, III-E, and III-F.
14. Output population POP.
Algorithm 3 reduces the energy consumption of SMD Ui,j by
Fig. 5. Pseudocode of the PSPI scheme. iteratively tuning the computing frequency levels of local
cores that are used to execute task(s). The resulting task
C. DVFS-Based Energy Conservation Scheme scheduling plan with a new computing frequency level
For a given SMD, if a high-performance core and a assignment consumes less energy. Different from the DVFS
low-performance core achieve similar computing performance algorithm in [25] that might lead to a higher completion time,
when executing a given task, then executing it on the latter can Algorithm 3 does not require additional time for completing
reduce the energy consumption. The DVFS technique can be Gi,j.
utilized to reduce the computing frequency of The pseudocode of the DVFS-EC scheme is shown in Fig. 6.
high-performance cores of SMDs, for energy conservation For each application Gi,j with a certain SOL(Gi,j), Algorithm 3
purpose. obtains a new computing frequency level assignment. The
Recently, DVFS has been widely used as a promising power DVFS-EC scheme aims at reducing the average energy
management solution to reduce energy consumption of SMDs consumption of all SMDs in the MEC system, i.e. AEC, which
in mobile cloud computing [25][27][45][46][47][48]. However, helps to improve quality of solutions to the MCOP.
to the best of our knowledge, there is a lack of research
 Step 2.4) Update of neighboring solutions: For each
1. Given a solution x, calculate its associated ACT and AEC values, q   (i ) , if g te ( y |  q , z* )  g te ( xq |  q , z* ) , then set
fACT(x) and fAEC(x); // see Eqs. (15) and (16)
2. for i = 1 to S do xq  y and f j ( xq )  f j ( y ) , j = 1,…,m.
3. for j = 1 to N iSMD do Step 2.5) Update of EP: Remove from EP those
4. Run Algorithm 3 based on the task scheduling plan solutions dominated by y, and add y to EP if no solution
associated with SOL(Gi,j);
5. for k = 1 to Ni,j do
in EP dominates y.
6. if 1 ≤ loci,j,k ≤ H then // local tasks Step 3) Stopping condition: If stopping condition is met,
7. actual
Update energy consumption ESMD ,h (vi , j ,k ) ;
then stop and output EP. Otherwise, go to Step 2.
8. Update fAEC(x).
In Step 2.1, crossover and mutation are applied to xk and xl
Fig. 6. Pseudocode of the DVFS-EC scheme.
(two neighbors of xi) to generate a new solution y. By
combining selected portions from two parent solutions, the
D. Overall Procedure of MOEA/D-MCOP crossover operator is regarded as the main evolutionary force
The proposed MOEA/D is based on the original MOEA/D for offspring production. Offspring solutions inherit some
(see Section IV-B). Denote the number of neighbors of each features from their parents. Yet, they are capable of exploring
SOSP by W. The set of neighbors of the i-th SOSP, φ(i), new areas in the search space as long as their parents are not
contains W closest neighbors, where the closeness between similar to each other.
any two SOSPs is measured by the Euclidean distance As mentioned in Section V-A, a solution
between the two corresponding weight vectors. Let EP x  ( SOL ( 1 ),..., SOL( S )) is composed of all SOLs
represent the external population storing the nondominated associated with all SeNBs in the MEC system, where
solutions obtained during the evolution. SOL( i )  ( SOL(Gi ,1 ),..., SOL(Gi , N SMD )) , i = 1,…,S.
The overall procedure of the proposed MOEA/D is i

presented as below. Let xpar1 and xpar2 be two parent solutions. Let
SOLpar1 (Gi , j )  ( Lipar 1 par1
, j , Oi , j ) and SOL
par 2
(Gi , j )  ( Lipar 2 par 2
, j , Oi , j )
MOEA/D-MCOP Procedure: be the SOLs for Gi,j in xpar1 and xpar2, respectively. The
Input:
crossover operator is applied to each SOLpar1 (Gi , j ) and
 Np: the number of subproblems;
  1 ,...,  N P : uniformly spread weight vectors; SOLpar 2 (Gi , j ) pair, i = 1,…,S, j = 1,…, N iSMD , to obtain two
 W: the number of neighbors for each subproblem; offspring SOLs for Gi,j, namely SOLoff 1 (Gi , j ) and
 Stopping condition. SOLoff 2 (Gi , j ) , as described in Algorithm 4, where randInt(1,
Output:
 EP: an external population storing the nondominated Ni,j) in step 2 is an integer randomly generated in the range [1,
solutions obtained during the evolution. Ni,j]. To be specific, for pair SOLpar1 (Gi , j ) and SOLpar 2 (Gi , j ) ,
Step 1) Initialization: single-point crossover is applied to the corresponding
Step 1.1) Set EP = ∅. execution location vector pair, i.e. Lipar 1
and Lipar 2
,j , j , and the
Step 1.2) For each  i , i = 1,…,NP, obtain W closest
execution order vector pair, i.e. Oipar
,j
1
and Oipar
,j
2
,
weight vectors based on Euclidean distance,  i1 ,...,  iW ,
respectively.
and set  (i )  {i1 ,..., iW } . First, we introduce the execution location (EL) crossover.
Step 1.3) Generate an initial population, x1 ,..., x N P , by For each pair ( Lipar 1 par 2
, j , Li , j ), we randomly generate a crossover
using the PSPI scheme in Section V-B and evaluate the point CPTi loc
, j (see steps 2-3 in Algorithm 4) and swap the
objective functions for each solution.
Step 1.4) Initialize reference point z *  ( z1* ,..., z m* ) . corresponding portions of Lipar 1
, j and Lipar
,j
2
before CPTi loc
,j .

Step 2) Repeat: Then, we obtain two offspring execution location vectors

for i = 1 to NP do Loff
i, j
1
and Loff 2
i , j . According to the task graph in Fig. 2, we
Step 2.1) Reproduction: Apply crossover (see present an example of the EL crossover operation in Fig. 7.
Algorithm 5) and mutation (see Algorithm 7) operators In the execution order (EO) crossover, all task precedence
to generate a new solution y based on xk and xl, where k, constraints must be met. A simple crossover is very likely to
l ∈ φ(i) and k ≠ l. produce infeasible execution order vectors for each application,
Step 2.2) DVFS-EC: Apply the DVFS-EC scheme (see as repetitive tasks may be created. In [20], an effective task
Section V-C) to reduce the AEC value of y, fAEC(y). execution order crossover operator ensures that all task
Step 2.3) Update of z*: If f j ( y )  z *j , then set precedence constraints are always satisfied. This operator is
adopted as the EO crossover in MOEA/D-MCOP, as described
z *j  f j ( y ) , j = 1,…,m.
below.
 Algorithm 4. EL and EO Crossovers on Two SOLs Associated with Gi,j Mutation plays an important role in introducing diversity to
Input: two parent SOLs for Gi,j, e.g. SOLpar1 (Gi , j )  ( Lipar 1 par 1
, j , Oi , j ) and the evolution. Bitwise mutation is applied to the execution
SOLpar 2 (Gi , j )  ( Lipar 2 par 2
, j , Oi , j ) .
location vector Lipar
, j , and single-point mutation is applied to

Output: two offspring SOLs for Gi,j, e.g. SOLoff 1 (Gi , j ) and SOLoff 2 (Gi , j ) . the execution order vector Oipar
,j in each SOLpar (Gi , j ) , i =
// the EL crossover 1,…,S, j = 1,…, N iSMD , to obtain an offspring SOL for Gi,j,
1. Initialize Loff 1 off 1 off 1 off 2 off 2 off 2
i , j  (loci , j ,1 ,..., loci , j , N i , j ) and Li , j  (loci , j ,1 ,..., loci , j , N i , j ) ;
namely SOLoff (Gi , j ) . This is described in Algorithm 6, where
2. Generate a random integer randInt(1, Ni,j);
3. Set CPTi loc random(0,1) is a number randomly generated in the range (0,
, j = randInt(1, Ni,j);
1). A mutation probability for all applications in the MEC
4. for k = 1 to CPTi loc do Set locioff, j ,1k  locipar 2
and locioff, j ,k2  locipar 1
, j ,k ;
,j , j ,k system, MPapp, is used to decide if SOL(Gi,j) is mutated, i =
for k = CPTi loc 1,…,S, j = 1,…, N iSMD .
off 1 par 1 off 2 par 2
5. , j +1 to Ni,j do Set loci , j , k  loci , j ,k and loci , j , k  loci , j ,k ;

// the EO crossover
In the EL mutation, a mutation probability for Lipar loc
, j , MPi , j ,
6. Generate a random integer randInt(1, Ni,j);
7. Set CPTi ,ord temp
j = randInt(1, Ni,j) and N i , j  CPTi ,ord
j  Ni , j ; is adopted to decide if each execution location in Lipar
,j is
8. Generate two N itemp
,j -dimension temporary vectors, e.g. mutated. If an execution location locipar par
, j , k in Li , j is chosen for

Oitemp
,j
1
 (uitemp 1 temp1 temp 2
, j ,1 ,..., ui , j , N temp ) and Oi , j  (uitemp 2 temp 2
, j ,1 ,..., ui , j , N temp ) ; mutation, a random integer number from {1,…,H+1} is used
i, j i, j

9. for k = 1 to CPTi ,ord Set uitemp 1 par 2

and uitemp 2 par1 to replace locipar
, j , k . After mutation, an execution location
j do , j , k  ui , j ,k , j , k  ui , j ,k ;

10. Set index = 1; vector Loff

i , j is generated. For the task graph in Fig. 2, an
ord temp
11. for k = CPT i, j +1 to N i, j do example of the EL mutation operation is presented in Fig. 9.
temp1 par1
12. Set u i , j ,k ui , j ,index , uitemp 2 par 2
, j , k  ui , j ,index and index = index +1;

13. Delete repetitive tasks from Oitemp

,j
1
and Oitemp
,j
2
, respectively;

14. Set two offspring EO vectors, Oioff, j 1  Oitemp

,j
1
and Oioff
,j
2
 Oitemp
,j
2
;
// two offspring SOLs for Gi,j are generated
15. Set SOLoff 1 (Gi , j )  ( Loff 1 off 1
i , j , Oi , j ) and SOL
off 2
(Gi , j )  ( Loff 2 off 2
i , j , Oi , j ) .

Fig. 8. An example of the EO crossover applied to the task graph in Fig. 2.

Fig. 7. An example of the EL crossover. Algorithm 5. Crossover Procedure on Two Solutions

Input: two parent solutions, e.g. xpar1 and xpar2.
Output: two offspring solutions, e.g. xoff1 and xoff2.
For each pair (Oipar 1 par 2 ord
, j , Oi , j ) , a crossover point CPTi , j is 1. Initialize xoff1 = (SOLoff1(π1),…,SOLoff1(πS)) and
xoff2 = (SOLoff2(π1),…,SOLoff2(πS));
randomly selected. Each parent EO vector is divided into two
// for each SOL par1(πi) and SOL par2(πi) pair
portions by CPTi ,ord ord
j . The two portions before CPTi , j are 2. for i = 1 to S do
// for each SOL par1(Gi,j) and SOL par2(Gi,j) pair
swapped and then concatenated to Oipar 1
and Oipar 2
,
,j ,j 3. for j = 1 to N iSMD do
respectively, resulting into two temporary vectors. All
4. Obtain two offspring SOLs, SOLoff 1 (Gi , j ) and SOLoff 2 (Gi , j ) ,
repetitive tasks in the temporary vectors are then removed,
reserving the order of the remaining tasks, resulting into two by running Algorithm 4 on SOLpar1 (Gi , j ) and SOLpar 2 (Gi , j ) ;

feasible execution order vectors, namely Oioff, j 1 and Oioff, j 2 . An

example of the EO crossover operation applied to the task In the proposed MOEA/D, the EO mutation in [20] is
graph in Fig. 2 is shown in Fig. 8. adopted, where all task precedence constraints are met. Let
Based on Algorithm 4, we design the crossover operator on Oipar par par par
, j  (ui , j ,1 ,..., ui , j , k ,..., ui , j , Ni , j ) be the parent execution order
two parent solutions in Algorithm 5. vector associated with Gi,j chosen for mutation. uipar
, j , k is the
k-th task to be executed in Oipar par par
, j , ui , j , k  Vi , j , ui , j ,1  vi , j , start , location other than the current location of uipar
, j , r is randomly

and uipar
, j , N i , j  vi , j , end . selected in temp, where uipar
, j , r is then moved to.

The EO mutation produces

Algorithm 6. EL and EO Mutation Procedures O  (ui , j ,1 ,..., ui , j , a )  temp  (ui , j ,b ,..., uipar
off
i, j
par par par
, j , Ni , j ) , where “∘”
Input: parent SOL for Gi,j, e.g. SOLpar (Gi , j )  ( Lipar par
, j , Oi , j ) .
concatenates the above produced three vectors. An example of
Output: offspring SOL for Gi,j, e.g. SOLoff (Gi , j ) . the EO mutation operation applied to the task graph in Fig. 2
1. Generate a random number random(0, 1); is illustrated in Fig. 10.
2. app
Set MPrnd = random(0, 1); Based on Algorithm 6, Algorithm 7 presents how a parent
3. app
if MPrnd ≤ MPapp then // SOLpar(Gi,j) is to be mutated solution is mutated.
// the EL mutation
4. Initialize the offspring EL vector Loff off off
i , j  (loci , j ,1 ,..., loci , j , N i , j ) ;

5. for k = 1 to Ni,j do
6. Generate a random number random(0, 1);
loc
7. Set MPrnd = random(0, 1);
loc
8. if MPrnd ≤ MPi loc
,j then
9. Generate a random integer randInt(1, H+1); Fig. 9. An example of the EL mutation.
off
10. Set loc i , j ,k = randInt(1, H+1);
off
11. else Set loc i , j ,k  locipar
, j ,k ;

// the EO mutation
12. Initialize the offspring EO vector Oioff off off
, j  (ui , j ,1 ,..., ui , j , N i , j ) ;

13. Randomly select a task uipar

, j ,r from Oipar par
, j , where ui , j ,r

cannot be the start task nor the end task;

14. Carry out forward search until the last predecessor of uipar
, j ,r ,

e.g. uipar
, j ,a , is found;

15. Include the visited tasks in vector (uipar par Fig. 10. An example of the EO mutation applied to the task graph in Fig. 2.
, j ,1 ,..., ui , j , a ) ;

16. Carry out backward search until the last successor of uipar
, j ,r ,
Algorithm 7. Mutation Procedure on One Solution
e.g. uipar
, j ,b , is found;
Input: parent solution, e.g. xpar.
17. Include the visited tasks in vector (uipar par Output: offspring solution, e.g. xoff.
, j ,b ,..., ui , j , Ni , j ) ;
1. Initialize xoff = (SOLoff(π1),…,SOLoff(πS));
18. Generate a temporary vector temp  (uipar par
, j , a 1 ,..., ui , j ,b 1 ) ; 2. for i = 1 to S do // for each SOL par(πi)
19. Randomly select a location in temp and move uipar 3. for j = 1 to N iSMD do // for each SOL par(Gi,j)
, j ,r there;

4. Obtain the offspring SOL SOLoff (Gi , j ) by running

, j  (ui , j ,1 ,..., ui , j ,a )  temp  (ui , j ,b ,..., ui , j , Ni , j ) ;
Set Oioff par par par par
20.
Algorithm 6 on SOLpar (Gi , j ) ;
21. Set SOLoff (Gi , j )  ( Loff off
i , j , Oi , j ) ;

22. else // SOLpar(Gi,j) is not mutated

23. Set SOLoff (Gi , j )  SOLpar (Gi , j ) . E. Complexity Analysis
Let O(f) be the time complexity for evaluating a solution to
par par task
A task in O i, j , u i , j ,r , is first randomly selected, where r ∈ the MCOP. Let N total and M be the total number of tasks in
{2,…,Ni,j-1}. Task u par
can be neither the start task nor the the MEC system and the number of the computing frequency
i , j ,r
levels on a core, respectively. Let the number of objectives
end task. Next, a forward search from uipar
, j ,1 to the last and that of neighbors for subproblem represented by m and W,
predecessor of uipar par par
, j , r , e.g. ui , j , a , is implemented on Oi , j .
respectively. Let the size of the external population (EP)
denoted by |EP|.
The visited tasks are included in a vector (uipar par
, j ,1 ,..., ui , j , a ) . First, we analyze the complexity of each step in the loop.
Similarly, a backward search from uipar
, j , N i , j is implemented on As the encoding length of each solution is N total task
, Step 2.1
Oipar par par (simple crossover and mutation) has a time complexity of
, j . When the last successor of ui , j , r , e.g. ui , j ,b , is found,
task
O( N total ) . There are two operations in Step 2.2 (namely the
the search terminates. The visited tasks are included in a
vector (uipar par par par DVFS-EC scheme), including solution evaluation and solution
, j , b ,..., ui , j , Ni , j ) . Let temp  (ui , j , a 1 ,..., ui , j ,b 1 ) denote a
improvement. In the first part, O(f) is the time complexity as
temporary vector between the two vectors of visited tasks. A defined above. In the second part, a solution is improved in
terms of energy consumption. The DVFS technique is applied
to each locally executed task, resulting into a time complexity TABLE III
PROBLEM CHARACTERISTICS
of O(M). In the worst case, all tasks are executed on SMDs,
task
Parameter Value
which corresponds to a time complexity of O( N total M) . Number of SeNBs in the MEC system (S) 5
task Total bandwidth offered by the MEC system (Btotal) 20 MHz
Hence, Step 2.2 has a time complexity of O( f  N total M) .
Number of channels offered by the MEC system
10
Steps 2.3, 2.4 and 2.5 update the reference point, the neighbors (Nchannel)
of each subproblem and EP, leading to time complexities of Noise power (σ2) 176 dBm
Computing capability of the MEC server (F) 4 GHz
O(m) , O(m  W ) and O(m | EP |2 ) , respectively. As the Number of heterogeneous cores of a SMD (H) 3
MCOP problem is highly complicated, solution evaluation is Number of the computing frequency levels on a
4
the most time-consuming operation in the loop. Compared core (M)
SMD
with it, other steps are trivial. Hence, the time complexity of Number of SMDs in the i-th small cell ( N i ) 3-9
txd
the loop (Step 2) is reduced to O(f). Power consumption when Ui,j offloads tasks ( p i, j ) 0.5 W
Then, we analyze the complexity of MOEA/D-MCOP. Power consumption when Ui,j receives data ( p rxd
) 0.1 W
i, j
Compared with the loop, the time complexity of the
Number of CPU cycles required to perform vi,j,k (ci,j,k) [0.1, 0.5] GHz
initialization is trivial and thus can be ignored. Hence, Input data size of vi,j,k (di,j,k) [5000, 6000] Kb
MOEA/D-MCOP is only dependent on the complexity of the Output data size of vi,j,k (oi,j,k) [500, 1000] Kb
loop, the number of subproblems, Np, and the predefined
number of iterations, Gmax, leading to a time complexity of TABLE IV
O( f  N p  Gmax ) . SIX TEST INSTANCES
Instance Number of tasks in an Total number of tasks in
No. application the MEC system
VI. EXPERIMENTS AND RESULTS ANALYSIS 1 10-20 349
2 15-25 566
3 20-30 647
A. Test Instances 4 25-35 948
In this paper, we consider a centralized MEC system with a 5 30-40 1230
6 10-40 630
radius of 100 m. The network parameter setup method in [30]
is adopted. A system with five small cells is regarded as a
medium-scale MEC scenario, which meets most of the users’ B. Experiment Setup
requirements. Therefore, we also use the five-small-cell MEC We ran the experiments on a computer with Windows 10
network to conduct all experiments. The cells are evenly OS, Intel(R) Core(TM) i7-8700 CPU 3.2 GHz and 16 GB
scattered, each with a radius of 50 m. The number of channels RAM. All algorithms were implemented using Python 3.6.
in the MEC system is fixed to 10 for simplicity purpose. To The parameters of the proposed MOEA/D-MCOP are listed in
guarantee there is no channel interference between SMDs Table V. The results are obtained by running each algorithm 20
within any small cell, we randomly generate the number of times, from which the statistics are collected and analyzed.
SMDs in each small cell in the range of [3, 9].
For an arbitrary SMD Ui,j, the maximum computing TABLE V
PARAMETERS OF MOEA/D-MCOP
frequency of the 1st core, f i ,max
j ,1 , is randomly generated in the Parameter Value
range [0.5, 1] GHz. The maximum computing frequencies of Population size (Np) 100
Predefined number of iterations 100
the 2nd and 3rd cores are set to f i ,max max
j ,2  f i , j ,1  0.1 and Number of neighbors for each subproblem (W) 10
f i ,max max Probability for mutating a SOL associated with Gi,j
j ,3  f i , j ,1  0.25 , respectively. Assume the power SMD
1/ N total
(MPapp)
consumption of the 1st, 2nd, and 3rd cores at the maximum Probability for mutating an EL associated with Gi,j
computing frequency is 4 W, 2 W, and 1 W, respectively. 1/ N i , j
( MPi loc
,j )
According to [25], we assume each core has 4 computing
frequency levels with scaling factors α1 = 0.2, α2 = 0.5, α3 =
0.8, and α4 = 1, respectively, and constant γ is set to 2. The C. Performance Measures
problem characteristics are shown in Table III. Four widely recognized performance metrics in the
For the application generation, we first randomly generate literature [31][32] are used to thoroughly evaluate the
the number of tasks, and then randomly generate their data performance of MOEA/D-MCOP. Let PFref and PFknown denote
size and the number of CPU cycles required to perform them. the reference PF approximating the true PF and the PF
The task-precedence constraints between tasks are randomly obtained by an algorithm, respectively.
generated based on the task generation method introduced in For the new MCOP problem concerned in this paper, the
[20]. To be specific, we randomly generated the number of true PF is not known. A widely used method in the research is
tasks in an application using six different ranges to control the to collect the best so far solutions found by all algorithms in
scale of the MCOP problem, as shown in Table IV. In each all runs and obtain the PF associated with those nondominated
instance, the number of tasks is randomly generated according ones as PFref.
to the corresponding range.
 that the problem specific knowledge incorporated in the PSPI
 Inverted generational distance (IGD) scheme is able to guide the search to start from promising
IGD as defined in Eq. (21) can simultaneously measure the areas. Moreover, MOEA/D-MCOP achieves better mean value
convergence and diversity of a given PF. For an algorithm, a than the other two in terms of IGD and GD in each instance.
smaller IGD value reflects better overall performance. This shows that the DVFS-EC scheme helps to reduce the
energy consumption of SMDs without sacrificing completion

 ref PFref
d ( ref , PFknown ) time, thus enhances the local exploitation ability of the search.
IGD  (21) Fig. 11 shows the PFs obtained by the three algorithms. It
PFref can be seen clearly that both the PSPI and DVFS-EC schemes
contribute to performance improvement of MOEA/D.
where |PFref| is the number of points in PFref and d(τref, PFknown)
is the Euclidean distance between point τref in PFref and its TABLE VI
nearest point in PFknown. RESULTS OF IGD (BEST RESULTS ARE IN BOLD)
Instance No. MOEA/D MOEA/D-PSPI MOEA/D-MCOP
 Generational distance (GD) 1 7.86(0.16) 7.64(0.15) 0.19(0.21)
2 4.88(0.25) 4.19(0.11) 0.47(0.14)
GD as defined in Eq. (22) can measure how closely PFknown 3 3.14(0.16) 3.11(0.24) 0.81(0.29)
converges to PFref. 4 8.91(0.39) 7.06(0.19) 1.14(0.30)
5 11.60(0.39) 11.23(0.25) 1.68(0.55)

 known PFknown
d ( known , PFref ) 6 5.74(0.22) 5.48(0.16) 0.55(0.21)
GD  (22) TABLE VII
PFknown
RESULTS OF GD (BEST RESULTS ARE IN BOLD)
Instance No. MOEA/D MOEA/D-PSPI MOEA/D-MCOP
where |PFknown| is the number of points in PFknown and d(τknown, 1 2.84(0.04) 2.74(0.03) 0.31(0.29)
PFref) is the Euclidean distance between point τknown in PFknown 2 1.73(0.04) 1.58(0.03) 0.56(0.10)
and its nearest point in PFref. 3 1.15(0.04) 1.09(0.04) 1.03(0.15)
4 2.00(0.08) 1.69(0.03) 0.89(0.26)
5 1.90(0.06) 1.81(0.04) 1.63(0.17)
 Student’s t-test 6 1.70(0.04) 1.60(0.02) 0.52(0.11)
In this paper, two-tailed t-test with 38 degrees of freedom at
a 0.05 level of significance [49] is utilized to compare two
algorithms Alg.1 and Alg.2 based on the IGD values obtained
E. Overall Performance Evaluation
in 20 runs. The results show whether performance of Alg.1 is
significantly better than, significantly worse than, or MOEA/D-MCOP is compared against the following eight
statistically equivalent to that of Alg.2, respectively. state-of-the-art algorithms, i.e. five MOEAs and three
heuristic algorithms, in six test instances in Table IV.
 Friedman test
The Friedman test [50] is a non-parametric test for detecting  NSGA-II: the modified fast and elitist nondominated
the differences among different algorithms in terms of IGD sorting genetic algorithm [30] used to achieve a trade-off
and GD. All algorithms under comparisons are ranked and between the average energy consumption and the average
their average ranks explicitly indicate how well they perform. completion time in a MEC network.
 MOWOA: the multiobjective whale optimization
D. Effectiveness of Two Performance Enhancing Schemes algorithm [27] applied to address the multiobjective task
workflow scheduling problem, where weighted sum is
To demonstrate the effectiveness of the two new schemes, used to aggregate workflow completion time and energy
namely PSPI in Section V-B and DVFS-EC in Section V-C, in consumption into one objective function.
the proposed MOEA/D-MCOP, the following three variants of  MOFOA: the knowledge-guided multiobjective fruit fly
MOEA/D are tested on the six test instances in Table IV.
optimization algorithm [51] developed to tackle the
multi-skill resource-constrained project scheduling
 MOEA/D: the original MOEA/D [7]. problem, where the completion time and the total cost are
 MOEA/D-PSPI: MOEA/D with the PSPI scheme. minimized at the same time.
 MOEA/D-MCOP: MOEA/D-PSPI with the DVFS-EC  HGPCA: the hierarchical GA and PSO-based
scheme. computation algorithm [23] proposed to solve the
multi-user offloading game problem in MCC, where the
For the three algorithms above, the population size and the energy consumption of SMDs is minimized.
predefined number of iterations are set to 100, respectively.  MOEA/D: the multiobjective evolutionary algorithm
The results of mean and standard deviation (SD) of IGD based on decomposition [7] with the Tchebycheff
and GD are collected in Tables VI and VII, respectively. It is method.
obvious that MOEA/D-PSPI outperforms MOEA/D against
the two performance measures in all instances. This is due to
  TSDVFS: the task scheduling with dynamic voltage and the inertia weight, and the acceleration instant are set to 0.6,
frequency scaling algorithm [25] developed to minimize 0.01, 0.4, and 1.5, respectively. In MOEA/D and
the energy consumption of SMDs in MCC, where the MOEA/D-MCOP, the number of neighbors for each
application completion time constraint and the subproblem is set to 10.
task-precedence constraints are satisfied. Note that each of three heuristics only obtains a single
 CTESA: the collaborative task execution scheduling solution after each run. To make a fair comparison, each
algorithm [22] devised to address the delay-constrained heuristic should obtain a set of nondominated solutions for
workflow scheduling problem in MCC network. CTESA performance comparison. Hence, we repeatedly run a heuristic
minimizes the energy consumption of SMD(s) while with incrementally increased application completion time
meeting the application completion time deadline. deadline as a constraint. Each deadline results into a solution
 eDors: the energy-efficient dynamic offloading and with explicit application completion time and energy
resource scheduling algorithm [28] presented to reduce consumption. By doing so, each heuristic can obtain a set of
the energy consumption and shorten the application nondominated solutions after a number of runs.
completion time, where the task-dependency requirement We first compare the average completion time of
and application completion time deadline are constrained. applications, i.e. ACT, and the average energy consumption of
 MOEA/D-MCOP: the proposed MOEA/D with the PSPI SMDs, i.e. AEC, obtained by the nine algorithms. Figs. 12 and
and DVFS-EC schemes in this paper. 13 depict the box plots of the nine algorithms in terms of ACT
and AEC, respectively. In Fig. 12, one can observe that
For all MOEAs under comparison, the population size and MOEA/D-MCOP performs better than the other eight
the predefined number of iterations are set to 100, respectively. algorithms in most of the test instances (except Instances 3
To make a fair comparison, we directly adopt the parameter and 4). This is because the PSPI scheme in MOEA/D-MCOP
settings in NSGA-II [30], MOWOA [27], MOFOA [51], adopts the latency-based execution location initialization
HGPCA [23], and MOEA/D [7]. To be specific, in NSGA-II, method (LELI). By reducing the completion time of each task
the crossover and mutation probabilities are set to 0.8 and 0.3, in a greedy manner, LELI can reduce the completion time of
respectively. In MOWOA, the upper and lower bounds of the each application, which also helps to reduce the ACT in the
search range are set to 4.4 and 0.5, respectively. For MOFOA, MEC system.
we set the sub-swarm size, the learning rate of the experience,
and the number of elite fruit flies to 5, 0.1, and 3, respectively.
In HGPCA, the crossover probability, the mutation probability,

(a) Instance 1 (b) Instance 2 (c) Instance 3

(d) Instance 4 (e) Instance 5 (f) Instance 6

Fig. 11. PFs obtained by the three algorithms.
 (a) Instance 1 (b) Instance 2 (c) Instance 3

(d) Instance 4 (e) Instance 5 (f) Instance 6

Fig. 12. Box plots of the nine algorithms in terms of ACT.

(a) Instance 1 (b) Instance 2 (c) Instance 3

(d) Instance 4 (e) Instance 5 (f) Instance 6

Fig. 13. Box plots of the nine algorithms in terms of AEC.

In Fig. 13, there is no doubt MOEA/D-MCOP is the best. level of each core. Besides, eDors and TSDVFS are the
This is because the DVFS-EC scheme can significantly second- and third-best algorithms, respectively. The two
reduce the AEC by dynamically adjusting the frequency algorithms decrease the energy consumption of SMDs
thanks to DVFS. Meanwhile, eDors always overweighs problem. On the one hand, NSGA-II, MOWOA, MOFOA
TSDVFS with respect to the AEC. The reason behind it is and HGPCA are Pareto-dominance based. If parameters are
that eDors takes advantage of transmission power control not set appropriately, they are likely to get stuck into local
mechanism, which further reduces the energy consumption. optima and converge slowly. On the other hand, MOEA/D
However, both eDors and TSDVFS are not good at is decomposition-based, addressing a number of scalar
obtaining a decent tradeoff between ACT and AEC, i.e. optimization subproblems in parallel. Compared with those
improving one objective harms the other. On the other hand, Pareto-dominance based MOEAs, MOEA/D is featured
if we consider ACT and AEC together, MOEA/D-MCOP with stronger global exploration capability. Therefore,
achieves the best overall performance. MOEA/D performs better than NSGA-II, MOWOA,
The mean and SD values of IGD and GD obtained by all MOFOA, and HGPCA. This also justifies why MOEA/D is
algorithms are shown in Tables VIII and IX, respectively. chosen for addressing the MCOP problem.
Firstly, if taking all algorithms into account, one can Thirdly, among heuristics, TSDVFS is the winner as it
observe that MOEA/D-MCOP performs the best with outperforms CTESA and eDors in most test instances
respect to IGD and GD in all instances. IGD reflects the except Instances 3 and 4 in terms of IGD and GD. TSDVFS
diversification and convergence of nondominated solutions first adopts the initial scheduling algorithm to generate the
simultaneously. GD reveals how far the obtained PF is from minimal-delay schedule. Then, it applies DVFS technology
the reference PF. Results in Tables VIII and IX show that to reduce the energy consumption of SMDs. However,
MOEA/D-MCOP always obtains the set of nondominated TSDVFS cannot strike a balance between the application
solutions closest to the reference PF, which indicates completion time and the energy consumption of SMDs.
MOEA/D-MCOP achieves a better trade-off between global This is why TSDVFS is beaten by MOEA/D-MCOP. On the
exploration and local exploitation. other hand, eDors and CTESA also have obvious drawbacks.
Secondly, it is easily seen that MOEA/D outperforms all eDors is not good at reducing of the application completion
MOEAs except MOEA/D-MCOP in almost all instances, time. CTESA schedules the tasks on the partial critical path
showing that MOEA/D is highly effective for the MCOP rather than considering the task graph as a whole.

TABLE VIII
RESULTS OF IGD (BEST RESULTS ARE IN BOLD)
Algorithm Instance 1 Instance 2 Instance 3 Instance 4 Instance 5 Instance 6
NSGA-II 8.71(0.24) 5.37(0.29) 5.07(0.24) 9.22(0.41) 10.77(0.44) 5.93(0.19)
MOWOA 9.94(0.16) 7.21(0.25) 6.42(0.32) 11.88(0.31) 13.32(0.47) 8.24(0.34)
MOFOA 10.39(0.16) 6.97(0.20) 5.15(0.16) 10.40(0.23) 13.80(0.24) 8.93(0.26)
HGPCA 10.47(0.32) 7.92(0.35) 8.29(0.54) 8.66(0.39) 11.07(0.52) 8.45(0.34)
MOEA/D 7.86(0.16) 4.88(0.25) 3.14(0.16) 8.91(0.39) 11.60(0.39) 5.74(0.22)
TSDVFS 6.40(0) 2.78(0) 3.64(0) 4.45(0) 5.79(0) 2.22(0)
CTESA 9.80(0) 6.14(0) 4.63(0) 4.16(0) 7.99(0) 6.51(0)
eDors 8.33(0) 3.93(0) 3.22(0) 3.56(0) 10.33(0) 8.25(0)
MOEA/D-MCOP 0.19(0.21) 0.47(0.14) 0.81(0.29) 1.14(0.30) 1.68(0.55) 0.55(0.21)

TABLE IX
RESULTS OF GD (BEST RESULTS ARE IN BOLD)
Algorithm Instance 1 Instance 2 Instance 3 Instance 4 Instance 5 Instance 6
NSGA-II 2.99(0.05) 1.84(0.05) 1.53(0.07) 2.25(0.10) 2.12(0.08) 1.75(0.04)
MOWOA 3.30(0.03) 2.44(0.04) 2.07(0.11) 2.77(0.10) 2.73(0.15) 2.49(0.07)
MOFOA 3.24(0.03) 2.14(0.04) 1.36(0.03) 2.30(0.04) 2.12(0.03) 2.18(0.04)
HGPCA 3.24(0.05) 2.36(0.07) 2.14(0.10) 2.28(0.13) 2.31(0.11) 2.21(0.07)
MOEA/D 2.84(0.04) 1.73(0.04) 1.15(0.04) 2.00(0.08) 1.90(0.06) 1.70(0.04)
TSDVFS 2.56(0) 1.21(0) 1.17(0) 1.78(0) 1.78(0) 1.34(0)
CTESA 3.32(0) 2.09(0) 1.70(0) 0.91(0) 1.93(0) 1.93(0)
eDors 3.47(0) 2.56(0) 2.46(0) 3.25(0) 2.17(0) 2.46(0)
MOEA/D-MCOP 0.31(0.29) 0.56(0.10) 1.03(0.15) 0.89(0.26) 1.63(0.17) 0.52(0.11)

The results of Student’s t-test based on IGD are shown in rankings of the nine algorithms are shown in Table XI. The
Table X. MOEA/D-MCOP is clearly the best among all PFs obtained by the nine algorithms are shown in Fig. 14.
algorithms. Friedman test is also utilized to rank algorithm Table XI and Fig. 14 both demonstrate the superiority of
performance. Based on the IGD and GD values, the average MOEA/D-MCOP over the rest of the algorithms.
 TABLE X
RESULTS OF STUDENT’S T-TEST BASED ON IGD
Alg.1 ↔ Alg.2 Instance 1 Instance 2 Instance 3 Instance 4 Instance 5 Instance 6
MOEA/D-MCOP ↔ NSGA-Ⅱ + + + + + +
MOEA/D-MCOP ↔ MOWOA + + + + + +
MOEA/D-MCOP ↔ MOFOA + + + + + +
MOEA/D-MCOP ↔HGPCA + + + + + +
MOEA/D-MCOP ↔ MOEA/D + + + + + +
MOEA/D-MCOP ↔ TSDVFS + + + + + +
MOEA/D-MCOP ↔ CTESA + + + + + +
MOEA/D-MCOP ↔ eDors + + + + + +
Symbol “+” indicates Alg.1 performs significantly better than Alg.2.

TABLE XI
RANKINGS OF ALL ALGORITHMS ON IGD AND GD
IGD GD
Algorithm
Average rank Position Average rank Position
NSGA-Ⅱ 5.33 6 4.50 4
MOWOA 7.67 7 8.00 8
MOFOA 8.00 9 5.67 6
HGPCA 7.67 8 7.00 7
MOEA/D 4.17 4 3.00 3
TSDVFS 2.67 2 2.33 2
CTESA 4.67 5 5.00 5
eDors 3.83 3 8.50 9
MOEA/D-MCOP 1.00 1 1.00 1

(a) Instance 1 (b) Instance 2 (c) Instance 3

(d) Instance 4 (e) Instance 5 (f) Instance 6

Fig. 14. PFs obtained by the nine algorithms.

completion time of applications and the average energy

VII. CONCLUSIONS AND FUTURE WORK consumption of all smart mobile devices (SMDs), are
minimized simultaneously. This new MCOP model, for the
A. Conclusions first time, considers the task-precedence constraints within
This paper models a new multiobjective computation each application in MEC, where an ordered list of tasks should
offloading problem (MCOP) in mobile edge computing (MEC) be executed one by one.
environment, where two objectives, namely the average To address the new problem, an improved MOEA/D with
two extensions, namely MOEA/D-MCOP is proposed. The
first extension is a problem-specific population initialization [3] D. Yao, C. Yu, L. Yang, and H. Jin, “Using crowdsourcing to provide
QoS for mobile cloud computing,” IEEE Trans. Cloud Comput., vol. 7,
scheme that generates high-quality initial population. The
no. 2, pp. 344–356, Apr. 2019.
second extension is a DVFS-based energy conservation [4] Y. Mao, C. You, J. Zhang, K. Huang, and K. Letaief, “A survey on
scheme that improves the quality of a given solution by mobile edge computing: The communication perspective,” IEEE
reducing the energy consumption of SMDs. Simulation results Commun. Surv. Tut., vol. 19, no. 4, pp. 2322–2358, Aug. 2017.
[5] S. Wang, X. Zhang, Y. Zhang, L. Wang, J. Yang, and W. Wang, “A
demonstrate that the proposed MOEA/D-MCOP performs
survey on mobile edge networks: Convergence of computing, caching
better than the five state-of-the-art MOEAs and three and communications,” IEEE Access, vol. 5, pp. 6757–6779, Mar. 2017.
heuristics in terms of the average completion time, the average [6] N. Abbas, Y. Zhang, A. Taherkordi, and T. Skeie, “Mobile edge
energy consumption, inverted generational distance, computing: A survey,” IEEE Internet Thing J., vol. 5, no. 1, pp. 450–465,
Sep. 2018.
generational distance, t-test, and Friedman test.
[7] Q. Zhang and H. Li, “MOEA/D: A multi-objective evolutionary
algorithm based on decomposition,” IEEE Trans. Evol. Comput., vol. 11,
no. 6, pp. 712–731, Nov. 2007.
B. Future Work [8] P. Mach and Z. Becvar, “Mobile edge computing: A survey on
architecture and computation offloading,” IEEE Commun. Surv. Tut., vol.
The MCOP problem modeled in this paper is a static 19, no. 3, pp. 1628–1656, Mar. 2017.
optimization problem in MEC network, where the number of [9] J. Liu, Y. Mao, J. Zhang, and K. B. Letaief, “Delay-optimal computation
task scheduling for mobile-edge computing systems,” in Proc. IEEE Int.
SMDs remains unchanged and SMDs do not move during
Symposium on Information Theory (ISIT), Barcelona, Spain, Jul. 2016,
computation offloading. However, in the real world, dynamic pp. 1451–1455.
and uncertainty are key features in MEC networks, such as [10] Y. Mao, J. Zhang, and K. B. Letaief, “Dynamic computation offloading
mobility, ever-changing wireless channel and number of for mobile-edge computing with energy harvesting devices,” IEEE J. Sel.
Area. Comm., vol. 34, no. 12, pp. 3590–3605, Sep. 2016.
SMDs. We will study the MCOP problem in a dynamic MEC
[11] L. Yang, J. Cao, H. Cheng, and Y. Ji, “Multi-user computation
environment, taking the three issues above into consideration. partitioning for latency sensitive mobile cloud applications,” IEEE Trans.
In this case, MOEA/D-MCOP cannot respond within a short Comput., vol. 64, no. 8, pp. 2253–2266, Nov. 2015.
time to the dynamic MEC network, especially when SMDs [12] T. Q. Dinh, J. Tang, Q. D. La, and T. Q. S. Quek, “Offloading in mobile
edge computing: Task allocation and computational frequency scaling,”
move quickly. Therefore, we will concentrate on developing
IEEE Trans. Commun., vol. 65, no. 8, pp. 3571–3584, Apr. 2017.
online algorithms and models in future work, e.g. [13] O. Muñoz, A. Pascual-Iserte, and J. Vidal, “Optimization of radio and
problem-specific heuristics, and deep reinforcement learning computational resources for energy efficiency in latency-constrained
based models. application offloading,” IEEE Trans. Veh. Technol., vol. 64, no. 10, pp.
4738–4755, Oct. 2015.
The computing resources on MEC servers and the spectrum
[14] L. Tong and W. Gao, “Application-aware traffic scheduling for workload
resources in wireless channels are both limited in MEC offloading in mobile clouds,” in Proc. IEEE 35th Int. Conf. on Computer
environment. Therefore, it is of significance to study how the Commun. (INFOCOM), San Francisco, CA, USA, Apr. 2016, pp. 1–9.
computing and spectrum resources are reasonably allocated [15] M. Masoudi, B. Khamidehi, and C. Cavdar, “Green cloud computing for
multi cell networks,” in Proc. IEEE Wireless Commun. and Networking
between SMDs in MEC networks. Moreover, we will jointly
Conf. (WCNC), San Francisco, CA, USA, Mar. 2017, pp. 1–6.
consider computation offloading, resource allocation, content [16] C. Wang, F. R. Yu, C. Liang, Q. Chen, and L. Tang, “Joint computation
caching, and task-precedence constraints among tasks to meet offloading and interference management in wireless cellular networks
the requirements of various applications. To be specific, we with mobile edge computing,” IEEE Trans. Veh. Technol., vol. 66, no. 8,
pp. 7432–7445, Mar. 2017.
will study a centralized MEC scenario with limited computing
[17] S. E. Mahmoodi, R.N. Uma, and K. P. Subbalakshmi, “Optimal joint
and spectrum resources, jointly taking computation offloading, scheduling and cloud offloading for mobile applications,” IEEE Trans.
resource allocation, content caching, and task-precedence Cloud Comput., vol. 7, no. 2, pp. 301–313, Apr. 2019.
constraints into account. We will model this complicated [18] X. Xu, Y. Li, T. Huang, Y. Xue, K. Peng, L. Qi, and W. Dou, “An
energy-aware computation offloading method for smart edge computing
scenario as a new multiobjective optimization problem (MOP).
in wireless metropolitan area networks,” J. Netw. Comput. Appl., vol.
There are three objectives for minimization at the same time, 133, pp. 75–85, May 2019.
including the completion time of applications, the energy [19] L. Yang, H. Zhang, M. Li, J. Guo, and H. Ji, “Mobile edge computing
consumption of SMDs and the resource cost of SMDs. The empowered energy efficient task offloading in 5G,” IEEE Trans. Veh.
Technol., vol. 67, no. 7, pp. 6398–6409, Jan. 2018.
resource cost includes the cost for renting computing
[20] B. Huang, Z. Li, P. Tang, S. Wang, J. Zhao, H. Hu, W. Li, and V. Chang,
resources from MEC servers, and that for leasing spectrum “Security modeling and efficient computation offloading for service
resources from small cell. In addition, we will propose an workflow in mobile edge computing,” Future Gener. Comp. Sy., vol. 97,
efficient multiobjective optimization algorithm to address the pp. 755–774, Aug. 2019.
[21] H. Guo and J. Liu, “Collaborative computation offloading for
problem.
multiaccess edge computing over fiber–wireless networks,” IEEE Trans.
Veh. Technol., vol. 67, no. 5, pp. 4514–4526, Jan. 2018.
REFERENCES [22] W. Zhang and Y. Wen, “Energy-efficient task execution for application
as a general topology in mobile cloud computing,” IEEE Trans. Cloud
[1] E. Novak, Z. Tang, and Q. Li, “Ultrasound proximity networking on
smart mobile devices for IoT applications,” IEEE Internet Things J., vol. Comput., vol. 6, no. 8, pp. 708–719, Jul. 2018.
[23] F. Guo, H. Zhang, H. Ji, X. Li, and V. C. Leung, “An efficient
6, no. 1, pp. 399–409, Feb. 2019.
[2] D. Mazza, A. Bernaus, D. Tarchi, A. A. Juan, and G. Corazza, computation offloading management scheme in the densely deployed
small cell networks with mobile edge computing,” IEEE ACM/Trans.
“Supporting mobile cloud computing in smart cities via randomized
algorithms,” IEEE Syst. J., vol. 12, no. 2, pp. 1598–1609, Jun. 2018. Network., vol. 26, no. 6, pp. 2651–2664, Oct. 2018.
[24] Z. Kuang, Y. Shi, S. Guo, J. Dan, and B. Xiao, “Multi-user offloading [44] H. Li, J. Deng, Q. Zhang, and J. Sun, “Adaptive epsilon dominance in
game strategy in OFDMA mobile cloud computing system,” IEEE Trans. decomposition-based multiobjective evolutionary algorithm,” Swarm
Veh. Technol., vol. 68, no. 12, pp. 12190–12201, Dec. 2019. Evol. Comput., vol. 45, pp. 52–67, Mar. 2019.
[25] X. Lin, Y. Wang, Q. Xie, and M. Pedram, “Task scheduling with [45] H. Liu, J. Pu, L. Yang, M. Lin, D. Yin, Y. Guo, and X. Chen, “A holistic
dynamic voltage and frequency scaling for energy minimization in the optimization framework for mobile cloud task scheduling,” IEEE Trans.
mobile cloud computing environment,” IEEE Trans. Serv. Comput., vol. Sus. Comput., vol. 4, no. 2, pp. 217–230, Oct. 2019.
8, no. 2, pp. 175–186, Dec. 2015. [46] W. Kang and J. Chung, “Power-and time-aware deep learning inference
[26] J. Zhang, X. Hu, Z. Ning, E. C. H. Ngai, L. Zhou, J. Wei, J. Cheng, and for mobile embedded devices,” IEEE Access, vol. 7, pp. 3778–3789, Dec.
B. Hu, “Energy-latency trade-off for energy-aware offloading in mobile 2019.
edge computing networks,” IEEE Internet Things J., vol. 5, no. 4, pp. [47] S. Srichandan, T. Kumar, and S. Bibhudatta, “Task scheduling for cloud
2633–2645, Dec. 2018. computing using multi-objective hybrid bacteria foraging algorithm,”
[27] H. Peng, W. Wen, M. Tseng, and L. Li, “Joint optimization method for Future Comput. Inform. J., vol. 3, no. 2, pp. 210–230, Dec. 2018.
task scheduling time and energy consumption in mobile cloud [48] T. Wu, H. Gu, J. Zhou, T. Wei, X. Liu, and M. Chen, “Soft error-aware
computing environment,” Appl. Soft Comput., vol. 80, pp. 534–545, Jul. energy-efficient task scheduling for workflow applications in
2019. DVFS-enabled cloud,” J. Syst. Architect., vol. 84, pp. 12–27, Mar. 2018.
[28] S. Guo, J. Liu, Y. Yang, B. Xiao, and Z. Li, “Energy-efficient dynamic [49] R. E. Walpole, R. H. Myers, S. L. Myers, and K. Ye, “Probability and
computation offloading and cooperative task scheduling in mobile cloud statistics for engineers and scientists,” Pearson Educ., 2007.
computing,” IEEE Trans. Mobile Comput., vol. 18, no. 2, pp. 319–333, [50] M. Friedman, “A comparison of alternative tests of significance for the
Apr. 2019. problem of m rankings,” Ann. Math. Stat., vol. 11, no. 1, pp. 86–92, Mar.
[29] Q. Wang, S. Guo, J. Liu, and Y. Yang, “Energy-efficient computation 1940.
offloading and resource allocation for delay-sensitive mobile edge [51] L. Wang and X. Zheng, “A knowledge-guided multi-objective fruit fly
computing,” Sustain. Comput. Infor., vol. 21, pp. 154–164, Mar. 2019. optimization algorithm for the multi-skill resource constrained project
[30] L. Cui, C. Xu, S. Yang, J. Huang, J. Li, X. Wang, Z. Ming, and N. Lu, scheduling problem,” Swarm Evol. Comput., vol. 38, pp. 54–63, Feb.
“Joint optimization of energy consumption and latency in mobile edge 2018.
computing for Internet of things,” IEEE Internet Things J., vol. 6, no. 3,
pp. 4791–4803, Sep. 2019.
[31] H. Xing, Z. Wang, T. Li, H. Li, and R. Qu, “An improved MOEA/D
algorithm for multi-objective multicast routing with network coding,”
Appl. Soft Comput., vol. 59, pp. 88–103, Oct. 2017.
[32] W. Xu, C. Chen, S. Ding, and P. M. Pardalos, “A bi-objective dynamic
collaborative task assignment under uncertainty using modified
MOEA/D with heuristic initialization,” Expert Syst. Appl., vol. 140, pp. Fuhong Song received the M.Eng. degree from
1–24, Feb. 2020. Southwest Jiaotong University, Chengdu, China, in 2018.
[33] C. Wang, W. Zhao, W. Li, and L. Yu, “Multi-objective optimisation of He is currently pursuing the Ph.D. degree at the School
electro–hydraulic braking system based on MOEA/D algorithm,” IET of Information Science and Technology, Southwest
Intell. Transp. Sy., vol. 13, no. 1, pp. 183–193, Jan. 2019. Jiaotong University, Chengdu, China.
[34] C. Shu, Z. Zhao, Y. Han, G. Min, and H. Duan, “Multi-user offloading His current research interests include mobile edge
for edge computing networks: A dependency-aware and latency-optimal computing, multiobjective optimization, and machine
approach,” IEEE Internet Things J., pp. 1–12, 2020, doi: learning.
10.1109/JIOT.2019.2943373.
[35] Y. Kwok and I. Ahmad, “Static scheduling algorithms for allocating
directed task graphs to multiprocessors,” ACM Comput. Surv., vol. 31,
no. 4, pp. 406–471, Dec. 1999. Huanlai Xing received the B.Eng. degree in
[36] Y. Liu, S. Wang, Q, Zhao, S. Du, A. Zhou, and X. Ma, communications engineering from Southwest Jiaotong
“Dependency-aware task scheduling in vehicular edge computing,” University, Chengdu, China, in 2006, the M.Eng. degree
IEEE Internet Things J., pp. 1–11, 2020, doi: in electromagnetic fields and wavelength technology
10.1109/JIOT.2020.2972041. from Beijing University of Posts and
[37] W. Aalst and K. Hee, “Workflow management: Models, methods, and Telecommunications, Beijing, China, in 2009, and the
systems,” The MIT Press, 2004. Ph.D. degree in computer science from University of
[38] T. Zhu, T. Shi, J. Li, Z. Cai, and X. Zhou, “Task scheduling in Nottingham, Nottingham, U.K., in 2013.
deadline-aware mobile edge computing systems,” IEEE Internet Things He is currently an Associate Professor with the
J., vol. 6, no. 3, pp. 4854–4866, Jun. 2019. School of Information Science and Technology,
[39] L. Antonio and C. C. Coello, “Coevolutionary multiobjective Southwest Jiaotong University, Chengdu, China. His current research interests
evolutionary algorithms: Survey of the state-of-the-art,” IEEE Trans. include mobile edge computing, network function virtualization, software
Evol. Comput., vol. 22, no. 6, pp. 851–865, Oct. 2018. defined networks, and evolutionary computation.
[40] A. Trivedi, D. Srinivasan, K. Sanyal, and A. Ghosh, “A survey of
multiobjective evolutionary algorithms based on decomposition,” IEEE
Trans. Evol. Comput., vol. 21, no. 3, pp. 440–462, Sep. 2017. Shouxi Luo received the bachelor’s degree in
[41] B. H. Nguyen, B. Xue, P. Andreae, H. Ishibuchi, and M. Zhang, communication engineering and the Ph.D. degree in
“Multiple reference points-based decomposition for multiobjective communication and information systems from the
feature selection in classification: Static and dynamic mechanisms,” University of Electronic Science and Technology of
IEEE Trans. Evol. Comput., vol. 24, no. 1, pp. 170–184, Feb. 2020. China, Chengdu, China, in 2011 and 2016,
[42] G. Zhang, Y. Hu, J. Sun, and W. Zhang, “An improved genetic algorithm respectively.
for the flexible job shop scheduling problem with multiple time He is currently a Lecturer with the School of
constraints,” Swarm Evol. Comput., vol. 54, pp. 1–15, May 2020. Information Science and Technology, Southwest
[43] M. Wu, K. Li, S. Kwong, Q. Zhang, and J. Zhang, “Learning to Jiaotong University, Chengdu, China. His current
decompose: A paradigm for decomposition-based multiobjective research interests include data center networks,
optimization,” IEEE Trans. Evol. Comput., vol. 23, no. 3, pp. 376–390, software-defined networking, and networked systems.
Aug. 2019.
 Dawei Zhan received the B.Eng. degree and the Ph.D.
degree in School of Naval Architecture and Ocean
Engineering from Huazhong University of Science and
Technology, Wuhan, China, in 2012 and 2018,
respectively.
His current research interests include evolutionary
algorithms, surrogate modeling, and surrogate-based
optimization.

Penglin Dai received the B.S. degree in mathematics

and applied mathematics and the Ph.D. degree in
computer science from Chongqing University,
Chongqing, China, in 2012 and 2017, respectively.
He is currently an Assistant Professor with the
School of Information Science and Technology,
Southwest Jiaotong University, Chengdu, China. His
current research interests include intelligent
transportation systems and vehicular cyber-physical
systems.

Rong Qu received the B.Sc. in Computer Science and

Its Applications from Xidian University, Xian, China
in 1996 and Ph.D. in Computer Science from The
University of Nottingham, Nottingham, U.K., in 2003.
She is an associated editor at IEEE Computational
Intelligence Magazine, IEEE Transactions on
Evolutionary Computation, Journal of Operational
Research Society and PeerJ Computer Science. She is
a Senior IEEE Member since 2012 and the Vice-Chair
of Evolutionary Computation Task Committee at
IEEE Computational Intelligence Society. Her current research interests
include the modeling and automated design of optimization algorithms for
combinatorial optimization problems including logistics transport scheduling,
personnel scheduling, network routing, portfolio optimization and timetabling
by using evolutionary algorithms, mathematical programming, constraint
programming in operational research and artificial intelligence. The hybrid
techniques integrated with knowledge discovery and machine learning provide
intelligent decision support for real-world complex problems at SMEs,
hospitals, education and industry.