高明中，唐秋華，錢新博

(1.武漢科技大學(xué)冶金裝備及其控制教育部重點實驗室，湖北 武漢，430081；2.武漢科技大學(xué)機械傳動與制造工程湖北省重點實驗室，湖北 武漢，430081)

生產(chǎn)調(diào)度和設(shè)備維護(hù)是相互關(guān)聯(lián)、相互影響的。持續(xù)生產(chǎn)一段時間后，機器可靠性會降低，可能發(fā)生機器故障，需要中斷生產(chǎn)進(jìn)行維護(hù)，使其恢復(fù)到工作狀態(tài)；或在設(shè)備發(fā)生故障前，根據(jù)“預(yù)防為主”“防患于未然”的原則，進(jìn)行有計劃的預(yù)防性維修。因此，在車間管理時必須綜合考慮生產(chǎn)調(diào)度、預(yù)防維護(hù)和故障維護(hù)，通過集成優(yōu)化來降低生產(chǎn)成本、延長設(shè)備壽命、提高產(chǎn)品質(zhì)量。更重要的是，在集成優(yōu)化過程中需要保證調(diào)度方案具有足夠的魯棒性，以促成生產(chǎn)組織與設(shè)備維護(hù)的無縫銜接。

生產(chǎn)調(diào)度與設(shè)備維護(hù)的集成優(yōu)化通常分成兩類：確定型和不確定型。確定型問題中，通過安排足量的預(yù)防維護(hù)來保證設(shè)備具備較高的可靠性，無需考慮隨機故障的發(fā)生。此方面研究目前已相對成熟，如Wang等[1]研究了兩階段混合流水車間的生產(chǎn)調(diào)度與預(yù)防維護(hù)集成優(yōu)化，可同時優(yōu)化制造周期和第一階段機器可用性。不確定型問題不僅需要考慮預(yù)防維護(hù)，更要考慮隨時可能發(fā)生的機器故障。Cassady等[2]和Cui等[3]以魯棒性為目標(biāo)，建立了設(shè)備故障函數(shù)服從Weibull分布時的單機調(diào)度魯棒集成優(yōu)化模型。Herroelen等[4]將魯棒性分為兩種：制造周期魯棒性和開始時間魯棒性，前者是指在隨機故障發(fā)生后調(diào)度目標(biāo)變動不大，后者是指在隨機故障產(chǎn)生后各操作的實際開始時間調(diào)整幅度不大。Xiong等[5]研究了存在隨機故障的柔性流水車間魯棒調(diào)度問題，以制造周期魯棒性和開始時間魯棒性為優(yōu)化目標(biāo)，提出兩種魯棒性指標(biāo)：一是考慮故障概率，二是考慮故障時間及位置。Paprocka[6]、Sajadi等[7]均研究了魯棒集成優(yōu)化問題，指出需在初始調(diào)度中插入閑置時間，以提高系統(tǒng)的魯棒性。Lu等[8]和Cui等[9]以制造周期魯棒性和開始時間魯棒性為目標(biāo)，使用遺傳算法優(yōu)化閑置時間。但是上述文獻(xiàn)均是針對小規(guī)模案例，未根據(jù)所研究問題的特點改進(jìn)算法。針對大規(guī)模生產(chǎn)調(diào)度問題的求解，需要制定新的算法，解決目前存在的計算時間長、算法收斂速度慢等問題。

為此，本文提出一種基于雙層循環(huán)的魯棒優(yōu)化算法，實現(xiàn)大規(guī)模案例下的置換流水車間生產(chǎn)調(diào)度與設(shè)備維護(hù)集成優(yōu)化。其中，特別針對插入性閑置時間的優(yōu)化問題，做出兩個改進(jìn)：①提出基于關(guān)鍵路徑的啟發(fā)式規(guī)則，以改善初始解的性能；②在傳統(tǒng)灰狼優(yōu)化算法的基礎(chǔ)上融入交叉算子，加強種群之間的信息交流。

1 問題描述及求解思路

本文所研究的問題描述如下：

(1)n個工件順次經(jīng)過m道工序，每道工序僅有一臺機器，且各工件在每臺機器上的加工順序相同。不考慮工件的加工準(zhǔn)備時間及機器的換型時間。

