董 君,毛 強
(河南工學院 管理學院,河南 新鄉 453003)
可重入混合流水車間(Re-entrant hybrid flow shop, RHFS)常見于半導體晶圓、印刷電路板、薄膜晶體管液晶顯示器等高精電子制造產業中,是典型的NP-hard問題[1]。本文提出的分布式可重入車間綠色共享制造與預維護聯合優化問題(Joint optimization of green shared manufacturing and preventive maintenance for distributed re-entrant workshop, GSMPM-DR)在RHFS基礎上進行擴展,難度更大,復雜度更高,同樣屬于NP-hard問題。
高精電子制造企業的設備一般較為昂貴,由于其對環境參數要求很高,所以工廠一經建立,設備基本全年全天不停歇運轉。長時間的持續生產,機器會產生退化和遺忘效應[2]。因此,很有必要對設備進行預維護操作,以避免延長加工時間,并相應地減少機器能耗和碳排放,從而實現企業向綠色制造模式轉變。本文研究中優化目標為最小化最大完工時間Cmax、最小化總碳排放TCT和最小化預維護成本Tcost。Cmax為最后一個工件的完工時間;TCT為綠色指標,本文僅考慮和工件調度相關的設備工作和空閑狀態電能消耗產生的碳排放以及使用潤滑油產生的碳排放。
本文提出的IHMMVO算法在單目標多元宇宙優化(Multi-verse optimizer, MVO)[3]算法的基礎上加入了快速非支配排序、擁擠距離計算、精英選擇策略去解決多目標優化問題。此外,主要的改進策略有同步調度維護策略、初始化種群融合策略、宇宙個體位置信息擾動策略和NSGA-II變異策略,IHMMVO算法流程如圖2所示。
為了擴大種群的多樣性,本文將兩個子種群融合后篩選出一個更優的初始種群。兩個子種群具有相同的規模N,其中子種群pop1個體的位置變量隨機生成,子種群pop2個體的位置變量是在pop1個體位置的基礎上進行差分進化變異操作后生成的。依次隨機從pop1個體中選取3個個體,進行變異形成pop2中個體的位置變量。將子種群pop1和pop2合并并進行擁擠距離的計算和快速非支配排序,得到非劣解集組成的初始外部檔案Archive。將整個種群分成兩個規模相同的子種群popx和popy。兩個子種群執行不同的進化策略,對popx中的宇宙個體執行萊維飛行擾動變異操作,對popy中的宇宙個體執行NSGA-II操作,以擴大種群多樣性和搜索范圍。
圖1 GSMPM-DR問題示意圖
圖2 IHMMVO算法流程圖
本文引入萊維飛行擾動策略,對迭代前期宇宙個體的位置信息進行擾動,以增加種群多樣性,并得到新的宇宙子代種群C1。個體位置信息變化公式為[4]:
(1)
w=wmax-(wmax-wmin×(l/L)2
(2)
其中:w是加權學習因子;Levy是Lévy飛行步長。
策略1 對每一個工廠內工件加工順序重新進行隨機排列,以擴大整個種群個體的多樣性。
策略2 根據隨機數rand取值,若rand<1/3,則針對Cmax指標進行操作;若0 為了驗證IHMMVO算法求解GSMPM-DR的有效性,實驗階段選取MMVO、IMSSA[5]和MOPSO算法[6]進行比較。實驗階段,為了使三個目標函數值處于相同的數量級,對其進行min-max歸一化處理。 因為公開的文獻中沒有求解GSMPM-DR問題的數據集,本文參考文獻[7]中的數據集設置方法,生成測試算例。數據集中包括2個工廠數標準(2/3)、3個工件數標準(20/60/100)、2個加工層次標準(U[2,3]/U[3,4])、3個工位數標準(U[2,4]/U[5,7]/U[8,10])、2個機器數標準([工件數/10]+1或+2)。共有2×3×2×3×2=72個參數組合。對于每個參數組合隨機生成10個測試算例,共包含72*10=720個測試算例。例如20l1g1-m代表工件數為20,加工層次為U[2,3],工位數為U[2,4],機器數隨機為3或4的測試算例。數據集中涉及的參數及其取值參見文獻[4]。 因篇幅有限,本文僅列出了工廠數為3時IHMMVO和MMVO、IMSSA、MOPSO四個算法之間的實驗結果對比,如表1所示??梢钥闯?針對SP指標,IHMMVO算法的占優率為66%,MMVO、IMSSA和MOPSO算法的分別為11%、6%和17%;針對GD和IGD指標,IHMMVO算法的占優率均為100%。表1還展示了威爾科克森(Wilcoxon)符號秩檢驗結果,分別用‘+’、‘=’和‘++’符號進行表示,對比不同算法之間是否存在顯著性差異?!?’代表IHMMVO算法顯著優于對比算法,‘=’代表兩種對比算法之間沒有明顯區別,‘++’代表IHMMVO顯著劣于對比算法。針對所有優化指標,相比其余算法,IHMMVO對于大部分測試算例均能夠實現顯著占優,說明其獲得的Pareto解集均勻性、多樣性以及收斂性優勢明顯,同時該結論通過圖3的三個評價指標箱線圖進一步得到了驗證。 表1 IHMMVO、MMVO、IMSSA、MOPSO算法實驗結果對比 圖3 評價指標箱線圖 (1) 圖4分別展示了2*60*[2,3]*[8,10](2個工廠、60個工件、加工層次在[2,3]中隨機選取、加工工位在[8,10]之間隨機選取)和3*20*[2,3]*[5,7]算例各個算法獲得的Pareto前沿對比圖??梢悦黠@看出,IHMMVO算法獲得的Pareto前沿位于其余三種對比算法獲得的Pareto前沿的下方,更加接近真實的Pareto前沿。 (a) 2*60*[2,3]*[8,10] (b) 3*20*[2,3]*[5,7]圖4 各個算法獲得的Pareto前沿對比圖 (2) 根據Hewlett Packard公司晶圓生產技術開發實驗室半導體生產線構建的HP24模型,大部分參數均來自實際設備采集的數據[8]193-194。該模型共包含24個設備群組,共27臺設備。圖5為HP24模型產品加工流程,其具體參數參見文獻[8]。因HP24模型只考慮一種產品的加工,所有產品加工時間、PM時間、設備維修間隔時間均相同,無需考慮各個工件的加工順序優化問題,因此本文在工廠數為2、工件數為20的情況下,考慮不同的工件分配方案對優化目標的影響,實驗結果如表2所示。結果顯示,針對HP24模型,對于該測試算例,當每個工廠各分配10個工件時,獲得的makespan、總PM成本和總碳排放均能夠達到最小值,且三個優化指標的變化趨勢基本相同。 圖5 HP24模型產品加工流程 表2 不同工件分配方案對比 本文針對半導體晶圓分布式綠色共享制造與預維護聯合優化問題,考慮了多工廠分布式制造模式和設備預維護的聯合優化,能夠提高生產效率、緩解機器退化和遺忘效應導致的加工時間延長、生產能耗增加的現象。通過仿真實驗驗證了所提出的IHMMVO算法能夠跳出局部最優值,對于求解該問題具有可行性和競爭力。算法獲得的Pareto前沿解集可以幫助決策者根據實際運營情況,從中選擇一個較優的調度方案。此外通過對半導體生產線HP24模型的實驗,驗證了在半導體晶圓制造企業應用分布式制造模式對于優化生產效益、經濟利益和綠色指標的有效性,證明了本文的實際應用價值和借鑒意義。3 仿真實驗
3.1 測試算例和參數設置
3.2 算法性能測試和結果分析
3.3 案例分析
4 結論