文档介绍：摘 要
网格计算是并行计算、分布式计算以及高性能计算必然的发展趋势和重点研
究方向，随着网格的发展而产生的网格工作流技术是网格计算的重要研究领域之
一。网格工作流技术能够更加有效地利用各种网格资源来完成具有时间、空间和
资源等多种约束条件的复杂任务。网格工作流模型是工作流管理系统的基础，同
时也是网格工作流流程的一种表示方法。因为工作流之间存在时间或数据等约束
关系，网格计算可用有向无环图（Directed Acyclic Graph，DAG）来表示工作流
调度模型。
通过对网格用户和系统资源在网格工作流任务调度中的不同目标进行分析，
本文对用 DAG 表示的工作流调度模型提出一种时间复杂度较低可以在一定程度
上缩短工作流时间跨度的基于逆向分层负载均衡的调度算法，并提出一种在最优
时间跨度下负载均衡的网格工作流调度算法。模拟实验表明，两种调度算法都能
缩短工作流时间跨度和均衡系统资源负载，最优时间跨度下负载均衡的调度算法
由于时间复杂度高所以比基于逆向分层负载均衡的调度算法更能缩短工作流时
间跨度，同时系统资源的负载也更均衡。
关键词：网格计算；网格工作流调度；负载均衡；时间跨度
I
Abstract
The grid computing is the inevitable development trend and the most important
research areas of the parallel computing, distributed computing and high performance
computing. The grid workflow technology is one of important research areas in grid
computing. Grid workflow technology can use grid resources to complete tasks with
the time, space and resources constraints more effectively. The model of grid
workflow is the base of the workflow management system, and it is also a method of
a grid workflow representation. There are time and data constraint relations in
workflow, so we can use the Directed Acyclic Graph（DAG） to represent the
workflow scheduling model.
It is analyzed for the different objectives of the grid users and the system of grid
resources in the grid workflow scheduling, the dissertation proposes a scheduling
algorithm based on the bottom level in the load balance and a scheduling algorithm
based on the optimal time span in the load balance. Simulations show that those
scheduling algorithms can have the optimal time span of the system resources while
the load is more balanced.
Key words: Grid Computing; Grid Workflow Scheduling; Load Balance; Time Span
II
目