# Structure-Aware Scheduling Methods for Scientific Workflows in Cloud
## 4 Algorithmic Solutions
### Hierarchy-Based Approach
#### 4.2.2 Resource Allocation
The input workflows for the presented experiments represent four real-world applications (LIGO, CyberShake, Montage, and SIPHT [16]). The size of each workflow is 1000 tasks, and each experiment shows the average for 10 different runs (10 workflows). Additionally, to execute the tasks, we have used two types of VMs, \(R_{1}\) and \(R_{2}\). \(R_{2}\) was designed to be two times faster than \(R_{1}\). The \(R_{1}\) and \(R_{2}\) charging rates were 10 and 20 cents per hour; respectively. In the presented experiments, we are interested in evaluating the performance of the proposed approaches in terms of cost and makespan. Cost and makespan are defined as follows:

* Makespan (\(m\)) is defined as the total execution time for the entire workflow tasks, and it is denoted by the \(AFT\) for the last task to be executed (exit task \(v_{e}\)) (\(m=AFT(v_{e})\));
* Cost (\(c\)) is defined as the total charges for the used VMs, where an hourly rate is used as the billing cycle formulation (\(bc\)). The cost (\(c\)) is calculated as follows: \[c=\left[\sum_{vm_{i}\in R_{1}}bc_{vm_{i}}\times 10+\sum_{vm_{j}\in R_{2}}bc_{vm _{j}}\times 20\right]\] (5)The performance of the proposed algorithms was validated against the RDAS [25], PBWS [18], and HEFT [3] algorithms. The HEFT algorithm uses a greedy mechanism that schedules tasks in a sequential fashion. Accordingly, for each task, the VM that results in reducing the AFT for this task will be selected. The RDAS algorithm partitions workflow tasks based on the structure of the workflow. Then, by employing a fair division strategy, the available VMs are fairly divided among the partitions with the objective of minimizing makespan and cost. In the PBWS algorithm, based on the pre-determined weight for each objective (makespan or cost), the algorithm works by determining the number of VMs and the execution schedule to achieve the desired objective. To ensure the fairness of the comparison, the PBWS was run first, and the number of used VMs by the PBWS was used as the input for the HBA, LBA, RDAS, and HEFT algorithms. Table 3 summarizes the results of the performed experiments. **LIGO**: Figure 4 depicts the LIGO workflow results. The LIGO workflow structure is well-organized, which is expected to result in the use of similar VM numbers for each group execution. Both proposed algorithms significantly outperformed the benchmark algorithms regarding execution cost. Allocating tasks uniformly over the available VMs decreased the idle timeslot numbers and thus reduced the total cost of the schedules obtained by the HBA and LBA algorithms. Nevertheless, the proposed algorithms produced makespan values highly similar to those of the benchmarks. The LBA algorithm obtained slightly higher makespan values stemming from the bottleneck task in the LIGO structure, which limited the performance of this strategy for makespan. The HBA algorithm obtained acceptable makespan values that were relatively better than those of the PBWS and RDAS algorithms, which was due to the advantage of using the lookahead strategy. **CyberShake**: Figure 5 depicts the CyberShake workflow results. The CyberShake workflow structure is extensive with numerous tasks at every level. The two proposed algorithms significantly outperformed the HEFT and RDAS algorithms regarding makespan and cost. The grouping and fair share strategies used in the LBA and HBA algorithms increased the utilization of the available VMs by identifying the necessary number of VMs needed to execute each group. The PBWS algorithm achieved a relatively close performance