赵英，李栋

（北京化工大学 信息科学与技术学院，北京 100029）

网格通过网络连接地理上分布的各种资源，形成一个对用户相对透明的环境。在网格技术[1]中，任务调度是一个研究热点。任务调度的目的是对所有任务进行合理调度，使其完成时间尽可能的短，并且尽可能地提高系统资源的利用率。

经典的任务调度算法有遗传算法[2]、模拟退火算法、Suffrage[3]算法、Min-Min[4]算法、Max-Min 算法等，这些算法被广泛应用于网格任务调度。其中Min-Min算法是一种简单快速的算法，但它忽略了网格任务对QoS[5]的要求。本文对网格任务的优先级进行划分和量化，结合网格任务的等待时间，提出了一种基于权值的改进Min-Min网格任务调度算法，并通过仿真实验，验证了其有效性。

1 网格任务调度

与传统的任务调度相比，网格任务调度必须针对网格资源的特点进行[6]。网格资源具有以下3个特点：

1）异构性 每个网格资源都不尽相同，主要体现在计算资源、存储资源和网络资源等方面的差异。同样的一个任务在不同资源上执行的时间不同，通信方式有可能不同，网络延迟也会不同。

2）动态性 网格资源工作时性能会不断变化，有些时候还会出现故障，比如断电等，调度必须考虑这些突发因素来适应网格资源的动态性。

3）独立自主性 每个网格资源都具有独立自主性，不受网格的完全控制，正是由于这个特性，网格资源不能专用于某个应用。

网格任务调度问题通常被认为是一个NP问题，其完成时间随着任务规模的增长而呈现指数级的增长。……