本文主要研究了两台平行机在线以及半在线排序调度问题，其中工件或者订单按照一个给定列表的顺序依次到达，我们要将列表中的工件或者订单按照某种规则安排到这两台平行机上使得所有工件或所有订单的最大完工时间最小，即我们的目标是最小化时间表长。　　 本文第二章考虑了四个关于两台同型机的已知订单部分信息的在线排序调度问题。第一个问题考虑已知每个订单的总加工时间都为T的问题，对订单数b≥2，我们得到了问题的下界为4/3，并设计了一个最优算法A1;对b≥3，我们得到了下界为5/4，并设计了一个最优算法A2。第二个问题考虑已知b个订单按照总加工时间非增序到达的问题，当b≥2时，得到了问题的下界为3/2，因此LS算法是最优的。第三个问题考虑已知每个订单中的最大工件加工时间且都相同的问题，当b≥2时，我们获得了问题的下界为5/4，并设计了一个最优算法A3。第四个问题考虑已知b个订单按照每个订单中最大工件加工时间非增序到达的问题，当b≥2时，我们获得了问题的下界为4/3，并设计了一个最优算法A4。　　 第三章考虑了三个已知组合信息的两台同型机半在线排序调度问题。第一个问题考虑已知工件按加工时间的非增序到达且所有工件的加工时间在区间[1，t]((t≥1))内的问题，我们给出了问题的下界为R=max N=1,2,3,…{min{4N+3/4N+2,Nt+N+1/2N+1}},并证明了LS算法在1≤t＜3/2时是最优的。第二个问题考虑已知最大工件的加工时间t且所有工件的加工时间在区间[1，t]((t≥1))内的问题，我们给出了问题的下界为{t+1/2,1≤t＜4/3,4t+4/3t+4,4/3≤t≤√2，2t/t+1，√2≤t≤2，4/3， t≥2。然后又对4/3≤t＜2设计了一个最优算法PIJS。第三个问题考虑已知最优解值和最大工件的加工时间pmax的问题，我们得到了问题的下界为6/5，并设计了一个竞争比也为6/5的最优算法OM。　　 第四章考虑了三个与缓冲区有关的两台同型机半在线排序调度问题。第一个问题考虑已知最大工件尺寸且带一个长度为k（k≥1）的缓冲区的问题，我们给出了问题的下界为6/5，同时设计了一个竞争比为5/4的算法。第二个问题考虑已知工件按照加工时间非增序到达且带一个长度为1的缓冲区的两台同型机半在线排序调度问题，我们得到了问题的下界为7/6。第三个问题考虑已知工件加工时间有界且带一个长度为1的缓冲区的两台同型机半在线排序调度问题，我们给出了问题的一个下界max{min{4/3，t+2/6}，min{5/4,t+1/4},min{7/6,t+2/3}}，同时对1≤t≤3/2设计了一个竞争比为max{t+2/3，8/7}的算法BB，且该算法在10/7≤t≤3/2是最优的。　　 第五章考虑了所有工件加工时间是有界的两台同类机半在线排序调度问题，，目标同样是最小化时间表长。我们首先对问题证明了一些下界，并研究了LS算法的竞争比。首先我们在对任意s和t得到LS算法的竞争比为min{2s+1/s+1，s+1/s，t}，结合我们给出的下界可知LS算法在s≥N+√N2+4N/2且t≥s/N时是最优的，竞争比为s+1/s;在N≤s≤N+1且1≤t≤min{1/s-N，s/N}时是最优的，竞争比为t;在1≤s≤1+√5/2且t≥1+s/sα2时是最优的，竞争比为2s+1/s+1}。然后我们又对LS算法进行深入分析，得到LS算法在max{2s(N+1)-2N-1/2N+1-2sN,(N+1)(s+1)/(N+1)(s+1)-1}≤t≤2/s和max{2(s+1)(2-s)N2+(3-2s)N+1-s)/2Ns(N+1)(s+1)-2N-1,sN-N+s/N+1-sN}≤t≤min{2s(N+1)-2N-1/2N+1-2sN,2N+1/2Ns}是最优的。进一步，我们证明了其在s≤N+1且t≥3(s2-1)/3(s+1)N-s时的竞争比为1+Nt/s，并在N+√N2+4N/2≤s≤N+1且max{3(s2+1)/3(s+1)N-s，1/s-N}≤t≤s/N时是最优的。最后我们设计了两个改进的算法，在1.325≤ s≤1+√5/2且s＜t≤s2-1/1+s-s2设计了一个竞争比为s的最优算法B1，并在1≤s≤1+√17/4且max{2s-1，-s+√9s2+8s/2s}≤t≤2/s给出了竞争比为1+t/2的最优算法B2。同时算法B2在s≥1.206且s≤t≤min{2s-1，2(s2-1)}/1+s-s2时的竞争比为s，也达到了最优。