Ordinal半在线排序模型算法的改进

发布时间：2021-04-02 08:46

　　本文主要讨论了同型机上加工时间相似的工件调度问题。规定在性能相同的m台机器M1,Ma,…,Mm上加工n个独立的工件J1,J2,…,Jn,且每件工件只能在一台机器上加工一次。为了方便本文的研究,以下不考虑工件到达时间的情况,并令每个工件以加工时间非递增的顺序排列,用p表示Ji的加工时间,则p1≥p2≥…≥pn。本文是在Wei-Ping Liu,Jeffrey B.Sidney,Andre van Vliet在1996（[1]）年设计Pm算法基础上进行改进得到的一个新算法,新算法规定了每个到达的工件按照序号排列依次被送到某一台特定的机器上加工,每台机器只能同一时间加工一个工件,本文给这种算法命名为PmD算法。将最后一个工件的完工时间记为总完工时间,这个调度问题的目标函数为极小化总完工时间。本文得到且证明了机器台数m=2或m=3台时的最坏性能比优于Pm算法的结果。本文由四章构成:第一章为绪论,主要介绍了组合优化问题,着重叙述了组合优化问题下的一个经典问题——排序问题,详细说明了排序问题的背景和分类。以及最优化问题的多种求解方法。由于本论文是在Pm算法下改进的PmD算法,在后文也详细说明了Pm... 

【文章来源】：湖南师范大学湖南省 211工程院校

【文章页数】：64 页

【学位级别】：硕士

【文章目录】：
中文摘要
英文摘要
1 绪论
    1.1 组合优化问题
    1.2 排序问题
m算法和P_mD算法及符号引入">    1.3 P_m算法和P_mD算法及符号引入
2 两台机上工件加工时长有约束的性能比分析
    2.1 引言
    2.2 定理及其证明
3 三台机上工件加工时长有约束的性能比分析
    3.1 引言
    3.2 定理及其证明
结语
参考文献
致谢


【参考文献】：
期刊论文
[1]平行机半在线排序问题研究（Ⅱ）[J]. 何勇,杨启帆,谈之奕.  高校应用数学学报A辑（中文版）. 2003(02)
[2]平行机半在线排序问题研究（Ⅰ）[J]. 何勇,杨启帆,谈之奕.  高校应用数学学报A辑（中文版）. 2003(01)
[3]带机器准备时间的平行机在线与半在线排序[J]. 谈之奕,何勇.  系统科学与数学. 2002(04)



本文编号：3114971