带结果收集的多趟调度优化模型及算法研究

论文摘要

任务调度策略研究一直是分布式计算平台研究的热点问题。分布式平台任务调度的目标是寻找合理的任务调度策略使得任务完成时间最短,其中任务完成时间包括传输时间、计算时间和结果回传时间。已有研究大多假设结果回传时间可以忽略不计,但是实际上很多大数据应用任务在分布式平台上完成任务计算后其结果的数据规模仍较大(如图像压缩问题),即结果的传输时间不能忽略不计。鉴于此,以任务最短完成时间为目标,研究了两种通信模式下带结果收集的多趟调度优化模型,并设计了高效的算法对模型进行求解。主要研究成果包括:1.针对异构分布式平台,研究了阻塞通信模式下带结果收集的可分任务多趟调度优化问题。首先,以任务完成时间最短为目标,建立了一个新的多趟调度优化模型;其次,在给定服务器调度顺序的情况下,推导得到了多趟调度的最优调度趟数和最优任务分配方案;然后,设计了一种新的全局优化遗传算法,得到了最优的服务器调度顺序;最后,通过与已有多趟任务调度算法进行比较,证实了所提算法能得到最短的任务完成时间,验证了模型和算法的有效性。而且,通过分析实验结果得知当任务规模很大时,服务器的最优调度顺序为服务器传输速率升序排列的顺序。2.针对异构分布式平台,研究了非阻塞通信模式下带结果收集的可分任务多趟调度优化问题。首先,以任务完成时间最短为目标,建立了一个新的多趟调度优化模型;然后,以上一章节的结论为基础,将服务器的调度顺序固定为传输速率升序排列的顺序,推导得到了非阻塞通信模式下多趟调度的最优调度趟数和最优任务分配方案;最后,通过实验验证了所提模型和算法的有效性。实验结果表明所提模型不仅可以最小化任务完成时间,而且可以极大地提高分布式平台的容错性能。

论文目录

• 摘要
• ABSTRACT
• 符号对照表
• 缩略语对照表
• 第一章 绪论
•   1.1 研究背景及其意义
•   1.2 国内外研究现状
•   1.3 本文研究内容
•   1.4 本文的组织框架
• 第二章 遗传算法概述
•   2.1 遗传算法基本原理
•   2.2 遗传算子
•   2.3 遗传算法的特点
•   2.4 本章小结
• 第三章 阻塞通信模式下带结果收集的可分任务多趟调度模型及算法研究
•   3.1 问题描述
•   3.2 阻塞通信模式下带结果收集的可分任务多趟调度模型
•     3.2.1 内部调度的任务分配方案
•     3.2.2 第一趟调度的任务分配方案
•     3.2.3 最后一趟调度的任务分配方案
•     3.2.4 调度模型
•   3.3 阻塞通信模式下带结果收集的可分任务多趟调度算法
•     3.3.1 编码和适应度函数
•     3.3.2 交叉算子
•     3.3.3 变异算子
•     3.3.4 局部搜索算子
•     3.3.5 全局优化遗传算法
•   3.4 实验与结果分析
•   3.5 本章小结
• 第四章 非阻塞通信模式下带结果收集的可分任务多趟调度模型及算法研究
•   4.1 问题描述
•   4.2 非阻塞通信模式下带结果收集的可分任务多趟调度模型
•     4.2.1 内部调度的任务分配方案
•     4.2.2 第一趟调度的任务分配方案
•     4.2.3 最后一趟调度的任务分配方案
•     4.2.4 调度模型
•   4.3 非阻塞通信模式下带结果收集的可分任务多趟调度算法
•   4.4 实验与结果分析
•   4.5 本章小结
• 第五章 总结和展望
•   5.1 本文工作总结
•   5.2 未来工作展望
• 参考文献
• 致谢
• 作者简介

文章来源

类型: 硕士论文

作者: 马海明

导师: 王宇平

关键词: 可分任务调度,多趟调度,结果收集,遗传算法,任务完成时间

来源: 西安电子科技大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 西安电子科技大学

分类号: O224

DOI: 10.27389/d.cnki.gxadu.2019.002682

总页数: 79

文件大小: 3482K

下载量: 13