董 君,毛 強(qiáng)

(河南工學(xué)院 管理學(xué)院,河南 新鄉(xiāng) 453003)

0 引言

可重入混合流水車間(Re-entrant hybrid flow shop, RHFS)常見于半導(dǎo)體晶圓、印刷電路板、薄膜晶體管液晶顯示器等高精電子制造產(chǎn)業(yè)中,是典型的NP-hard問題[1]。本文提出的分布式可重入車間綠色共享制造與預(yù)維護(hù)聯(lián)合優(yōu)化問題(Joint optimization of green shared manufacturing and preventive maintenance for distributed re-entrant workshop, GSMPM-DR)在RHFS基礎(chǔ)上進(jìn)行擴(kuò)展,難度更大,復(fù)雜度更高,同樣屬于NP-hard問題。

1 GSMPM-DR問題描述

高精電子制造企業(yè)的設(shè)備一般較為昂貴,由于其對(duì)環(huán)境參數(shù)要求很高,所以工廠一經(jīng)建立,設(shè)備基本全年全天不停歇運(yùn)轉(zhuǎn)。長時(shí)間的持續(xù)生產(chǎn),機(jī)器會(huì)產(chǎn)生退化和遺忘效應(yīng)[2]。因此,很有必要對(duì)設(shè)備進(jìn)行預(yù)維護(hù)操作,以避免延長加工時(shí)間,并相應(yīng)地減少機(jī)器能耗和碳排放,從而實(shí)現(xiàn)企業(yè)向綠色制造模式轉(zhuǎn)變。本文研究中優(yōu)化目標(biāo)為最小化最大完工時(shí)間Cmax、最小化總碳排放TCT和最小化預(yù)維護(hù)成本Tcost。Cmax為最后一個(gè)工件的完工時(shí)間;TCT為綠色指標(biāo),本文僅考慮和工件調(diào)度相關(guān)的設(shè)備工作和空閑狀態(tài)電能消耗產(chǎn)生的碳排放以及使用潤滑油產(chǎn)生的碳排放。

2 改進(jìn)的IHMMVO算法

2.1 IHMMVO算法流程

本文提出的IHMMVO算法在單目標(biāo)多元宇宙優(yōu)化(Multi-verse optimizer, MVO)[3]算法的基礎(chǔ)上加入了快速非支配排序、擁擠距離計(jì)算、精英選擇策略去解決多目標(biāo)優(yōu)化問題。此外,主要的改進(jìn)策略有同步調(diào)度維護(hù)策略、初始化種群融合策略、宇宙?zhèn)€體位置信息擾動(dòng)策略和NSGA-II變異策略,IHMMVO算法流程如圖2所示。

2.2 初始化子種群融合策略

為了擴(kuò)大種群的多樣性,本文將兩個(gè)子種群融合后篩選出一個(gè)更優(yōu)的初始種群。兩個(gè)子種群具有相同的規(guī)模N,其中子種群pop1個(gè)體的位置變量隨機(jī)生成,子種群pop2個(gè)體的位置變量是在pop1個(gè)體位置的基礎(chǔ)上進(jìn)行差分進(jìn)化變異操作后生成的。依次隨機(jī)從pop1個(gè)體中選取3個(gè)個(gè)體,進(jìn)行變異形成pop2中個(gè)體的位置變量。將子種群pop1和pop2合并并進(jìn)行擁擠距離的計(jì)算和快速非支配排序,得到非劣解集組成的初始外部檔案Archive。將整個(gè)種群分成兩個(gè)規(guī)模相同的子種群popx和popy。兩個(gè)子種群執(zhí)行不同的進(jìn)化策略,對(duì)popx中的宇宙?zhèn)€體執(zhí)行萊維飛行擾動(dòng)變異操作,對(duì)popy中的宇宙?zhèn)€體執(zhí)行NSGA-II操作,以擴(kuò)大種群多樣性和搜索范圍。

圖1 GSMPM-DR問題示意圖

圖2 IHMMVO算法流程圖

