## 3 The Multiple Workflows Allocation Model
### Problem Formulation and Parameter Estimation  
Effectively managing multiple workflows in an IaaS cloud environment while respecting precedence constraints and utilizing heterogeneous resources is a challenging task. The objective is to reduce the total time needed to complete several processes while taking into account the diverse range of resources and task priority precedence constraints. For the purpose of computing the optimum schedule, the workflow allocation problem is established and formulated here. The mapping (m) between W and VM in the cloud system can be used to establish the workflow allocation as  
\[\text{m}:\text{ W}\rightarrow\text{ VM} \tag{3}\]  
To minimize the makespan (MS) subject to the following constraints  
\[\text{i.}\quad\sum_{j=1}^{n_{\text{wf}_{1}}}\text{ Allocation }[\text{i}][\text{j}][\text{k}]=\text{P}_{i}\text{ where }0\leq\text{P}\leq\text{n}_{i}\]  
\[\text{ii.}\quad\sum_{k=1}^{\text{K}}\text{ Allocation }[\text{i}][\text{j}][\text{k}]=1\]  
\[\text{iii.}\quad\sum_{i=1}^{\text{N}}\sum_{j=1}^{\text{n}_{i}}\sum_{k=1}^{ \text{K}}\text{ Allocation }[\text{i}][\text{j}][\text{k}]=\sum_{i=1}^{\text{N}}\text{n}_{i}\]  
\[\text{iv.}\quad\text{EST}\Big{(}\text{T}_{\text{ijk}}\Big{)}\geq\max\{\text{ EFT}\big{[}\text{Pred}\big{(}\text{T}_{\text{ij}}\big{)}\big{]}\}\]  
The process starts with the merging of \(\forall\text{Wf}_{i}\in\text{W}\) by using a pseudo entry and exit task at both ends. Afterward, the allocation workflows were performed in accordance with the technique that is detailed in the following Section 4.1. The allocation procedure is illustrated level-wise in Section 4.2. If a task has no parent task in a workflow, it is known as a source task, i.e., \(\textit{Pred}_{\bar{j}}=\Phi\), and if a task has no child task in a workflow, it is known as a sink task, i.e., \(\textit{Succ}_{\bar{j}}=\Phi\). The level of \(W\) and maximum level of \(L\) of any task \(T_{ij}\in W\) are defined as per Equations (4) and (5), respectively. The number of depth levels of \(T_{\bar{j}}\) is determined recursively as follows:  
\[l=\left\{ \begin{array}{c}1,\;Pred_{ij}=\Phi\\ 1+\text{max}\{l_{ix}:\forall\;t_{ix}\in\textit{Pred}_{\bar{j}}\},\;Pred_{\bar{ j}}\
eq\Phi\end{array} \right. \tag{4}\]  
Figure 3: Sample multiple workflow. \[L=max_{i=1}^{N}\
_{i}^{i_{i}}[l_{ij}]=\max\{l_{ij}:\forall\ T_{ij},Succ_{ij}= \Phi\} \tag{5}\]  
The average expected execution time (\(\overline{E_{ij}}\)) for task \(T_{ij}\) is estimated as the mean of the execution time of the considered task on all VMs available at the time of allocation and can be written by using Equation (6). \[\overline{E_{ij}}=\frac{1}{K}\left[\sum_{k=1}^{K}E_{ijk}\right] \tag{6}\]  
Every entry task, \(\forall\ \text{wf}_{i}\in W\), is joined with a pseudo entry task (T\({}_{\text{entry}}\)), and every exit task in W is also joined with a pseudo exit task (T\({}_{\text{exit}}\)) in such a way that W is converted into a single DAG. The execution cost of these pseudo tasks and the communication cost between the edge joining these pseudo tasks to entry or exit tasks are zero. For finding the topological order of the tasks in the workflows for processing, the upward rank for all tasks is computed using Equation (7) as  
\[\text{r}_{\text{u}}\big{(}\text{T}_{\text{ij}}\big{)}=\overline{\text{E}_{ \text{ij}}}+\underbrace{Max}_{T_{ip}\in succ(T_{ij})}\big{(}\overline{C_{ij} }+r_{u}\big{(}T_{ip}\big{)}\big{)} \tag{7}\]  
Here, succ(T\({}_{\text{ij}}\)) is the set of immediate successors of the task T\({}_{\text{ip}}\). The rank of entry tasks is equal to the average values of the expected execution time (\(\overline{E_{exit}}\)). The critical path length from task T\({}_{\text{ij}}\) to T\({}_{\text{exit}}\), which includes task T\({}_{\text{ij}}\)'s execution cost, is represented by the upward rank of T\({}_{\text{ij}}\)(r\({}_{\text{u}}\)(T\({}_{\text{ij}}\))). Allocation of the batch of workflows begins by dividing the tasks into partitions (\(\rho^{l}\): \(l\leq 1\leq L\)) as the depth level.