(2)預(yù)防維護(hù)只會在機器待機時執(zhí)行，執(zhí)行預(yù)防維護(hù)會使機器“恢復(fù)如新”，設(shè)備役齡清零。

(3)假定所發(fā)生故障均可被修復(fù)，且故障后立即執(zhí)行設(shè)備維護(hù)。因故障而中斷的操作可以繼續(xù)，不會造成額外的時間損失；故障維護(hù)采取最小維修規(guī)則，設(shè)備修復(fù)后壽命不變。

(5)以制造周期魯棒性和開始時間魯棒性的線性加權(quán)值最小化作為優(yōu)化目標(biāo)。

在置換流水車間生產(chǎn)調(diào)度與設(shè)備維護(hù)的集成優(yōu)化時，需要考慮多種生產(chǎn)情形：①正常工作，即置換流水車間內(nèi)工件能正常加工；②根據(jù)設(shè)備可用性、可靠性等的預(yù)測，在機器待機時決策執(zhí)行預(yù)防性維護(hù)；③設(shè)備故障后立即維護(hù)。當(dāng)三者集成時，生產(chǎn)過程就變成多種情形間的切換。

針對上述問題，本文提出如圖1所示的基于雙層循環(huán)的魯棒優(yōu)化方法。其中，外層循環(huán)調(diào)整加工序列，確定執(zhí)行設(shè)備預(yù)防維護(hù)的位置；在此基礎(chǔ)上，內(nèi)層循環(huán)優(yōu)化插入性閑置時間，實現(xiàn)調(diào)度方案的魯棒性。外層循環(huán)通過鄰域搜索改變初始加工序列，繼而改變預(yù)防維護(hù)位置矩陣；內(nèi)層循環(huán)包含兩部分：基于啟發(fā)式規(guī)則的閑置時間初始解生成以及基于改進(jìn)灰狼算法的閑置時間優(yōu)化。雙層循環(huán)不斷迭代，直至達(dá)到終止條件，得到魯棒性最優(yōu)的調(diào)度計劃。

圖1 基于雙層循環(huán)的車間調(diào)度、預(yù)防維護(hù)與故障維護(hù)魯棒集成優(yōu)化方法

2 基于關(guān)鍵路徑的啟發(fā)式規(guī)則設(shè)計

在求解大規(guī)模問題時，插入性閑置時間一般隨機產(chǎn)生，使得初始解性能和算法收斂性較差，需探索新的啟發(fā)式規(guī)則，以生成具有高性能的初始解?？紤]到閑置時間長度與加工序列、預(yù)防維護(hù)位置有強耦合關(guān)系，因此首先要找到關(guān)鍵路徑并推導(dǎo)出各任務(wù)的閑置時間范圍。

2.1 關(guān)鍵操作與關(guān)鍵路徑

圖2 關(guān)鍵路徑示意圖

路徑一：O1,1→O1,2→O2,2→O3,2，則

路徑二：O1,1→O2,1→O2,2→O3,2，則

路徑三：O1,1→O2,1→O3,1→O3,2，則

從而可以得到：

(1)

2.2 啟發(fā)式規(guī)則設(shè)計

(2)

(3)

(4)

規(guī)則：插入性閑置時間dk,j在區(qū)間(uk,j,value/number)內(nèi)進(jìn)行初始化，所得到的解是可行的。

3 基于改進(jìn)灰狼算法的閑置時間優(yōu)化

灰狼優(yōu)化算法是一種仿生群體智能算法，其模仿灰狼種群的社會領(lǐng)導(dǎo)層級機制和捕食行為，在每次迭代中選出最具競爭力的3只灰狼，領(lǐng)導(dǎo)其余個體包圍獵物，進(jìn)行捕食。考慮所研究問題的特殊性，在原有算法基礎(chǔ)上加入了交叉算子[10]，以實現(xiàn)種群間的信息交流。

3.1 個體表示及適應(yīng)度評價

