分別由同型機和批處理機組成的二階段流水作業(yè)問題.pdf

1、本文討論一類兩階段流水作業(yè)問題，其中第一階段由m臺同型機組成，第二階段為一臺批處理機，目標函數(shù)是最小化各工件完工時間之和。按照工件在同型機和批處理機上有相同或任意加工時間，分為4個問題討論。其中： 1.工件在同型機和批處理機上分別有相同加工時間(第二章) (1)運用Ahmadi et al.(1992)解一單機問題時的動態(tài)規(guī)劃(DP)至本流水作業(yè)問題； (2)針對本問題給出一新算法H2.1，在一些特殊情況下H2.

2、1優(yōu)于(DP)。該部分內(nèi)容已被上海大學(xué)學(xué)報(自然版)錄用。 2.工件在同型機上有任意加工時間、在批處理機上有相同加工時間(第三章) (1)證明了此問題是NP-hard的； (2)給出一個優(yōu)勢序，在此優(yōu)勢序的基礎(chǔ)上得出同型機為1臺時的子問題是多項式可解的； (3)給出一個一般算法并對性能比進行理論分析； (4)給出一計算量為O(n3)的2-近似算法。 該部分內(nèi)容已被雜志Asia-Pacifi

3、c Journal of Operational Research錄用。 3.工件在同型機上有相同加工時間，但在批處理機上具有任意加工時間(第四章) (1)指出此問題是強NP—hard的； (2)給出三個優(yōu)勢序，在優(yōu)勢序的基礎(chǔ)上給出三個近似算法，對前二個算法作了性能比分析，對第三個算法的性能比作了數(shù)值試驗。 該部分內(nèi)容已投雜志Optimization。 4.工件在同型機和批處理機上都具有任意加工時