两类可拒绝同类机排序问题

论文摘要

排序问题是一类重要的组合优化问题,它广泛应用于管理科学、计算机科学、工农业生产、交通运输等许多领域,而其中的在线排序及工件可拒绝的排序问题,因其具有明显的实际应用背景,更是吸引了国内外许多学者。特别是对于工件可拒绝的排序问题,这一方面的研究结果还比较少,本文主要研究在线排序和工件可拒绝排序问题。 论文共分三章。 第一章（引言）主要介绍了排序的产生背景、发展及其一些符号等相关的基本知识。 第二章讨论的是带惩罚费用的单位工时的工件在同类机上的在线排序问题。所研究的问题若用三参数法应表示为Qm|on-line,pj=1|∑Cj+∑ej（此处涉及到工件的惩罚费用ej,是指当某工件Jj到达后,如果不加工该工件,将要受到一定的惩罚ej）。 本章是由工件在一台机器上及在任意台同型平行机的在线情况,推广到在任意台同类平行机上。文中针对m台同类平行机,设计了一在线算法G1,并给出了此算法的竞赛比为1/2(2+31/2)≈1.86602。并对离线情况给出了多项式时间的最优算法。 第三章主要研究了带惩罚费用的工件在同类机上的排序问题,目标为极小化最大完工时间与总的惩罚费用之和,并分别讨论了在线与离线两种情况。该问题用三参数法应表示为Qm|on-line|Cmax+∑ej和Qm‖Cmax+∑ej。 本章是由平行机推广到同类机上,文中针对m台同类平行机,设计一在线算法G2,并给出了此算法的竞赛比不超过1+ρ,其中p=min{（S1（m-1）/∑Si）1/2+S1（m-2）/∑Si,φS1},φ=(51/2+1)/2,S1是m台机器的最大速度,这推广了原有的结果。并

论文目录

• 第一章 序言
• §1.1 排序
• §1.2 工件可拒绝的在线排序问题
• §1.3 计算复杂性
• §1.4 P类和NP类
• §1.5 近似算法
• 第二章 带有惩罚费用的单位工时的工件在同类机上的排序问题
• §2.1 引言
• §2.2 预备知识
• §2.3 算法及其分析
• §2.4 主要定理
• §2.5 结论
• 第三章 带有惩罚费用的同类机排序问题
• §3.1 引言
• §3.2 预备知识
• §3.3 在线算法
• §3.4 可拒绝的离线排序
• §3.5 一类特殊情形
• §3.6 结论
• 参考文献