## 3 Problem Formulation  
This Section introduces the system models and formulates the optimization problem. We consider an edge computing system with a certain number of local processors and MEC servers, as shown in Figure 2. These processors and servers cooperate to compute a set of dependent tasks. Hence, we investigate the problem of offloading dependent tasks in the edge computing system. We begin by listing the notation and terminology in Notation. In the system, the local processors are typically installed in the mobile users and mobile peers. Each local processor is only capable of executing one task at a time, while other assigned tasks wait in a queue. Nevertheless, each MEC server is able to execute multiple tasks concurrently, depending on how many processors it possesses. We also assume a remote cloud center (RCC) which is able to provide an unlimited amount of computation resources. In other words, the processing cores of the remote cloud center are infinite. Therefore, all the assigned tasks can be performed simultaneously. Let \(P\) be the set of all processors and its size be \(M\). Let \(f_{i}\) denote the time taken by processor \(i\) to process per unit workload. Let \(d_{ij}\) define the delay per unit data transfer from processor \(i\) to processor \(j\). It is clear that the value of \(f_{i}\) is much smaller while offloading to RCC, yet the value of \(d_{ij}\) is often much higher. We consider a scenario where a single application must be completed before its deadline \(T_{dl}\). The application is partitioned into multiple tasks, whose dependency is modeled as a Directed Acyclic Graph (DAG), as shown in Figure 3. Let \(G(v,\varepsilon)\) denote a DAG, where \(v\) represents the set of task vertices and \(\varepsilon\) represents the set of directed edges. Each task \(v_{i}\) is assigned with a certain amount of workload, which is represented by \(w_{v_{i}}\). Hence, the execution time of task \(v_{i}\) on processor \(p_{j}\) is  
\[T_{ex}(v_{i})=w_{v_{i}}f_{p_{j}} \tag{1}\]  
Each directed edge \((v_{i},v_{j})\) in \(\varepsilon\) indicates that there is some data, denoted as \(e_{v_{1}v_{j}}\), required to be transferred from \(v_{i}\) to \(v_{j}\). Therefore, \(v_{j}\) will not be able to start until \(v_{i}\) finishes. We define \(v_{i}\) to be the parent of \(v_{j}\). Furthermore, if \(v_{i}\) and \(v_{j}\) are scheduled to be executed on processor \(p_{m}\) and processor \(p_{n}\) respectively, the time taken by data transferring is \(d_{p_{m}p_{n}}e_{v_{2}v_{j}}\). However, such time is ignored if \(v_{i}\) and \(v_{j}\) are scheduled on the same processor, since no data transferring is required. Figure 3: A topology representation of task graphs. Figure 2: An offloading model of a MEC system. It is assumed that the application starts at a particular local processor and must end at the same local processor. For simplicity, we insert one dummy node at the start of DAG to trigger the application, which is referred to as the entry node hereinafter. It has zero weight and no data to be transferred. Likewise, one dummy node, called the exit node, is inserted at the end of DAG to retrieve the results at the processor where the application started. Therefore, the number of tasks considered is  
\[N=|v|+2 \tag{2}\]  
Each task shall be assigned to a position of a processor; hence, the task-scheduling decision involves both the processor mapping and the relative order of tasks on each processor. Let \(x_{ijr}\) denote the scheduling decision, which is given as follows:  
\[x_{ijr}: \begin{cases}1\;if\;task\;i\;is\;assigned\;to\;processor\;j\;in\; position\;r\\ 0\;if\;otherwise\end{cases}