初始種群中一半個體采用啟發(fā)式規(guī)則在(uk,j,value/number)范圍內(nèi)生成，剩余個體隨機生成。由于dk,j存在下界uk,j，為避免算法進(jìn)化和交叉過程中產(chǎn)生不可行解，轉(zhuǎn)換個體dk,j為Δdk,j，Δdk,j=dk,j-uk,j。

魯棒優(yōu)化一般是以調(diào)度計劃魯棒性作為優(yōu)化目標(biāo)。如式(5)所示，調(diào)度計劃魯棒性由制造周期魯棒性與開始時間魯棒性兩部分線性加權(quán)求和，其中ρ1與ρ2是權(quán)重系數(shù)，ρ1+ρ2=1。

minz=

(5)

由于制造周期魯棒性與最大完工時間有關(guān)，當(dāng)案例規(guī)模較大時，制造周期魯棒性的值遠(yuǎn)大于開始時間魯棒性的值。在相同的工件加工序列下，為突出魯棒優(yōu)化性能，對目標(biāo)函數(shù)進(jìn)行等價轉(zhuǎn)換，用插入性閑置時間d與推遲時長I展開目標(biāo)函數(shù)式(5)：

其中，ρ1Cn,m僅與權(quán)重系數(shù)、工件加工序列有關(guān)，與閑置時間dk,j無關(guān)。因此，采用式(6)作為適應(yīng)度評價函數(shù)：

(6)

3.2 控制參數(shù)C的確定

Rodriguez等[10]通過實驗驗證了灰狼算法中控制參數(shù)C(0

(7)

式中：T為算法運行時間；MaxIter為迭代終止條件，這里為算法最大運行時間。

3.3 進(jìn)化機制及交叉算子設(shè)計

進(jìn)化機制根據(jù)基本灰狼算法包圍獵物原理，通過適應(yīng)度函數(shù)選取最優(yōu)的3只灰狼α、β和δ，引導(dǎo)其余灰狼包圍獵物，實現(xiàn)位置更新。

基本灰狼算法中只有最佳的3只灰狼α、β、δ與其余灰狼存在信息交流，其余灰狼之間無信息交流。為了增強低等級狼群間的信息交流，改進(jìn)算法融入交叉算子?？紤]到個體Δdk,j是連續(xù)變量，采用線性重組的交叉方法。對于父代個體ch1和ch2，生成兩個取值范圍在[-0.25,1.25]的隨機數(shù)α1和α2，交叉生成的子代個體表示為：

off1=α1ch1+(1-α1)ch2,

off2=α2ch1+(1-α2)ch2。

4 魯棒集成優(yōu)化算法流程

首先，使用NEH(Nawaz-Enscore-Ham)規(guī)則獲得初始工件加工序列。其次，建立最大化可用性的預(yù)防維護(hù)周期模型，求解得到最佳預(yù)防維護(hù)周期。最后，使用雙層循環(huán)算法優(yōu)化調(diào)度計劃的魯棒性：內(nèi)循環(huán)是改進(jìn)灰狼算法，用于優(yōu)化閑置時間；外循環(huán)通過鄰域搜索確定最佳調(diào)度計劃。算法流程具體如下。

輸入:工件數(shù)(n),機器數(shù)(m),工件加工時長(p),故障維護(hù)平均時長(tr),預(yù)防維護(hù)平均時長(tp),機器失效函數(shù)參數(shù)(β和θ),種群規(guī)模(PS),交叉率輸出:最佳調(diào)度計劃步驟:1. 使用NEH規(guī)則獲得初始工件加工序列;依據(jù)機器可用性,確定各機器預(yù)防維護(hù)位置。2. while鄰域搜索不滿足終止迭代次數(shù)do3. 使用啟發(fā)式規(guī)則初始種群,計算所有個體適應(yīng)度值,并確定領(lǐng)頭狼α、β和δ。4. while灰狼優(yōu)化不滿足終止條件do5. fori=1toPSdo6. 更新參數(shù)C,根據(jù)領(lǐng)頭狼更新當(dāng)前狼的位置,計算適應(yīng)度值。7. endfor8. 交叉生成新灰狼個體,計算新灰狼個體的適應(yīng)度值。9. 更新領(lǐng)頭狼α、β和δ。10. endwhile//終止改進(jìn)灰狼算法11. 記錄初始加工序列下的最佳調(diào)度計劃魯棒性以及無閑置時間的最大完工時間C0。12. 將初始加工序列下調(diào)度計劃魯棒性z0賦值給zbest,構(gòu)建初始加工序列X0的鄰域N(X0)。13. 隨機選取鄰域N(X0)中的序列X1,并記錄序列X1下的最大完工時間C1。14. whileC1>101%×C015. 重新選取鄰域N(X0)中的序列X1,并重新計算C1。16. endwhile17. 將序列X1下最優(yōu)調(diào)度計劃魯棒性賦值給z1,比較zbest與z1,若z1

