周鑫文,陳 豪,張劍銘,劉 文

(1.福州大學(xué)先進(jìn)制造學(xué)院,晉江 362251;2.中國科學(xué)院海西研究院泉州裝備制造研究中心,泉州 362000)

0 引言

近年來,柔性作業(yè)車間調(diào)度問題(flexible job-shop scheduling problem,FJSP)已成為制造業(yè)企業(yè)主要面臨的問題之一。在實(shí)際的生產(chǎn)過程中,經(jīng)常發(fā)生諸如機(jī)器故障[1]、訂單加急[2]等動態(tài)事件,使生產(chǎn)環(huán)境越加復(fù)雜,因此延伸出動態(tài)柔性作業(yè)車間調(diào)度問題(dynamic flexible job-shop scheduling problem,DFJSP)。受動態(tài)事件影響,未加工工序需要調(diào)整加工設(shè)備,進(jìn)一步造成相應(yīng)的原料需求變更,而過度的備料計(jì)劃調(diào)整會進(jìn)一步降低生產(chǎn)效率[3]。因此,引起許多研究學(xué)者在物料準(zhǔn)備方面做研究,CHAKRABORTTY等[4]考慮資源中斷的因素,提出了多種的啟發(fā)式算法來求解建立的混合整數(shù)規(guī)劃模型。刁林倩[5]在機(jī)器故障下考慮物料搬運(yùn)問題,設(shè)計(jì)改進(jìn)的文化基因算法解決調(diào)度問題。涂海寧等[6]提出一種改進(jìn)的蟻群算法解決生產(chǎn)車間中物料配送不及時、效率低等問題。

為解決動態(tài)柔性作業(yè)車間調(diào)度問題,國內(nèi)外的許多研究學(xué)者提出了多種解決方法。AHMADI等[7]采用基于NSGA-Ⅱ的右移重調(diào)度與完全重調(diào)度,但只考慮了對最大完成時間與穩(wěn)定性的優(yōu)化。朱傳軍等[8]建立了基于調(diào)度穩(wěn)健性的動態(tài)調(diào)度模型,并提出差分變頻鄰域算法,雖然提高了魯棒性與穩(wěn)定性,但實(shí)時性差。ZHANG等[9]提出一種基于動態(tài)博弈的雙層調(diào)度方法,采用逆向推導(dǎo)法求解子博弈精煉納什均衡,能夠?qū)崟r解決多種動態(tài)問題,卻缺乏考慮魯棒性與穩(wěn)定性。衛(wèi)少鵬等[10]針對質(zhì)檢擾動問題,采用改進(jìn)的頭腦風(fēng)暴算法求解,卻沒有考慮調(diào)度方案的實(shí)時性。因此,HE等[11]采用路線更改與右移重調(diào)度方式實(shí)現(xiàn)機(jī)器故障下的實(shí)時動態(tài)調(diào)度,提高了調(diào)度方案的穩(wěn)定性與魯棒性。尤一琛等[12]將動態(tài)調(diào)度問題看作完全信息下的動態(tài)博弈,提出一種混合納什均衡策略有效平衡魯棒性與穩(wěn)定性,并具有較好的實(shí)時性。

綜上所述,為兼顧動態(tài)調(diào)度方案的實(shí)時性、魯棒性和穩(wěn)定性,針對備料計(jì)劃調(diào)整問題,以最小化最大完成時間為預(yù)調(diào)度目標(biāo),當(dāng)機(jī)器故障時快速建立帶有備料計(jì)劃關(guān)聯(lián)調(diào)整的柔性作業(yè)車間動態(tài)調(diào)度模型,提出改進(jìn)的受影響工序選擇方法,并設(shè)計(jì)多階段的合作博弈策略,用于快速尋找最優(yōu)的動態(tài)調(diào)度方案。

1 問題描述

