## 3 The Multiple Workflows Allocation Model
### Workflow Model  
A set of workflows, W = {wf\({}_{i}\): i = 1, 2,..., N}, comprising N independent workflows, is considered for processing. A DAG is used to represent each workflow. The workflow consists of a set of tasks \(\tau_{i}=\{T_{ij}\}\)\(\big{|}1\leq i\leq N,1\leq j\leq n_{i}\big{\}}\) and a set of connections (edges). Tasks in the workflows may require some inter-task communication with parent tasks. The following attributes of workflows are listed:  
* N is the number of compute-intensive multiple workflows. * Each Tij is labeled with a unique level attribute lij. * Size (Tij) is the size in million instructions (MIs) of Tij. * To manage the dependence and precedence constraints, the upward rank (\(r_{u}\big{(}T_{ij}\big{)}\)) of Tij is calculated. * Li is the workflow level (wf\({}_{i}\)) (Li = max (lij: \(\forall\) level (Tij) \(\in\) wf\({}_{i}\))). * The level of W(L) is the maximum of Li, i.e., L= max (Li). * Workflow has been partitioned into L groups (\(\rho^{L}\)) according to depth levels. * Task communication (TCipq) is also considered between any two tasks Tip and Tiqq and measured in MIs. Sample workflows for the above-mentioned scenario are shown in Figure 3. Here, individual tasks are presented in various depth levels (level of precedence/level). The levels of each workflow in W may not be the same. Tasks in wf\({}_{i}\) at the same depth level have been shown in the same color, e.g., set of tasks (T11, T12, T13, T21,...,T1N1) and (T14, T22, T23,..., TN2) have precedence level 1 and 2 with dark green and yellow colors, respectively. Other level tasks can also be categorized in the same manner as seen in Figure 3. Further, T14 is seen to be a child task with three parent tasks T11, T12, and T13. The execution of child tasks depends on the execution of the parent tasks. In other words, child tasks will be executed after parent tasks. The tasks with the same level are siblings and can be executed simultaneously (e.g., T14, T22, T23,...,TN2). The communication cost, when allocating tasks to different VMs in a cloud environment is the overhead of sending data between tasks on various VMs. Data exchange size, VM distance (e.g., between data centers or regions), and network bandwidth or latency affect this cost. High communication costs can slow workflow execution, especially for highly interconnected operations or big data transfers. Efficient scheduling algorithms assign jobs with frequent interactions to the same VM or nearby VMs to reduce data transfer times and costs. Communication costs can be reduced by data compression, caching, and high-speed network connections. Cloud workflows must balance communication and computational costs to be efficient and cost-effective. Here, the level of communication is influenced by two factors: machine distance (MD\({}_{\text{kr}}\)) and task communication (TC\({}_{\text{ipq}}\)). The communication cost is calculated as in our previous work [11]. The communication cost (CC\({}_{ipqkr}^{l,l-s}\) ) of tasks T\({}_{\text{iq}}\in\rho^{l}\) and T\({}_{\text{ip}}\in\rho^{l-s}\) assigned on machine VM\({}_{\text{k}}\) and VM\({}_{\text{r}}\), respectively, can be computed as [11]  
\[CC_{ipqkr}^{l-s,l}=L_{r}+w\big{(}TC_{ipq}\times MD_{kr}\big{)} \tag{1}\]  
where L\({}_{\text{r}}\) is the latency and w is the constant of proportionality. Now, we see that CC\({}_{ipqkr}^{l-s,l}\) is directly proportional to the TC\({}_{\text{ipq}}\) and MD\({}_{\text{kr}}\). If the relationship between \(CC_{ipqkr}^{l-s,l}\) and TC\({}_{\text{ipq}}\), MD\({}_{\text{kr}}\) is taken to be linear, the value of \(w\) will be one.