两类解决基于光网络的分布式计算系统的项目调度问题的混合遗传算法

发布时间：2022-10-11 11:40

　　在这篇文章中,我们主要介绍基于光网络的分布式计算系统的调度算法。基于光网络的分布式计算系统通过高速低延时传输的光网络将分布在不同地理位置的计算资源存储资源等各种设备资源连接起来,为科学计算、系统设计和虚拟现实等新型应用提供计算服务。 本文主要研究基于光网络的分布式计算系统中的任务调度算法。由于各类设备资源的数量有限,使用需求又非常大,所以如何提高系统效率就成为一个棘手的问题。而且这些资源的成本非常高,专用高速光网络的运营费用更是非常昂贵,所以尽快的执行用户提交的应用能尽可能多的降低使用者的成本。因此,基于光网络的分布式计算系统非常需要一个高效的调度算法。 首先,我们对基于光网络的分布式计算系统的任务调度进行数学建模,建立了基于任务流的DAG调度模型,并论述了该问题属于资源约束下项目调度问题,随后本文对资源约束下项目调度问题进行介绍。在描述完问题后,本文介绍了目前已有的对基于光网络分布式计算系统的调度算法的研究情况。介绍了两种解决该问题的贪心算法:经典的扩展链表调度算法和在此基础上改进的基于调度关键路径算法。 在介绍了已有的研究情况后,我们提出了两类混合遗传算法:... 

【文章页数】：66 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
第一章：绪论
    1.1 研究背景
        1.1.1 分布式计算
        1.1.2 基于光网格的分布式计算
        1.1.3 面临的问题与挑战
    1.2 资源约束下的项目调度问题
        1.2.1 项目调度问题
        1.2.2 资源约束下的项目调度问题
        1.2.3 典型的资源约束下项目调度问题
    1.3 本文结构
第二章：问题展开与数学模型
    2.1 基于光网格的资源约束项目调度问题
    2.2 基于光网络的分布式计算系统的网络拓扑模型
    2.3 基于光网络的分布式计算系统基于任务流的数学模型
    2.4 调度目标以及约束条件
第三章：基于该问题的传统调度算法
    3.1 RCPSP 研究现状与主要算法
        3.1.1 穷举类算法
        3.1.2 贪心类算法
        3.1.3 全局最优算法
    3.2 基于光网格分布式计算系统的调度算法
        3.2.1 扩展链表调度算法
        3.2.2 基于调度关键路径的调度算法
第四章：基于混合权重编码的遗传算法
    4.1 基于任务优先权编码的遗传算法
        4.1.1 基于任务优先权的编码
    4.2 基于混合权重编码的遗传算法
        4.2.1 基于混合优先权的编码
        4.2.2 杂交与变异
        4.2.3 适应值计算与选择
        4.2.4 实例分析
    4.3 算法仿真及性能比较分析
        4.3.1 与最优结果的比较
        4.3.2 算法在更复杂的系统中的性能分析
第五章：基于ELS 的混合权重编码遗传算法
    5.1 基于ELS 的混合权重编码遗传算法
        5.1.1 编码过程
        5.1.2 译码过程
        5.1.3 杂交与变异
        5.1.4 适应值计算与选择
    5.2 算法仿真及性能比较分析
第六章：总结与展望
    6.1 全文总结
    6.2 研究展望
参考文献
致谢


【参考文献】：
期刊论文
[1]一种基于遗传算法的网格任务调度算法[J]. 马学彬,温涛,郭权,王刚.  东北大学学报(自然科学版). 2007(07)

硕士论文
[1]资源约束下多项目调度问题遗传算法研究[D]. 李敏.浙江大学 2008
[2]基于光网络的分布式计算系统中任务调度及容错策略研究[D]. 孙震宇.上海交通大学 2008
[3]基于微粒群算法的多模式资源受限项目调度优化问题研究[D]. 程晓梅.合肥工业大学 2007



本文编号：3690506