论文部分内容阅读
本文主要研究可中断平行机(半)在线排序问题的近似算法设计及其竞争比分析．对多个不同机器环境和目标函数下的可中断(半)在线问题以及两个新排序模型，本文讨论了这些问题的下界，设计了相应的近似算法并给出了它们的竞争比．
全文共分为七章，第一章首先介绍了与排序问题相关的一些概念以及预备知识，并总结了近些年在半在线领域研究中取得的成果．
第二章研究可中断的机器覆盖问题(P(Q)|pmpt|C<,min>).对m台同类机的离线情形，文中证明了能在O(mn)时间内找到最优解．随后研究了在线机器覆盖问题的下界，给出了一个求解这类问题下界的一般公式并由此得出了问题Qm|pmpt|C<,min>)和Pm|pmpt|C<,min>)的下界分别为m和∑<,i=1> 1/i．最后，文章还研究了两台同类机的在线算法并分别给出了在不允许机器空闲与允许机器空情况下的最优在线算法．
第三章研究已知工件加工时间位于某一区间的可中断半在线排序问题．文中分别给出了问题．P3|pmpt，group|Cmax、Q2|prapt，group|C<,max>和Q2|pmpt，group|C<,min>的最优可中断参数界算法．
第四章研究了两台同类机上已知工件按非增序到达和已知最大工件长度这两个可中断半在线排序问题．文中分别给出了Q2|pmpt，decr|C<,min>、Q2|pmpt，max|C<,max<和Q2|pmpt，max|C<,min>．的最优可中断算法．
第五章研究带不确定信息的可中断半在线排序问题．文章分别给出了Pm|pmpt，dist opt|C<,max>、Q2|pmpt，dist opt|C<,max>和Q2|pmpt，dist max|C<,max>的最优可中断算法．
第六章研究带机器费用的平行机可中断(半)在线排序问题．在该问题中，一开始没有任何机器可用，当一个工件到达后，算法必须作出选择是购买新机器加工该工件还是将其放在已购买的机器上加工．目标函数是极小化makespan和所有机器的购买费用之和．文中首先给出了一个竞争比为(2<平方根6>+2)/5≈1.3798的在线可中断算法，而该问题的下界为4/3．此外，还研究了已知工件按非增序到达的半在线情形，给出了竞争比为4/3的最优算法，该算法无需工件被中断，因此也是不可中断问题的最优算法．
第七章研究带服务等级约束的平行机在线排序问题．该问题对每个工件和机器都赋予一个服务等级，工件只能在服务等级不高于自己的机器上加工．文中首先给出了两台机器上的最优在线算法．对m台机器带有两个服务等级的在线排序问题，证明了该问题的下界至少为2，随后证明了贪婪算法求解该问题的紧界为4-1/m并给出了一个竞争比为12+4<平方根2>/7≈2.522的改进算法.