柔性制造系統(tǒng)時延Petri網(wǎng)模型排產(chǎn)優(yōu)化研究

洪 良，王藝翔，南愷愷，田海霖

（西安工程大學電子信息學院，陜西 西安 710048）

1 引言

柔性制造系統(tǒng)[1（]Flexible Manufacturing Systems，F(xiàn)MS）在工業(yè)系統(tǒng)中的生產(chǎn)效率問題受到越來越廣泛的關(guān)注。當生產(chǎn)目標發(fā)生變化時，若FMS不能及時調(diào)整生產(chǎn)計劃，容易產(chǎn)生資源閑置、系統(tǒng)停滯等問題，從而降低生產(chǎn)效率。因此，如何在多項約束條件下提高FMS的排產(chǎn)效率，是制造產(chǎn)業(yè)中需要重視的問題。

排產(chǎn)優(yōu)化問題是一個NP?hard問題，文獻[2]提出了一種基于整數(shù)線性規(guī)劃的算法，在系統(tǒng)參數(shù)變化后調(diào)整生產(chǎn)計劃，但在復雜的實際生產(chǎn)中隨著計算對象的增多會產(chǎn)生狀態(tài)空間爆炸問題。文獻[3]提出一種啟發(fā)式算法解決并行多機組工件加工最短時間問題，但對大規(guī)模調(diào)度問題不能建立相應(yīng)的模型，從而降低問題處理的效率。因此，為復雜FMS建立適合的模型十分必要。文獻[4]可以描述系統(tǒng)的動態(tài)行為，可簡單準確地表示系統(tǒng)中的并發(fā)、資源共享、沖突、相互抑制等特征，圖像界面直觀清晰，這些特點都表明Petri網(wǎng)FMS建模方面的優(yōu)越性。目前，Petri網(wǎng)理論已經(jīng)在車間生產(chǎn)調(diào)度問題中得到廣泛應(yīng)用。文獻[5]提出應(yīng)用可達分析技術(shù)，在可達圖中選擇最優(yōu)路徑來提高效率的方法，但是該方法面對大規(guī)模復雜系統(tǒng)時，同樣存在狀態(tài)爆炸計算中止的問題?？梢姡胀≒etri網(wǎng)在解決FMS排產(chǎn)優(yōu)化問題時存在一定的局限性。時延Petri網(wǎng)對FMS建模時可以準確描述系統(tǒng)的時間和路徑等約束信息，因此更適合于排產(chǎn)優(yōu)化研究。

文獻[6]提出時延Petri網(wǎng)啟發(fā)式派遣規(guī)則法解決FMS的排產(chǎn)優(yōu)化問題，但啟發(fā)函數(shù)和實際應(yīng)用聯(lián)系過于緊密，其針對性的模型導致通用性不強。遺傳算法在全局范圍內(nèi)快速有效地尋優(yōu)，文獻[7]將時延Petri網(wǎng)與遺傳算法結(jié)合，既可以通過網(wǎng)模型準確地描述系統(tǒng)的動態(tài)過程，也可以在短時間內(nèi)尋找到最優(yōu)或次優(yōu)解，具有通用性，但是僅依靠遺傳算法尋優(yōu)存在早熟現(xiàn)象容易陷入局部最優(yōu)的現(xiàn)象。因此，應(yīng)用時延Petri網(wǎng)為FMS建模，在遺傳算法的并行搜索的基礎(chǔ)上，結(jié)合模擬退火算法引入隨機元素跳出局部最優(yōu)的能力，提出一種融合遺傳算法和模擬退火算法的混合算法，解決FMS的排產(chǎn)優(yōu)化問題，提高生產(chǎn)效率。

2 時延Petri網(wǎng)

（1）Petri網(wǎng)（Petri Nets，PN）定義為一個五元組，可表示為N=（P，T，F(xiàn)，W，MO），P和T分別稱為庫所和變遷的集合，其中P≠?，T≠?，P∩T=?。F?（P×T）∪（T×P）稱為有向弧集，W：（P×T）∪（T×P）?N+為有向弧的權(quán)函數(shù)，M0：P?N+是一個列向量，稱為N的初始標識，庫所中黑點被稱作托肯，M0表示初始狀態(tài)下所有庫所中的托肯數(shù)。Petri網(wǎng)是有向圖，庫所和變遷都稱為Petri網(wǎng)的節(jié)點。庫所p∈P表示系統(tǒng)對象的某種狀態(tài)，變遷t∈T表示改變狀態(tài)的事件。

