本文主要研究了两台平行机(同型机和同类机)在线以及半在线排序问题,其中工件按照一个给定列表中的顺序依次到达,且目标都是最小化时间表长。对于在线问题,工件的信息是随着排序过程依次释放的,排序者只有在位于某个工件前的所有工件均被安排好后才知道该工件的相关信息,且工件一旦被安排好后就不可以再改变。半在线问题与在线问题的不同之处在于排序者在排序之前已经知道某些工件的部分信息。　　 第2章研究了两台同型机上的一个半在线问题,其中所有工件的加工时间有界且预先知道最大工件的加工时间Pmax,也就是说我们不仅知道所有工件的加工时间在区间[p,tp]内((P>0,t≥1)),同时也知道至少存在一个加时间为tp的工件。我们证明了此问题的下界为max{min{t+1/2,4t+4/3t+4｝,min{2t/t+1,4/3}},并对4/3≤t<2设计了竞争比为max{4t+4/3t+3,2t/t+1｝的最优算法A1。　　 第3章研究了已知最大加工时间的两台同类机半在线排序问题,其中两台机器的速率比为s(s≥1)。在所有工件到达前,我们预先知道最大工件的加工时间pmax。对1≤s≤√2,我们设计了一个竞争比为max{2s+2/2s+1,s}的最优半在线算法H1。对s≥√2,我们设计了一个竞争比为min{s+1/s,max{s+2/s+1,3s+2/2s+2))的半在线算法H2。对1.559≤s≤2.293和s≥3+√17/2,我们分别证明了此问题的下界为s+2/s+1和s+1/s,因此算法H2在1.559≤s≤2和s≥3+√17/2是最优的,同时我们也在2≤s≤3+√17/2改进了问题的下界。　　 第4章考虑了所有工件加工时间是有界的两台同类机半在线排序问题。假设所有工件的加工时间在区间[p,tp]内,但可能没有加工时间为p和tp的工件到达。我们证明了一些下界,并研究了LS算法的竞争比。它存2s+√5s2-2s-3/s+1≤t≤2/s时的竞争比为1+t/2；设N∈{1,2,3,…},它在s≥N+√N2+4N/2且t≥s/N时的竞争比为s+1/s；在N≤s≤N+1且1≤t≤min{1/s-N,s/N}时的竞争比为t；在N+√N2+4S/2≤s≤N+1且max{3(s2-1)/3(s+1)N-s,1/s-N｝≤t≤s/N时的竞争比为1+Nt/s；设α=1+s-s2/s2,它在t≥1+s/sα2时的竞争比为2s+1/s+1。LS算法在上述关于s和t的区间都达到了最优。进一步,我们对1.325≤s≤1+√2/2且s