排序就是在一定的限制条件下,分配时间资源去完成一些任务,使得一个或者多个目标达到最优.近年来,平行分批排序和在线排序是两个发展比较迅速的排序模型.平行分批排序模型中,机器可以同时加工多个工件,并且每批的加工时间是该批所有工件中加工时间的最大者.一旦批开始加工就不能被中断,直到该批被加工完毕.在线排序模型中,工件的信息在其到达之前是一无所知的,并且一旦工件被安排之后就不允许再改变.在LKβ模型下,在时刻t,在线算法能预见到将在时间区间(t,t+βp(t)]内到达的所有工件的信息,而p(t)是在时刻t可用工件中加工时间最大者.　　 本文研究了两种排序模型:(1)带有前瞻区间的平行分批处理机的在线排序问题;(2)带有运输时间的单机在线排序问题.采用Graham等人[1]提供的三参数表示法,这些问题分别表示为　　 1|on-line,rj,p-batch,b=∞,LKβ|Cmax;　　 1|on-line,rj,p-batch,agreeable(pj,qj),b=∞,LKβ|Lmax;　　 1|on-line,rj,qj≥pj|Lmax.　　 下面我们具体地给出本文的主要结果.@2在第二章中,对于前两个在线分批排序问题,我们分别证明了这些问题的竞争比的下界至少是1+α,其中α是方程α2+(β+1)α+β-1=0的一个正根,然后分别提供了一个竞争比为1+α的在线算法H1(α,β)和H2(α,β),最后我们证明了当0＜β≤1/6时,算法H1(α,β)和H2(α,β)是最好可能的.　　 在第三章中,对于在线排序问题1|on-line,rj,qj≥pj|Lmax,我们首先证明了该问题的所有在线算法的竞争比的下界是√3+1/2,进一步,我们提供了一个竞争比为√2的在线算法H.