# Structure-Aware Scheduling Methods for Scientific Workflows in Cloud
## 2 Related Work  
Several studies have investigated the problem of scheduling scientific workflows on the cloud. [PERSON] et al. [18] formulated the scheduling issue as a mixed integer linear program (MILP) in which several scheduling strategies were discussed to minimize the schedule length. [PERSON] et al. [19] reported a statistical analysis of single-, hybrid-, and hyper-based heuristic approaches. The authors' analysis demonstrated that hybrid- and hyper-based heuristics were expected to achieve better results compared to the single-based heuristic. [PERSON] et al. [10] suggested the HEFT algorithm to minimize the execution time. The HEFT algorithm first ranks tasks based on their workflow locality and computational requirements. Subsequently, each task is scheduled based on the VM that minimizes the overall makespan. [PERSON] et al. [20] extended the HEFT algorithm by proposing an additional dynamic step to reallocate the scheduled tasks, based on new dynamic scheduling requirements. Both [PERSON] et al. [12] and [PERSON] et al. [13] attempted to  
Figure 2: Structure-aware example. decrease the execution time while adhering to budget constraints. [PERSON] et al. [13] proposed a rescheduling approach to ensure fairness and load balancing in task distribution between VMs, which considers the workflow execution deadline. While the proposed method utilized VMs, dynamic resource leasing or releasing available in a hybrid cloud was not considered. [PERSON] et al. [12] proposed a dynamic resource management system that aids the addressing of unforeseen demands by off-loading a portion of the workload to public cloud computing resources. [PERSON] et al. [21] proposed a scheduler designed for random environments, in which tasks could be received at any time. [PERSON] et al. [22] suggested a greed-based approach to reduce execution time while adhering to budget constraints, which used the budget-level concept to determine task execution order in a homogeneous cloud environment. [PERSON] et al. [23] extended the proposed greed-based approach [22] by involving the heterogeneous cloud computing environment. [PERSON] et al. [24] proposed a grouping-based algorithm to decrease the execution time, in which tasks are divided into categories or classes based on their characteristics (user type and task type, size, and latency). Subsequently, the scheduling process determines each task class and the execution order in each. [PERSON] et al. [25] proposed a hybrid approach that mainly establishes the execution environment (private or public) according to the execution cost. In this method, provided the privacy-related constraints are not assumed, every task can be performed on the public cloud. [PERSON] et al. [26] also suggested a hybrid approach to decrease the execution cost. Both data transfer and computational costs are considered to determine the potential cost of public or private clouds and select the cost-efficient cloud while meeting task deadlines. In Refs. [6; 8], the authors focus on minimizing both execution time and cost. In Ref. [6], a partitioning-based algorithm that utilizes a slack parameter (B) was proposed to determine the priority of each objective with a value of either 0 or 1. The proposed algorithm prioritizes minimizing the execution time when B = 0 while prioritizing execution cost when B = 1. The proposed algorithm sequentially partitions workflow tasks beginning with entry-level tasks. The number of VMs assigned per partition is determined according to the B value, which ensures that each task is implemented at its earliest starting time (EST). In this line, the RDAS algorithm [8] apportions VMs using a fair allocation approach between workflow tasks to decrease the makespan and efficiently uses VMs to reduce the total execution cost. [PERSON] et al. [27] proposed a deadline-aware workflow scheduling strategy that involves planning deadline-constrained scientific workflows on dynamically provisioned cloud resources while reducing the execution cost.