Cost-efficient task scheduling for executing large programs in the cloud

Executing a large program using clouds is a promising approach, as this class of programs may be decomposed into multiple sequences of tasks that can be executed on multiple virtual machines (VMS) in a cloud. Such sequences of tasks can be represented as a directed acyclic graph (DAG), where nodes are tasks and edges are precedence constraints between tasks. Cloud users pay for what their programs actually use according to the pricing models of the cloud providers. Early task scheduling algorithms are focused on minimizing make-span, without mechanisms to reduce the monetary cost incurred in the setting of clouds. We present a cost-efficient task-scheduling algorithm using two heuristic strategies. The first strategy dynamically maps tasks to the most cost-efficient VMs based on the concept of Pareto dominance. The second strategy, a complement to the first strategy, reduces the monetary costs of non-critical tasks. We carry out extensive numerical experiments on large DAGs generated at random as well as on real applications. The simulation results show that our algorithm can substantially reduce monetary costs while producing make-span as good as the best known task-scheduling algorithm can provide. (C) 2013 Elsevier B.V. All rights reserved.