基于遗传算法的分布式任务调度系统的分析

论文摘要

任务调度是分布式计算系统研究的核心内容之一。如何合理的将作业分配给不同的资源,以使整个系统达到最佳的性能,这就是任务调度要解决的问题。由于分布式计算系统的异构性和动态性,以及运行于系统之中的应用程序对于资源的不同需求,使得任务调度变得极其复杂,不好的任务分配策略,将会增加任务的执行时间、降低整个系统的吞吐量。本论文首先介绍了分布式系统的概况,分析了分布式环境下任务调度的问题,并且设计了分布式计算任务调度系统中针对机器资源特性的收集模块,针对任务调度的NP完全问题,遗传算法具有很好的处理能力,但是传统的遗传算法有着过早收敛等缺陷,本文针对传统遗传算法的缺点,结合遗传算法操作过程中对各项参数的要求提出了一种对分布式异构计算系统进行任务分配与调度的改进的遗传算法,根据分布式计算系统各服务节点的计算能力、负载及网络状态进行动态调度,从而能够向用户提供最优性能,提高任务完成的效率。本论文的改进遗传算法,在传统遗传算法的基础上,针对分布式计算任务调度的动态特性,首先对任务分配调度问题做出定义,然后提出了新的编码机制和适应度函数,根据新的编码机制,重新设计了选择算子、交叉算子和变异算子。最后给出算法的仿真实验结果分析与结论等。任务调度问题是一个典型的NP问题,将遗传算法应用于任务调度中,利用遗传算法所具有的并行性和全局解空间搜索的特点,可以有效地缩短任务的完成时间,提高分布式系统资源的使用效率。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 分布式系统概述
• 1.2 论题研究意义
• 1.3 本文的主要研究内容
• 1.4 论文的框架
• 2 分布式计算系统介绍及任务分配问题
• 2.1 分布式计算定义
• 2.2 分布式系统中负载不平衡的原因
• 2.3 任务调度问题介绍
• 2.3.1 调度问题的一般模型
• 2.3.2 任务调度的分类
• 2.4 常见任务调度的基本算法
• 3 系统资源特性分析模块
• 3.1 分布式计算任务调度系统模型介绍
• 3.2 WMI技术简介
• 3.3 MPI技术简介
• 3.4 资源特性收集模块实现
• 4 改进的遗传算法的实现
• 4.1 任务调度问题定义
• 4.2 传统遗传算法介绍
• 4.2.1 传统遗传算法的形式化定义
• 4.2.2 传统遗传算法的流程
• 4.2.3 遗传编码
• 4.2.4 适应度函数
• 4.2.5 基因选择问题
• 4.2.6 交叉运算
• 4.2.7 变异操作
• 4.2.8 主要运行参数的选择
• 4.3 改进的遗传调度算法描述
• 4.3.1 染色体编码策略
• 4.3.2 适应度函数评价
• 4.3.3 选择操作
• 4.3.4 自适应交叉算子
• 4.3.5 自适应变异算子
• 5 实验实例及试验结果
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