关键词: 网格计算, 工作流, 动态规划, 通信开销

Abstract: In this text， the author uses DAG graph and task-resource allocation graph to define the grid task scheduling model， and utilizes dynamic programming method to propose workflow task scheduling algorithm based on communication cost. By using extended topological sorting algorithm， dependent tasks are divided into subsets， according to them， obtains corresponding phases. At each stage， carries out task allocation of resource nodes which meet constraint conditions and optimal objective function based on computing cost， communication cost and the success rate of implementation， so it can get the most optimal workflow task scheduling. Uses the GridSim tool package to realize the scheduling algorithm， and compares with the Min- Min algorithm. Simulation results show that the proposed algorithm has good adaptability， and can solve grid scheduling problem better under different network environment and large number of data transmission circumstances.

Key words: grid computing, workflow, dynamic planning, communication cost