本文主要研究平行机上的几个在线排序问题以及半在线排序问题。我们主要研究这些排序问题的下界、设计算法并分析算法的竞争比。全文主要分为六部分内容。 第一章主要介绍了组合优化、排序问题相关的一些概念，并介绍了在线排序以及半在线排序的研究现状。 第二章研究了同型机上的在线排序问题，目标为极小化所有工件的完工时间之和。这是在线排序中一个非常重要的问题，已经有了很多的研究成果。Vestjens证明了此问题的任何在线算法的竞争比不可能小于1.309，对具体的机器数m，这个结果可以做进一步改进。 本文给出了此问题的一个在线算法DSPT，证明了这个算法的竞争比为2。这是目前最好的结果，也是大家一直希望得到的结果。 第三章主要研究了两台同类机上的在线排序问题。两台同类机的速度分别为1和s(s≥1)。我们分别研究了不可中断和可中断两个排序模型。对不可中断的情形，我们研究目标函数为极小化完工时间之和的在线排序问题。我们证明了此问题的任何在线算法的竞争比不可能小于1.5，同时我们给出了一个2＋min(s/s＋1，1/s)—competitive的在线算法。而对可中断的情形，我们研究目标函数为极小化加权完工时间之和的在线排序问题，我们给出了一个竞争比为2的在线算法。 第四章研究了同型机上带配送时间的在线排序问题，最优化准则是极小化所有工件最迟配送时间，即极小化Lmax。Vestjens[1]证明了此问题的任何在线算法的竞争比都不可能小于1.5。利用LDT(Largest Delivery Time)算法的思想，对机器数为2的情形，我们给出了此问题的一个在线算法，并证明了这个算法的竞争比为1.618。 第五章主要研究了两台同类同型机上的半在线排序问题，目标函数为极小化最大完工时间。两台同类机，假设它们的速度分别为1和s(s≥1)。工件是从一个列表中逐个释放的(over list)。我们首先研究了一个带buffer的半在线问题。对带buffer的两台同类平行机上的半在线排序问题，我们给出了任意确定性在线算法的竞争比的下界，同时当s≥√2时，我们给出了一个竞争比为s＋2/s＋1等的最好可能的半在线算法，当1≤s≤√2，我们给出了一个2s＋2/s＋2-competitive的半在线算法。接下来，我们研究了已知工件最大加工时间的半在线排序问题。当1≤s≤1＋√17/4时，Cai和Yang给出了已知工件最大加工时间的半在线排序问题的一个2s＋2/2s＋1-competitive的半在线算法，同时他们证明了当1≤s≤1.192时，此问题不存在竞争比小于2s＋2/2s＋1的半在线算法。当s≥3.777时，他们证明了LS算法就是最优的在线算法。我们给出了一个更简单的算法，同时证明了当1≤s≤1＋√17/4时，这个算法都是最优的半在线算法。 第六章研究了同型批处理机在线排序问题。一台批处理机一次可以把B个工件作为一批加工，批的加工时间由批中最长工件的加工时间决定。同一批中的工件具有相同的开工时间和完工时间。我们只考虑B=∞的情形。目标函数为极小化最大完工时间。我们给出了这个排序问题的下界1＋√m2＋4－m/2，同时我给出了一个最优的在线算法。