本文对一些在线分批排序问题进行了研究，我们设计了在线算法，并进行了竞争比分析。在经典排序中，同一时刻机器只能最多加工一个工件，而对于分批排序的平行批(parallel batch)模型，批处理机器一批最多可以同时加工B个工件，这里B被称为批处理机器的容量。本文中的在线模型是工件实时到达(overtime)的，在每个工件到达之前，我们不知道它的任何信息。当它到达以后，它的信息便被完全知晓，我们需要决定是否开始加工或者是等待更多的信息，一且决策，将来不可更改。　　 本文主要由五个部分组成。首先，我们给出了组合优化和排序问题的一些概念，并对在线排序和分批排序问题的研究进行了综述。　　 第二章讨论加工时间有限制的在线单机分批排序问题，我们假设工件加工时间满足pj∈[p，(1+φ)p]，这里p为参数，φ=(∫5-1)/2。目标分别是极小化最大完工时间和最终送达时间，这些问题的下界均为1.618，我们分别给出了最优算法。　　 第三章研究了m台同型批处理机上工件带运输时间的在线排序问题，目标为极小化最终送达时间。当所有工件加工时间相等时，我们对于容量无限和有限两种情形，都给出了最优在线算法。当工件加工时间为一般的情形时，对于机器容量无限的情形，当m=2或m=3时，我们分别给出了竞争比为2的在线算法；当m＞4时我们给出了竞争比严格小于2的在线算法，当m趋于无穷时，竞争比趋近于1.5。　　 第四章研究了单台容量无限的批处理机上的在线排序间题，目标是极小化加权完工时间和。对于这个问题的一般情形，不存在竞争比小于2的在线算法。陈礴等人给出了一个10/3-competitive的算法。在此基础上，我们给出了一个在线算法，并证明了它的竞争比为3.236。当所有工件的加工时间都相等时，我们给出了一个1.618-competitive的算法，并证明了它是最优的。　　 第五章研究了单台容量无限的批处理机上带批运输在线排序问题。工件在批处理机上加工后需要用一台运输车辆运输到目的地，目标是极小化最终所有工件被送达日的地并且车辆返回的时间。对于加工时间都相等的情形，我们给出了下界。对运输车辆容量无限的情形，我们给出了最优在线算法；并对车辆容量有限的情形，我们给出了在线算法IHc和MIHc，并证明当p≥2T等情形时，我们的算法是最优的，这里p为加工时间，T为车辆一次运输与返回所需时间。对于加工时间一般的情形，问题的下界不小于1.618，当车辆容量无限时，我们给出了最优算法；当车辆容量有限时，我们给出了2-competitive的算法。　　 最后，我们对本文中研究的问题进行了总结与展望。