(论文 页数:85 字数:44581) 摘 要:计算网格系统实现了不同地理分布的异构资源的共享、选择和聚合，以解决在科研、工程、经济学等领域大规模的计算问题。网格资源的异构性和地理分布性使得在大规模分布环境中的任务调度成为一个复杂的问题，而任务调度算法性能的好坏直接影响着网格系统的使用率和吞吐量。
遗传算法是建立在自然选择原理和自然遗传机制上的新型优化算法，有着简单、通用、健壮性强、适于并行处理以及高效实用等显著特点，因此，我们主要采用遗传算法来解决网格环境下的任务调度问题。本文对任务调度算法作了如下几个方面的改进：
1、从考虑网格系统中各台机器的负载均衡性出发，提出了基于虚拟截止期的元任务调度算法。参考平均闲置时间来设定任务调度的优先级，从而缩短了任务的时间跨度，并使得负载均衡性得到了提高；
2、提出了结合免疫原理的遗传算法。通过重新调整算法的结构，保证了种群的多样性；通过接种免疫疫苗，使算法的求精能力得到了显著的增强。该算法缩短了时间跨度，并具有很好的收敛性能；
3、研究了信任的定义及信任模型，并针对特定的信任模型，提出了新的遗传算法。通过设计新的编码方案，选择相应的交叉、变异算子，实现种群的多样化，使算法的平均信任效益值得到了明显的提高；
4、指出了经济因素在网格系统中的重要性。针对本文的经济模型，提出了确保任务在截止期内完成，同时尽可能最小化任务的时间和费用的遗传算法。算法同时考虑了子任务之间的通信和费用，弥补了Buyya算法只考虑没有依赖关系的任务调度以及只能单方面考虑时间或费用的缺陷。

关键词：网格，任务调度，遗传算法，信任，经济
THE RESEARCH ON TASK SCHEDULING
BASED ON GENETIC ALGORITHM
FOR COMPUTING GRID



ABSTRACT


The concept of grid computing is becoming a more and more important one in the high performance computing world and enables the sharing, selection, and aggregation of geographically distributed heterogeneous resources for solving large-scale problems in science, engineering, and commerce. The resources in the grid are heterogeneous and geographically distributed. The management of task scheduling in such a large-scale distributed environment is a complex problem. And the performance of task scheduling algorithm will affect the efficiency and throughput of the grid system directly.
Genetic algorithm is a new-style optimizing algoirhtm based on natural selection theory and natural heredity mechanism, which is simple、current robust、high efficiency and is fit for parellel processing. So, this paper does research on task scheduling algorithm on the basis of genetic algorithm.The contributions of this paper are as follows:
1. An algorithm based on the virtual deadline in view of the load balance among the machines in the grid system is presented, which uses the mean slack time to set the priority of each task. This algorithm has better results in terms of makespan and load balance compared with other algorithms.
2. An algorithm based on immune system theory is brought up. This algorithm expands the variety of population by adjusting the structure of the algorithm, and it also improves the local search ability by injecting vaccine operator. It produces better results in terms of schedule length and it also has good convergent speed.
3. An algorithm is proposed based on one of the grid trust models after doing research on trust definition and models. We design a new coding scheme, and select the corresponding crossover and mutate operators to increase the diversification. So it can reach a better average trust utility than others.
4. An algorithm which aims at optimizing the time and budget on the basis of satisfying the deadline constraint is presented after pointing out the importance of considering the factor of economy in grid system. This algorithm considers the communication among tasks. It makes up the algorithms proposed by Buyya which only consider the tasks with no dependencies and which can only consider the time or budget independently.


KEY WORDS：grid, task scheduling, genetic algorithm, trust, economy

目 录


摘 要 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.1研究背景
1.1.1 网格计算的研究
随着各种技术的进步与发展，很多计算问题变得越来越复杂，规模也越来越大。由于超级计算机非常昂贵，不能广泛普及和使用，人们开始用分布式方法来解决大规模计算问题。搭建分布式系统有多种方式，集群系统和网格系统是其中最常见的两种分布式应用系统。集群系统利用高性能网络或LAN将若干个人计算机或工作站连接起来。而网格[1]系统利用网络，将互联网上分散的闲置资源很好地利用起来。网格计算使用互联网连接，能够提供更大范围的资源共享，提高资源使用率，打破了传统分布式系统的空间限制，可以实现跨平台操作，充分利用闲置的计算资源。
网格计算技术是一种先进的资源共享模型，它的主要目标是解决资源利用率和资源分布的不平衡问题，它是科学家针对当今的一些科学难题于20世纪90年代初提出的新概念。这里的资源不仅包括传统的数据资源，还包括其它网络资源，比如计算资源、存储资源、信息资源、知识资源、算法资源等等。网格计算环境要求不影响各节点本地的管理和自主性，不改变原有操作系统、网络协议和服务，保证用户和各个节点的安全性。一个理想的网格计算类似当前的Web服务，可以架构在当前的所有硬件和软件平台上，给用户提供完全透明的计算环境。事实上，网格计算是企图把众多同构、异构的资源变成一个同构的虚拟计算环境，从而提供一种高性能计算、管理及服务能力。人们用这些资源就像用电能一样，不必计较这些资源的来源和负载情况。由于网格计算系统高效、强大的计算能力，使得网格计算被誉为“下一代计算模式”。它不仅解决了计算能力的限制，也解决了地理位置的限制，打破了传统共享与协作方面的限制，而且十分有效地节省了资源。