DAGMap: Efficient scheduling for DAG grid workflow job

Abstract

DAG has been extensively used in grid workflow modeling. Since the computational capacity of available grid resources tends to be heterogeneous, efficient and effective workflow job scheduling becomes essential. It poses great challenges to achieve minimum job accomplishing time while maintaining high grid resources utilization efficiency. Based on list scheduling and group scheduling, in this paper we propose a novel static scheduling heuristic, called DAGMap. DAGMap consists of three phases, namely prioritizing, grouping, and independent task scheduling. Three salient features of DAGMap are 1) Task grouping is based on dependency relationships and task upward priority; 2) Critical tasks are scheduled first; and 3) Min-Min and Max-Min selective scheduling are used for independent tasks. The experimental results show that DAGMap can achieve better performance than other previous algorithms in terms of makespan, speedup, and efficiency.