一類(lèi)平行機(jī)和批處理機(jī)組成的二階段柔性流水作業(yè)問(wèn)題.pdf

1、本文考慮m臺(tái)同型機(jī)(專(zhuān)用機(jī))與一臺(tái)批處理機(jī)組成的二階段柔性流水作業(yè)問(wèn)題.全文分六章： 第一章簡(jiǎn)述排序與復(fù)雜性理論，介紹FSMP(FlowShopwithMultipleProcessors)型問(wèn)題F2‖f和BI(BurnIn)型問(wèn)題1|BI|f的各自研究成果，進(jìn)而引出本文所研究的F2(·;·)|BI|Cmax型問(wèn)題、記號(hào)及其結(jié)論(參考1.3節(jié)的表1.1～表1.4)等. 第二章討論階段1由m臺(tái)同型機(jī)組成、階段2僅有一臺(tái)批處

2、理機(jī)M的極小化最大完工時(shí)間(Cmax)的流水作業(yè)問(wèn)題.其中，相應(yīng)工件Jj在階段1加工時(shí)間aj≡a(j∈N={1，2，…，n})的情況在max{O(nlogn)，O(nB)}時(shí)間內(nèi)獲最優(yōu)解；相應(yīng)工件Jj在階段2加工時(shí)間bj≡b(j∈N)的情況，除b≥an(a1≤a2≤…≤an)和B≤m＜n時(shí)可在O(nlogn)時(shí)間內(nèi)獲最優(yōu)解外，對(duì)其余情況及一般情況(aj(≠)a和bj(≠)b(j∈N))均指出或證得為(強(qiáng))NP-hard的，并給出各自對(duì)應(yīng)

3、情況的近似算法及其性能比分析(參考1.3節(jié)的表1.1). 第三章討論階段1由m臺(tái)專(zhuān)用機(jī)組成、階段2僅有一臺(tái)批處理機(jī)M并以Cmax為目標(biāo)函數(shù)的流水作業(yè)問(wèn)題.其中，相應(yīng)工件Jij在階段2加工時(shí)間bij≡b(i=1，2，…，m；j-1，2，…，ni)的情況在多項(xiàng)式時(shí)間內(nèi)獲最優(yōu)解；對(duì)一般情況(aij(≠)a和bij(≠)b(i=1，2,…,m；j=1，2，…，ni))給出其強(qiáng)NP-hard性、近似算法及其性能比分析(參考1.3節(jié)的表1.