# Structure-Aware Scheduling Methods for Scientific Workflows in Cloud
## 4 Algorithmic Solutions
### Hierarchy-Based Approach
#### 4.2.2 Resource Allocation
```
Data:\(G\): set of group ; \(R\): virtual machines Result:\(S\): schedule
1\(T\gets getTasks(G)\) whileT is not emptydo
2\(G\gets sortDependency(G)\) for\(g_{i}\in G\)do
3\(L\gets getTasksbyLevel(g_{i})\) \(VMs^{\prime}\gets getVMs(g_{i},R)\) for\(l_{i}\in L\)do
4 if\(isAssigned(MIP(l_{i}))\) or \(MIP(l_{i})==null\)then
5 add (\(l_{i},VMs^{\prime}\)) to \(S\) \(remove(l_{i},T)\)
6 else
7 Continue
8 end if
9
10 end for
11
12 end for return\(S\)
```

**Algorithm 5**Scheduling

### Discussion and Limitation

To discuss the performance of the LBA and HBA, let us consider the example in Figure 3. In this discussion, we focus on the execution time (makespan), as the cost is also impacted by the number of available VMs. The running time for tasks \(1,6,8,12\), and \(14\) are assigned to be \(250\) s each, whereas the running time for the rest of the tasks is assigned to be \(100\) s each. Furthermore, we assume that the number of available VMs equals \(4\). In the LBA, the workflow is divided into five groups highlighted by the dashed lines, in which each group contains tasks from the same level (Figure 3b). Regarding the makespan, the number of available VMs equals the number of tasks in the widest established group, and thus the availability of the VMs will not influence this approach's performance. The identity of the tasks assigned to each VM is shown in Table 1. Starting from the entry-level group, to maximize the overall utility, each task is assigned to a separate VM. Once group (\(i\)) tasks are assigned to MVs, the approach moves to assign the next group (\(i+1\)) tasks, in which the starting time for group (\(i+1\)) tasks depends on the latest finishing time for group (\(i\)) tasks. For example, in Figure 3b, group 2 starts their execution after \(250\) s, which is the execution time for task \(1\). In each level, the maximum execution time for a taskis 250 s, and therefore, the total execution time for the workflow is 1250 (\(250\times 5\)). The introduced waiting time (idle time) before each group (level) task assignment is impacted by the number of available VMs. In situations where the number of available VMs is close to the number of tasks in the largest group, the introduced waiting time becomes noticeable as for each task, several tasks are expected to obtain the same utility. However, this is not expected to occur frequently as the number of available VMs is typically significantly smaller than the number of tasks to be scheduled. The task groups obtained using the HBA are shown in Figure 3c. Once the groups are established, this approach calculates the weight and share of each group as shown in Table 2. In this example, as we can see from the table, two VMs will be allocated to group one and a single VM to the second group, where the third group will also be allocated a single VM. Accordingly, by using such a division strategy, the execution time for group one plays a dominant factor in determining the overall execution time. The execution of groups two and three is expected to occur without any noticeable dependency-related delay. Each group has a dependency value that represents the dependency of a group's tasks on other groups' data. Group one has the highest dependency value, whereas the second group has a higher dependency value compared to the third group. Such dependency is addressed by the employed sharing mechanism as groups expected to take longer to execute will be assigned more VMs (as shown in Table 2). In the presented example, based on the structure of the groups, each group is assigned enough VMs to ensure the execution of the tasks without any interruption. In this line, the total execution time for the workflow using the hierarchy-based scheduling is 1100 s, which is 150 s shorter than that obtained by the LBA. The efficiency of the HBA is influenced by the available number of VMs and the heterogeneity of the tasks' execution times. To clarify this dependency, let us re-visit the example shown in Figure 3. In this example, if the number of available VMs is reduced