考慮備料計(jì)劃關(guān)聯(lián)調(diào)整的DFJSP依然采用同F(xiàn)JSP一致的描述:車間共有m臺{M1,M2,…,Mm}機(jī)器用于工作,包含n個待加工工件{J1,J2,…,Jn},每個工件有j道工序,每道工序可以在不同機(jī)器上加工,加工時間根據(jù)機(jī)器的性能決定。引入機(jī)器故障作為動態(tài)擾動因素,在工件生產(chǎn)過程的隨機(jī)時刻機(jī)器發(fā)生故障,且恢復(fù)時間可預(yù)測,此時車間動態(tài)調(diào)度任務(wù)為:在機(jī)器故障下進(jìn)行合理的動態(tài)調(diào)度,以滿足動態(tài)調(diào)度目標(biāo)。

針對DFJSP,進(jìn)行如下規(guī)范化約束:

(1)初始零時刻所有工件皆可進(jìn)行加工;

(2)每臺機(jī)器同一時刻只能加工一個工件;

(3)每個工件的加工都按照嚴(yán)格的加工工藝次序,不能搶斷;

(4)每個工件的工序同一時刻只能在一個機(jī)器上加工;

(5)不同工件優(yōu)先級相同;

(6)不同工件的各工序之間沒有先后次序之分;

(7)工件一旦開始在機(jī)器上加工,便不能中斷;

(8)故障機(jī)器上的在生產(chǎn)工件立刻停止加工,且不可轉(zhuǎn)移,等待故障修復(fù)成功后繼續(xù)加工;

(9)除故障機(jī)器外,其余機(jī)器上正在加工的工件仍在原分配的機(jī)器上進(jìn)行加工,直至完成。

對DFJSP變量及含義設(shè)置如表1所示。

表1 DFJSP變量及含義設(shè)置表

柔性作業(yè)車間的預(yù)調(diào)度目標(biāo)為最小化最大完成時間,指所有工件加工完成的時間最小:

(1)

預(yù)調(diào)度方案采用IPSO算法[13]獲得,這里不再復(fù)述,僅引入余弦自適應(yīng)調(diào)整因子來提升pf在迭代前期的全局搜索能力,增強(qiáng)后期的收斂能力,pf為IPSO算法中的自適應(yīng)調(diào)整概率,用于優(yōu)化機(jī)器選擇部分,其表達(dá)式為:

(2)

式中:Iter為總迭代次數(shù),k為當(dāng)前迭代次數(shù),pfmin與pfmax分別為自適應(yīng)調(diào)整概率的最小值與最大值。

對于動態(tài)事件處理,研究機(jī)器故障下的DFJSP,考慮到備料計(jì)劃調(diào)整將會大幅度惡化生產(chǎn)計(jì)劃的進(jìn)展,故將備料計(jì)劃調(diào)整次數(shù)定義為穩(wěn)定性f3,而魯棒性作為衡量預(yù)調(diào)度受影響后的性能指標(biāo),這里指最大完成時間偏差f2。

(3)

(4)

(5)

根據(jù)動態(tài)調(diào)度特性,通過采用加權(quán)和的方式可以兼顧魯棒性與穩(wěn)定性,生成式(6)評價指標(biāo)Y:

Y=r1f2+r2f3

(6)

式中:r1、r2分別為魯棒性與穩(wěn)定性的懲罰因子,r1+r2=1,且0

2 柔性作業(yè)車間動態(tài)調(diào)度方法

2.1 改進(jìn)的受影響工序選擇方法

當(dāng)機(jī)器發(fā)生故障時,傳統(tǒng)的路線更改方式挑選的受影響工序?yàn)樵诠收蠒r間范圍內(nèi)覆蓋的工序,雖然避免了本機(jī)器后續(xù)工序的調(diào)整,保證了一定的穩(wěn)定性,但往往不能很好的兼顧魯棒性。因此為兼顧魯棒性與穩(wěn)定性,提出一種改進(jìn)的受影響工序選擇方法(an improved method of selection of the affected process,IMSAP),對影響弱的工序,可將其直接影響轉(zhuǎn)移到該機(jī)器上的后續(xù)的工序中,該方法的步驟如下:

步驟1:工序后移。故障機(jī)器上的后續(xù)工序后移:

