网格环境下任务调度算法的研究与实现

论文摘要

随着网格技术的深入研究与发展,地理上分布的异构资源可以通过网格工具整合成一个完整的计算平台,而高效的网格任务调度则成为研究的热点和亟待解决的问题,其难点在于综合考虑网格环境的各项特征对于调度的影响,包括网格资源的异构性、动态性、任务截止期约束、网格QoS问题。本文首先研究DAG模型下的网格任务调度,着重分析了基于遗传算法和基于任务复制的调度算法,发现现有的遗传算法都不能很好的利用任务复制以减少任务间的通信延迟,因此本文提出了一种基于任务复制的遗传调度算法。该算法采用了一种结合直接编码和间接编码的染色体编码方式,便于使用任务复制,并在生成初始种群时,通过复制关键路径上的任务来加快算法的收敛性,另外,设计了三个变异算子来增加染色体的多样性,并且通过优化减少不必要的复制。最后通过仿真实验,验证了该算法的有效性。此外,本文还研究了经济模型中的Deadline and BudgetConstrained(DBC)调度策略和它的3个算法—时间最优化算法、费用最优化算法和费用时间优化算法,针对这3个算法只能集中对一个目标(时间或费用)进行优化的问题,提出了基于平均成本的DBC分类调度算法,该算法综合考虑了任务调度的完成时间和费用。通过仿真实验证明,基于平均成本的DBC分类调度算法在均衡完成时间和费用方面有很大的优势,有效的扩展了原有算法。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究意义
• 1.3 研究内容
• 1.4 文章的组织结构
• 第二章 网格技术概述
• 2.1 网格的体系结构
• 2.1.1 五层沙漏结构
• 2.1.2 开放网格服务体系结构OGSA
• 2.2 网格计算的关键技术
• 2.3 本章小结
• 第三章 网格环境下的任务调度方法
• 3.1 任务调度的基本特征与主要目标
• 3.1.1 任务调度的基本特征
• 3.1.2 任务调度的主要目标
• 3.2 现有的网格任务调度算法
• 3.2.1 NP完全问题
• 3.2.2 启发式算法
• 3.2.3 基于Agent的任务调度
• 3.2.4 基于Petri网的任务调度模型
• 3.3 本章小结
• 第四章 基于任务复制的遗传调度算法
• 4.1 DAG模型
• 4.2 遗传算法
• 4.3 基于任务复制的调度算法
• 4.4 基于任务复制的遗传调度算法
• 4.4.1 染色体编码与解码
• 4.4.2 初始种群
• 4.4.3 适应度函数
• 4.4.4 选择操作
• 4.4.5 交叉操作
• 4.4.6 变异操作
• 4.4.7 优化
• 4.4.8 TDGA算法流程
• 4.5 仿真实验与结果分析
• 4.5.1 遗传算法参数的设置
• 4.5.2 交叉概率Pc对TDGA的影响
• 4.5.3 变异概率Pm对TDGA的影响
• Size对TDGA的影响'>4.5.4 种群规模Pop_Size对TDGA的影响
• G对TDGA的影响'>4.5.5 最大进化代数Max_G对TDGA的影响
• 4.5.6 算法对比分析实验
• 4.6 本章小结
• 第五章 基于经济模型的网格任务调度算法
• 5.1 基于经济学的网格资源分配模型
• 5.2 Nimrod-G系统及其调度框架
• 5.2.1 Nimrod-G系统的调度框架
• 5.2.2 Deadline and Budget Constrained（DBC）调度策略
• 5.3 问题描述
• 5.4 基于平均成本的DBC分类调度算法
• 5.5 模拟实验
• 5.5.1 GridSim
• 5.5.2 实验条件
• 5.5.3 与时间最优化算法的比较
• 5.5.4 与费用优化算法、费用时间优化算法的比较
• 5.6 本章小结
• 第六章 总结及未来展望
• 6.1 本文总结
• 6.2 本文的局限性
• 6.3 未来展望
• 参考文献
• 致谢
• 攻读学位期间发表论文