论文部分内容阅读
本文讨论一类两阶段流水作业问题，其中第一阶段由m台同型机组成，第二阶段为一台批处理机，目标函数是最小化各工件完工时间之和。按照工件在同型机和批处理机上有相同或任意加工时间，分为4个问题讨论。其中：
1.工件在同型机和批处理机上分别有相同加工时间(第二章)
(1)运用Ahmadi et al.(1992)解一单机问题时的动态规划(DP)至本流水作业问题；
(2)针对本问题给出一新算法H2.1，在一些特殊情况下H2.1优于(DP)。该部分内容已被上海大学学报(自然版)录用。
2.工件在同型机上有任意加工时间、在批处理机上有相同加工时间(第三章)
(1)证明了此问题是NP-hard的；
(2)给出一个优势序，在此优势序的基础上得出同型机为1台时的子问题是多项式可解的；
(3)给出一个一般算法并对性能比进行理论分析；
(4)给出一计算量为O(n3)的2-近似算法。
该部分内容已被杂志Asia-Pacific Journal of Operational Research录用。
3.工件在同型机上有相同加工时间，但在批处理机上具有任意加工时间(第四章)
(1)指出此问题是强NP—hard的；
(2)给出三个优势序，在优势序的基础上给出三个近似算法，对前二个算法作了性能比分析，对第三个算法的性能比作了数值试验。
该部分内容已投杂志Optimization。
4.工件在同型机和批处理机上都具有任意加工时间(第五章)
(1)指出此问题是强NP—hard的；
(2)给出了一近似算法并对性能比作了数值试验。
该部分内容也被杂志Asia-Pacific Journal of Operational Research录用。