## 2 Related Work  
In the last two decades, several research studies have been conducted that address the problem of workflow scheduling due to its NP-completeness. The Quality of Service (QoS)-constrained workflow scheduling algorithms tries to maximize the performance while meeting other user-defined QoS constraints, for example, cost minimization of a workflow execution under deadline constraints, as in IC-PCP and IC-PCP2 [15], URH [16], DPDS [17] and EPSM [18]. [PERSON] and [PERSON] [19] considered an application model similar to the one addressed in this paper and proposed a scheduling algorithm for optimizing a workflow's execution time (that is, makespan) under a budget constraint. They proposed resource provisioning plan for a subset of the workflow tasks as a mixed integer linear programming (MILP) model. However, their solution is tailored for fine-grained billing periods such as per-minute billing. Moreover, the algorithm's objective is to minimize the makespan instead of meeting a deadline constraint. Despite these differences, we consider their work relevant as the authors not only consider dynamic resource provisioning and delays but also consider several VM instance types with different characteristics and prices. [PERSON] et al. [20] presented an adaptive algorithm and used the MIP approach to schedule workflows in IaaS clouds for optimizing cost under a deadline constraint. However, they do not consider reusing of already assigned VMs and also do not consider data transfer time. [PERSON] et al. [8] presented a dynamic resource provisioning and scheduling algorithm called DPDS. It schedules workflows under given deadline and budget constraints along with the information about resource utilization for VM provisioning and scheduling. However, it attempts to maximize the number of completed workflows rather than minimizing the rental cost of a single BoT workflow. Moreover, it supports single instance type and do not consider resource heterogeneity which is in contrast to the current IaaS cloud model that offer a wide variety of instance types and dynamic provisioning and scheduling of resources. Task granularity has been addressed in several research studies for reducing the impact of overheads that may arise when executing scientific workflows in distributed environments, such as the cloud [4; 12; 21]. Task grouping methods reduce computational granularity by reducing the number of computational activities by grouping fine-grained tasks into course-grained tasks. These techniques attempt to minimize queuing times and scheduling overheads when resources are limited. However, task granularity may limit the degree of inherent parallelism, therefore it must be done optimally. [PERSON] and [PERSON] [9] proposed an auto-scaling mechanism that schedules workflow jobs in order to minimize the monetary cost while meeting the application deadlines on clouds. A static resource provisioning plan is made based on a global optimization heuristic and then adapted to dynamic changes by running the global optimization algorithm every time a task is scheduled. However, they do not consider the different priorities of each job and considered dynamic and unpredictable workloads of workflow. Furthermore, the high computational overhead in Scaling-Consolidation-Scheduling (SCS) hinders its scalability in terms of the number of tasks in the workflow and they do not provide a near-optimal solution. [PERSON] et al. [22] explicate a deadline and budget constraint scheduling algorithm which tries to maximize the amount of work completed. The scheduling algorithm proposed by [PERSON] et al. [10] estimated the minimum number of resources needed to execute the workflow in a cost- effective way. But, they considered a single type of VM and fails to consider the heterogeneous nature of clouds.