链组约束下的平行机在线排序

论文摘要

在经典的排序问题中,总是假设工件信息在排序之初都已经全部知道。在实际应用中,工件的信息在一开始往往是不知道的,而是随着时间的推移而逐个到达。这就是我们在此文中所要研究的按时在线（on-line-over-time）排序问题。本文研究一类链组约束下的平行机在线排序问题,目标是最小化最大完工时间。这里工件的加工时间相同,工件之间的序约束关系是平行链,工件链一旦到达,该链上所有工件的信息才可知,已到达工件按照序约束关系在两台恒同机上加工。该问题用三参数法表示为P2|pj=p,chainsi released at ri|Cmax。Huo和Leung在《SIAM J.Comput》（2005）上发表的文章中给出了此问题的一个（16）/（15）的下界,并由此得出结论:该问题不存在能达到离线最优的在线算法。在本文中,我们首先利用对手法构造一组实例证明了该问题有一个更好的下界1+α(α=(（13）1/2-3)/2)≈1.3028。接着提供了一个最好可能的在线算法。该结论的证明是论文的主体部分。之后,我们对此问题的所有数据都是整数的情况进行了讨论:对于每一个固定的工件长度p,证明问题的下界为max{（p+[αp]）/p,（3p）/（2p+[αp]）};若p不固定,当p→+∞时,下界为1+α。最后,给出问题在整数情况下的一个最好可能的在线算法。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 排序论概述
• 1.2 在线排序和在线算法
• 1.3 工件之间的序约束
• 1.4 序约束下的平行机排序
• 第二章 链组约束下的平行机在线排序
• 2.1 引言
• 2.2 问题的下界
• 2.3 问题的一个最好可能的在线算法
• 2.4 整数条件下的问题
• 后记
• 参考文献
• 致谢