（2）設(shè)x∈P∪T是Petri網(wǎng)N的節(jié)點。x的前置集·x定義為·x={y∈P∪T｜（y，x）∈F}，后置集·x定義為·x={y∈P∪T｜（x，y）∈F}。

（3）時延Petri網(wǎng)（Timed Petri Nets，TdPN）表示為Nt=（N，D），其中N表示普通Petri網(wǎng)，D表示時延dt的集合，dt∈N+是變遷t∈T的延遲，N+為正整數(shù)的集合。當且僅當?p∈·t，M（p）≥W（p，t），變遷t∈T在標識M下使能，記為M[t〉。變遷t發(fā)射后，經(jīng)過dt個單位時間，變遷t發(fā)射結(jié)束，從·t中轉(zhuǎn)移定量的托肯到t·中。

3 FMS的TdPN模型

FMS的特點表明，單一加工工序可經(jīng)由不同路徑實現(xiàn)。加工工序的路徑信息稱為該工序的約束信息，工序約束信息表明該工序經(jīng)由若干機床按照特定順序完成加工，同時限定解空間內(nèi)的可選擇路徑，找到最優(yōu)或次優(yōu)解。

引入TdPN為FMS建模，考慮工序的約束信息，在普通Petri網(wǎng)的基礎(chǔ)上，建立TdPN模型的具體步驟如下：

（1）設(shè)該系統(tǒng)中共有β臺機床，共有z個包含約束信息的工序變遷。選擇其中任一變遷t（ii∈｛1，2，…，z｝），·ti=｛p｝s，·ti=｛ps+1｝，ps和ps?1分別表示ti的輸入庫所和輸出庫所，Si（kk∈｛1，2，…，n｝）表示工序ti對應(yīng)的n種加工路徑之一，若路徑Sik中只包含一個機床，用變遷ti表示該機床的工序，若路徑Sik中包含多個機床，則用變遷tikx表示這些機床的工序；x∈｛1，2，…，β｝表示機床的編號，資源庫所pmx表示機床x的狀態(tài)；

（2）刪除變遷ti；

（3）case1（該路徑僅包含一個機床）：添加資源庫所pmx與變遷tik，構(gòu)成可達路徑EP（pmx，tik）=pmxtik，其中pmx?=·pmx=｛ti｝k，tik?=｛pmx，ps｜1｝，·tik=｛pmx，p｝s，此時M（opmx）=1；

case2（該路徑包含α（1<α≤β）個機床）：根據(jù)約束信息添加α個資源庫所pmx與數(shù)量相等的變遷tikx，構(gòu)成可達路徑EP（pmx，tikx′）=pmxtikx…pmx’tikx′，pmx（’x ′∈｛1，2，…，β｝）表示資源庫所，與最后一個變遷tikx′對應(yīng)，其中pmx?=·pmx=｛tikx｝，tikx′?=｛pmx′，ps+1｝，·tikx=｛pmx，p｝s，此時M（opmx）=1；

（4）已建立的獨立網(wǎng)模型末尾庫所與下一組網(wǎng)模型的首部庫所為同一庫所，通過該庫所將獨立的網(wǎng)模型連接，建立完整的TdPN。

為使網(wǎng)模型更加簡潔，網(wǎng)模型中名稱相同的資源庫所pmx重復出現(xiàn)在網(wǎng)模型的不同位置但實際表示同一庫所。一套簡單加工進程的普通Petri網(wǎng)模型，如圖1所示。其中各庫所和變遷表示的含義，如表1所示。該進程中的所有工序均由四臺機床m1、m2、m3、m4完成，每臺機床同時只能加工一個工件。單一工序可選擇約束信息內(nèi)的任意生產(chǎn)路徑完成加工，如工序t1可由S11、S12、S13中的任一路徑完成，S11表示由m2和m3順序加工完成工序t1的工作。描述了該簡單加工進程中各變遷的生產(chǎn)路徑和時間約束信息，如表2所示。

表1 Petri網(wǎng)各節(jié)點與實際加工過程映射關(guān)系Tab.1 Mapping Relations Between Nodes of Petri Nets and Machining Processes

圖1 簡單加工進程的Petri網(wǎng)模型Fig.1 The Petri Net of A Simple Machining Process

表2 工序生產(chǎn)路徑約束和工作耗時（分鐘）Tab.2 Production Path Constraints and Worktime（min）

在圖1普通Petri網(wǎng)模型中增加時間參數(shù)與加工路徑信息，得到時延Petri網(wǎng)模型，如圖2所示。圖2（a）中的與構(gòu)成路徑S11，表示機床m2和m3順序參與加工，分別耗時3min和9min。同理，t12構(gòu)成路徑S12、t13構(gòu)成路徑S13。圖2（b）、圖2（c）表示對t2、t3發(fā)生時的不同加工路徑，最終，將三個獨立部分通過共享庫所p3、p4連接復合，建立完整的TdPN模型，如圖2（d）所示。

圖2 TdPN建模步驟Fig.2 Modeling Steps of TdPN

4 算法

已建立的TdPN模型顯示，F(xiàn)MS生產(chǎn)具有加工路徑多樣性。引入TdPN 為FMS 建模，更加清晰地描述了某項工序的多種路徑，但同時網(wǎng)模型中也產(chǎn)生了資源沖突問題。為解決模型中的資源沖突，實現(xiàn)FMS的高效生產(chǎn)，設(shè)計遺傳算法和模擬退火算法的混合算法。

遺傳算法的特點是高度并行和自適應(yīng)性，同時比較多個解，在搜索效率上有較高的優(yōu)越性。對目標函數(shù)G（x）求解時，設(shè)置初始變量，最大遺傳代數(shù)imax，種群數(shù)量Size，交叉概率Pc和變異概率Pm，種群可表示為S=[S1，S2，…，Sr，…，Ssize]T，其中，當染色體長度為l時整個種群S是Size×l的矩陣。算法根據(jù)適應(yīng)度判斷是否接受新解，適應(yīng)度函數(shù)為：

模擬退火算法在解空間的搜索中引入隨機元素，以Metrolo‐lis準則判定當前解是否被接受并有概率跳出局部最優(yōu)解。初始化時給定初始溫度To，目標函數(shù)G（x），模型擾動產(chǎn)生新解x′及對應(yīng)的目標函數(shù)值G（x′），函數(shù)差值△f=（fx′）?（fx），若△f≤0則接受新解為當前解，若△f>0，則以概率p接受新解。

式中：降溫系數(shù)q∈（0，1），當前溫度T=To·qk，k—常數(shù)，表示當前迭代次數(shù)。

為保證算法的通用性，又使得算法易于實現(xiàn)，采用變遷發(fā)生序列作為染色體編碼，對現(xiàn)有網(wǎng)模型中的變遷發(fā)生序列尋優(yōu)，通過計算時間找到最優(yōu)或次優(yōu)變遷發(fā)生序列。因此，本算法優(yōu)化的目標函數(shù)為：

式中：di—染色體S（rr∈[1，size]）對應(yīng)的變遷ti發(fā)生的時延；

l—FMS總工序數(shù)，變量與建模步驟中的變量保持一致。

算法的約束條件：

（1）TdPN模型運行規(guī)則

當且僅當?p∈·t，M（p）≥W（p，t），變遷t在標識M下使能，變遷t在滿足工件加工規(guī)則時，經(jīng)過dt個單位時間，從·t中轉(zhuǎn)移一個托肯到t·中。

（2）工件加工規(guī)則

工件按照工序順序進行加工，但每道工序可通過滿足工序約束信息的任意路徑完成，路徑對應(yīng)變遷t的發(fā)射順序是固定的。

（3）設(shè)備資源競爭

當多個變遷t同時使能，且滿足工件加工規(guī)則時，依據(jù)混合算法產(chǎn)生的變遷發(fā)生序列，確定加工路徑。

基于遺傳算法與模擬退火算法的混合算法步驟如下：

輸入：TdPN網(wǎng)模型與工序約束矩陣，最大遺傳代數(shù)imax，種群數(shù)量Size，交叉概率Pc和變異概率Pm，初始溫度T0，降溫系數(shù)q；

輸出：當前種群最短加工時間及其對應(yīng)的染色體序列。

（1）根據(jù)TdPN中變遷個數(shù)確定染色體長度l，產(chǎn)生初始種群其中每個基因位的選擇由各工序的生產(chǎn)路徑約束信息決定，令i：=0，i表示當前遺傳代數(shù)；

（2）若i

（3）計算適應(yīng)度函數(shù)（fS）r=

（4）輪盤賭選取個體進入下一代，個體Sr被選擇的概率P（S）r

（5）以交叉概率Pc運算，將交叉算子插入種群；

（6）在約束信息范圍內(nèi)以變異概率Pm運算，將變異算子插入種群；

（7）模擬退火操作隨機生成擾動解Sr′，計算△f=（fSr′）?（fS）r，若△f≥0，或者△f≤0且符合Metropolis準則，Sr：=Sr′，更新種群；否則，不再更新種群；

（8）降溫T：=To·qi，i：=i+1，返回（2）。

采用圖2已建立的TdPN對上述算法進行驗證，該網(wǎng)模型中共有3個變遷，故染色體共包含3個基因位，其約束信息，如表1所示，因此共有12種加工方案。經(jīng)算法多次實驗，可以得到最優(yōu)加工路徑為S13S22S32，與其對應(yīng)的最短加工時間為12分鐘。

5 算例

柔性車間中4臺機床m1、m2、m3、m4組成的FMS，如圖3所示。

圖3 FMS圖示Fig.3 Presentation of FMS

每臺機床同時只能執(zhí)行一項操作，各機床分別承擔車削、裝配等操作，該系統(tǒng)完整加工工件流程共需要8道工序，每道工序由特定的路徑完成，4臺設(shè)備通過機械臂來調(diào)度，設(shè)備之間相互配合，按已設(shè)定的程序工作。根據(jù)系統(tǒng)加工順序建立的Petri網(wǎng)模型，如圖4所示。各項加工工序的約束信息，如表3所示。

表3 FMS中機床路徑約束信息和工作耗時（分鐘）Tab.3 Production Path Constraints of FMS and Worktime（min）

圖4 FMS Petri網(wǎng)模型Fig.4 Petri Nets of FMS

建模過程中，所有表示待執(zhí)行工序的庫所中均保留至少一個托肯，保證任意變遷都是使能的。應(yīng)用提出的混合算法，實驗中的算法各參數(shù)設(shè)置為：最大遺傳代數(shù)imax=100，種群數(shù)量Size=50，交叉概率Pc=0.8，變異概率Pm=0.2，初始溫度T0=1000，冷卻系數(shù)q=0.2，任務(wù)可選擇方案共1944 個。

在同等條件下，該算法與文獻[7]僅使用遺傳算法的性能比較，如表4所示?？梢娞岢龅乃惴ㄔ谒褜ぷ顑?yōu)變遷發(fā)生序列時，50次實驗中有32次得到最短的生產(chǎn)時間為25min，10次得到較短的加工時間，其中8次得到加工時間超過了30min。

