## 2 Multi-Objective Task Graph Scheduling Problem  
In a multi-objective task graph scheduling problem, all the tasks of a directed acyclic task graph representing a parallel program are distributed over a fully connected heterogeneous distributed system in order to minimize the Makespan (total completion time), minimize the average flow time, and maximize the reliability. Instead of the reliability maximization, the reliability index is minimized in the literature. A task graph comprises some nodes representing the tasks and some directed edges indicating inter-processor communications [30]. The edges are weighted based on the communication cost between the processors when the tasks at the two ends of the edges are performed on different processors. The communication cost turns to zero if the tasks are executed on the same processor [30]. A sample task graph comprising 19 tasks is presented in Figure 2 including the name and time for each task [8; 30]. The tasks are uniquely named by \(t\) followed by a number, and the number in the box on the right side of each task number is the task time. The goal of the task graph scheduling problem is to find an optimal schedule that maps tasks to the processors in a distributed system in order to optimize all the objectives. Figure 2: Sample Task Graph. Task graph scheduling problem is formulated as below [11; 12; 13; 14]:  
\[Min\ f=[f_{1},f_{2},f_{3}] \tag{1}\]  
In Equation (1), \(f_{1},f_{2}\) and \(f_{3}\) state the objective functions where \(f_{1}\) indicates the total scheduling completion time that is known as Makespan. The value of \(f_{1}\) is computed as below. \[f_{1}=max_{j}C_{j}(s) \tag{2}\]  
\(C_{j}\) (s) in Equation (2) is the time that processor p\({}_{j}\) finishes the execution and becomes idle. Consequently, \(max_{j}C_{j}(s)\) indicates the completion time of the last processor in schedule s. The symbol '\(s\)' denotes the scheduling and it points to the scheduling represented by solution representation scheme in Figure 3.  
Total processor p\({}_{j}\) completion time is computed as Equation (3). \[C_{j}(s)=\sum_{i\in\wp(j,s)}\big{(}st_{ij}+w_{ij}\big{)} \tag{3}\]  
In Equation (3), all the tasks assigned to a processor p\({}_{j}\) belong to a set denoted by \(\wp(j,s)\). Likewise, start and finish times of the task \(v_{i}\) on processor p\({}_{j}\) are denoted by \(st_{ij}\) and \(w_{ij}\) respectively. In other words, \(w_{ij}\) is the time processor p\({}_{j}\) finishes executing task \(v_{i}\). Second objective in Equation (1), \(f_{2}\), indicates the average flow-time that is computed as Equation (4). \[f_{2}=aft(s)=\frac{\sum_{j}C_{j}(s)}{|P|} \tag{4}\]  
The value of aft(s) in the schedule s is the summation of all completion times divided by \(|P|\) (number of processors). \(f_{3}\) in Equation (1) denotes the value of the reliability index. It is important to notice that the reliability index minimization is equivalent to the reliability maximization [11; 12]. There is a possibility for the processors to fail during the execution but failure of a processor does not affect the other processors. Probability of successfully performing all the tasks on processor p\({}_{j}\) is computed as Equation (5). \[P_{succ}^{j}(s)=e^{-\lambda_{j}C_{j}(s)} \tag{5}\]  
In Equation (5), \(\lambda_{j}\) is the processor p\({}_{j}\)'s failure rate. Eventually, Probability of successfully performing a schedule s is calculated as Equation (6). \[P_{succ}=e^{-\sum_{j}\lambda_{j}C_{j}(s)} \tag{6}\]  
Likewise, the communication reliability between the processors p\({}_{m}\) and p\({}_{n}\) is computed as Equation (7). \[R_{mn}(V,S)=e^{-\lambda_{mn}\sum_{i=1}^{|V|}\sum_{j=1}^{|V|}s_{im}s_{im}\cdot s _{im}} \tag{7}\]  
In Equation (7), the set of tasks is denoted by \(V\) and the rate of communication failure rate between processors p\({}_{m}\) and p\({}_{n}\) is denoted by \(\lambda_{mn}\). Meanwhile, \(s_{im}\) and \(s_{jn}\) indicate that tasks \(i\) and \(j\) have been mapped to processors p\({}_{m}\) and p\({}_{n}\).