论文部分内容阅读
任务调度是网格研究领域的一个焦点问题,研究基于网格资源实际特征的任务调度对于高性能网格的实际应用具有重要的意义,任务调度已被证明是NP难解问题,考虑网格资源实际特征的任务调度就使得问题变得更加复杂。国内外学者提出了很多启发式算法并取得了良好的效果。但是,不少调度算法往往忽视了任务间的数据关联与优先约束关系。而考虑任务优先关系的基于DAG表示的任务调度算法却往往忽略了网格节点的异构性和任务之间的通信关系,不能反映网格环境和任务的实际特征。本文是在异构网格环境下,运用遗传算法在解决组合优化方面的优越性,对带通信的DAG任务图调度进行研究。详细分析了传统遗传算法BGA和基于表调度技术的启发式调度算法DLS的调度策略和算法特点,提出了一种新的改进算法——混合遗传算法,主要改进有：(1)提出了基于预处理的种群初始化方法。针对传统遗传算法初始种群较差,进化时间较长的不足,基于预处理的种群初始化方法充分考虑了任务的重要程度和网格异构的特点,使得独立的任务尽量并行化,进而得到比较优秀的初始种群,在进化代数相同的情况下,能够获得更好的解,减少进化时间。(2)提出了混合交叉算子。针对传统遗传算法的交叉算子在两父个体相同或相似时,交叉效率降低的特点,改进的混合交叉算子考虑了两父个体的特征,当两个体相同或相似时,就分别执行单亲遗传方式,可以产生新个体,提高交叉操作的效率。(3)提出了动态变异算子。针对传统遗传算法的变异算子在进化后期容易产生盲目性,难以快速全局收敛的特点,动态变异算子根据进化阶段来限制变异的范围,后期进化时采用相邻基因变异,减少随意性,快速收敛到全局最优解。(4)提出了融合DLS算法的pDLS启发式算子。针对DLS算法在异构网格调度中能够取得较好解的特点,本文在传统遗传算子之后融合了部分改进的DLS操作——pDLS算子,以一定的概率来修正选择的个体,对个体进一步优化。本文对改进后的混合遗传算法进行了相应的实验模拟和结果分析,实验结果表明,基于混合遗传算法的网格任务调度能够有效缩短网格任务调度时间,可实际应用于带通信的异构网格环境中。