论文摘要
调度算法的性能分析,由于其在实际应用中对提高生产效率起着至关重要的作用,从而吸引了众多学者的兴趣。而预测调度算法由于可以充分利用生产过程中的任务信息,所以能比只利用当前时刻信息的在线算法更有效地进行调度。而相比起必须提前知道所有信息进行优化的离线算法,预测调度算法对加工环境的信息约束又有着很强的适应性。然而,目前已有文献针对预测调度算法的性能分析还几乎是空白。本文主要借鉴在线算法性能分析的手段和方法,并发展出实例转换的全新分析方法,对预测调度算法在最小化完工时间问题中的设计与性能分析进行了研究。首先,通过算法集划分和构造相应极端实例,我们得到了1|rj|∑Cj问题预测调度算法的竞争比下界,从而确定预测调度算法针对该问题的性能极限。之后,我们分别针对1|rj|∑Cj和P |rj|∑Cj问题设计了三种单步预测调度算法,从竞争比和平均性能比角度进行了性能分析,发现它们都远优于在线算法。本文主要研究成果包括:1)对于1|rj|∑Cj问题,从在线算法D-SPT出发,设计出两种单步预测调度算法,在性能上大大改善了原在线算法。2)在对单步预测调度算法P-SPT1竞争比的求解中,创造性地提出了实例转换的求解思想,并获得了成功。这也是本文的重要理论贡献。3)通过划分算法集和构造特殊实例的手段,求解了1|rj|∑Cj问题预测调度算法的竞争比下界。从相反的角度,刻画了预测调度算法随着预测步长的性能极限。4)对于更复杂的P |rj|∑Cj问题,通过借鉴OMPR算法的两层调度结构,并利用已构造出的单机预测规则P-SPT1,设计了一种同速机单步预测调度算法,在性能上同样都远优于原在线算法。5)尝试将实例转换的方法推广应用于P-SPT2和P-PSA的竞争比求解中,但在实际的推导中遇到了一些障碍。我们将推导过程所存在的困难一一作了详细的描述和分析,并给出了一些可能的解决思路。这些工作为进一步的深入分析也有着借鉴和帮助意义。
论文目录
摘要ABSTRACT第一章 绪论1.1 引言1.2 调度问题描述1.3 调度算法概述1.3.1 离线调度算法1.3.2 在线调度算法1.3.3 预测调度算法1.4 调度算法的性能研究1.5 本文研究意义和章节安排1.5.1 本文研究内容与意义1.5.2 本文章节安排j|∑Cj 问题的一般预测调度算法的竞争比研究'>第二章 1|rj|∑Cj问题的一般预测调度算法的竞争比研究2.1 引言2.2 研究算法集竞争比下界的意义与一般方法j|∑Cj 问题的在线算法的竞争比下界'>2.3 1|rj|∑Cj问题的在线算法的竞争比下界j|∑Cj 问题的单步预测调度算法的竞争比下界'>2.4 1|rj|∑Cj问题的单步预测调度算法的竞争比下界j|∑Cj 问题的多步预测调度算法的竞争比下界'>2.5 1|rj|∑Cj问题的多步预测调度算法的竞争比下界2.6 本章小结j|∑Cj 问题的单步预测调度算法的设计与性能分析'>第三章 1|rj|∑Cj问题的单步预测调度算法的设计与性能分析3.1 引言j|∑Cj 问题的在线算法的介绍与分析'>3.2 1|rj|∑Cj问题的在线算法的介绍与分析3.2.1 三种最优在线算法介绍3.2.2 算法D-SPT的最差实例分析3.3 单步预测调度算法P-SPT13.3.1 P-SPT1 算法的设计3.3.2 求解P-SPT1 算法竞争比的准备3.3.3 P-SPT1 算法的性质3.3.4 P-SPT1 算法竞争比的证明3.4 单步预测调度算法P-SPT23.4.1 P-SPT2 算法的设计3.4.2 P-SPT2 算法最差实例的仿真分析3.4.3 求解算法P-SPT2 竞争比的一些困难3.5 两种单步预测调度算法与在线算法平均性能比的仿真比较3.5.1 仿真说明3.5.2 仿真结果比较与分析3.6 本章小结j|∑Cj 问题的单步预测调度算法的设计与性能分析'>第四章 P|rj|∑Cj问题的单步预测调度算法的设计与性能分析4.1 引言j|∑Cj 问题在线算法OMPR的介绍与分析'>4.2 P|rj|∑Cj问题在线算法OMPR的介绍与分析4.3 单步预测调度算法P-PSA的设计与分析4.3.1 P-PSA算法的设计4.3.2 P-PSA算法最差实例的仿真分析4.3.3 求解算法P-PSA竞争比的一些困难4.4 P-PSA与OMPR算法平均性能比的仿真比较4.4.1 仿真说明4.4.2 仿真结果比较与分析4.5 本章小结第五章 总结与展望5.1 本文研究内容5.2 本文研究意义和主要贡献5.3 今后的研究方向参考文献致谢攻读硕士学位期间发表的论文
相关论文文献
标签：预测调度算法论文; 竞争比论文; 性能比论文; 实例转换论文;
