## 3 Scheduling Problem Formation
### Application Model  
The workflow is a directed acyclic graph (DAG) [38] which is represented by D = (T, E), where T = {T\({}_{1}\), T\({}_{2}\),..., T\({}_{n}\)} is indicative of a set of tasks and E represents the set of directed edges between the tasks, standing dependencies, or communication between the set of tasks [39]. Each directed edge \(\mathrm{e_{ps}}\) = (T\({}_{p}\),T\({}_{s}\)) belongs to E, where tasks T\({}_{p}\) and T\({}_{s}\) are indicative of precedence constraint. This means that the task, T\({}_{s}\), cannot start its execution until task T\({}_{p}\) is completed. In workflow applications, a T\({}_{p}\) without any predecessors is referred as an entry task, T\({}_{entry}\), and a T\({}_{s}\) without any successor task is referred to as an exit task, T\({}_{exit}\). If the workflow application contains multiple instances of T\({}_{entry}\) or T\({}_{exit}\), then a virtual edge with zero computation time and zero execution time is to be assumed. **Scheduling Factors:**  
**Data Transfer Time:**  
\[\mathrm{DTT}= \begin{array}{cccc}\mathrm{T_{1}}&\mathrm{T_{2}}&\ldots& \mathrm{T_{n}}\\ \mathrm{T_{2}}&\mathrm{T_{1}}&\left[\begin{array}{cccc}0&\mathrm{DTT}_{1,2}& \ldots&\mathrm{DTT}_{1,n}\\ 0&0&\ldots&\mathrm{DTT}_{2,n}\\ \vdots&\vdots&\ldots&\vdots\\ 0&0&\ldots&0\end{array}\right]\end{array}  \tag{1}\]  
In Equation (1), DTT refers to the data transfer time and the element DTT\({}_{p,q}\), \(1\leq p\leq n\) and \(1\leq q\leq n\) indicates the data transfer time between T\({}_{p}\) and T\({}_{q}\). \begin{table}
\begin{tabular}{p{113.8 pt} p{113.8 pt}} \hline \hline
**Abbreviations** & **Definitions** \\ \hline DTT & Data transfer time \\ \hline DTTp\({}_{q}\) & Data transfer time from T\({}_{p}\) to T\({}_{q}\) \\ \hline CS & Cloud server \\ \hline E\({}^{\mathrm{ct}}\) & Estimated computation time \\ \hline Ms & Makespan \\ \hline A\({}_{\mathrm{cu}}\) & Average cloud utilization \\ \hline t\({}_{p}\) & Predecessor task \\ \hline t\({}_{s}\) & Successor task \\ \hline E\({}^{\mathrm{st}}\) & Early start time \\ \hline E\({}^{\mathrm{ft}}\) & Early finish time \\ \hline N\(\_{e}^{\mathrm{ct}}\) & Normalized estimated computation time \\ \hline Pt\({}_{\mathrm{vm}}\) & Processing time on VM \\ \hline R\({}_{\mathrm{same}}\) & Same resource \\ \hline Th(dTi) & A threshold value of each task, T\({}_{i}\) \\ \hline RLi & Ready List of tasks at level 1 of DAG \\ \hline T\(\_{N\_{e}}^{\mathrm{ct}}\) & Temporary normalized estimated computation time \\ \hline T\(\_{E}^{\mathrm{ct}}\) & Temporary estimated computation time \\ \hline Act & Actual completion time \\ \hline \hline \end{tabular}
\end{table} 
Table 2: List of Notations. Estimated Computation Time:  
The task execution time may vary depending on the VMs. The estimated computation time (E\({}^{\text{ct}}\)) is calculated according to Equation (2). \[ \begin{array}{ccccc}\text{cs}_{1}&&\cdots&&\text{cs}_{\text{m}}\\ \text{vm}_{1}&\cdots&\text{vm}_{\text{n}|\text{cs}_{\text{n}}|}&\cdots&\text{vm }_{\text{n}|\text{cs}_{\text{m}}|}\\ \text{T}_{1}\begin{bmatrix}\text{Et}_{1,1}&\cdots&\text{Et}_{1|\text{CS}_{1}|} &\cdots&\text{Et}_{1|\text{CS}_{\text{m}}|}\\ \vdots&\cdots&\vdots&\cdots&\vdots\\ \text{Et}_{n,1}&\cdots&\text{Et}_{n|\text{CS}_{1}|}&\cdots&\text{Et}_{1|\text{CS }_{\text{m}}|}\end{bmatrix}\end{array}  \tag{2}\]  
where Et\({}_{\text{p},\text{q}}\), \(1\leq\text{p}\leq\text{n}\) and \(1\leq\text{q}\leq|\text{CS}_{\text{m}}|\) indicates the estimated computation time of T\({}_{\text{p}}\) on the VM of the cloud server \(|\text{CS}_{\text{m}}|\). Makespan:  
Makespan is referred to the time it takes to complete a given task. Minimizing makespan is a popular optimization criterion when scheduling tasks because most users want their applications to run as quickly as possible. Makespan, \(M_{s}\), is calculated as per Equation (3):  
\[\text{M}_{\text{s}}{=}\max(\text{Makespan}(\text{CS}_{\text{m}})),1\leq\text{ CS}\leq\text{m} \tag{3}\]  
where M\({}_{\text{s}}\) is the overall makespan of tasks on the cloud server, CS\({}_{\text{m}}\).