a low-cost rescheduling policy for efficient mapping of workflows on grid systems

Abstract

Workflow management is emerging as an important service in Grid computing. A simple model that can be used for the representation of certain workflows is a directed acyclic graph. Although many heuristics have been proposed to schedule such graphs on heterogeneous environments, most of them assume accurate prediction of computation and communication costs. This limits their direct applicability to a dynamically changing environment, such as the Grid. In this environment, an initial schedule may be built based on estimates, but run-time rescheduling may be needed to improve application performance. This paper presents a low-cost rescheduling policy, which considers rescheduling at a few, carefully selected points during the execution. This policy achieves performance results, which are comparable with those achieved by a policy that dynamically attempts to reschedule before the execution of every task.