基于遗传与禁忌混合优化算法的网络任务调度的研究

摘要

网格技术将所有可用于共享的资源(例如,计算机、高性能设备、S贵仪器、存储设备、科学数据、软件、数据库等)通过网络连接起來,并将它们转化成一种随处可得的、可靠的、标准的和经济的计算能力。用户将任务提交给网格后,需要对任务进行合理的分配和调度,即将任务分配给网格资源去执行,因此网格任务在各种资源之间的合理调度成为一个关键的问题。
　　本文在研究目前网格调度的特点和分级式调度模式的基础上,提出了适合网格任务调度系统的基于域的分层任务调度模型。
　　本文着重研究相互间存在通信的网格任务调度,针对这种类型的网格任务调度系统的特点,采用遗传算法作为网格任务调度的基础性算法,4于遗传算法存在“早熟”收敛的不足,利用禁忌搜索算法異有灵活的记忆功能和藐视准则的特点,将二者结合起來,提出了在网格任务调度系统中的GATS-TSM混合优化策略,实现对算法的优化。
　　在 GATS-TSM混合优化算法的基础上,对基于DAG图的网格任务调度进行数学建模,构建了 GATS-TSM的网格任务调度系统的数学模型。针对网格调度系统中的GATS-TSM调度算法的特点,详细设计了其遗传操作算子和禁忌操作算子的实现方式。然后针对网格调度系统的各种资源的不稳定性,设计了网格任务调度的容错策略。
　　本文利用Simgrid的仿真工異在Linux环境下建立了 GATS-TSM调度算法的网格调度模拟平台,设计了网格调度主模块Mainsim、网格构建模块G C M、遗传模块GA TSM现各种不同的应用场景來评估调度算法的性能。比较了轻重负载情况下,经典遗传算法和GATS-TSM的性能差异,并通过实验分析GATS-TSM中各种控制参数对算法调度系统性能的影响。
　　实验数据证明了遗传与禁忌混合优化算法的正确性和有效性。改进的算法異有全局搜索能力,又異有较快的收敛速度,能够在较少的进化代数之内收敛于近似最优解,提高了网格任务调度的性能。

目录

封面

声明

中文摘要

英文摘要

目录

第一章绪论

第二章网格环境下的任务调度和基于域的调度模型研究

第三章遗传与禁忌混合优化算法的网格任务调度的理论研究

第四章遗传与禁忌混合优化算法的网格任务调度系统的设计

第五章基于Sim grid的模拟仿真验证和结果分析

第六章结束语

参考文献

致谢

作者在攻读硕士期间的主要研究成果和项目