本篇论文主要是研究半在线模型下的算法设计以及算法性能比分析。论文主要分为四章内容,第一章为绪论部分,首先介绍了组合优化问题的定义以及其研究意义,然后就组合优化问题中典型的排序问题进行背景、分类、研究现状等多方面叙述,最后引入近似算法的概念和基本思想并介绍Pm和本文我们所构造的S形算法。第四章是对整篇文章做了一个总结,并提出了今后研究工作可能的方向。主体内容将分别在第二章和第三章中展开详细证明。第二章:我们构造了S形算法,证明了当m=2时,对于任意的工件序列L={J1,J2,…,Jn},加工时间非递增(p1 ≥ p2≥…≥ pn),工件具有相似的加工时长pj ∈[1,r](1 ≤ r ≤ 2)时,其最坏性能比为:而在Wei-Ping Liu,Jeffrey B.Sidney,Andre van Vliet 1996年([20])给出的算法P(2)中,其最坏性能比为CmaxP2/CmaxOPT(L≤4/3,后证得即使加入工件具有相似的加工时长pj∈[1,r](r≥1)这一约束后该算法的最坏性能比仍不变,始终有supLCmaxP2/CmaxOPT(L)=4/3但是在S形算法中我们通过限定工件加工时长得到了更好的结果。第三章:本章证明了对于任意的工件序列L={J1,J2,...,Jn},工件满足加工时长非递增,到达时间不都为零且非递减(即p1 ≥ p2 ≥...≥pn,r1≤r2≤...≤rn)时,Pm算法的最坏性能比为本章主要是对文献[11]做了相关的修正,并且优化了该算法的最坏性比能,从而得到了更加精确的结果。