在线排序是现代排序中的核心研究方向，广泛地应用于生产管理、物流运输、商品销售、网络服务等很多领域。近二十年来，在线排序得到国内外同行的广泛关注和深入研究，并促使其成为现代排序领域中发展最为迅速的方向之一。本文所说的“在线”是指时间在线(onlineovertime)。也就是说，工件是随着时间依次到达的，并且只有在工件的到达时间我们才能详知它的一切信息。我们有以下三种关于时间在线的排序模型:不可中断模型(non-preemptivemodel)，中断可续模型(preemption-resumemodel)，中断重启模型(preemption-restartmodel)。　　人们通常用竞争比来衡量一个在线算法的性能。对一个最大化目标函数的在线排序问题，我们称在线算法A是ρ竞争的(ρ≥1)，如果对任一实例I都有A(I)≥(1/ρ)·OPT(I)成立，其中A(I)表示I在算法A生成的排序下的目标值，OPT(I)表示I在离线最优排序下的目标值。类似的，对一个最小化目标函数的在线排序问题，称A是ρ-竞争的如果满足A(I)≤ρ·OPT(I)。由此可见，竞争比ρ越接近于1，就表明在线算法的性能越优良。　　在第二章中，我们研究多组不兼容等长工件多台平行批处理机在线排序问题。在该问题中，同组工件可以放入一个加工批中进行加工，不同组的工件不能在同一批被加工。每一批最多可加工b个工件，b=∞表示批容量无界，b＜∞表示批容量有界。每个工件J具有一个等长的整的加工时间p＞0，一个整的释放时间r(J)≥0，一个整的必须交货期d(J)≥0和一个实数的权值ω(J)≥0。目标是确定一个工件可以中断重启的在线排序使得按时完工工件个数的权和达到最大。　　当p=1时，证明了该问题的下界为2-1/b，并得到一个竞争比为2的在线算法。这表明对b=∞的情形，我们设计的在线算法是最好可能的。　　当p是任意正整数时，得到一个竞争比为3+2√2在线算法，它也是关于该问题的第一个具有常数界竞争比的在线算法。　　在第三章中，我们研究多组等长工件两台（或三台）平行机在线分批排序问题。目标函数是最大化按时完工工件个数（或加权和）。　　对两台平行批处理机不可中断模型，给出一个与批容量b有关的下界，并得到一个竞争比为b+1的在线算法。　　对两台平行批处理机中断重启模型，证明了该问题的下界为2，并得到一个竞争比为3的在线算法。　　对三台平行批处理机，b=∞，同组工件的中断重启模型，得到一个竞争比为(8+2√15)/3≈5.249的在线算法。　　在第四章中，我们引入了友好释放时间(kindreleasetime)这种新的在线排序环境:当所有机器都在忙碌的时候不会有新的工件被释放;并记为KRT假设。　　证明了在KRT假设下，在线SWPT规则是单机最小化加权完工时间和在线排序问题的一个最优的在线算法。注意到，如果去掉KRT假设，在线SWPT规则关于该问题的竞争比将不会是常数界的。　　研究了在KRT假设下，在线LPT算法关于最小化时间表长的m台平行机的在线排序问题的竞争比。　　当m=2时，证明了LPT算法是一个竞争比为5/4的最好可能的的在线算法。相比Chen和Vestjens(OperationsResearchLetters，1997)给出的LPT是3/2-竞争的结果，表明对两台机器的情形，在KRT假设下确实改进了LPT算法的竞争比。　　对m≥3的情形，证明LPT的竞争比是3/2。　　对任意的m≥1，证明了LPT是一个最好可能的在线稠密算法。　　对m≥3的情形，证明了不存在竞争比小于1.3473的在线算法。　　对单机工件恰有两个加工时间1，κ的最大化完工工件总长度问题，证明该问题的下界为max{4/(2+k)，1}，并得到了一个竞争比为[k]/k的在线算法。表明当k是正整数的时候，我们的算法是最优的在线算法。　　在第五章中，我们研究了在lookahead作用下可中断等长区间单机在线排序问题。假设实例I中的所有区间都具有相同的长度（加工时间）p。目标就是从I中选择一些区间（区间之间不能重叠）使得所选区间的总权值达到最大。这里的“lookahead”是指在任一时刻点t，一个在线算法可以预见在时间段（t，t+L）上将要到达的所有区间的信息，其中L≥0。　　当L=p时，得到一个竞争比为2的在线算法。该项工作改进了Zheng等人(Computers&OperationsResearch，2013)给出的争比为3的在线算法。