网格任务调度算法的研究.pdfVIP

学兔兔 第l期 (总第164期) 机 械 工 程 与 自动 化 NO．1 2011年 2月 MECHANICAL ENGINEERING ＆ AUT0MAT1ON Feb． 文章编号：1672—6413(2011)01—0066—03 网格任务调度算法的研究 刘先刚，廖述剑 (太原理工大学信息工程学院，山西 太原 030024) 摘要：提出了一种基于遗传算法和Min～Min的网格调度算法，该算法主要分为资源有哪些信誉好的足球投注网站和任务分配两部分。 首先，利用遗传算法从网格的可用资源中快速地有哪些信誉好的足球投注网站出最优的或是近最优的资源；然后从任务队列中取一组任 务，利用Min--Min算法把任务分配给已有哪些信誉好的足球投注网站到的资源上去执行。仿真实验结果证明：对于大规模资源的调度 该算法是有效的，能够减少了任务执行时间，改善网格任务调度的效率。 关键词：网格计算；任务调度；遗传算法；Min—Min 中图分类号：TP301．6 文献标识码：A 0 引言 遗传算法的优势在于[2]：具有与领域无关的群体 在网格计算中，采用何种方法最有效地管理各种 性全局有哪些信誉好的足球投注网站能力，可避免一些算法容易陷入的局部最 计算资源并利用这些计算资源去完成各种计算任务是 优；易于与其他优化技术或已有模型结合。图1为经 一 个最主要的问题。因此任务调度是网格计算中的一 典遗传算法流程图。 个重要的组成部分，它一直是国际和国内学术界的研 究热点。本文主要研究了当前经典算法中的遗传算法 和Min—Min算法，并在这两种算法的基础上，提出了 GAMM算法。该算法在一定程度上减少任务执行时 间，提高了网格的性能。 1 算法介绍 1．1 遗传算法 遗传算法是美国Michigan大学的J．Holland教 授最先提出的[1]，它以达尔文生物进化理论和孟德尔 遗传变异理论为基础，是一种模拟生物进化过程的优 化有哪些信誉好的足球投注网站方法。 图 1 经典遗传算法流程图 遗传算法的基本流程如下：①首先对资源进行编 1．2 Min—Min算法 码，每个资源编一个唯一的二进制编码，即资源的染 Min—Min算法也称为极小一极小算法[3]。Min— 色体；②随机产生多个初始个体，形成初始种群；③ Min算法的目的是将大量的任务调度给不仅完成它最 计算每个个体适应度Fitness，将适应度高的个体保 早、而且执行最快的机器，以使全部任务完成时间最 留，淘汰适应度低的个体；④按照一定的概率对个体 小。该算法计算每个任务在各机器上的期望完成时间， 进行基因杂交产生新的个体；⑤以一定的概率对个体 获得每个任务的完成时问及机器号，再将最小最早完 的基因进行变异，得出新的个体；⑥种群的代数f一￡+ 成时间的任务调度给该机器，调度完成后更新机器就 1，如果终止条件成立则结束该算法，否则返回③。 绪时间。如此重复，直到全部任务被调度为止。该算 通过该算法有哪些信誉好的足球投注网站出种群中的最优个体给予分配任 法的缺点是长任务可能需要较长的等待时间。 务，重复该算法直到把所有的任务调度完毕。 2 GAMM算法介绍 收稿日期：2010—04—27；修回日期：2010-09—23 作者简介：刘先刚(1983一)。男