基于貝葉斯決策的柔性作業(yè)車間擾動處理方法研究

吳正佳 朱穎穎，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ù).

1 貝葉斯網(wǎng)絡(luò)概述

貝葉斯網(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é)點的概率可表示為：

2 不確定擾動下調(diào)度車間的貝葉斯網(wǎng)絡(luò)

2.1 調(diào)度車間的貝葉斯網(wǎng)絡(luò)構(gòu)建思想

生產(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)系

2.2 不確定擾動下調(diào)度車間的貝葉斯網(wǎng)絡(luò)構(gòu)建過程

構(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)行分析.

3 不確定擾動的評估

從工序的角度去分析，擾動事件對生產(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ò)

4 不確定擾動下柔性作業(yè)車間重調(diào)度方法

在上述網(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 車間擾動事件處理全過程

5 仿真驗證

在工件按原方案加工的情形下，本文將設(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 擾動處理方法對比

6 結(jié) 論

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)實踐.