## 4 Levelized Multiple Workflow Heterogeneous Earliest Finish Time
### The LMAEFT Algorithm
Finally, LMHEFT generates a feasible schedule, and the QoS parameters makespan (MS), average utilization (U\({}_{\text{S}}\)), and flowtime (FT) are computed as per Equations (9)-(12). ```
Input: T\({}_{y}\) TC\({}_{\text{Sup}}\), PC\({}_{k}\), MD\({}_{\text{Ex}}\), ETC\({}_{\text{Sub}}\) Output: V\({}_{\text{Sub}}\)
```

**Algorithm 3**\(\left[\text{V}_{\text{Sub}}\right]\) = Allocation (T\({}_{y}\), TC\({}_{\text{Sup}}\), PC\({}_{k}\), MD\({}_{\text{Ex}}\), ETC\({}_{\text{Sub}}\))

The suggested strategy has been created to make use of both workflow-level and sub-workflow-level parallelism. Here, two factors--the number of sub-workflow depth levels and the number of sub-workflows at each depth level--determine how much of the workflow(s) is parallelized. When there are few depth levels or, more accurately, when the average number of sub-workflows at each depth level is high, a workflow is said to be highly parallel. The schedule of the whole batch of workflows on available virtual machines is obtained using the proposed model, which improves makespan, flowtime, and resource utilization. ### An Illustration of LMHEFT Algorithm

An illustration is presented to explain the proposed algorithm with the help of three workflows, WF = (Wf\({}_{1}\), Wf\({}_{2}\), Wf\({}_{3}\)), submitted for execution with 4, 5, and 4 tasks in a cloud computing environment on three VMs. These workflows are merged using two pseudo tasks, at entry and exit as shown in Figure 4. The associated data of the VMs are shown in Figure 5, where the computing capacity (CCk) and initial ready time (RTk) of V1 are 15 and 10, respectively. This merging process using pseudo tasks increases the height/depth of the combined workflows by two. The depth level of the combined workflows is L = max (5, 5, 5) = 5. The edge label is \((TC_{ipq}/\overline{C_{ipq}})\), where \(TC_{ipq}\) is the task communication requirement (in millions of instructions) between T\({}_{\text{ip}}\) and T\({}_{\text{iq}}\), and \(\overline{C_{ipq}}\) is the average communication cost (in time units) computed for the workflow tasks using Equation (2) from Section 3.3 (step 3, Algorithm 1). The complete information on merged workflows, such as the E\({}_{\text{ijk}}\) of each task onto VM\({}_{k}\), the average values of the expected time to compute \((\overline{E_{ij}})\) (steps 1-2, Algorithm 1), and the upward rank \(\left(r_{u}\left(\text{T}_{\text{ij}}\right)\right)\) of the workflow (step 4, Algorithm 1) tasks are shown in Table 1.

In the merged workflow shown in Figure 4, T\({}_{14}\), T\({}_{25}\), T\({}_{33}\), and T\({}_{34}\) are exit tasks, and T\({}_{11}\), T\({}_{21}\), T\({}_{22}\), and T\({}_{31}\) are entry tasks of three workflows (Wf\({}_{1}\), Wf\({}_{2}\), Wf\({}_{3}\)), which are joined with the pseudo entry tasks T\({}_{\text{entry}}\) and exit tasks T\({}_{\text{exit}}\), respectively. T\({}_{\text{exit}}\) has all the edges and vertices labeled zero. So, the upward rank of all exit tasks will be equal to the value of the average execution time \(\left(\overline{\text{E}_{ij}}\right)\), i.e., \(r_{u}\left(\text{T}_{14}\right)\) = 47.78, \(r_{u}\left(\text{T}_{25}\right)\) = 39.42, \(r_{u}\left(\text{T}_{33}\right)\) = 39.42, and \(r_{u}\left(\text{T}_{34}\right)\) = 35.83. Figure 4: A sample of merged workflow. Figure 5: A sample of cloud resources. Now, we calculate the upward rank of the tasks with the child (say T\({}_{12}\)) as per Equation (7). From Table 1, the average ETC value \(\left(\overline{\text{E}_{12}}\right)\) of T\({}_{12}\) is 59.66. The successor task of T\({}_{12}\) is T\({}_{14}\), with \(\overline{C_{124}}\) = 33.3, as shown in Figure 5, and the upward rank of T\({}_{14}\), i.e., \(r_{u}\left(\text{T}_{14}\right)\) = 47.78. Thus, \(r_{u}\left(\text{T}_{12}\right)\) = \(\overline{\text{E}_{12}}\) + max (\(\overline{C_{124}}\) + \(r_{u}\left(\text{T}_{14}\right)\) = 59.66 + max (33.30 + 47.78) = 140.74. Similarly, \(r_{u}\left(\text{T}_{13}\right)\) = 70.59 + max (26.64 + 47.78) = 145.01.