带有工件运输的在线排序研究

发布时间：2021-07-10 19:24

　　在线排序是排序论的一个前沿研究方向,近二十年来得到人们广泛的研究。文献中有多种不同的在线排序模型,而本文的“在线排序”指的是“时间在线（onlinetime）排序”:工件是按时间到达,并且当一个工件到达时,才知道这个工件的具体信息。对在线问题的研究中,决策者在当前时刻需要在仅仅知道已经到达的工件信息的前提下做出决策。因而,很多在线排序问题是没有最优算法的。人们通常用竞争比来衡量一个在线算法的好坏。我们以最小化目标函数的排序问题为例。在线算法A的竞争比ρA定义为ρA=sup{A（I）/OPT（I）:I是任意一个实例且满足OPT（I）>0},其中I是排序问题的任意一个实例,A（I）是执行了在线算法A得到的实例I的目标函数值,而OPT（I）则是由离线最优排序所得到的实例I的目标值。因而竞争比ρA≥1,而且ρA越趋近于1,在线算法的性能越好。如果不存在竞争比小于ρA的其他在线算法,我们就说在线算法A是最好可能的。在本文中我们研究了四类带工件运输时间的在线排序问题:在线折衷排序问题;工件具有不相容性并考虑工件运输的在线排序问题;工件的加工时间有限制的在线排序问题;工件具有退化效应的在线排序... 

【文章来源】：郑州大学河南省 211工程院校

【文章页数】：106 页

【学位级别】：博士

【文章目录】：
摘要
abstract
第1章 绪论
    1.1 排序问题
    1.2 排序的三参数表示法
    1.3 在线排序问题
    1.4 相关文献
        1.4.1 多目标排序
        1.4.2 平行分批排序
        1.4.3 工件带有运输时间的排序
        1.4.4 不相容工件组的排序
        1.4.5 工件具有退化效应的排序
    1.5 本文的主要结果
第2章 最小化时间表长和最大运输完工时间的在线折衷排序问题
    2.1 引言
    2.2 在线算法D-LDT(ρ)
    2.3 算法竞争比的分析
第3章 多个不相容工件组的无界平行批排序问题
    3.1 引言
    3.2 准备工作
    3.3 算法及其竞争比分析
第4章 不相容工件组已确定的无界平行批排序问题
    4.1 引言
    4.2 准备工作
    4.3 排序问题Dmax(online, pj= p, Ti= T )
    4.4 排序问题Dmax(online, f )
第5章 加工时间有限制的单机排序问题
    5.1 引言
    5.2 准备工作
    5.3 问题的下界
    5.4 c = ∞ 的情形
    5.5 c < ∞ 的情形
第6章 单机上考虑运输的退化工件的在线排序问题
    6.1 引言
    6.2 准备工作
    6.3 车辆的容量充分大的情形
        6.3.1 问题的下界
        6.3.2 算法及竞争比分析
    6.4 容量有限制的情形
        6.4.1 问题的下界
        6.4.2 算法及竞争比分析
第7章 结论与展望
参考文献
在学期间学术论文发表情况
致谢


【参考文献】：
博士论文
[1]具有交货期或友好释放时间的在线排序研究[D]. 李文杰.郑州大学 2014
[2]工件具有不相容性质的机器排序问题[D]. 李士生.郑州大学 2012
[3]关于一些在线分批排序问题的研究[D]. 方阳.华东理工大学 2011
[4]加工时间非常数的排序与调度模型研究[D]. 张新功.上海理工大学 2010
[5]平行批在线排序问题[D]. 付乳燕.郑州大学 2009
[6]多台平行批处理机在线排序和带有运输时间的在线排序[D]. 田记.郑州大学 2009
[7]多目标分批排序及其相关课题[D]. 何程.郑州大学 2009
[8]工件加工时间可变的现代排序问题[D]. 王吉波.大连理工大学 2005



本文编号：3276516