基于遗传算法的网格任务调度算法的研究.doc
约84页DOC格式手机打开展开
基于遗传算法的网格任务调度算法的研究,本文共84页44159字摘 要计算网格系统实现了不同地理分布的异构资源的共享、选择和聚合，以解决在科研、工程、经济学等领域大规模的计算问题。网格资源的异构性和地理分布性使得在大规模分布环境中的任务调度成为一个复杂的问题，而任务调度算法性能的好坏直接影响着网格系统的使用率和吞吐量。遗传...
内容介绍
此文档由会员 张阳阳 发布
基于遗传算法的网格任务调度算法的研究
本文共84页 44159字
摘 要
计算网格系统实现了不同地理分布的异构资源的共享、选择和聚合，以解决在科研、工程、经济学等领域大规模的计算问题。网格资源的异构性和地理分布性使得在大规模分布环境中的任务调度成为一个复杂的问题，而任务调度算法性能的好坏直接影响着网格系统的使用率和吞吐量。
遗传算法是建立在自然选择原理和自然遗传机制上的新型优化算法，有着简单、通用、健壮性强、适于并行处理以及高效实用等显著特点，因此，我们主要采用遗传算法来解决网格环境下的任务调度问题。本文对任务调度算法作了如下几个方面的改进：
1、从考虑网格系统中各台机器的负载均衡性出发，提出了基于虚拟截止期的元任务调度算法。参考平均闲置时间来设定任务调度的优先级，从而缩短了任务的时间跨度，并使得负载均衡性得到了提高；
2、提出了结合免疫原理的遗传算法。通过重新调整算法的结构，保证了种群的多样性；通过接种免疫疫苗，使算法的求精能力得到了显著的增强。该算法缩短了时间跨度，并具有很好的收敛性能；
3、研究了信任的定义及信任模型，并针对特定的信任模型，提出了新的遗传算法。通过设计新的编码方案，选择相应的交叉、变异算子，实现种群的多样化，使算法的平均信任效益值得到了明显的提高；
4、指出了经济因素在网格系统中的重要性。针对本文的经济模型，提出了确保任务在截止期内完成，同时尽可能最小化任务的时间和费用的遗传算法。算法同时考虑了子任务之间的通信和费用，弥补了Buyya算法只考虑没有依赖关系的任务调度以及只能单方面考虑时间或费用的缺陷。
关键词：网格，任务调度，遗传算法，信任，经济
目 录
摘 要 I
ABSTRACT II
第一章 绪论 1
1.1研究背景 1
1.1.1 网格计算的研究 1
1.1.2 网格计算与任务调度 3
1.2 网格环境下的任务调度 4
1.2.1 任务调度系统的特点 4
1.2.2 任务调度的模型 5
1.2.3 任务调度的算法 8
1.3研究目标与思路 10
1.3.1 元任务调度算法 11
1.3.2 基于信任机制的任务调度算法 11
1.3.3 基于经济模型的任务调度算法 11
1.4 本文的内容组织 12
1.5 本章小结 13
第二章 遗传算法 14
2.1 遗传算法的发展 14
2.2 遗传算法的基本流程 14
2.3 遗传算法的实现方法 16
2.3.1 编码 16
2.3.2 适应度函数 16
2.3.3 遗传操作 17
2.3.4 停止准则 18
2.3.5 参数设定 18
2.4 遗传算法的基本理论 19
2.4.1模式定理 19
2.4.2 隐含并行性 20
2.4.3 收敛问题 20
2.5遗传算法的特点及改进 21
2.5.1 遗传算法的优缺点 21
2.5.2 遗传算法的改进 22
2.6 发展方向 23
2.7 本章小结 24
第三章 元任务调度算法 25
3.1相关工作 25
3.1.1 算法研究现状 25
3.1.2 异构性表示 26
3.2 问题描述与分析 27
3.2.1 问题描述 27
3.2.2 Min-min算法分析 27
3.3基于虚拟截止期的调度算法 28
3.3.1算法描述 28
3.3.2仿真实验结果与分析 30
3.4基于免疫原理的遗传算法 33
3.4.1算法描述 33
3.4.2仿真实验结果与分析 37
3.5 本章小结 39
第四章 基于信任机制的任务调度算法 40
4.1相关工作 40
4.1.1信任的定义 40
4.1.2信任模型及量化 41
4.1.3算法研究现状 42
4.2问题描述 43
4.2.1信任模型 43
4.2.2信任效益函数 44
4.3改进的遗传算法 45
4.3.1算法描述 45
4.3.2仿真实验结果与分析 48
4.4本章小结 50
第五章 基于经济模型的相关任务图调度算法 51
5.1 相关工作 51
5.1.1 经济学模型 51
5.1.2 算法研究现状 52
5.2问题描述与分析 54
5.2.1 问题描述 54
5.2.2 问题分析 55
5.3 改进的遗传算法 56
5.3.1 算法描述 57
5.3.2 仿真实验结果与分析 61
5.4 本章小结 63
第六章 总结与展望 64
6.1 本论文的主要成果 64
6.2 现有研究成果存在的问题 65
6.3 展望 65
参考文献 67
致谢 74
硕士期间的科研项目和发表的论文 75
参考文献
[1] 都志辉，陈渝，刘鹏. 网格计算[M]. 北京:清华大学出版社,2002,204-211
[2] Foster I. What is the Grid? A Three Point Checklist[M]. Grid Today, July 22,2002, 3-4
[3] 罗红，幕德俊，邓智群. 网格计算中任务调度研究综述[J]. 计算机应用研究，2005,22(5):16-19
[4] 王德民,刘小灵,刘昕,胡平. 计算网格中经济模型调度算法[J]. 计算机工程与应用,2006,29:207-209
本文共84页 44159字
摘 要
计算网格系统实现了不同地理分布的异构资源的共享、选择和聚合，以解决在科研、工程、经济学等领域大规模的计算问题。网格资源的异构性和地理分布性使得在大规模分布环境中的任务调度成为一个复杂的问题，而任务调度算法性能的好坏直接影响着网格系统的使用率和吞吐量。
遗传算法是建立在自然选择原理和自然遗传机制上的新型优化算法，有着简单、通用、健壮性强、适于并行处理以及高效实用等显著特点，因此，我们主要采用遗传算法来解决网格环境下的任务调度问题。本文对任务调度算法作了如下几个方面的改进：
1、从考虑网格系统中各台机器的负载均衡性出发，提出了基于虚拟截止期的元任务调度算法。参考平均闲置时间来设定任务调度的优先级，从而缩短了任务的时间跨度，并使得负载均衡性得到了提高；
2、提出了结合免疫原理的遗传算法。通过重新调整算法的结构，保证了种群的多样性；通过接种免疫疫苗，使算法的求精能力得到了显著的增强。该算法缩短了时间跨度，并具有很好的收敛性能；
3、研究了信任的定义及信任模型，并针对特定的信任模型，提出了新的遗传算法。通过设计新的编码方案，选择相应的交叉、变异算子，实现种群的多样化，使算法的平均信任效益值得到了明显的提高；
4、指出了经济因素在网格系统中的重要性。针对本文的经济模型，提出了确保任务在截止期内完成，同时尽可能最小化任务的时间和费用的遗传算法。算法同时考虑了子任务之间的通信和费用，弥补了Buyya算法只考虑没有依赖关系的任务调度以及只能单方面考虑时间或费用的缺陷。
关键词：网格，任务调度，遗传算法，信任，经济
目 录
摘 要 I
ABSTRACT II
第一章 绪论 1
1.1研究背景 1
1.1.1 网格计算的研究 1
1.1.2 网格计算与任务调度 3
1.2 网格环境下的任务调度 4
1.2.1 任务调度系统的特点 4
1.2.2 任务调度的模型 5
1.2.3 任务调度的算法 8
1.3研究目标与思路 10
1.3.1 元任务调度算法 11
1.3.2 基于信任机制的任务调度算法 11
1.3.3 基于经济模型的任务调度算法 11
1.4 本文的内容组织 12
1.5 本章小结 13
第二章 遗传算法 14
2.1 遗传算法的发展 14
2.2 遗传算法的基本流程 14
2.3 遗传算法的实现方法 16
2.3.1 编码 16
2.3.2 适应度函数 16
2.3.3 遗传操作 17
2.3.4 停止准则 18
2.3.5 参数设定 18
2.4 遗传算法的基本理论 19
2.4.1模式定理 19
2.4.2 隐含并行性 20
2.4.3 收敛问题 20
2.5遗传算法的特点及改进 21
2.5.1 遗传算法的优缺点 21
2.5.2 遗传算法的改进 22
2.6 发展方向 23
2.7 本章小结 24
第三章 元任务调度算法 25
3.1相关工作 25
3.1.1 算法研究现状 25
3.1.2 异构性表示 26
3.2 问题描述与分析 27
3.2.1 问题描述 27
3.2.2 Min-min算法分析 27
3.3基于虚拟截止期的调度算法 28
3.3.1算法描述 28
3.3.2仿真实验结果与分析 30
3.4基于免疫原理的遗传算法 33
3.4.1算法描述 33
3.4.2仿真实验结果与分析 37
3.5 本章小结 39
第四章 基于信任机制的任务调度算法 40
4.1相关工作 40
4.1.1信任的定义 40
4.1.2信任模型及量化 41
4.1.3算法研究现状 42
4.2问题描述 43
4.2.1信任模型 43
4.2.2信任效益函数 44
4.3改进的遗传算法 45
4.3.1算法描述 45
4.3.2仿真实验结果与分析 48
4.4本章小结 50
第五章 基于经济模型的相关任务图调度算法 51
5.1 相关工作 51
5.1.1 经济学模型 51
5.1.2 算法研究现状 52
5.2问题描述与分析 54
5.2.1 问题描述 54
5.2.2 问题分析 55
5.3 改进的遗传算法 56
5.3.1 算法描述 57
5.3.2 仿真实验结果与分析 61
5.4 本章小结 63
第六章 总结与展望 64
6.1 本论文的主要成果 64
6.2 现有研究成果存在的问题 65
6.3 展望 65
参考文献 67
致谢 74
硕士期间的科研项目和发表的论文 75
参考文献
[1] 都志辉，陈渝，刘鹏. 网格计算[M]. 北京:清华大学出版社,2002,204-211
[2] Foster I. What is the Grid? A Three Point Checklist[M]. Grid Today, July 22,2002, 3-4
[3] 罗红，幕德俊，邓智群. 网格计算中任务调度研究综述[J]. 计算机应用研究，2005,22(5):16-19
[4] 王德民,刘小灵,刘昕,胡平. 计算网格中经济模型调度算法[J]. 计算机工程与应用,2006,29:207-209
