论文部分内容阅读
排序论是组合优化的一个重要分支,对它的研究有着深刻的理论意义和重要的应用前景.在线排序和分批排序是近年来排序论研究中十分活跃的前沿课题.本文对两个在线平行分批排序问题进行了研究.论文的主要内容如下:
第一章简单介绍了排序问题的相关定义、记号及相关知识.
第二章考虑了两台机器在线分批排序问题,其中一台是批处理机,一台是标准机；目标函数为极小化工件的最大完工时间.利用Graham等人(1979)引入的三参数法,该问题可表示为
P2｜on-line,p-batch,B1=∞,B2=1｜Cmax.
对上述一般问题,我们首先给出了一个改进的下界1+β,其中β=√2/2≈0.707.接着给出了两个竞争比为2的简单在线算法.最后设计了两个有待进一步研究的在线算法.对限制问题
P2｜on-line,p-batch,agreeable(rj,pj),B1=∞,B2=1｜Cmax,
我们给出了一个竞争比为(√5+1/2)的最好可能在线算法.
第三章考虑了单机在线分批排序问题,工件带有运输时间,目标函数为最小化工件的最大运输完工时间.利用Graham等人(1979)引入的三参数法,该问题可表示为:
1｜p-batch,on-line,B=∞｜Lmax.对于限制问题
1｜p-batch,on-line,Pj≥qj,B=∞｜Lmax,
1｜p-batch,on-line,agreeable(pj,qj),B=∞｜Lmax和
1｜p-batch,on-line,Pj=P,B=∞｜Lmax,
我们给出了一个竞争比为(√5+1/2)的最好可能的在线弹性算法.对于限制问题
1｜p-batch,on-line,qmax＼qmin≤1+α,B=∞｜Lmax,我们证明了Poon和Yu(2005)的弹性算法的竞争比不超过(√5+1/2),也就是说,该弹性算法仍是最好的.
第四章总结全文并指出了下一步要研究的问题.