Minimizing Monetary Costs for Deadline Constrained Workflows in Cloud Environments

Abstract

As one of the latest market-oriented resource provisioning paradigms, cloud computing has been widely adopted by a growing number of consumers due to its powerful computing ability and storage ability. Although cloud computing can achieve effective cost reduction and convenience enhancement in the development of large-scale applications, it results in a complex cost optimization problem for data-dependent tasks represented by a workflow. All tasks in a workflow should be scheduled according to a proper strategy such that the cost is minimized and the precedence constraints and timing requirements are satisfied. In this paper, we study the cost optimization problem of deadline constrained workflows on cloud computing, and propose two list scheduling algorithms named Look-back Workflow Scheduling (LBWS) and Structure Aware Workflow Scheduling (SAWS) to solve the problem. LBWS distributes the deadline over the workflow as sub-deadlines to tasks in different levels, and schedules the tasks according to their priorities to the resources which meet their sub-deadlines and the best time-cost trade off requirements. Compared with LBWS, SAWS considers tasks allocated to the same level at a time and provisions resources with minimum cost to these tasks. Experiments on scientific workflow applications with different data and computational characteristics are conducted to show that, the proposed approaches can achieve better performance in terms of success rate and monetary cost.

Keywords

• Cloud computing
• workflow scheduling
• deadline constraint
• cost minimization