表4 分別利用該算法和文獻[7]提出算法優(yōu)化結(jié)果對比Tab.4 Contrasts of Optimization Results of the Algorithms Proposed in this Paper and in Paper[7]

故而混合算法在得到最短時間的概率上和和跳出陷阱的能力上都更加高效。

經(jīng)該算法計算可得到多種最優(yōu)或次優(yōu)的變遷發(fā)生序列所對應(yīng)生產(chǎn)時間都為25min，其中一條染色體序列為：S13S22S33S41S21S62S73S81，仿真實驗適應(yīng)度隨遺傳代數(shù)變化曲線，如圖5所示。可見隨著遺傳代數(shù)的增加，適應(yīng)度趨于穩(wěn)定。

圖5 仿真實驗結(jié)果適應(yīng)度曲線Fig.5 The Fitness Curve of Simulation Experiment

改變FMS中的生產(chǎn)約束信息，即僅改變網(wǎng)模型的變遷數(shù)及其對應(yīng)的加工時間，其他條件保持不變的情況下進行50次實驗，實驗結(jié)果，如表5所示?？梢婋S著生產(chǎn)路徑的多樣化，可選擇加工方案數(shù)的增多，計算得到最優(yōu)解或次優(yōu)解的準確率越高，說明算法在一定程度上解決了大型生產(chǎn)系統(tǒng)加工優(yōu)化問題。

表5 所提出算法對不同模型計算最優(yōu)或次優(yōu)實驗結(jié)果Tab.5 The Results of the Experiments of Algorithm Proposed in this Paper for Calculating Optimal or Suboptimal Solutions of Different Models

6 結(jié)語

通過引入TdPN對FMS建模，結(jié)合遺傳算法的并行搜索能力和模擬退火算法更易跳出陷阱的優(yōu)勢，設(shè)計混合算法，快速搜索到最優(yōu)或次優(yōu)變發(fā)生序列，優(yōu)化FMS生產(chǎn)路徑。引入TdPN模型在一定程度上解決了加工系統(tǒng)建模精準度與通用性的問題，設(shè)計遺傳算法結(jié)合模擬退火算法的混合算法，提升了加工路徑優(yōu)化中計算準確性與跳出局部最優(yōu)方面的能力。算例仿真驗證了算法的高效性，同時表明了該算法在解決大規(guī)模生產(chǎn)加工優(yōu)化問題方面具有一定的應(yīng)用價值。