(7)

(8)

(9)

式中:tcko、tck(o+1)分別為預(yù)調(diào)度中在機(jī)器k上正在加工的與后一個工序的結(jié)束時間,tsk(o+1)為預(yù)調(diào)度中機(jī)器k上安排的下一個工序的開始時間,PTko為對應(yīng)工序在機(jī)器k上的加工時長,Tbk為機(jī)器故障預(yù)計(jì)恢復(fù)時間,t′為故障發(fā)生后工序后移的狀態(tài)。

步驟2:工序分類。步驟1結(jié)束后,將故障后續(xù)工序分為3類:受影響弱、受影響強(qiáng)、可調(diào)節(jié),分別對應(yīng)等級1、2、3。

①受影響弱的工序指,工序后移并不直接造成下一道工序的開始時間延后:

(10)

②受影響強(qiáng)的工序指,工序后移直接造成下一道工序的開始時間延后:

(11)

③可調(diào)節(jié)的工序指,工序?yàn)樽詈笠坏拦ば蚧蛴乙浦卣{(diào)度后的關(guān)鍵路徑上的工序:

O={Oij|j=hi∪Oij?Ocpfr}

(12)

步驟3:工序挑選。采用窗戶位置更新的方式挑選工序。只有受影響弱的工序才能逃脫挑選,否則表示消除故障影響的有效工序。預(yù)調(diào)度工件工序的STijk在窗戶位置thk內(nèi),如果至少存在一個受影響弱的工序則不可選中該類工序,選擇其它類別的工序,然后將窗戶位置更新再進(jìn)行下一個工序判斷,否則可選中。當(dāng)thk內(nèi)不再含有受影響弱的工序,則結(jié)束窗戶位置更新,僅需要判斷后續(xù)工序是否屬于可調(diào)節(jié)工序,如果是則選中,否則不選中,直至后續(xù)工序遍歷結(jié)束。具體窗戶位置更新方式如下:

①故障發(fā)生出現(xiàn)在這兩種情況:空轉(zhuǎn)機(jī)器與在生產(chǎn)工序機(jī)器,那么初始的窗戶位置t0k:

(13)

②第h次的窗戶經(jīng)過更新后的位置thk:

(14)

(15)

式中:「thk?表示thk的上界,υ表示窗戶包含的最后一個工序的序號。

例如1個3×3算例,假設(shè)工序O21在tbk為8 min時機(jī)器M1出現(xiàn)故障,故障修復(fù)時間預(yù)計(jì)為7 min,采用上述提出的影響轉(zhuǎn)移方法,最終選中的工序?yàn)镺32、O13。具體的演示如圖1～圖3和表2、表3所示。

圖1 預(yù)調(diào)度 圖2 工序后移

圖3 右移重調(diào)度關(guān)鍵路徑

表2 采用窗戶位置更新方式選中工序

表3 待窗戶位置更新結(jié)束后選中工序

2.2 基于多階段的合作博弈策略

機(jī)器故障會直接導(dǎo)致后續(xù)工序的開始時間延遲,由于工序加工與機(jī)器分配存在一定的約束關(guān)系,因此可以將重調(diào)度問題看成在完全信息下的動態(tài)博弈問題[12]。將動態(tài)博弈問題分為多階段的靜態(tài)合作博弈問題,并在此基礎(chǔ)上設(shè)計(jì)基于多階段的合作博弈策略(multi-stage cooperative game strategy,MCGS)。

在生產(chǎn)過程中,當(dāng)機(jī)器發(fā)生故障時,通過采用IMSAP可以獲得被挑選的工序集Ou。在動態(tài)調(diào)度中進(jìn)行分階段的調(diào)度,在每一個階段,從Ou中隨機(jī)選取g(g≥2)道工序作為待加工工序,并放入待調(diào)度任務(wù)池(task pool,TP)中,再對TP中的工序進(jìn)行重調(diào)度,見圖4。每一個階段中至少存在一個待加工的工序需要進(jìn)行排序,將TP中的工序作為博弈玩家集Pt,可用機(jī)器集作為決策池St,玩家進(jìn)行策略選擇后的所有效用集記為Ut,因此構(gòu)建基于多階段的柔性作業(yè)車間動態(tài)調(diào)度模型:

