改进遗传算法在网格任务调度中的应用
摘 要：为了提高遗传算法的搜索性能，同时满足网格资源的优化分配，提出了一种带过滤机制的遗传算法，使其适用于网格任务调度问题的优化处理。仿真研究表明该算法更符合网格调度的复杂环境，能得到较短的任务执行时间和较好的负载均衡性。
关键词：遗传算法；网格；任务调度；完成时间
网格任务调度的基本思想是把分布在不同地理位置上的计算资源、存储资源、通信资源、软件资源、信息资源和知识资源等通过Internet整合成一台巨大的超级计算机，实现各种资源的全面共享[1]。网格技术的关键是资源管理，即有效地分配和使用网格资源。
用户通过向网格系统提交计算任务来共享网格资源，网格调度程序再按照某种策略把这些任务分配给合适的资源[2]。高效的调度策略或算法可以充分利用网格系统的处理能力，从而提高应用程序的性能。目前在网格调度算法研究中，其目标主要是增加吞吐率和系统的使用率，实现经济系统和用户的约束条件，以实现在整个系统中网格应用任务的完成时间最短。
另外，在网格环境中，由于任务到达的随机性以及各节点处理能力上的差异，会造成某些节点分配的任务过重，而另外一些节点却是空闲的，即出现负载不均衡现象[3]。因此，考察调度算法的性能时，也应考虑负载均衡性问题。
遗传算法（GA）是建立一个调度的集合并从其中找出优化的调度，将这种特性遗传给下一代。遗传算法通过适应度函数交叉和重组得出最优的调度。这是一种迭代的算法，它的优点是在不断进化的过程中吸收系统发生改变，能够适应动态变化的网格系统。
本文将改进的遗传算法（IGA）用于网格任务调度，用IGA寻找满足完成所有任务时间最短的优化方案，仿真实验表明，该方案性能良好。
1 问题描述
网格是一个集成的计算与资源环境，网格技术作为一种高性能广域分布式计算模型，已经成为众多研究机构的研究热点。
在网格技术的众多问题中，网格计算中的任务调度在一般形式下是一个NP问题，没有最优解。在调度算法的高效性、资源的异构性以及资源分配决策的并行性和分布性等方面，传统的调度算法并不能很好地适应网格资源的特点。因此，如何对网格资源进行合理分配和管理，满足各种应用的服务需求，实现资源的优化利用，就成为该领域的研究关键。
网格任务调度根据任务间是否存在通信关系可以分为对相互间存在通信任务的任务组的调度和对相互独立的任务组的调度[4]。在算法实现中都假定资源的信息是可获取的。
网格任务调度的实质就是在一个由m个需要调度的任务、n个可用的任务执行单元(主机或集群)、k个数据存储单元构成的网格环境下，把m个任务T={t1，t2，…，tm}以合理的方式调度到n台主机的过程，目的是得到尽可能短的总完成时间（makespan）。把每个执行单元广义地当作一台主机来看待，把k个数据存储单元当成一个存储系统整体来看待。