2.3 宇宙?zhèn)€體位置信息擾動(dòng)策略

本文引入萊維飛行擾動(dòng)策略,對(duì)迭代前期宇宙?zhèn)€體的位置信息進(jìn)行擾動(dòng),以增加種群多樣性,并得到新的宇宙子代種群C1。個(gè)體位置信息變化公式為[4]:

(1)

w=wmax-(wmax-wmin×(l/L)2

(2)

其中:w是加權(quán)學(xué)習(xí)因子;Levy是Lévy飛行步長。

2.4 NSGA-II變異策略

策略1 對(duì)每一個(gè)工廠內(nèi)工件加工順序重新進(jìn)行隨機(jī)排列,以擴(kuò)大整個(gè)種群個(gè)體的多樣性。

策略2 根據(jù)隨機(jī)數(shù)rand取值,若rand<1/3,則針對(duì)Cmax指標(biāo)進(jìn)行操作;若0

3 仿真實(shí)驗(yàn)

為了驗(yàn)證IHMMVO算法求解GSMPM-DR的有效性,實(shí)驗(yàn)階段選取MMVO、IMSSA[5]和MOPSO算法[6]進(jìn)行比較。實(shí)驗(yàn)階段,為了使三個(gè)目標(biāo)函數(shù)值處于相同的數(shù)量級(jí),對(duì)其進(jìn)行min-max歸一化處理。

3.1 測(cè)試算例和參數(shù)設(shè)置

因?yàn)楣_的文獻(xiàn)中沒有求解GSMPM-DR問題的數(shù)據(jù)集,本文參考文獻(xiàn)[7]中的數(shù)據(jù)集設(shè)置方法,生成測(cè)試算例。數(shù)據(jù)集中包括2個(gè)工廠數(shù)標(biāo)準(zhǔn)(2/3)、3個(gè)工件數(shù)標(biāo)準(zhǔn)(20/60/100)、2個(gè)加工層次標(biāo)準(zhǔn)(U[2,3]/U[3,4])、3個(gè)工位數(shù)標(biāo)準(zhǔn)(U[2,4]/U[5,7]/U[8,10])、2個(gè)機(jī)器數(shù)標(biāo)準(zhǔn)([工件數(shù)/10]+1或+2)。共有2×3×2×3×2=72個(gè)參數(shù)組合。對(duì)于每個(gè)參數(shù)組合隨機(jī)生成10個(gè)測(cè)試算例,共包含72*10=720個(gè)測(cè)試算例。例如20l1g1-m代表工件數(shù)為20,加工層次為U[2,3],工位數(shù)為U[2,4],機(jī)器數(shù)隨機(jī)為3或4的測(cè)試算例。數(shù)據(jù)集中涉及的參數(shù)及其取值參見文獻(xiàn)[4]。

3.2 算法性能測(cè)試和結(jié)果分析

因篇幅有限,本文僅列出了工廠數(shù)為3時(shí)IHMMVO和MMVO、IMSSA、MOPSO四個(gè)算法之間的實(shí)驗(yàn)結(jié)果對(duì)比,如表1所示。可以看出,針對(duì)SP指標(biāo),IHMMVO算法的占優(yōu)率為66%,MMVO、IMSSA和MOPSO算法的分別為11%、6%和17%;針對(duì)GD和IGD指標(biāo),IHMMVO算法的占優(yōu)率均為100%。表1還展示了威爾科克森(Wilcoxon)符號(hào)秩檢驗(yàn)結(jié)果,分別用‘+’、‘=’和‘++’符號(hào)進(jìn)行表示,對(duì)比不同算法之間是否存在顯著性差異?！?’代表IHMMVO算法顯著優(yōu)于對(duì)比算法,‘=’代表兩種對(duì)比算法之間沒有明顯區(qū)別，‘++’代表IHMMVO顯著劣于對(duì)比算法。針對(duì)所有優(yōu)化指標(biāo),相比其余算法,IHMMVO對(duì)于大部分測(cè)試算例均能夠?qū)崿F(xiàn)顯著占優(yōu),說明其獲得的Pareto解集均勻性、多樣性以及收斂性優(yōu)勢(shì)明顯,同時(shí)該結(jié)論通過圖3的三個(gè)評(píng)價(jià)指標(biāo)箱線圖進(jìn)一步得到了驗(yàn)證。

