在经典的排序问题中,总是假设工件信息在排序之初都已经全部知道。在实际应用中,工件的信息在一开始往往是不知道的,而是随着时间的推移而逐个到达。这就是我们在此文中所要研究的按时在线(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+α。最后,给出问题在整数情况下的一个最好可能的在线算法。