Abstract: Since the time order and the data dependence exist in the grid workflow, the workflow scheduling in grid is a complete NP-hard. Concerning the Directed Acyclic Graph (DAG)-based workflow in the grid, the paper presented a scheduling algorithm, which confirmed the critical path and scheduled the member nodes on the critical path firstly. This algorithm results in the better system load balancing under the best makespan. The simulation shows the validity of the proposed algorithm.

Key words: grid, workflow, scheduling, critical path, load balance, makespan

摘要： 由于网格工作流任务之间存在时序和数据依赖等关系，使得网格环境中工作流的调度问题成为一个NP完全问题。针对有向无环图(DAG)类型工作流提出一种调度算法，先确定关键路径，从而优先调度关键路径成员节点，该算法追求在最优时间跨度下的系统均衡负载，最后通过实验验证了该算法的有效性。

关键词: 网格, 工作流, 调度, 关键路径, 负载均衡, 时间跨度