表1 IHMMVO、MMVO、IMSSA、MOPSO算法實(shí)驗(yàn)結(jié)果對(duì)比

圖3 評(píng)價(jià)指標(biāo)箱線圖

3.3 案例分析

(1) 圖4分別展示了2*60*[2,3]*[8,10](2個(gè)工廠、60個(gè)工件、加工層次在[2,3]中隨機(jī)選取、加工工位在[8,10]之間隨機(jī)選取)和3*20*[2,3]*[5,7]算例各個(gè)算法獲得的Pareto前沿對(duì)比圖?？梢悦黠@看出,IHMMVO算法獲得的Pareto前沿位于其余三種對(duì)比算法獲得的Pareto前沿的下方,更加接近真實(shí)的Pareto前沿。

(a) 2*60*[2,3]*[8,10] (b) 3*20*[2,3]*[5,7]圖4 各個(gè)算法獲得的Pareto前沿對(duì)比圖

(2) 根據(jù)Hewlett Packard公司晶圓生產(chǎn)技術(shù)開發(fā)實(shí)驗(yàn)室半導(dǎo)體生產(chǎn)線構(gòu)建的HP24模型,大部分參數(shù)均來自實(shí)際設(shè)備采集的數(shù)據(jù)[8]193-194。該模型共包含24個(gè)設(shè)備群組,共27臺(tái)設(shè)備。圖5為HP24模型產(chǎn)品加工流程,其具體參數(shù)參見文獻(xiàn)[8]。因HP24模型只考慮一種產(chǎn)品的加工,所有產(chǎn)品加工時(shí)間、PM時(shí)間、設(shè)備維修間隔時(shí)間均相同,無需考慮各個(gè)工件的加工順序優(yōu)化問題,因此本文在工廠數(shù)為2、工件數(shù)為20的情況下,考慮不同的工件分配方案對(duì)優(yōu)化目標(biāo)的影響,實(shí)驗(yàn)結(jié)果如表2所示。結(jié)果顯示,針對(duì)HP24模型,對(duì)于該測(cè)試算例,當(dāng)每個(gè)工廠各分配10個(gè)工件時(shí),獲得的makespan、總PM成本和總碳排放均能夠達(dá)到最小值,且三個(gè)優(yōu)化指標(biāo)的變化趨勢(shì)基本相同。

圖5 HP24模型產(chǎn)品加工流程

表2 不同工件分配方案對(duì)比

4 結(jié)論

本文針對(duì)半導(dǎo)體晶圓分布式綠色共享制造與預(yù)維護(hù)聯(lián)合優(yōu)化問題,考慮了多工廠分布式制造模式和設(shè)備預(yù)維護(hù)的聯(lián)合優(yōu)化,能夠提高生產(chǎn)效率、緩解機(jī)器退化和遺忘效應(yīng)導(dǎo)致的加工時(shí)間延長、生產(chǎn)能耗增加的現(xiàn)象。通過仿真實(shí)驗(yàn)驗(yàn)證了所提出的IHMMVO算法能夠跳出局部最優(yōu)值,對(duì)于求解該問題具有可行性和競爭力。算法獲得的Pareto前沿解集可以幫助決策者根據(jù)實(shí)際運(yùn)營情況,從中選擇一個(gè)較優(yōu)的調(diào)度方案。此外通過對(duì)半導(dǎo)體生產(chǎn)線HP24模型的實(shí)驗(yàn),驗(yàn)證了在半導(dǎo)體晶圓制造企業(yè)應(yīng)用分布式制造模式對(duì)于優(yōu)化生產(chǎn)效益、經(jīng)濟(jì)利益和綠色指標(biāo)的有效性,證明了本文的實(shí)際應(yīng)用價(jià)值和借鑒意義。