5 實驗及結(jié)果分析

參照文獻(xiàn)[11]，實驗參數(shù)設(shè)置如下：工件數(shù)n={20,50,100,200}，機器數(shù)m={5,10,15,20}，存在16種n與m的組合方式；在任意組合方式下，工件加工時間pi,j服從均勻分布U[15,29]；Weibull分布的參數(shù)服從一定區(qū)間的均勻分布，θ=U[80,100]，β=U[2,4]；機器維護(hù)時長tr=U[5,10]，tp=U[15,20]。同時，目標(biāo)函數(shù)中權(quán)重系數(shù)取ρ1=ρ2=0.5，利用相對百分誤差(RPD)評估實驗結(jié)果，RPD的具體計算公式為

(8)

式中：CTsol是算法求得的當(dāng)前解；Bestsol是當(dāng)前案例所有算法求得的最優(yōu)解。

5.1 參數(shù)校驗

由于參數(shù)對算法性能有很大影響，本文對相關(guān)參數(shù)都進(jìn)行了校驗。改進(jìn)灰狼算法的參數(shù)水平是：種群規(guī)模{20,30,50}，交叉率{0.7,0.8,0.9}。通過全因素方差實驗，每種參數(shù)組合運行5次，以5組數(shù)據(jù)中平均RPD作為評價標(biāo)準(zhǔn)。改進(jìn)灰狼算法最佳參數(shù)組合是：種群規(guī)模為30、交叉率為0.8。限于篇幅，其余對比算法的詳細(xì)參數(shù)校驗分析暫不列出。

5.2 算法性能分析

在本文雙層循環(huán)算法中，核心是旨在優(yōu)化閑置時間的改進(jìn)灰狼算法。為驗證啟發(fā)式規(guī)則及交叉算子的有效性，將基本灰狼算法、只融合交叉算子的灰狼算法、只融合啟發(fā)式規(guī)則的灰狼算法、融合兩處改進(jìn)的灰狼算法進(jìn)行對比。驗證實驗中采用了16個案例，每組案例運行10次，評價標(biāo)準(zhǔn)是RPD最小值和RPD平均值。圖3所示為幾種算法的RPD值95%置信區(qū)間。

(a)RPD最小值的95%置信區(qū)間

由圖3可見，基本灰狼算法在16個案例下的平均相對誤差達(dá)到58.6%，融合啟發(fā)式規(guī)則的灰狼算法的平均相對誤差有31.9%，融合交叉算子的灰狼算法的平均相對誤差有12.9%，而經(jīng)過兩處改進(jìn)的灰狼算法的平均相對誤差僅有11.2%。實驗結(jié)果表明，本文算法改進(jìn)是有效的。

為驗證改進(jìn)灰狼算法的優(yōu)越性，選取文獻(xiàn)[8-9]中使用的遺傳算法進(jìn)行對比實驗。同時，根據(jù)連續(xù)性優(yōu)化問題的特點，另選取擅于優(yōu)化連續(xù)性問題的粒子群算法以及近年來被廣泛使用的人工蜂群算法進(jìn)行對比實驗。實驗結(jié)果見表1，其中min是使用算法運行10次的最小適應(yīng)度值，avg是10次運行的平均適應(yīng)度值。由表1可見，改進(jìn)灰狼算法性能最優(yōu)。

表1 各算法的測試結(jié)果對比

