具有服务等级的在线和半在线排序及其相关问题

论文摘要

排序问题是运筹学与组合优化领域中的一类重要问题.对排序理论的研究具有重要的理论意义和广阔的实际应用前景.具有服务等级的排序问题是现代工业生产中出现的一个新的组合优化模型,近年来受到了许多学者的关注.本文主要研究具有服务等级的在线和半在线排序问题.全文共分为五章.在第一章中,我们首先介绍了排序问题的基本概念和基本理论,然后给出了具有服务等级的平行机排序问题的描述以及该问题近年来取得的研究进展.在第二章中,我们主要研究了具有两个服务等级的m台同类机上的在线和半在线负载问题.在该模型中,工件按序在线到达且是可分的.其中,k（1≤k≤m-1）台机器的速度为s,服务等级为1,能加工所有的工件,另外的m-k台机器的速度为1,服务等级为2,只能加工服务等级为2的工件.对于目标为最大化最小完工时间的不可分模型,我们证明了不存在具有有界竞争比的在线算法,因此我们研究工件可分模型.对于目标为最大化最小完工时间的可分模型,我们设计了竞争比为（2ks+m-k）/（ks+m-k）（0<s<∞）的最好可能的在线算法.对于目标为最小化最大完工时间的可分模型,我们设计了竞争比为的最好可能的在线算法.对于已知所有工件的加工时间总和（sum）的目标为最小化最大完工时间的可分模型,我们给出了最优的在线算法（即竞争比为1的算法）.在第三章中,我们主要研究了具有两个服务等级的m台同类机上的在线排序问题.在该模型中,工件按序在线到达且是不可分的.其中,k（1≤k≤m-1）台机器的速度为s,服务等级为1,能加工所有的工件,另外的m-k台机器的速度为1,服务等级为2,只能加工服务等级为2的工件.对0<s<1和s≥1两种情形,我们分别给出了在线算法.当0<s<1时,我们给出的算法的竞争比为当s≥1时,我们给出的算法的竞争比为其中,s1∈（0,1）是方程k2s3+k（2m-2k-1）s2+（m-k）（m-2k）s-（m-k）2=0的实根,s2是方程ks2-（2k-1）s-（m-k）=0的正根.当k=1且m=2时,这两个算法都是最好可能的.我们还给出了一些特殊情形时的问题的下界.在第四章中,我们主要研究了具有服务等级的两台恒同机上的在线排序问题,其中工件的到达方式是按时在线到达.首先我们证明了任何在线算法的竞争比都至少是3/2,接着我们给出了一个竞争比为1+（?）/2的在线算法.在第五章中,我们主要研究了机器有到达时间的在线和半在线排序问题,其中工件的到达方式是按序在线到达.对机器有到达时间且允许重排的两台恒同机上的在线排序问题,我们研究了两种不同的模型,允许重排任意k个工件的模型和允许重排每台机器上的最后一个工件的模型.对这两种模型我们分别给出了竞争比为4/3和（?）的最好可能的在线算法.对于具有服务等级且机器有到达时间的两台恒同机上的在线和半在线排序问题,我们分别给出了修正的在线算法,并且这两个算法都是最好可能的.

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• §1.1 排序问题
• §1.2 近似算法和竞争比分析
• §1.3 经典的平行机排序问题
• §1.4 具有服务等级的排序问题
• §1.5 本文的主要工作
• 第二章 具有服务等级的同类机在线和半在线负载问题
• §2.1 引言
• min'>§2.2 模型Qm|online,g=2,frac|C_min
• max'>§2.3 模型Qm|online,g=2,frac|C_max
• max'>§2.4 模型Qm|online,g=2,frac,sum|C_max
• 第三章 具有两个服务等级的同类机在线排序问题
• §3.1 引言
• max的在线算法'>§3.2 当0max的在线算法
• max的在线算法'>§3.3 当s≥1时,模型Qm|online,g=2|C_max的在线算法
• 第四章 具有服务等级的两台恒同机在线排序问题
• §4.1 引言
• j,g=2|C_max'>§4.2 模型P2|online,r_j,g=2|C_max
• 第五章 机器有到达时间的在线和半在线排序问题
• §51 引言
• i|online,P_A|C_max'>§5.2 模型P2,r_i|online,P_A|C_max
• i|online,P_E|C_max'>§5.3 模型P2,r_i|online,P_E|C_max
• i|online,g=2（sum）|C_max'>§5.4 模型P2,r_i|online,g=2（sum）|C_max
• 结论
• 参考文献
• 作者攻读博士学位期间完成的论文
• 致谢