圖4 分階段選取工序

Gt={Pt;St;Ut}t=1,2,…,L

(16)

式中:L為博弈階段次數(shù)。

在每一階段的合作博弈中,各個博弈玩家之間相互協(xié)調(diào)以達(dá)到全體效果的最優(yōu)值:

(17)

引入條件篩選轉(zhuǎn)移工序的可用機(jī)器集,獲取St:

(18)

式中:k為預(yù)調(diào)度中工序Oij的機(jī)器,k*為該階段選取的機(jī)器。對每個階段的工序只有滿足式(18)的情況下才有可轉(zhuǎn)移的機(jī)器集St。

在t階段,從TP中取出待加工的工序,然后從St選取可轉(zhuǎn)移機(jī)器,對所有可能組合選擇最優(yōu)min(Y),當(dāng)出現(xiàn)多個最優(yōu)組合時,選擇最小σ2的組合,σ2的計(jì)算方式如下:

(19)

(20)

對每一階段選擇最優(yōu)決策后,將決策結(jié)果作為下一階段的初始基礎(chǔ),并指導(dǎo)下一次博弈。在最后一次合作博弈中,不考慮σ2,直接選取最優(yōu)值即可。

2.3 IMSAP-MCGS重調(diào)度流程

IMSAP-MCGS重調(diào)度流程如圖5所示,步驟如下:

圖5 重調(diào)度流程圖

步驟1:讀取故障機(jī)器信息;

步驟2:通過故障機(jī)器信息,采用IMSAP獲得待調(diào)整工序集Ou;

步驟3:將Ou分階段從中隨機(jī)選取g個工序給TP;

步驟4:判斷第t階段TP中是否僅剩一個工序,如果是則跳躍到步驟7,否則進(jìn)入下一個步驟;

步驟5:將每個工序作為玩家,在決策池中選取機(jī)器,采用MCGS求解最優(yōu)組合;

步驟6:判斷所有工序是否都被選擇,是則跳躍到步驟8,否則t=t+1,回到步驟4;

步驟7:采用枚舉法選擇最優(yōu)機(jī)器;

步驟8:輸出最終多階段合作博弈最優(yōu)解。

3 實(shí)驗(yàn)結(jié)果與分析

本文仿真實(shí)驗(yàn)的硬件環(huán)境處理器為Intel(R) Core(TM) i7-11700 CPU @ 2.50 GHz,RAM 32 GB;使用Windows 11操作系統(tǒng),運(yùn)行平臺為PyCharm。

3.1 實(shí)驗(yàn)設(shè)置與內(nèi)容

在整個調(diào)度策略中設(shè)置參數(shù)如下:IPSO算法[13]群體規(guī)模為100,迭代次數(shù)為100,ω為0.15,C1、C2分別為0.5與0.7,最小調(diào)整閾值因子pfmin為0.2,最大調(diào)整閾值因子pfmax為0.8,懲罰因子r1、r2分別設(shè)置為0.6、0.4。

本文首先使用Brandimarte的標(biāo)準(zhǔn)算例MK1,10×6實(shí)例進(jìn)行仿真測試,該算例中含有10個工件,每個工件含有5～6個工序,共有6臺機(jī)器可供使用。然后對MK1～MK10經(jīng)典調(diào)度案例集進(jìn)行仿真驗(yàn)證,將IMSAP-MCGS重調(diào)度與右移重調(diào)度、完全重調(diào)度和傳統(tǒng)路線更改-MCGS重調(diào)度的仿真結(jié)果進(jìn)行了對比分析。

3.2 實(shí)驗(yàn)仿真分析

