在经典的排序问题中,总是假设工件信息在排序之初都已经全部知道。在实际应用中,工件的信息在一开始往往是不知道的,而是随着时间的推移而逐个到达。这就是我们在此文中所要研究的有到达时间的在线排序问题(on-line-over-time)。带拒绝费用的平行机排序问题,由Bartal等人最先提出并研究。其目标是最小化最大完工时间与所有被拒绝工件的罚值之和。对列表在线情形,他们给出一个竞争比2+α的最好可能的在线算法。一般来说,单机平行分批排序和多台同型机排序之间存在密切的联系。文中,我们考虑单机批容量无界和两台同型机环境下的两个在线模型。我们可以用三参数法表示这两个模型为1丨on-line,p-batch,b=∞,lj=upj丨w,P2丨on-line,rj,lj=upj丨w,其中u∈(0,1),w=max{ri,cj}+P(R)。文章的主要结果,是用H∞算法和AR算法对前述模型分别进行分析得出的。对单机批容量无界情形,H∞算法的竞争比是(1+α)/u;对两台同型机情形,AR算法的竞争比是1+2u。本文中,我们还使用对手方法构造实例,得到上述两个模型的下界。