## 4 The Proposed DSB Workflow Scheduling Algorithm
### Proposed Algorithm
#### 4.4.5 Elastic Resource Provisioning
```
procedureERP(Execution queue containing set of ready BoTs \(ExeQ\), Set of VM types \(VM\))
1\(ExeQ^{new}\ \leftarrow\ null\)
2 forall\(bot_{q}\in ExeQ\)
3 if\(bot_{q}\_count(tasks)\ >1\)then
4 Solve the MIP problem by CPLEX and get \(\mathcal{SP}_{bot}^{r}\)
5 forall\(\mathcal{SP}_{q}^{r}=(m_{r},m_{q^{\prime}}^{r},k_{bot_{t}}^{m_{r}})\)do
6 forall\(m_{r}\in\mathcal{SP}_{q}^{r}\)do
7\(ExeQ\leftarrow\frac{m_{r}^{r}}{q}\)
8\(VM\leftarrow\sum_{bot}^{m_{r}}\)
9\(ExeQ^{new}\ \leftarrow\) Call LFI(ExeQ, VM)
10 if\(ExeQ^{new}\
eq null\)then
11 Call RSU(\(ExeQ^{new},\ VM\))
12 endif
13 endfor
14 endfor
15 elseif\(bot_{q}\_count(tasks)=1\)then
16\(v_{run}\gets bot_{q}\)
17\(m_{sel}\leftarrow\) select cheapest VM that can run task within deadline
18 Schedule \(v_{run}\) to \(m_{sel}\)
19\(ExeQ\gets ExeQ-\{v_{run}\}\)
20\(CT^{sel}\gets CPT^{sel}+ET_{sel}^{run}\)
21 Update next available time of \(m_{sel}\)
22 endif
23 endfor
```  
**Algorithm 2****Elastic Resource Provisioning**  
```
procedureLFI(Set of ready tasks of BoT \(ExeQ\), Set of VMs \(VM\))
1\(v_{run}\leftarrow\) Get the next ready task with highest priority from \(ExeQ\)
2\(m_{sel}\gets null\)
3\(M_{sel}\gets null\)
4\(m\leftarrow null\)
5\(freenetural\leftarrow false\)
6 forall\(m_{r}\in VM\)do
7 Calculate \(EC_{run}\) //according to Equation (5)
8 Calculate \(FT_{run}\) //according to Equation (9)
9 if\(EC_{run}<SD_{run}\)and\(FT_{run}^{r}<SD_{run}\)then
10\(freenetural\leftarrow true\)
11\(M_{sel}\gets M_{sel}\cup\{m_{r}\}\)
12 endif
13 endfor
14\(m_{sel}\gets m_{r}\in M_{sel}\) such that \(EF_{run}^{sel}\) is minimum
15 if\(m_{sel}\
eq null\)then
16\(m_{t}\gets m_{sel}\)
17 endif
18 if\(freenetural=true\)then
19 Schedule\(v_{run}\)to\(m_{sel}\)
20\(ExeQ\gets ExeQ-\{v_{run}\}\)
21\(CPT^{sel}\gets CPT^{sel}+ET_{run}^{sel}\)
22 Update next available time of \(m_{sel}\)
23 else
24\(ExeQ^{new}\gets ExeQ^{new}\cup\{v_{run}\}\)
25 endif
```  
**Algorithm 3****Lease Free Interval**  
```
procedureLFI(Set of ready tasks of BoT \(ExeQ\), Set of VMs \(VM\))
1\(v_{run}\leftarrow\) Get the next ready task with highest priority from \(ExeQ\)
2\(m_{sel}\gets null\)
3\(M_{sel}\gets null\)
4\(m_{t}\gets null\)
5\(freenetural\leftarrow false\)
6 forall\(m_{r}\in VM\)do
7 Calculate \(EC_{run}\) //according to Equation (5)
8 Calculate \(FT_{run}\) //according to Equation (9)
9 if\(EC_{run}^{r}<SD_{run}\)and\(FT_{run}^{r}<SD_{run}\)then
10\(freenetural\leftarrow true\)
11\(M_{sel}\gets M_{sel}\cup\{m_{r}\}\)
12 endif
13 endfor
14\(m_{sel}\gets m_{r}\in M_{sel}\) such that \(EF_{run}^{sel}\) is minimum
15 if\(m_{sel}\
eq null\)then
16\(m_{t}\gets m_{sel}\)
17 endif
18 if\(freenetural=true\)then
19 Schedule\(v_{run}\)to\(m_{sel}\)
20\(ExeQ\gets ExeQ-\{v_{run}\}\)
21\(CPT^{sel}\gets CPT^{sel}+ET_{run}^{sel}\)
22 Update next available time of \(m_{sel}\)
23 else
24\(ExeQ^{new}\gets ExeQ^{new}\cup\{v_{run}\}\)
25 endif
```  
**Algorithm 4****Lease Free Interval**  
```
procedureLFI(Set of ready tasks of BoT \(ExeQ\), Set of VM \(VM\))
1\(v_{run}\leftarrow\) Get the next ready task with highest priority from \(ExeQ\)
2\(m_{sel}\gets null\)
3\(M_{sel}\gets null\)
4\(m_{t}\gets null\)
5\(freenetural\leftarrow false\)
6 forall\(m_{t}\in VM\)do
7 Calculate \(EC_{run}\) //according to Equation (5)
8 Calculate \(FT_{run}\) //according to Equation (9)
9 if\(EC_{run}^{r}<SD_{run}\)and\(FT_{run}^{r}<SD_{run}\)then
10\(freenetural\leftarrow true\)
11\(M_{sel}\gets M_{sel}\cup\{m_{r}\}\)
12 endif
13 endfor
14\(m_{sel}\gets m_{r}\in M_{sel}\) such that \(EF_{run}^{sel}\) is minimum
15 if\(m_{sel}\
eq null\)then
16\(m_{t}\gets m_{sel}\)
17 endif
18 if\(freenetural=true\)then
19 Schedule\(v_{run}\)to\(m_{sel}\)
20\(ExeQ\gets ExeQ-\{v_{run}\}\)
21\(CPT^{sel}\gets CPT^{sel}+ET_{run}^{sel}\)
22 Update next available time of \(m_{sel}\)
23 else
24\(ExeQ^{new}\gets ExeQ^{new}\cup\{v_{run}\}\)
25 endif
```  
**Algorithm 5****Lease Free Interval**  
```
procedureLFI(Set of ready tasks of BoT \(ExeQ\), Set of VM \(VM\))
1\(v_{run}\leftarrow\) Get the next ready task with highest priority from \(ExeQ\)
2\(m_{sel}\gets null\)
3\(M_{sel}\gets null\)
4\(m_{t}\gets null\)
5\(freenetural\leftarrow false\)
6 forall\(m_{t}\in VM\)do
7 Calculate \(EC_{run}\) //according to Equation (5)
8 Calculate \(FT_{run}\) //according to Equation (9)
9 if\(EC_{run}^{r}<SD_{run}\)and\(FT_{In order to adapt to unexpected delays such as variations in task runtime estimations, network congestion and resource provisioning delays, the sub-deadline of remaining workflow tasks is adjusted whenever a task finishes either earlier or later than expected.