本文采用引入余弦自適應(yīng)調(diào)整因子的IPSO算法[13]得到預(yù)調(diào)度方案如圖6所示,其最大完成時間為42 min。當(dāng)機(jī)器3在時刻為15 min時發(fā)生故障,預(yù)測機(jī)器恢復(fù)時間為20 min,分別采用IMSAP-MCGS重調(diào)度、右移重調(diào)度和完全重調(diào)度進(jìn)行調(diào)度,仿真實(shí)驗(yàn)得到如圖7～圖9所示的調(diào)度方案及表4對比結(jié)果。從中可以看出當(dāng)機(jī)器發(fā)生故障時,采用IMSAP-MCGS重調(diào)度得到的評價指標(biāo)Y優(yōu)于右移重調(diào)度與完全重調(diào)度,其魯棒性指標(biāo)小于完全重調(diào)度和右移重調(diào)度,降低了機(jī)器故障對生產(chǎn)目標(biāo)的影響,而且運(yùn)行時間也更快于完全重調(diào)度,保證了柔性車間遇到機(jī)器故障時能夠進(jìn)行及時有效的反應(yīng)。在穩(wěn)定性方面,雖然右移重調(diào)度穩(wěn)定性指標(biāo)最好,但是魯棒性差,而IMSAP-MCGS重調(diào)度對兩者的平衡更好。因此,IMSAP-MCGS重調(diào)度能夠有效平衡魯棒性與穩(wěn)定性,能夠及時有效地解決柔性作業(yè)車間下因機(jī)器故障造成備料計(jì)劃調(diào)整的問題。

圖6 預(yù)調(diào)度甘特圖

圖7 IMSAP-MCGS重調(diào)度甘特圖

圖8 右移重調(diào)度甘特圖

圖9 完全重調(diào)度甘特圖

表4 仿真結(jié)果對比

表5記錄MK1～MK10采用多種重調(diào)度方式后的最終結(jié)果。從表中可以看出右移重調(diào)度的穩(wěn)定性最好,運(yùn)行時間也最短,但是魯棒性卻很差。完全重調(diào)度的魯棒性最好,但是穩(wěn)定性很差、運(yùn)行時間很長。在案例中,IMSAP-MCGS重調(diào)度的評價指標(biāo)相比于右移重調(diào)度、完全重調(diào)度和傳統(tǒng)路線更改-MCGS重調(diào)度會更有優(yōu)勢,而且IMSAP-MCGS重調(diào)度的穩(wěn)定性指標(biāo)2[14]也同樣更有優(yōu)勢,同時運(yùn)行時間遠(yuǎn)遠(yuǎn)小于完全重調(diào)度。綜上所述,本文提出的IMSAP-MCGS重調(diào)度在針對備料計(jì)劃調(diào)整問題下?lián)碛懈玫男阅?在機(jī)器故障發(fā)生時不僅能夠及時有效地處理動態(tài)事件,還能合理減輕備料計(jì)劃調(diào)整壓力,具有較好的魯棒性與穩(wěn)定性。

表5 仿真結(jié)果對比

4 結(jié)論

本文研究在機(jī)器故障下,針對生產(chǎn)車間備料計(jì)劃調(diào)整問題,提出一種改進(jìn)的受影響工序選擇方法,并設(shè)計(jì)多階段的合作博弈調(diào)度策略。首先,采用引入余弦自適應(yīng)調(diào)整因子的IPSO算法產(chǎn)生預(yù)調(diào)度方案;其次,利用機(jī)器故障信息采用改進(jìn)的受影響工序選擇方法獲得工序集;然后,設(shè)計(jì)多階段的合作博弈策略,在每一個階段通過合作博弈的方式選取階段性的最優(yōu)策略,最終得到動態(tài)調(diào)度方案;最后,通過實(shí)驗(yàn)結(jié)果對比分析,驗(yàn)證了針對機(jī)器故障下的備料計(jì)劃調(diào)整問題,IMSAP-MCGS重調(diào)度不僅具有較好的魯棒性和穩(wěn)定性,而且對機(jī)器故障的處理具有實(shí)時性。

本文僅考慮了機(jī)器故障動態(tài)事件,對于其他動態(tài)事件下的備料計(jì)劃調(diào)整問題還需進(jìn)一步研究。