柔性制造系統時延Petri網模型排產優化研究

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

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

1 引言

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

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

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

2 時延Petri網

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

（2）設x∈P∪T是Petri網N的節點。x的前置集·x定義為·x={y∈P∪T｜（y，x）∈F}，后置集·x定義為·x={y∈P∪T｜（x，y）∈F}。

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

3 FMS的TdPN模型

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

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

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

（2）刪除變遷ti；

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

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

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

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

表1 Petri網各節點與實際加工過程映射關系Tab.1 Mapping Relations Between Nodes of Petri Nets and Machining Processes

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

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

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

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

4 算法

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

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

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

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

為保證算法的通用性，又使得算法易于實現，采用變遷發生序列作為染色體編碼，對現有網模型中的變遷發生序列尋優，通過計算時間找到最優或次優變遷發生序列。因此，本算法優化的目標函數為：

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

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

算法的約束條件：

（1）TdPN模型運行規則

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

（2）工件加工規則

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

（3）設備資源競爭

當多個變遷t同時使能，且滿足工件加工規則時，依據混合算法產生的變遷發生序列，確定加工路徑。

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

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

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

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

（2）若i

（3）計算適應度函數（fS）r=

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

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

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

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

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

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

5 算例

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

圖3 FMS圖示Fig.3 Presentation of FMS

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

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

圖4 FMS Petri網模型Fig.4 Petri Nets of FMS

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

在同等條件下，該算法與文獻[7]僅使用遺傳算法的性能比較，如表4所示。可見提出的算法在搜尋最優變遷發生序列時，50次實驗中有32次得到最短的生產時間為25min，10次得到較短的加工時間，其中8次得到加工時間超過了30min。

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

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

經該算法計算可得到多種最優或次優的變遷發生序列所對應生產時間都為25min，其中一條染色體序列為：S13S22S33S41S21S62S73S81，仿真實驗適應度隨遺傳代數變化曲線，如圖5所示?？梢婋S著遺傳代數的增加，適應度趨于穩定。

圖5 仿真實驗結果適應度曲線Fig.5 The Fitness Curve of Simulation Experiment

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

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

6 結語

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