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

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

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

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