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