## 2 Problem Description
### Objective Function  
In this work, we follow the approach of list scheduling algorithms. List scheduling algorithms are a family of heuristics in which tasks are ordered according to a particular priority criterion. The task execution order is equivalent to a DAG \(G=(T,C)\) topological order from the task graph, without violating the precedence constraints. Table 2 shows an example of a feasible order for the task graph from Figure 1.  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Task** & \(\mathbf{m_{1}}\) & \(\mathbf{m_{2}}\) & \(\mathbf{m_{3}}\) \\ \hline \(t_{0}\) & 11 & 13 & 9 \\ \(t_{1}\) & 10 & 15 & 11 \\ \(t_{2}\) & 9 & 12 & 14 \\ \(t_{3}\) & 12 & 16 & 10 \\ \(t_{4}\) & 15 & 11 & 19 \\ \(t_{5}\) & 13 & 9 & 5 \\ \(t_{6}\) & 11 & 15 & 13 \\ \(t_{7}\) & 11 & 15 & 10 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Computational costs of the tasks \(P_{i,j}\) on every machine.  
Figure 1: Graph \(G=(T,C)\) of precedence tasks with communication costs \(C_{i,j}\).  
Although the task order of execution is not indispensable for the scheduling, it simplifies the objective function computation [1], i.e., because it is not necessary to compute different combinations of the tasks, starting and finish times, to compute the minimum makespan [3; 15; 17]. However, this approach has the deficiency that the optimal value may not be possible in every task execution order. Algorithm 1 details the computation of the makespan objective function, using the computation times \(P_{i,j}\) from Table 1 and a time counter (\(Time_{j}\)) for each machine, to keep track of the last executed task in each machine.  
```
0:\(G=(T,C)\), computational costs \(P_{t_{i},i}\), and an order execution of the tasks \(O=\{o_{1},\ldots,o_{|T|}\}\).
0:makespan
1:\(Time_{j}\gets 0\), \(\forall m_{j}\in M\)
2:for\(x=1\) to \(|O|\)do
3:\(t_{current}=o_{x}\)
4:\(j\leftarrow\) the index of the machine \(m_{j}\) assign to \(t_{current}\)
5:if\(\forall u=\{1,...,|T|\}\
exists(t_{u},t_{current})\in C\)then
6:\(ts_{current}\leftarrow\)Time\({}_{j}\)
7:\(tf_{current}\gets ts_{current}+P_{t_{current},j}\)
8:\(Time_{j}\gets tf_{current}\)
9:else
10:\(t_{u^{*}}\leftarrow\operatorname*{argmax}_{\{t_{u}|(t_{u},t_{current})\in C\}} \left(tf_{u}+C^{\prime}_{t_{u},t_{current}}\right)\)
11:\(ts_{current}\leftarrow\max(tf_{u^{*}}+C^{\prime}_{t_{u^{*}},t_{current}},Time _{j})\)
12:\(tf_{current}\gets ts_{current}+P_{t_{current},j}\)
13:\(Time_{j}\gets tf_{current}\)
14:endif
15:endfor
16:returnmakespan\(\leftarrow\max\{tf_{i}\}\forall t_{i}\in T\)
```  
**Algorithm 1**Makespan objective function  
Finally, the parallel program makespan (computation time) is the difference between the start and the ending of the first and last tasks. The makespan objective function uses the auxiliary variables \(ts_{i}\) (the starting time of task \(i\)), \(tf_{i}\) (the finish time of task \(i\)), and \(C^{\prime}_{i,j}\) which is the communication cost that is zero if the tasks are executed in the same machine. The objective is to compute the tasks, from the first to the last of the feasible execution order. Finally, the parallel program makespan (computation time) is the difference between the start and end of the first and last tasks. The complexity of the Algorithm 1 is \(O(|T|\cdot|C|)\), although, in practice, it is remarkably lower than that, because not all the edges in \(G\) are connected to every node.