本文讨论一类三阶段流水作业的问题,第一阶段由m台同型机组成,第二阶段和第三阶段均为1台批处理机,目标函数为最小加工全程??maxC.全文分六章:第一章简述排序及其相关的基本概念、本文研究的问题和结论.第二章讨论工件在同型机和两台批处理机上工件的加工时间分别相同情况下,利用已有的动态规划构造了一般情况的??1O n B算法和几类特殊情况的O?n?算法.第三章讨论工件在同型机上具有任意加工时间但在两台批处理机上的加工时间分别相同的情况.其中:复杂性给出除4类情况?2类O?nlogn?2可解,类open?外,其余情况均为NP-hard的结论;对一般情况给出max?O?nlogn?,???1O n B的近似算法H3.1且性能比H 3.1R?2,对13种特殊情况分别给出O?nlogn?的2个最优算法和性能比不超过?2?1 m?的4个近似算法.第四章讨论工件在同型机和第一台批处理机上的加工时间分别相同但在第二台批处理机上具有任意加工时间的情况下,先分3类情况进行讨论(前2类情况为多项式时间可解,第3类情况给出一多项式时间近似算法并进行性能比和数值模拟的分析),然后给出本问题性能比小于等于2的多项式时间近似算法.第五章讨论工件在同型机和第二台批处理机上的加工时间分别相同但在第一台批处理机上具有任意加工时间的情况下,给出两个多项式时间的近似算法并进行性能比和数值模拟的分析.第六章总结了本文所得的结论.