本文主要讨论了同型机上加工时间相似的工件调度问题。规定在性能相同的m台机器M1,Ma,…,Mm上加工n个独立的工件J1,J2,…,Jn,且每件工件只能在一台机器上加工一次。为了方便本文的研究,以下不考虑工件到达时间的情况,并令每个工件以加工时间非递增的顺序排列,用p表示Ji的加工时间,则p1≥p2≥…≥pn。本文是在Wei-Ping Liu,Jeffrey B.Sidney,Andre van Vliet在1996([1])年设计Pm算法基础上进行改进得到的一个新算法,新算法规定了每个到达的工件按照序号排列依次被送到某一台特定的机器上加工,每台机器只能同一时间加工一个工件,本文给这种算法命名为PmD算法。将最后一个工件的完工时间记为总完工时间,这个调度问题的目标函数为极小化总完工时间。本文得到且证明了机器台数m=2或m=3台时的最坏性能比优于Pm算法的结果。本文由四章构成:第一章为绪论,主要介绍了组合优化问题,着重叙述了组合优化问题下的一个经典问题——排序问题,详细说明了排序问题的背景和分类。以及最优化问题的多种求解方法。由于本论文是在Pm算法下改进的PmD算法,在后文也详细说明了Pm算法和PmD算法。第二、三章分别证明了PmD算法下,两、三台机的最坏性能比。PmD算法是在Pm算法的基础上改进得到的算法,Pm算法已经证得m2,m=3的情况下,最坏性能比的上界为4/3,7/5本文在控制任意工件加工时长1 ≤pj≤r(r≥1)的条件下,我们得到的最坏性能比明显优于Pm算法。结语是对本文的一个总结,限于本文篇幅,并没有对PmD算法在任意台机器的情况下得到一个最坏性能比,但本文最后对可进行的工作也提出了一些建议。