经典排序总是提前知道工件的信息，从而可以找到最优的排序.而在实际应用中，在排序之初工件的信息通常是未知的，随着时间的推移工件逐一被释放.这就是现代排序中的按时在线排序，也正是此文要研究的内容.　　 本文研究的是单机分批在线排序问题.分批排序是排序领域中一类非常重要的问题.分批排序就是指处理机可以将多个工件作为一批同时进行加工.同一批中的所有工件具有相同的开工时间与完工时间.对于平行批排序，每一批工件的加工时间等于该批中最长工件的加工时间.根据批容量可将平行批排序分为两种类型:批容量有限和批容量无限。　　 本文第二章研究的问题是单机批容量无限且工件的加工时间都在区间[p，(1+α)p]上，其中p＞0且α=√5-1/2.目标函数是最小化最大流程.此目标函数的研究具有很好的实际意义.该问题用三参数法表示记为:1|online，Tj，p-batch，b=+∞，pj∈[p，(1+α)p]|Fmax.文献[9]针对工件加工时间任意的情形给出了一个竞争比为2的在线算法.在此我们将工件的加工时间限制在一个范围内.我们首先利用对手法构造一个实例证明了该问题的下界√5+1/2.然后设计了一个在线算法，接着证明了此在线算法的竞争比为1+1/2α≈1.809。　　 本文在第三章对该问题进行了进一步讨论.首先进行了数值实验，通过数值实验可知，虽然H∞算法不是最好可能的在线算法，但当所考虑实例中工件的个数不是太大时，此在线算法具有很好的可靠度.进而对于批容量有限问题给出了一个下界;对于工件加工时间为任意的情形设计了在线算法。