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

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

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

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