  Multi-access Edge Computing (MEC) is an enabling technology to leverage new
network applications, such as virtual/augmented reality, by providing faster
task processing at the network edge. This is done by deploying servers closer
to the end users to run the network applications. These applications are often
intensive in terms of task processing, memory usage, and communication; thus
mobile devices may take a long time or even not be able to run them
efficiently. By transferring (offloading) the execution of these applications
to the servers at the network edge, it is possible to achieve a lower
completion time (makespan) and meet application requirements. However,
offloading multiple entire applications to the edge server can overwhelm its
hardware and communication channel, as well as underutilize the mobile devices'
hardware. In this paper, network applications are modeled as Directed Acyclic
Graphs (DAGs) and partitioned into tasks, and only part of these tasks are
offloaded to the edge server. This is the DAG application partitioning and
offloading problem, which is known to be NP-hard. To approximate its solution,
this paper proposes the FlexDO algorithm. FlexDO combines a greedy phase with a
permutation phase to find a set of offloading decisions, and then chooses the
one that achieves the shortest makespan. FlexDO is compared with a proposal
from the literature and two baseline decisions, considering realistic DAG
applications extracted from the Alibaba Cluster Trace Program. Results show
that FlexDO is consistently only 3.9% to 8.9% above the optimal makespan in all
test scenarios, which include different levels of CPU availability, a
multi-user case, and different communication channel transmission rates. FlexDO
outperforms both baseline solutions by a wide margin, and is three times closer
to the optimal makespan than its competitor.
