在离线排序问题中,工件信息在排序之前已经知道.本文我们研究的是具有前瞻区间的按时在线(on-line-over-time)排序问题.按时在线排序是指工件各种信息在加工之初并不清楚,而是随着时间推移逐个到达之后才被了解.工件按时在线到达,具有前瞻区间是指在时刻t在线算法能预见到时间区间(t,t+β]内到达的所有工件的信息.不可相容的工件组是指属于不同工件组的工件不能被安排在同一批中加工.平行机在线排序是现代排序领域中的一类重要问题.平行机在线排序模型中共有m台机器.本文主要研究三类平行机上的在线排序问题.研究模型用三参数法表示为：(1)P2|online,p-batch,pj=1,b=∞,β,3-family|Cmax；(2)Pm|online,p-batch,pj=1,b=∞,β,f-family|Cmax(其中f为偶数)；(3)Pm|online,p-batch,pj=1,b=∞,β｜Fmax.模型(1)的基本描述：在该问题中,我们研究在两台平行机上,具有前瞻区间的三个不相容工件组的在线排序.目标函数是最小化最大完工时间.在此模型中,所有工件的加工长度都是1.其特点是工件的所有信息都是分阶段逐步释放给决策者,决策者只能根据已有的信息来做出排序决策.在线算法的优良程度通常用它的竞争比来衡量.对问题1｜online,p-batch,pj=1,b=∞,β,two-family|Cmax付等人[1]给出了一个竞争比(?)的最好可能在线算法.在本文第二章中,我们先给出了问题的一个下界1+α,其中α是方程2α2+(1+β)α+β-2=0的正根.并提供了一个最好可能的在线算法.模型(2)的基本描述：在该问题中,我们研究m台平行机上具有前瞻区间的多个不相容工件组的在线排序,目标函数是最小化最大完工时间.平行批排序是一类重要的现代排序问题,在这种模型中,机器可以同时将无数个属于同一工件组的工件作为一批进行加工,但不同工件组不能放在同一批加工.批容量有两种不同的类型,一种是批容量有限,一种是批容量无限.本文研究的是批容量无限的情形.同一批中的工件具有相同的开工时间和完工时间.一个批的加工时间定义为此批中最长工件的加工时间.记β为前瞻区间的长度,那么在任意时刻t,在线算法都可以预测到在时间段(t,t+β]内到达的工件信息.本文第三章提供了当0<β≤1且f为偶数时的一个最好可能的在线算法,其竞争比为1+αf,其中αf是方程f·α2f+2(β+1)αf+2β-f=0的一个正根.模型(3)的基本描述：在该问题中,我们研究m台平行机上具有前瞻区间的等长工件组的在线排序,工件按时在线到达,目标函数是最小化最大流程时间.在本文的在线排序环境中,记β为前瞻区间的长度,那么在任意时刻t,在线算法都可以预测到在时间段(t,t+β]内到达的工件信息.本文第四章提供了当0<β≤1时的一个最好可能的在线算法,其竞争比为1+α,其中α是方程α2+(β+1+m)α+(m+1)β-1=0的一个正根.