## 4 Levelized Multiple Workflow Heterogeneous Earliest Finish Time
### The LMAEFT Algorithm
The

\begin{table}
\begin{tabular}{c c c c c c c} \hline \multirow{2}{*}{**Depth Level (l)**} & \multirow{2}{*}{**Task (T\({}_{ij}\))**} & \multicolumn{2}{c}{**EST and EFT of T\({}_{ij}\) on Virtual Machine V\({}_{k}\)**} & \multicolumn{2}{c}{**Ready Time of Virtual**} & \multirow{2}{*}{**VM\({}_{k}\)**} \\  & & \multicolumn{2}{c}{**VM\({}_{1}\)**} & \multicolumn{2}{c}{**VM\({}_{2}\)**} & \multicolumn{2}{c}{**VM\({}_{3}\)**} & \multicolumn{2}{c}{**Machine VM\({}_{k}\) (CRT\({}_{k}\))**} \\ \hline \(l=1\) & T\({}_{\rm entry}\) & (10, 10) & (90, 90) & (30, 30) & (10, 90, 30) & VM\({}_{1}\) \\ \hline \multirow{4}{*}{\(l=2\)} & T\({}_{11}\) & (10, 57.2) & (90, 125.4) & (30, 74.25) & (57.2, 90, 30) & VM\({}_{1}\) \\  & T\({}_{31}\) & (57.2, 94.53) & (90, 118) & (30, 65) & (57.2, 90, 65) & VM\({}_{3}\) \\  & T\({}_{22}\) & (57.2, 95.87) & (90, 119) & (65, 101.25) & (95.87, 90, 65) & VM\({}_{1}\) \\  & T\({}_{21}\) & (95.87, 120.87) & (90, 108.75) & (65, 88.44) & (95.87, 90, 88.44) & VM\({}_{3}\) \\ \hline \multirow{4}{*}{\(l=3\)} & T\({}_{13}\) & (95.87, 174.67) & (90, 149.1) & (88.44, 162.315) & (95.87, 149.1, 88.44) & VM\({}_{2}\) \\  & T\({}_{32}\) & (95.87, 187.2) & (149.1, 217.6) & (88.44, 174.066) & (95.87, 149.1, 174.066) & VM\({}_{3}\) \\  & T\({}_{12}\) & (95.87, 162.47) & (149.1, 199.05) & (174.066, 236.506) & (162.47, 149.1, 174.066) & VM\({}_{1}\) \\  & T\({}_{23}\) & (162.47, 211.14) & (149.1, 185.6) & (174.066, 220.691) & (162.47, 185.6, 174.066) & VM\({}_{2}\) \\  & T\({}_{24}\) & (162.47, 201.8) & (185.6, 215.1) & (174.066, 210.941) & (201.8, 185.6, 174.066) & VM\({}_{1}\) \\ \hline \multirow{4}{*}{\(l=5\)} & T\({}_{14}\) & (201.8, 255.13) & (195.77, 235.77) & (195.77, 245.77) & (201.8, 235.77, 174.066) & VM\({}_{2}\) \\  & T\({}_{33}\) & (201.8, 245.8) & (235.77, 268.77) & (215.316, 256.566) & (201.8, 235.77, 215.316) & VM\({}_{3}\) \\  & T\({}_{25}\) & (205.58, 249.58) & (235.77, 265.77) & (215.316, 252.816) & (249.58, 235.77, 215.316) & VM\({}_{1}\) \\  & T\({}_{34}\) & (249.58, 289.58) & (235.77, 26



has \(\mathrm{n_{i}}\) number of tasks. Let \(\mathrm{n}\) and \(\mathrm{p}\) be the average number of workflow tasks in the workflows and partitions, respectively, i.e., \(n=\frac{\sum_{i=1}^{i\to\mathrm{n_{i}}}\mathrm{n_{i}}}{\sum_{i=1}^{i\to \mathrm{n_{i}}}\mathrm{N_{i}}}\). K is the number of VMs. The depth level of \(\mathrm{W}\) is \(\mathrm{L}\)= max (\(l_{\mathrm{\acute{c}}}\) where \(i\) varies from 1 to \(\mathrm{N}\)) = \(\mathrm{log}\) \(\mathrm{n}\). The following points show the time complexity of the workflow task allocation, sorting partitions, and partitioning. * For partitioning, \(\mathrm{O}(\mathrm{L}\ \times\mathrm{N}\times\mathrm{n})\). * For sorting, \(\mathrm{O}(\mathrm{L}\times\mathrm{p}\times\mathrm{p})\). * For allocation, \(\mathrm{O}(\mathrm{L}\times\mathrm{p}\times\mathrm{K})\). Thus, the time complexity of LIMEFT = \(\mathrm{O}(\mathrm{L}\ \times\mathrm{N}\times\mathrm{n})+\mathrm{O}( \mathrm{L}\times\mathrm{p}\times\mathrm{p})+\mathrm{O}(\mathrm{L}\times\mathrm{ p}\times\mathrm{K})\approx\mathrm{O}(\mathrm{L}\times\mathrm{p}^{2})=\mathrm{O}(\mathrm{ log}\mathrm{n}\times\mathrm{p}^{2})\). ## 5 Experimental Evaluation

The performance metrics on the distribution of the batch of workflow applications onto virtual machines for various input parameters have been observed in an experimental investigation. The end user can choose from a variety of VM types offered by cloud service providers. The input parameters of the experimental setup in LIMEFT are shown in Table 4. A batch of workflows has been generated at random in a specified range of input data associated with workflow tasks in the batch, as suggested in [19]. LIMEFT has been evaluated by comparing its results with DLS [14] and HEFT [9] for the same environment and objective parameters.