论文部分内容阅读
本文考虑m台同型机(专用机)与一台批处理机组成的二阶段柔性流水作业问题.全文分六章：
第一章简述排序与复杂性理论，介绍FSMP(FlowShopwithMultipleProcessors)型问题F2‖f和BI(BurnIn)型问题1|BI|f的各自研究成果，进而引出本文所研究的F2(·;·)|BI|Cmax型问题、记号及其结论(参考1.3节的表1.1～表1.4)等.
第二章讨论阶段1由m台同型机组成、阶段2仅有一台批处理机M的极小化最大完工时间(Cmax)的流水作业问题.其中，相应工件Jj在阶段1加工时间aj≡a(j∈N={1，2，…，n})的情况在max{O(nlogn)，O(nB)}时间内获最优解；相应工件Jj在阶段2加工时间bj≡b(j∈N)的情况，除b≥an(a1≤a2≤…≤an)和B≤m＜n时可在O(nlogn)时间内获最优解外，对其余情况及一般情况(aj(≠)a和bj(≠)b(j∈N))均指出或证得为(强)NP-hard的，并给出各自对应情况的近似算法及其性能比分析(参考1.3节的表1.1).
第三章讨论阶段1由m台专用机组成、阶段2仅有一台批处理机M并以Cmax为目标函数的流水作业问题.其中，相应工件Jij在阶段2加工时间bij≡b(i=1，2，…，m；j-1，2，…，ni)的情况在多项式时间内获最优解；对一般情况(aij(≠)a和bij(≠)b(i=1，2,…,m；j=1，2，…，ni))给出其强NP-hard性、近似算法及其性能比分析(参考1.3节的表1.2).
第四(五)章讨论第二(三)章的对称情况.即：原第二(三)章阶段1的m台同型机(专用机)改为一台批处理机M，而阶段2的一台批处理机M改为m台同型机(专用机)，其余假设同第二(三)章(参考1.3节的表1.3和表1.4).
第六章在总结的基础上指出拟进一步可讨论研究的内容.