本文主要分为两个部分，我们对一类一致平行机上工件有非递减和任意到达时间两种情况下的在线算法分别进行了性能比分析。　　第一部分:Cho和Sahni(1980)首次提出了m台一致平行机的在线算法问题，对于Qm/online/Cmax(m≥2)，他们证明出LS算法的最坏性能比不会大于1+√m-1/√2。当si=1(i=1，2，…，…，m-1)并且sm=s＞1时，他们证明了LS算法的最坏性能比1+m-1/m+s-1min{s，2}≤3-4/m+1并且当s=2(m≥3)时，能够取到3-4/m+1。　　对于Qm/online/Cmax，Aspnes et al.(1997)第一个设计了一个比LS算法更好的算法，他们提出新算法在确定的情况下最坏性能比能达到8，在随机情况下能达到5.436。随后，Berman et al.(2000)将上述两个性能比分别降低到了5.828和4.311。　　本文在Berman的基础上，加入了到达时间非递减即r1≤r2≤…≤rn这一约束，与Berman的模型中到达时间为零这一模型相比，本章的模型更为复杂，分析过程要考虑的因素也更多，从而得到该模型在LS算法下其最坏性能比为R(m，U)=sup L CUmax(L)/COPT/max(L)＜5.8284　　第二部分:在第一部分的基础上，进一步放松到达时间的条件，工件具有任意到达时间，与之前的模型相比，本模型更为复杂，分析的过程要素也更多，并证明了对于任意满足条件的工件序列L，在U算法的最坏性能比为R(m，U)=sup L CUmax(L)/COPTmax(L)＜7.4641　　工件具有任意到达时间，是他模型的一个推广，应用的领域也越发普及。固然性能比数值要比Berman原始模型大。这一部分内容将在第三章展开详细证明。　　文章的第一章为绪论，主要是对组合优化问题、近似算法以及排序问题的研究进展等基本问题进行简要价绍说明。　　文章的第四章是对整篇文章的一个总结，并指出了未来可能的研究方向。