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

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