| 【中文题名】 | 基于遗传算法的网格任务调度算法的研究 |
| 【英文题名】 | The Research on Task Scheduling Based on Genetic Algorithm for Computing Grid |
| 【学科专业】 | 计算机应用技术 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-11-6 |
| 【中关键词】 | 网格,任务调度,遗传算法,信任,经济, |
| 【英关键词】 | grid,task scheduling,genetic algorithm,trust,economy, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>计算技术、计算机技术>计算机的应用>计算机网络>一般性问题 |
| 【论文摘要】 |
计算网格系统实现了不同地理分布的异构资源的共享、选择和聚合，以解决在科研、工程、经济学等领域大规模的计算问题。网格资源的异构性和地理分布性使得在大规模分布环境中的任务调度成为一个复杂的问题，而任务调度算法性能的好坏直接影响着网格系统的使用率和吞吐量。
遗传算法是建立在自然选择原理和自然遗传机制上的新型优化算法，有着简单、通用、健壮性强、适于并行处理以及高效实用等显著特点，因此，我们主要采用遗传算法来解决网格环境下的任务调度问题。本文对任务调度算法作了如下几个方面的改进：
1、从考虑网格系统中各台机器的负载均衡性出发，提出了基于虚拟截止期的元任务调度算法。参考平均闲置时间来设定任务调度的优先级，从而缩短了任务的时间跨度，并使得负载均衡性得到了提高；
2、提出了结合免疫原理的遗传算法。通过重新调整算法的结构，保证了种群的多样性；通过接种免疫疫苗，使算法的求精能力得到了显著的增强。该算法缩短了时间跨度，并具有很好的收敛性能；
3、研究了信任的定义及信任模型，并针对特定的信任模型，提出了新的遗传算法。通过设计新的编码方案，选择相应的交叉、变异算子，实现种群的多样化，使算法的平... |
| 【论文题纲】 |
|
摘要 |
5-6 |
|
ABSTRACT |
6-11 |
|
第一章 绪论 |
11-24 |
|
1.1 研究背景 |
11-14 |
|
1.1.1 网格计算的研究 |
11-13 |
|
1.1.2 网格计算与任务调度 |
13-14 |
|
1.2 网格环境下的任务调度 |
14-20 |
|
1.2.1 任务调度系统的特点 |
14-15 |
|
1.2.2 任务调度的模型 |
15-18 |
|
1.2.3 任务调度的算法 |
18-20 |
|
1.3 研究目标与思路 |
20-22 |
|
1.3.1 元任务调度算法 |
21 |
|
1.3.2 基于信任机制的任务调度算法 |
21 |
|
1.3.3 基于经济模型的任务调度算法 |
21-22 |
|
1.4 本文的内容组织 |
22-23 |
|
1.5 本章小结 |
23-24 |
|
第二章 遗传算法 |
24-35 |
|
2.1 遗传算法的发展 |
24 |
|
2.2 遗传算法的基本流程 |
24-26 |
|
2.3 遗传算法的实现方法 |
26-29 |
|
2.3.1 编码 |
26 |
|
2.3.2 适应度函数 |
26-27 |
|
2.3.3 遗传操作 |
27-28 |
|
2.3.4 停止准则 |
28 |
|
2.3.5 参数设定 |
28-29 |
|
2.4 遗传算法的基本理论 |
29-31 |
|
2.4.1 模式定理 |
29-30 |
|
2.4.2 隐含并行性 |
30 |
|
2.4.3 收敛问题 |
30-31 |
|
2.5 遗传算法的特点及改进 |
31-33 |
|
2.5.1 遗传算法的优缺点 |
31-32 |
|
2.5.2 遗传算法的改进 |
32-33 |
|
2.6 发展方向 |
33-34 |
|
2.7 本章小结 |
34-35 |
|
第三章 元任务调度算法 |
35-50 |
|
3.1 相关工作 |
35-37 |
|
3.1.1 算法研究现状 |
35-36 |
|
3.1.2 异构性表示 |
36-37 |
|
3.2 问题描述与分析 |
37-38 |
|
3.2.1 问题描述 |
37 |
|
3.2.2 Min-min算法分析 |
37-38 |
|
3.3 基于虚拟截止期的调度算法 |
38-43 |
|
3.3.1 算法描述 |
38-40 |
|
3.3.2 仿真实验结果与分析 |
40-43 |
|
3.4 基于免疫原理的遗传算法 |
43-49 |
|
3.4.1 算法描述 |
43-47 |
|
3.4.2 仿真实验结果与分析 |
47-49 |
|
3.5 本章小结 |
49-50 |
|
第四章 基于信任机制的任务调度算法 |
50-61 |
|
4.1 相关工作 |
50-53 |
|
4.1.1 信任的定义 |
50-51 |
|
4.1.2 信任模型及量化 |
51-52 |
|
4.1.3 算法研究现状 |
52-53 |
|
4.2 问题描述 |
53-55 |
|
4.2.1 信任模型 |
53-54 |
|
4.2.2 信任效益函数 |
54-55 |
|
4.3 改进的遗传算法 |
55-60 |
|
4.3.1 算法描述 |
55-58 |
|
4.3.2 仿真实验结果与分析 |
58-60 |
|
4.4 本章小结 |
60-61 |
|
第五章 基于经济模型的相关任务图调度算法 |
61-74 |
|
5.1 相关工作 |
61-64 |
|
5.1.1 经济学模型 |
61-62 |
|
5.1.2 算法研究现状 |
62-64 |
|
5.2 问题描述与分析 |
64-66 |
|
5.2.1 问题描述 |
64-65 |
|
5.2.2 问题分析 |
65-66 |
|
5.3 改进的遗传算法 |
66-73 |
|
5.3.1 算法描述 |
67-71 |
|
5.3.2 仿真实验结果与分析 |
71-73 |
|
5.4 本章小结 |
73-74 |
|
第六章 总结与展望 |
74-77 |
|
6.1 本论文的主要成果 |
74-75 |
|
6.2 现有研究成果存在的问题 |
75 |
|
6.3 展望 |
75-77 |
|
参考文献 |
77-84 |
|
致谢 |
84-85 |
|
硕士期间的科研项目和发表的论文 |
85 |
|
| 【DOI】 | LunWen.ID:2.2008.376537 |
