本文主要分为两部分内容，分别对两类半在线模型的算法性能比进行了分析。　　第一部分:He and Zhang在1999([12])年提出了一个半在线的排序模型:对任意的工件序列L={J1，J2,…，Jn}，工件具有相似的加工时长pj∈[1，r](r≥1）。将这些工件安排在两台平行机上。得到对任意满足该模型的实例L在LS算法下的最坏性能比为R(2,LS,r)={1+r/21≤r≤23/2r≥2。　　本文在其工件具有相似的加工时长pj∈[1，r](r≥1)的基础上，加入了到达时间非递减即r1≤r2≤…≤rn这一约束，与([12])的到达时间为零这一模型相比，本章的模型更为复杂，分析过程要考虑的因素也更多，从而得到该模型在LS算法下其最坏性能比为R(2，LS，r)={k+3/k+2k+2/k+1≤r＜1+k+1/k(k+2),k∈Z+kr+1/k+11+k+1/k(k+2)≤ r＜k+1/k,k∈Z+3/2 r≥2这是一个紧界，并且LS算法是解决此模型的最好的近似算法。这一部分内容将在第二章展开详细证明。　　第二部分:Wei-Ping Liu，Jeffrey B.Sidney，Andre van Vliet在1996([24])年给出了一个模型:工件到达时间都为零，且加工时长非递增。并给出了解决这一模型的算法Pm算法(在本文中暂称为Pm算法，与([24])中的称呼保持一致）且证明了对任意满足该模型的实例L在Pm算法下的性能比为R(m，Pm)=sup L CPm max(L)/COPT max(L)≤1+m-1/m+[m/2]。　　本文在其模型的基础上，增加了一个约束条件，即当工件的到达时间不都为零且满足非递减（即r1≤r2≤…≤rn）。并证明了对于任意满足条件的工件序列L，在Pm算法的最坏性能比为R(m，Pm)=sup L CPm max(L)/COPT max(L)≤2+m-1/m+[m/2]虽然单看性能比数值比之前要大，但是本章的模型是([24])的一个推广，模型更为复杂，应用的范围也更加广泛。这一部分内容将在第三章展开详细证明。　　第一章介绍了组合优化问题、近似算法以及排序问题的研究进展。　　第四章对整篇文章做了一个总结，并指出了未来的研究方向。