工件允许重启的平行分批在线排序研究

发布时间：2020-12-03 02:51

　　排序论是运筹学与组合最优化的重要分支.分批排序是人们十分关注的现代排序模型;其特点是可将工件分批进行加工,每一批工件具有相同的开工时间和相同的完工时间.在本文研究的平行分批排序模型中,每一批的加工时间等于该批中工件的最长加工时间.按照每一批可以加工的工件数目b的限制（称为批容量）,平行分批排序又可分为批容量有限（b<∞）和批容量无限（b=∞）两种情形.在线排序问题是近年来排序论研究的热点方向;其特点是工件的信息事先并不确定,决策者在没有获得所有工件信息之前就必须对已有工件进行排序.本文所研究的在线排序是工件实时到达（over time）的情形,即工件是随着时间逐渐到达的.工件的所有信息在其到达时刻才能获知.针对在线优化问题设计的算法称为在线算法.人们常用竞争比来衡量在线算法性能的好坏.对于一个极小化目标函数的优化问题,我们称一个在线算法是ρ-竞争的,如果对于该问题的任意实例,算法所产生的目标函数值不大于最优离线算法所产生的目标函数值的ρ倍.在线算法A的竞争比定义为ρA=inf{ρ:A是ρ-竞争的}.不难看出,ρA总是大于等于1的.由于信息的缺乏,ρA=1的情形只有在很特殊的问题上... 

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

【文章页数】：91 页

【学位级别】：博士

【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 排序理论简介
    1.2 算法和计算复杂性
    1.3 排序的相关知识及进展
    1.4 本文结果
第2章 允许有限重启的多台平行批处理机上的排序问题
    2.1 引言
    2.2 算法A（α）及相应排序的性质
    2.3 问题的下界
    2.4 在线算法
第3章 允许有限重启的单台平行批处理机上的排序问题
    3.1 引言
    3.2 批容量为2时问题的下界
    3.3 批容量为2时的最好可能的在线算法及竞争比分析
    3.4 批容量大于2时问题的下界
    3.5 批容量大于2时最好可能的在线算法及竞争比分析
第4章 允许重启的单台平行批处理机上的排序问题
    4.1 引言
    4.2 批容量为3时问题的下界
    4.3 批容量为3时的最好可能的在线算法及竞争比分析
    4.4 批容量大于3时问题的下界
    4.5 批容量大于3时的最好可能的在线算法及竞争比分析
    4.6 允许κ-有限重启（κ≥2）时的问题
第5章 允许有限重启且带有运输的平行批处理机上的排序问题
    5.1 引言
    5.2 批容量为2时问题的下界
    5.3 批容量为2时的最好可能的在线算法及竞争比分析
    5.4 批容量大于2时问题的下界
    5.5 批容量大于2时的最好可能的在线算法及竞争比分析
结论与展望
参考文献
个人简历、在学期间发表的学术论文与研究成果
致谢



本文编号：2895870