## 4 The Proposed DSB Workflow Scheduling Algorithm
### Basic Definitions  
**Definition 1**: _Estimated runtime of task \(v_{i}\) on a VM \(m_{r}\), denoted by \(RT_{i}^{r}\), is computed using Equation (1)._  
\[RT_{i}^{r}=\frac{l_{i}}{p_{r}\times(1-pv_{r})} \tag{1}\]  
where \(l_{i}\) is the service length of task \(v_{i}\) measured in Floating Point Operations (FLOP), \(p_{r}\) is the Central Processing Unit (CPU) processing capacity of VM \(m_{r}\) in Million Floating Point Operations Per Second (MFLOPS) based on the number of EC2 compute units and \(pv_{r}\) is the VM performance variability which represent the uncertainties such as potential variability or degradation in CPU performance in real cloud environments. **Definition 2**: _Communication time of edge \(e_{ij}\) between tasks \(v_{i}\) and \(v_{j}\) on VM \(m_{r}\), denoted by \(CT_{ij}^{r}\), is computed using Equation (2)._  
\[CT_{ij}^{r}=s_{ij}/b_{r} \tag{2}\]  
where \(s_{ij}\) is the size of data needed to be communicated from tasks \(v_{i}\) and \(v_{j}\) in Megabytes (MB) and \(b_{r}\) is the bandwidth capacity of VM \(m_{r}\) in Megabytes Per Second (MBps). **Definition 3**: _Execution time of task \(v_{i}\) on a VM, denoted by \(ET_{i}^{r}\), is computed using Equation (3)._  
\[ET_{i}^{r}=RT_{i}^{r}+\max_{v_{i}\in pred(i)}CT_{ij}^{r}+d_{r} \tag{3}\]  
In IaaS cloud, provisioning delay in VM allocation, that is \(d_{r}\) can be caused by multiple factors such as, data center location, VM setup time, software setup time, VM migration time, quantity of simultaneous VM provisioning requests and variations in VM types, Operating Systems (OS) and time zones. **Definition 4**: _Start time of running task \(v_{i}\) on VM \(m_{r}\), denoted by \(ST_{i}^{r}\), is computed as in Equation (4)._  
\[ST_{i}^{r}=slt_{r}+\sum_{v_{p}\in pred(v_{i})}ET_{p}^{r} \tag{4}\]  
where \(slt_{r}\) is start leasing time of VM \(m_{r}\) and \(\sum_{v_{p}\in pred(v_{i})}ET_{p}^{r}\) is the total execution time of assigned tasks to VM \(m_{r}\). **Definition 5**: _Execution cost of task \(v_{i}\) on VM \(m_{r}\), denoted by \(EC_{i}^{r}\), is computed as in Equation (5)._\[EC_{i}^{\tau}=\left(\frac{ET_{i}^{\tau}\times c_{r}}{h_{r}}\right)+\left(s_{ij} \times tc_{ij}\right) \tag{5}\]  
where \(h_{r}\) represents used billing interval of VM \(m_{r}\), \(c_{r}\) represents the cost per interval unit of VM \(m_{r}\), \(s_{ij}\) is the size of the data to be transferred from \(v_{i}\) to \(v_{j}\) and \(tc_{ij}\) represents the data transfer cost (per MB) of communicating data from task \(v_{i}\) to \(v_{j}\). It becomes zero, if the tasks are scheduled on VMs within the same data center. So, we also do not consider this price when calculating the workflow's execution cost. **Definition 6**. : _The upward rank for a task \(v_{i}\) is the length of critical/longest path from task \(v_{i}\) to the exit task \((v_{exit})\), including the execution time of \(v_{i}\). Thus, the priority of each task is defined as given by [PERSON] et al. (2019)._  
\[urank_{i}=RT_{i}+\max_{v_{j}\in succ(v_{i})}\left(CT_{ij}+urank_{j}\right) \tag{6}\]  
**Definition 7**. : _The Degree of Dependency of each task \(v_{i}\), denoted as \(DD_{i}\), is provided by Equation (7)._  
\[dd_{i}=\left(\sum_{v_{p}\in pred(v_{i})}e_{p,i}+\sum_{v_{c}\in succ(v_{i})}e_{ i,c}\right) \tag{7}\]  
where \(\sum_{v_{p}\in pred(v_{i})}e_{p,i}\) is the sum of all inward edges of task \(v_{i}\) and \(\sum_{v_{p}\in pred(v_{i})}e_{p,i}\) is the sum of all outward edges of task \(v_{i}\). **Definition 8**. : _Level of a task \(v_{j}\) in the workflow, denoted as \(lv(v_{j})\), is defined as the maximum number of edges from the task \(v_{entry}\) to \(v_{j}\). All the tasks in a BoT have same level. It is computed by Equation (8). Level of \(v_{entry}\) is assumed to be zero._  
\[lv(v_{j})=1+\max_{v_{i}\in pred(v_{j})}\left(lv(v_{i})\right) \tag{8}\]  
**Definition 9**. : _Finish Time of task \(v_{i}\) on VM \(m_{r}\) is computed as in Equation (9)._  
\[FT_{i}^{\tau}=ST_{i}^{\tau}+ET_{i}^{\tau} \tag{9}\]  
**Definition 10**.