本文我们主要研究的是单机上的分批在线排序问题,并且都是批容量有界的模型.假设所有工件的加工时间都在区间[p,(1+Φ)p]上,其中p＞0.本文研究的模型用三参数法表示模型即是:　　 (1)1|p-batch,online,B＜n,rj,pj∈[p,(1+Φ)p],limited restarts|Cmax,其中Φ=1/2.　　 (2)1|p-batch,online,B＜n,rj,pj∈[p,(1+Φ)p],qj|Dmax,其中Φ=√5-1/2.　　 第一个排序模型的基本情况:　　 此模型中研究的是允许有限重启的平行分批在线排序问题,目标函数是最小化最大完工时间.　　 工件批允许“重新启动”(简称重启)是指,我们可以打断当前正在加工的批,已经加工的部分全部作废,批中工件被释放出来,各自成为独立的未加工工件,它们可以与其它已经到达的未加工的工件重新组合成一批,再被加工.排序中允许重启可以降低错误的决策造成的损失.　　 工件批的“有限重启”,是在文献[12]提出的新定义,是指每批工件最多被重启一次.　　 文献[3]在模型1|p-batch,online,B＜n,rj,pj∈[p,(1+Φ)p],Cmax中提供了一个竞争比为√5-1/2的最好可能的在线算法.(其中Φ=√5-1/2).　　 我们在此模型的基础上加上允许工件有限重启,即得到了本文所论述问题的模型.我们证明了此排序问题的任意在线算法的下界不小于3/2,并给出一个竞争比为3/2的最好在线算法.　　 第二个排序模型的基本情况:　　 此模型是带有运输的单机上的平行分批在线排序,目标函数是最小化所有工件被运输到目的地的时间.其中Dmax=max{Dj|Dj=Cj+qj}.J.Tian等人[22]在排序问题1|p-batch,online,B＜n,rj,pj=p|Cmax中给出了竞争比为√5+1/2的最好可能的在线算法.我们在此模型的基础上扩大了加工时间的范围,也就是用pj∈[p,(1+Φ)p]代替pj=p,其中Φ=√5-1/2.我们证明了此排序问题的任意在线算法的下界不小于√5+1/2,并且给出一个竞争比为√5+1/2的最好可能的在线算法.