在线排序是排序论的一个前沿研究方向，近二十年来得到人们广泛的研究。文献中有多种不同的在线排序模型，而本文的“在线排序”指的是“时间在线(online-time)排序”：工件是按时间到达，并且当一个工件到达时，才知道这个工件的具体信息。对在线问题的研究中，决策者在当前时刻需要在仅仅知道已经到达的工件信息的前提下做出决策。因而，很多在线排序问题是没有最优算法的。人们通常用竞争比来衡量一个在线算法的好坏。我们以最小化目标函数的排序问题为例。在线算法A的竞争比ρA定义为其中I是排序问题的任意一个实例，A(I)是执行了在线算法A得到的实例I的目标函数值，而OPT(I)则是由离线最优排序所得到的实例I的目标值。因而竞争比ρA≥1，而且ρA越趋近于1，在线算法的性能越好。如果不存在竞争比小于ρA的其他在线算法，我们就说在线算法A是最好可能的。　　在本文中我们研究了四类带工件运输时间的在线排序问题：在线折衷排序问题；工件具有不相容性并考虑工件运输的在线排序问题；工件的加工时间有限制的在线排序问题；工件具有退化效应的在线排序问题。本文的主要结果如下：　　在第二章中，我们研究了单台机器上的在线折衷排序问题，目标是最小化时间表长和最大运输完成时间。对该问题，我们给出了一个折衷竞争比为(ρ,1+1ρ)的最好可能的(非支配的)在线算法，其中1≤ρ≤　　在第三章中，我们研究了单台无界平行批处理机工件具有不相容性并考虑工件运输的在线排序问题，目标是最小化最大运输完成时间。这里，工件的不相容性指的是：不同工件组的工件不能放在同一个加工批或者同一个运输批进行加工或者运输。本章假设不相容工件组的数目事先不知道，运输车辆只有一台并且它的容量是充分大的。对该问题，我们给出了一个竞争比为2的最好可能的在线算法。　　在第四章中，我们继续研究单台无界平行批处理机工件具有不相容性并考虑工件运输的在线排序问题，目标仍是最小化最大运输完成时间。本章假设不相容工件组的数目 f事先已经确定，而运输车辆依旧只有一台并且它的容量是充分大的。对于 pj=p且 Ti=T的情形，我们给出了一个竞争比为1+线算法。对于一般情形，我们给出了一个竞争比为2的在线算法。　　在第五章中，我们研究了单台机器考虑工件运输且工件的加工时间有限制的在线排序问题，目标是最小化最大运输完成时间。这里，工件的加工时间有限制是指所有的工件的加工时间都在[p,(1+α)p]内。本章假设运输车辆只有一台。对该问题，在运输车辆的容量是无界和有界的两种情形，我们均给出了竞争比为√5+12的最好可能的在线算法。　　在第六章中，我们研究了单台机器考虑工件运输的退化工件的在线排序问题，目标是最小化最大运输完成时间。工件的退化效应是指工件的加工时间依赖于工件的开工时间，即 pi= ait，其中 ai≥0，t表示工件的开工时间。当运输车辆的容量无界时，我们给出了竞争比为√5+12的最好可能的在线算法。当运输车辆的容量有界时，我们给出了一个竞争比为2的在线算法。