# Structure-Aware Scheduling Methods for Scientific Workflows in Cloud
## 1 Introduction  
Workflow has become a frequently used model for large-scale scientific computing and data-intensive applications operating on infrastructure-as-a-service (IaaS) platforms. A workflow involves hundreds or even thousands of tasks subject to data dependency constraints. Typically, workflow scheduling encounters decreasing cost or execution duration (makespan) issues. Cloud computing has developed as an encouraging computing paradigm that presents elastic, scalable, and highly available resources. In cloud computing, virtualization is an important factor that cost-effectively divides physical machines into virtual machines (VMs) [1]. Organizations and companies that use cloud computing can initiate operations without investing time and money into infrastructure. Accordingly, cloud service customers can be charged based on their consumption of the VMs. Such characteristics (e.g., cost-effectiveness and fee flexibility) underline the premise of cloud computing as a promising workflow execution platform [2]. Workflow task execution involves high communication and computation costs, specifically in scientific workflow domains (e.g., biology and astronomy, see Figure 1). The challenge in workflow scheduling [3] is to determine the workflow task execution order and the optimal mapping of tasks to VMs to achieve the scheduling objective. Typically,workflow scheduling involves minimizing the execution time or cost where these objectives conflict in practice. Given its combinatorial characteristic, this scheduling problem is by nature NP-Complete, which has inspired researchers to suggest near-optimal solutions [4]. Accordingly, to address the problem, several studies have investigated the use of nature-inspired optimization methods [5], such as particle swarm optimization (PSO) and simulated annealing (SA). Additionally, other studies [5; 6; 7; 8] have investigated the use of heuristic approaches to schedule workflows. In Refs. [9; 10; 11; 12; 13], the authors have investigated building scheduling solutions by employing greedy-based mechanisms that schedule the tasks to reduce their execution time. Others [6; 8; 14; 15] have built their solution by considering the entire structure of the workflow, whereas the main distinguisher between these proposals is in the employed strategy that utilizes the extracted structure-related feature. The structure-related information is typically used to establish semi-balanced task groups (partitions) in terms of computational requirements. Unlike the previous studies [6; 8; 14; 15], in this work, the structure-related information is used to establish a lookahead workflow partitioning strategy, which results in minimizing the dependency between the obtained groups of tasks. Additionally, the employed fair share division strategy aims to determine each group's share of VMs based on the overall computational requirements for the group's tasks. Workflows have different structures, in which inside the same workflow, the number of tasks and data dependency constraints frequently change between the levels of the workflow. Workflow structures capture the dependency constraints that eventually impact the quality of the obtained schedule. To further clarify the relationship between the workflow structure and the expected schedule efficiency, consider the workflow depicted in Figure 2. In this example, the levels of the workflow are separated by dashed lines, and the entry-level tasks are 1, 2, 3, and 4. A task can start its execution once all the required data are received from its parents, among whom the last parent to finish its execution is termed the most influential parent (MIP). For example, task 6 cannot start its execution before tasks 2 and 3 finish their execution and transfer the required data to task 6. From the figure, we can see that before starting the execution of the workflow, the overall structure of the workflow should be analyzed.