吳正佳 朱穎穎,2 龔 穩(wěn) 吳縣洋
(1.三峽大學(xué) 水電機(jī)械設(shè)備設(shè)計(jì)與維護(hù)湖北省重點(diǎn)實(shí)驗(yàn)室, 湖北 宜昌443002;2.三峽大學(xué) 機(jī)械與動(dòng)力學(xué)院,湖北 宜昌 443002)
近年來,許多學(xué)者針對(duì)不同擾動(dòng)因子(機(jī)器擾動(dòng)、訂單擾動(dòng)、原材料短缺等)的機(jī)加工車間生產(chǎn)調(diào)度問題做了大量研究工作.比如,劉明周[1]等提出在重調(diào)度優(yōu)化集內(nèi)按規(guī)則選取待加工工件,采用主動(dòng)和被動(dòng)觸發(fā)式重調(diào)度驅(qū)動(dòng)規(guī)則響應(yīng)各種擾動(dòng).朱傳軍[2]等針對(duì)動(dòng)態(tài)事件特點(diǎn),采用工件到達(dá)發(fā)生器和機(jī)器故障預(yù)維護(hù)發(fā)生器模擬動(dòng)態(tài)事件.劉樂[3]針對(duì)開放式車間中的急件到達(dá)干擾,基于匹配式調(diào)度策略探索擾后實(shí)施重調(diào)度的具體方法.有文獻(xiàn)[4-5]針對(duì)機(jī)器故障這一類動(dòng)態(tài)調(diào)度問題,提出插入空閑時(shí)間、工件右移調(diào)度和變路徑調(diào)度方法來提高調(diào)度方案的穩(wěn)定性和魯棒性.也有文獻(xiàn)[6-7]考慮生產(chǎn)過程中訂單不確定、加工時(shí)間不確定等因素,建立魯棒調(diào)度模型并求解.但由于實(shí)際生產(chǎn)過程的復(fù)雜性,擾動(dòng)因子的多樣性和不確定性,上述方法對(duì)擾動(dòng)的處理缺乏靈活性和針對(duì)性,能處理的擾動(dòng)事件單一,研究成果很難符合生產(chǎn)實(shí)際.實(shí)現(xiàn)對(duì)各類擾動(dòng)的有效處理,探究擾動(dòng)實(shí)質(zhì)和擾動(dòng)下生產(chǎn)調(diào)度重回穩(wěn)健狀態(tài)的機(jī)制成為車間作業(yè)調(diào)度問題研究的瓶頸.
貝葉斯網(wǎng)絡(luò)為解決這類問題提供了思路.本文首先構(gòu)建了生產(chǎn)和擾動(dòng)要素的貝葉斯網(wǎng)絡(luò)模型,利用貝葉斯網(wǎng)絡(luò)的決策機(jī)制來分析和處理各類擾動(dòng)事件,實(shí)現(xiàn)生產(chǎn)調(diào)度系統(tǒng)由擾動(dòng)恢復(fù)到穩(wěn)定的過程,最后用仿真實(shí)驗(yàn)驗(yàn)證了該方法能有效應(yīng)對(duì)各類不確定擾動(dòng)事件,減弱和吸收擾動(dòng)事件的擾動(dòng)程度,進(jìn)而減少重調(diào)度次數(shù).
貝葉斯網(wǎng)絡(luò)(bayesian networks,BN)是用來表示變量間概率分布的圖解化模型,它與規(guī)則庫(kù)、神經(jīng)網(wǎng)絡(luò)或決策樹等知識(shí)表示形式相比,具有直觀的模型和推理,局部及分布式的學(xué)習(xí)機(jī)制,適用于表達(dá)和分析不確定性和概率性事物的優(yōu)點(diǎn)[8].
貝葉斯網(wǎng)絡(luò)是一個(gè)有向無環(huán)圖(directed acyclic graph,DAG),它由代表變量的節(jié)點(diǎn)及連接這些節(jié)點(diǎn)的有向邊構(gòu)成.其中節(jié)點(diǎn)代表論域中的變量,每一個(gè)節(jié)點(diǎn)X i都有一個(gè)條件概率P(X i|parents(X i))表示父節(jié)點(diǎn)對(duì)該節(jié)點(diǎn)的影響程度.對(duì)于連續(xù)變量,用一個(gè)條件概率分布(conditional probability distribution,CPD)來表示,對(duì)于離散變量,則用條件概率表(conditional probability table,CPT)以表格的形式表示.如果存在從節(jié)點(diǎn)X到節(jié)點(diǎn)Y的有向邊,則節(jié)點(diǎn)X是節(jié)點(diǎn)Y的一個(gè)父節(jié)點(diǎn),表示X對(duì)Y有直接影響.貝葉斯網(wǎng)絡(luò)提供了對(duì)域的完整描述,域中所有變量節(jié)點(diǎn)的條件概率都可通過貝葉斯網(wǎng)絡(luò)的信息計(jì)算出來.即
其中X i是第i個(gè)隨機(jī)變量,x i是X i的特定取值,parents(X i)是X i的父節(jié)點(diǎn),表示X i的一個(gè)特定取值.式(1)表明每一個(gè)節(jié)點(diǎn)的條件概率都可表示為貝葉斯網(wǎng)絡(luò)條件概率表中適當(dāng)元素的乘積.在貝葉斯網(wǎng)絡(luò)中,一個(gè)節(jié)點(diǎn)與其父節(jié)點(diǎn)和子節(jié)點(diǎn)以外的節(jié)點(diǎn)是條件獨(dú)立的,表達(dá)了變量間的條件獨(dú)立性.
構(gòu)建一個(gè)完整的網(wǎng)絡(luò)一般分為3步:確定變量集,確定網(wǎng)絡(luò)結(jié)構(gòu),確定各變量的條件概率.現(xiàn)以一個(gè)簡(jiǎn)單的貝葉斯網(wǎng)絡(luò)具體說明構(gòu)建方法和正向推理過程.
1)確定變量集.如圖1中有4個(gè)變量s,c,b,d,分別表示吸煙、肺癌、支氣管炎和呼吸困難.
2)確定網(wǎng)絡(luò)結(jié)構(gòu).即確定變量間的有向邊的連接,可根據(jù)變量間的條件獨(dú)立性或根據(jù)變量間的因果關(guān)系來確定有向邊的存在性和方向.圖中吸煙會(huì)造成肺癌、支氣管炎和呼吸困難,而吸煙先造成肺癌和支氣管炎,然后造成呼吸困難,因此吸煙和呼吸困難兩個(gè)變量不存在條件獨(dú)立性.最終形成的網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示.
3)確定各變量的條件概率.可根據(jù)實(shí)驗(yàn)數(shù)據(jù)或者專家知識(shí)來確定.如圖1,變量取1或0表示事件為真或假,P(s=1)=0.5表示吸煙概率為0.5.P(d=1|c=1,b=0)=0.9表示患肺癌而沒有支氣管炎的情況下,呼吸困難的概率為0.9,其他概率表示類似上述推理.
圖1 簡(jiǎn)單貝葉斯網(wǎng)絡(luò)圖
由于各變量間具有條件獨(dú)立性,上圖中各節(jié)點(diǎn)的概率可表示為:
生產(chǎn)系統(tǒng)在進(jìn)行工序的加工時(shí),來自于系統(tǒng)內(nèi)部和外部因素的擾動(dòng),往往會(huì)破壞生產(chǎn)調(diào)度系統(tǒng)中調(diào)度資源的平衡關(guān)系.具體地說,當(dāng)擾動(dòng)事件對(duì)某一個(gè)工序或多個(gè)工序的加工產(chǎn)生影響時(shí),受影響的工序繼而對(duì)后續(xù)工序的加工也有可能帶來干擾.如果能用一種網(wǎng)絡(luò)去描述擾動(dòng)情形下工序的這種相互影響關(guān)系,并用定量的數(shù)值去評(píng)估工序受擾動(dòng)影響的大小,進(jìn)而推導(dǎo)出生產(chǎn)系統(tǒng)受擾動(dòng)影響的大小,這種擾動(dòng)評(píng)估方法的實(shí)現(xiàn)有利于生產(chǎn)調(diào)度人員針對(duì)不確定擾動(dòng)發(fā)生情況,進(jìn)行有效的調(diào)度決策.
貝葉斯網(wǎng)絡(luò)的拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)具有描述各變量相互影響關(guān)系的特征,將這種網(wǎng)絡(luò)結(jié)構(gòu)表示生產(chǎn)加工過程中受擾動(dòng)影響的工序的相互關(guān)系,根據(jù)工序受擾動(dòng)影響的概率大小推理出系統(tǒng)受擾動(dòng)影響的概率大小,能輔助選擇一種較優(yōu)的調(diào)度方法,實(shí)現(xiàn)對(duì)不確定擾動(dòng)事件對(duì)系統(tǒng)影響程度的有效判斷,解決了生產(chǎn)決策者面對(duì)復(fù)雜影響關(guān)系難以決策的難題.
根據(jù)生產(chǎn)調(diào)度車間機(jī)器加工工序的特點(diǎn),用貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)表示生產(chǎn)調(diào)度中受擾工序的相互關(guān)系時(shí),受擾工序集為貝葉斯網(wǎng)絡(luò)的節(jié)點(diǎn)集合,連接節(jié)點(diǎn)的有向邊表示同一工件相鄰工序或者不同工序在同一機(jī)器上加工的相互影響關(guān)系,節(jié)點(diǎn)的條件概率可用該工序在機(jī)器上加工時(shí)受擾動(dòng)影響的概率來表示,簡(jiǎn)稱受擾程度,貝葉斯網(wǎng)絡(luò)表示車間工序的一一對(duì)應(yīng)關(guān)系,見表1.
表1 調(diào)度車間的貝葉斯網(wǎng)絡(luò)對(duì)應(yīng)關(guān)系
構(gòu)建受擾工序的貝葉斯網(wǎng)絡(luò)時(shí),受擾工序用O ij表示,代表著工件i的第j道工序,有向邊為受擾工序間的機(jī)器約束和工序約束,節(jié)點(diǎn)中O ij=1表示工序O ij受到擾動(dòng)的影響,O ij=0表示工序O ij沒有受擾動(dòng)的影響.如圖2所示,p(O12=1)=0.3表示O12工序受擾動(dòng)影響的程度為0.3,p(O13=1|O12=1)=0.49表示工序O23受擾動(dòng)影響的情況下,工序O13受擾動(dòng)影響的程度為0.49,p(S=1|O23=1,O13=0)=0.6表示在工序O23受擾動(dòng)影響,而工序O13沒有受擾擾動(dòng)影響的情況下,生產(chǎn)系統(tǒng)受擾動(dòng)影響的程度為0.6.工序O12與O13工序之間的有向邊代表工序約束,工序O12與O23工序之間的有向邊代表機(jī)器約束,工序O12與工序O23之間具有條件獨(dú)立性.
圖2 受擾工序的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)
用貝葉斯的拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)就可以計(jì)算出系統(tǒng)受擾動(dòng)程度的大小,有
當(dāng)生產(chǎn)系統(tǒng)發(fā)生擾動(dòng),首先找到直接受擾動(dòng)影響的工序,然后分析當(dāng)該工序采取部分重調(diào)度策略時(shí),對(duì)后續(xù)工序產(chǎn)生的影響大小,如此類推,就能將受擾動(dòng)影響的全部工序的關(guān)系用貝葉斯網(wǎng)絡(luò)呈現(xiàn)出來.以8×8的FJSP調(diào)度問題為例,其初始調(diào)度甘特圖如圖3所示,設(shè)定一個(gè)隨機(jī)擾動(dòng)t=2時(shí)刻,工序O31延遲一個(gè)單位完工,表2用圖解方式來說明柔性作業(yè)車間的貝葉斯網(wǎng)絡(luò)構(gòu)建過程.
圖3 8×8的柔性作業(yè)車間甘特圖
表2 基于貝葉斯網(wǎng)絡(luò)的柔性作業(yè)車間擾動(dòng)分析
確定了擾動(dòng)下受擾工序的貝葉斯網(wǎng)絡(luò)后,計(jì)算出各工序的受擾程度值,就可以利用網(wǎng)絡(luò)結(jié)構(gòu)推理出生產(chǎn)系統(tǒng)受擾動(dòng)影響的程度P(S=1).當(dāng)生產(chǎn)過程中出現(xiàn)兩個(gè)及兩個(gè)以上的擾動(dòng),同樣可以用上述方法建立受擾工序的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu),對(duì)生產(chǎn)系統(tǒng)的受擾程度進(jìn)行分析.
從工序的角度去分析,擾動(dòng)事件對(duì)生產(chǎn)系統(tǒng)穩(wěn)定性產(chǎn)生的影響主要表現(xiàn)為加工任務(wù)的擾動(dòng)和成本的擾動(dòng).比如工序開工時(shí)間的偏差,機(jī)器負(fù)荷變化量.
1)開工時(shí)間偏差量R1
式中,C i表示擾動(dòng)發(fā)生前工序的開工時(shí)間,C'i表示擾動(dòng)發(fā)生后工序的預(yù)計(jì)開工時(shí)間,i=1,2,…,M.
2)機(jī)器負(fù)荷的變化量R2
式中,L i為未發(fā)生擾動(dòng)時(shí)機(jī)器m i的負(fù)荷數(shù),L'i為擾動(dòng)發(fā)生后受擾工序在該加工機(jī)器上加工機(jī)器的實(shí)際加工負(fù)荷數(shù).
上述兩種指標(biāo)給工序帶來的影響程度各不相同,比如開工時(shí)間的提前或推遲影響后續(xù)工序的加工,而機(jī)器負(fù)荷量的變化僅影響機(jī)器的開工或停工,兩指標(biāo)給生產(chǎn)系統(tǒng)造成的不穩(wěn)定性不同.因此在計(jì)算時(shí),賦予各指標(biāo)的權(quán)重分別為w1,w2,(w1≠w2且w1+w2=1),得到工序的總的影響值W為
在不同的擾動(dòng)事件的影響下,得到的W也會(huì)發(fā)生變化,且在一個(gè)大的擾動(dòng)事件發(fā)生的樣本中,可以認(rèn)為W是一個(gè)連續(xù)性的變化值,所以兩者可以建立一種函數(shù)映射關(guān)系:f:W→U,即當(dāng)輸入一個(gè)大于0的W值,對(duì)應(yīng)地輸出一個(gè)位于[0,1]區(qū)間的工序受擾程度值.且W與工序受擾程度呈正比關(guān)系,W越大,對(duì)應(yīng)的工序受擾程度值也越大.W=0時(shí),相應(yīng)的工序的受擾程度值也為0,可以用一個(gè)過零點(diǎn)的二次函數(shù)表達(dá)式y(tǒng)=AW2+BW(y∈[0,1])來描述這種一一對(duì)應(yīng)關(guān)系,結(jié)合生產(chǎn)實(shí)際狀況來確定A,B、d的具體數(shù)值.當(dāng)受擾工序的受擾程度接近1時(shí),認(rèn)為工序產(chǎn)生的局部擾動(dòng)過大,直接采取重調(diào)度策略.
設(shè)定A=-1/9,B=2/3,w1=0.6,w2=0.4,用上述擾動(dòng)評(píng)估方法,計(jì)算表2所述的各受擾工序的受擾程度值如圖4所示.用公式(1)得到系統(tǒng)的受擾程度P(S=1).
圖4 受擾工序的貝葉斯網(wǎng)絡(luò)
在上述網(wǎng)絡(luò)模型中,當(dāng)有不確定擾動(dòng)發(fā)生時(shí),需根據(jù)具體的擾動(dòng)情況選擇重調(diào)度策略.部分重調(diào)度保護(hù)初始調(diào)度方案不受破壞的性能較好,但擾動(dòng)較大時(shí),生產(chǎn)系統(tǒng)的穩(wěn)定性會(huì)遭到破壞;完全重調(diào)度固然能得到較好的調(diào)度效果,但執(zhí)行成本較高.
在實(shí)際生產(chǎn)過程中,擾動(dòng)事件的不同,生產(chǎn)系統(tǒng)受擾動(dòng)影響的程度也有所差異.擾動(dòng)發(fā)生時(shí),是進(jìn)行調(diào)度的局部調(diào)整以維持生產(chǎn)的穩(wěn)定還是該擾動(dòng)給生產(chǎn)帶來較大的波動(dòng)進(jìn)而進(jìn)行重調(diào)度,擾動(dòng)事件對(duì)生產(chǎn)系統(tǒng)產(chǎn)生的擾動(dòng)程度大小無法提前預(yù)知.根據(jù)企業(yè)經(jīng)驗(yàn)規(guī)則,本文設(shè)定一個(gè)重調(diào)度閾值θ,通過比較系統(tǒng)的受擾程度值P(S=1)與重調(diào)度閾值θ的大小決定最終的重調(diào)度策略.
當(dāng)生產(chǎn)過程中出現(xiàn)擾動(dòng)時(shí),對(duì)受擾工序進(jìn)行局部調(diào)整,同時(shí)構(gòu)建受擾工序的貝葉斯網(wǎng)絡(luò)對(duì)系統(tǒng)受擾程度進(jìn)行推理,計(jì)算出系統(tǒng)受擾動(dòng)影響程度值P(S=1):
1)當(dāng)P(S=1)<θ時(shí),說明擾動(dòng)對(duì)生產(chǎn)系統(tǒng)的影響較小,維持原有的調(diào)度方案,只對(duì)受擾工序進(jìn)行局部調(diào)整;
2)當(dāng)P(S=1)≥θ時(shí),說明擾動(dòng)對(duì)生產(chǎn)過程產(chǎn)生嚴(yán)重的干擾,需進(jìn)行完全重調(diào)度.
這種將不確定擾動(dòng)的評(píng)估值與重調(diào)度閾值相比較的方法,建立一種自適應(yīng)的重調(diào)度策略,不論擾動(dòng)事件擾動(dòng)程度的大或小,都能實(shí)現(xiàn)對(duì)其進(jìn)行靈活地處理.重調(diào)度策略用流程圖如圖5所示.
圖5 重調(diào)度流程圖
基于貝葉斯網(wǎng)絡(luò)模型的柔性作業(yè)車間的擾動(dòng)處理過程并不是孤立存在的,它表示受擾工序的相互影響關(guān)系,得到系統(tǒng)的受擾程度值,與擾動(dòng)閾值進(jìn)行比較,確定最終的擾動(dòng)處理方案.圖6用輸入層、處理層和輸出層的3層結(jié)構(gòu)流程圖來表示柔性作業(yè)車間的動(dòng)態(tài)調(diào)度過程.輸入層包含生產(chǎn)加工信息、初始調(diào)度方案、擾動(dòng)事件的類型以及擾動(dòng)發(fā)生的結(jié)果,這些輸入信息有助于對(duì)擾動(dòng)信息進(jìn)行管理,為后續(xù)的擾動(dòng)處理過程做好準(zhǔn)備工作.處理層主要用貝葉斯網(wǎng)絡(luò)實(shí)現(xiàn)對(duì)擾動(dòng)的評(píng)估,工序按照初始調(diào)度方案加工過程中受擾動(dòng)事件的干擾,通過各工序受擾動(dòng)影響的大小推理得到系統(tǒng)受擾動(dòng)影響程度值.如果得到的系統(tǒng)擾動(dòng)評(píng)估值小于設(shè)定的閾值,執(zhí)行局部修正方案;否則對(duì)未加工完工件進(jìn)行全重排.將這種調(diào)度策略信息傳遞給輸出層,生產(chǎn)調(diào)度人員根據(jù)輸出的指令執(zhí)行局部修正方案或者進(jìn)行完全重調(diào)度,完成后續(xù)工序的生產(chǎn).此過程可用圖6來表示.
圖6 車間擾動(dòng)事件處理全過程
在工件按原方案加工的情形下,本文將設(shè)定3種擾動(dòng)事件的詳細(xì)信息,運(yùn)用上述提到的基于貝葉斯網(wǎng)絡(luò)模型的擾動(dòng)處理方法對(duì)擾動(dòng)進(jìn)行處理.圖7為5個(gè)工件在6臺(tái)機(jī)器上加工的原調(diào)度方案.
圖7 原調(diào)度方案(擾動(dòng)前)
擾動(dòng)情形1:在t=6時(shí)刻,工序O51的完工時(shí)間由6變?yōu)?;
擾動(dòng)情形2:在t=10時(shí)刻,機(jī)器4故障,故障持續(xù)時(shí)間為5;
擾動(dòng)情形3:在t=20時(shí)刻,有緊急訂單插入,訂單的加工信息見表3.
表3 緊急訂單加工信息表
3種擾動(dòng)事件按時(shí)間先后順序分別進(jìn)入輸入層,記錄擾動(dòng)信息的種類、擾動(dòng)時(shí)刻和持續(xù)時(shí)間等信息后,將此信息傳遞給擾動(dòng)處理層,每種擾動(dòng)處理完后將信息傳遞給輸出層,最終的調(diào)度方案如圖8所示,紅色部分是對(duì)原方案的改動(dòng).
圖8 最終調(diào)度方案(擾動(dòng)后)
在擾動(dòng)處理層中,針對(duì)擾動(dòng)情形1,在t=6時(shí)刻,工序O51在M1上的加工時(shí)間由4變?yōu)?,擾動(dòng)發(fā)生時(shí)刻,還有1/5的任務(wù)等待完成.通過貝葉斯網(wǎng)絡(luò)模型圖進(jìn)行分析,如果繼續(xù)在M1上加工,工序的受擾程度為1/6,如果轉(zhuǎn)移到其他機(jī)器上加工,擾動(dòng)程度如圖7所示,所以最終選擇在M5上加工,受擾程度為1/10.
針對(duì)擾動(dòng)情形2,在t=10時(shí)刻,M4故障,會(huì)影響工序O41的加工.通過貝葉斯網(wǎng)絡(luò)進(jìn)行分析,工序的加工可在機(jī)器維修后使用,也可以將工序轉(zhuǎn)移到其他機(jī)器上進(jìn)行加工,如圖9所示.工序O41最終選擇在M1上加工,受擾程度為0.
圖9 擾動(dòng)后柔性作業(yè)車間調(diào)度的貝葉斯網(wǎng)絡(luò)模型圖
針對(duì)擾動(dòng)情形3,在t=20時(shí)刻,有緊急訂單插入.通過貝葉斯網(wǎng)絡(luò)分析可知,訂單的3道工序分別在M4,M5,M4上加工,如圖8所示,對(duì)原方案無擾動(dòng)產(chǎn)生.
表4分析了不同擾動(dòng)事件下,常見處理結(jié)果與本文處理結(jié)果的對(duì)比,從對(duì)比結(jié)果中可以看出,本文提出的方法能應(yīng)對(duì)各類不確定擾動(dòng)事件,與常見處理方法相比,基于貝葉斯網(wǎng)路的車間擾動(dòng)處理方法能有效減弱擾動(dòng)程度,甚至能吸收擾動(dòng)事件帶來的擾動(dòng),減少重調(diào)度次數(shù).
表4 擾動(dòng)處理方法對(duì)比
1)針對(duì)調(diào)度車間中各類不確定擾動(dòng)對(duì)生產(chǎn)帶來的困擾,借鑒貝葉斯網(wǎng)絡(luò)表達(dá)不確定性事件的特點(diǎn),揭示了擾動(dòng)事件的擾動(dòng)實(shí)質(zhì),提出了基于貝葉斯網(wǎng)絡(luò)的車間擾動(dòng)處理方法,對(duì)擾動(dòng)情形下的工序進(jìn)行調(diào)度資源的評(píng)估和選擇,有效應(yīng)對(duì)各類不確定擾動(dòng)事件.
2)實(shí)驗(yàn)結(jié)果表明,該方法優(yōu)于常見的擾動(dòng)處理方法,能有效減弱或吸收擾動(dòng)事件對(duì)調(diào)度系統(tǒng)的影響,減少重調(diào)度次數(shù),指導(dǎo)生產(chǎn)實(shí)踐.