平行分批排序是一种重要的现代排序模型。在平行分批排序中,一台容量为b的机器可以把b个工件作为一批同时加工。同一批中的工件具有相同的开工时间和完工时间。每一批的加工时间和该批中最长工件的加工时间相同。在LKβ模型下,在时刻t,在线算法能预见到将在时间区间(t,t+β]内到达的所有工件的信息。不可相容的工件组是指属于不同组的工件不能被安排在同一批中加工。在本文中,主要研究了四个能够前瞻下一个时间区间内工件信息的单位长度工件的平行分批处理机的在线排序问题,包括单机和平行机,其中批容量是无界的。目标函数是使所有工件的最大完工时间最小。采用Graham等人(1979)提供的三参数表示法,这些问题分别表示为Pm|on-line,p-batch,b=∞,pj=1,LKβ|Cmax,1|on-line,p-batch,b=∞,pj=1,LKβ,two families|Cmax,1|on-line,p-batch,b=∞,pj=1,LKβ,families|Cmax,Pm|on-line,p-batch,b=∞,pj=1,LKβ,f=m|Cmax。　　 下面具体地给出本文的主要结果：　　 在第二章中,对于第一个排序问题Pm|on-line,p-batch,b=∞,pj=1,LKβ|Cmax,当β≥1／m时,给出了一个最优的在线算法H∞(β≥1／m)。当0≤β<1／m时,首先证明了该问题的所有的在线算法的竞争比的下界是1+αm,其中0<αm<1是方程(1+αm)(m+1)=αm+2-β∑mi=1(1+αm)i的一个根,然后提供了一个竞争比为1+αm的最好可能的在线算法H∞(β<1／m)。　　 在第三章中,对于后三个带有不可相容的工件组的在线排序问题,分别证明了这些问题的竞争比的下界至少是1+α2,1+αf,和1+α,其中α2,αf和α分别是方程2α22+(β+1)α2+β-2=0,f·α2f+(β+1)αf+β-f=0和α2+(β+1)α+β-1=0的一个正根。然后依次提供了最好可能的在线算法H2(β),Hf(β)和Hm(β)。