算法魯棒性的測試結(jié)果用RPD值表征，如圖4所示。在相同的運行時間內(nèi)，粒子群算法、人工蜂群算法、遺傳算法的平均相對誤差分別為262.8%、87.9%、40.8%，改進(jìn)灰狼算法的結(jié)果最好，平均相對誤差僅有6.9%，遠(yuǎn)遠(yuǎn)小于其余3種群智能算法，進(jìn)一步驗證了該算法的優(yōu)越性。

(a)RPD最小值的95%置信區(qū)間

5.3 靈敏度分析

本文的優(yōu)化目標(biāo)是系統(tǒng)魯棒性，由制造周期魯棒性和開始時間魯棒性兩部分線性加權(quán)求得。權(quán)重系數(shù)的取值將直接影響最終優(yōu)化結(jié)果，因此需對權(quán)重系數(shù)進(jìn)行靈敏度分析。選取一個案例：m=5、n=20，設(shè)定制造周期魯棒性的系數(shù)ρ1從0.9逐漸減小至0.1，而ρ2=1-ρ1。隨著權(quán)重系數(shù)ρ1的變化，制造周期和開始時間的魯棒性變化情況如圖5所示。

圖5 制造周期和開始時間的魯棒性隨權(quán)重系數(shù)的變化

由圖5可以看出，隨著ρ1的減小，優(yōu)化目標(biāo)中制造周期魯棒性所占比重逐漸減小，開始時間魯棒性所占比重逐漸增大。在此過程中呈現(xiàn)的變動趨勢是：制造周期魯棒性變動幅度逐步減小，而開始時間魯棒性變動幅度逐步擴(kuò)大。若決策者更重視開始時間魯棒性，須設(shè)置ρ1<0.5，以制造周期魯棒性的降低為代價來換取開始時間魯棒性的提升。

5.4 魯棒性分析

以案例1為對象進(jìn)行系統(tǒng)魯棒性分析，運用蒙特卡洛方法模擬故障場景。圖6(a)是不含閑置時間的調(diào)度計劃甘特圖，圖6(b)是含閑置時間的調(diào)度計劃甘特圖，圖6(c)和圖6(d)是兩種故障維護(hù)情形下的調(diào)度計劃甘特圖。圖中綠色區(qū)域表示工件加工區(qū)間，紅色區(qū)域表示預(yù)防維護(hù)區(qū)間，藍(lán)色區(qū)域表示故障維護(hù)區(qū)間。

比較圖6(a)和圖6(b)，不含閑置時間調(diào)度計劃的最大完工時間Cmax=631，含閑置時間調(diào)度計劃的Cmax=656.98，可見閑置時間的插入確實在一定程度上延長了制造周期，松弛了生產(chǎn)節(jié)奏。從圖6(c)和圖6(d)可得，在故障維護(hù)情形下Cmax分別等于711.59和693.85，與不含閑置時間的調(diào)度計劃相比Cmax分別延長12.78%和9.96%，與含閑置時間的調(diào)度計劃相比Cmax僅分別延長8.31%和5.61%。這表明閑置時間的插入吸收了故障維護(hù)對工件加工的影響，保證更多的工件能在原計劃開始時間開始，而所有工件盡可能在原定制造周期內(nèi)完成加工，即調(diào)度方案更具魯棒性。

(a)不含閑置時間的調(diào)度計劃

6 結(jié)語

本文提出基于雙層循環(huán)的車間調(diào)度與設(shè)備維護(hù)魯棒集成優(yōu)化算法，內(nèi)層循環(huán)使用融合啟發(fā)式規(guī)則的灰狼算法優(yōu)化閑置時間，外層循環(huán)通過鄰域搜索優(yōu)化加工序列。針對內(nèi)層循環(huán)的閑置時間設(shè)置，提出基于關(guān)鍵路徑的啟發(fā)式規(guī)則，以提高初始解性能；提出融入交叉算子的混合灰狼算法，以加強低等級狼群的信息交流。實驗結(jié)果證明了啟發(fā)式規(guī)則的有效性以及改進(jìn)算法的優(yōu)越性。在未來的研究中，可嘗試將本文方法推廣應(yīng)用到柔性流水車間調(diào)度，也可以繼續(xù)挖掘工件加工序列對系統(tǒng)調(diào)度魯棒性的影響。