在离线排序问题中，工件信息在排序之前已经知道.本文我们研究的是按时在线(online-over-time)排序问题.按时在线排序是指工件各种信息在加工之初并不清楚，而是随着时间推移逐个到达之后才被了解.　　 平行机在线排序是现代排序领域中的一类重要问题.平行机在线排序模型中共有m台机器，我们要对已经到达的工件做出安排，即将工件安排在哪台机器上进行加工.本文主要研究两类平行机上的在线排序问题.　　 研究模型用三参数法表示为:　　 (1)P2|online，chains，pj∈[p，(1+α)p]|Cmax;　　 (2)Pm|online,p-batch,pj=1,b＜∞，β|Cmax.　　 模型(1)的基本描述:　　 在该问题中，我们研究在两台平行机上，工件加工长度在一个定区间内变化并且工件之间具有链组约束的在线排序问题，目标函数是最小化最大完工时间.在此模型中，所有工件的加工长度都是区间[p，(1+α)p]内的某个数值.在这个模型中，工件之间的序约束关系为链组约束.同一条链上的工件具有一个到达时间，一旦一条链到达，这条链上的所有工件信息都可知.　　 在本文第二章中，我们先给出了问题的一个下界1+α，其中α=√2-1.之后提供了一个竞争比为1+α的算法，从而说明此算法是最好可能的在线算法.　　 模型(2)的基本描述:　　 在该问题中，我们有m台平行机，对带有预测区间的等长工件进行平行批的在线排序，目标函数是最小化最大完工时间.平行批排序是一类重要的现代排序问题，在这种模型中，机器可以同时将b(批的容量)个工件作为一批进行加工.批容量有两种不同的类型，一种是批容量有限，一种是批容量无限.本文研究的是批容量有限的情形.同一批中的工件具有相同的开工时间和完工时间.一个批的加工时间定义为此批中最长工件的加工时间.在本文的在线排序环境中，记β为预测区间的长度，那么在任意时刻t，在线算法都可以预测到在时间段(t，t+β]内到达的工件信息.　　 对问题Pm|online，p-batch，pj=1，b＜∞，0＜β≤1/6|Cmax，Li，Zhang和Yang[17]在《InformationProcessingLetters》[2012]上发表的文章中给出最好可能的在线算法.本文第三章提供了当0＜β≤1时的一个最好可能的在线算法，其竞争比为ρ(H)={1+α1，0＜β≤1/2,1+α2,1/2＜β≤1.　　 其中α1为方程α2+(β+1)α+β-1=0的正根，α2=√17-3/4.