基于時(shí)延Petri網(wǎng)的大型工程機(jī)械裝備排產(chǎn)模型與收斂算法

摘要：在大型工程機(jī)械裝備的柔性制造系統(tǒng)中，由于涉及多個(gè)車間且存在大量的并行加工過程，因此資源被閑置浪費(fèi)的情況比較常見。為解決此問題，提出一種基于時(shí)延Petri網(wǎng)的大型工程機(jī)械裝備排產(chǎn)模型與收斂算法。首先，在建模過程中對(duì)各種存在并行加工的情況使用約束矩陣進(jìn)行描述，利用Petri網(wǎng)建立系統(tǒng)模型，實(shí)現(xiàn)對(duì)車間內(nèi)各機(jī)床之間調(diào)度流程的描述，并在發(fā)生突發(fā)事件時(shí)進(jìn)行模型重建；其次，使用一種基于遺傳算法和粒子群優(yōu)化的融合算法，構(gòu)建算法的適應(yīng)度函數(shù)；最后，根據(jù)算法求出模型的最優(yōu)路徑，達(dá)到資源利用的最大化。

關(guān)鍵詞：柔性制造系統(tǒng)；大型工程機(jī)械裝備；Petri網(wǎng)；遺傳算法

中圖分類號(hào)：TP301.6文獻(xiàn)標(biāo)志碼：A

0引言（Introduction）

Petri網(wǎng)已被廣泛應(yīng)用于眾多行業(yè)。張寧等［1］針對(duì)魚雷裝備測試維修使用需求，采用廣義隨機(jī)Petri網(wǎng)模型進(jìn)行測試維修建模；閆哲等［2］提出邏輯博弈概率Petri網(wǎng)，使用Petri網(wǎng)描述動(dòng)態(tài)博弈過程；賈云富等［3］提出了一種適用于柔性生產(chǎn)線調(diào)度研究的Petri網(wǎng)模型，用于描述柔性生產(chǎn)線的調(diào)度過程；王慧英等［4］提出基于約束優(yōu)化的Petri網(wǎng)可達(dá)性偽標(biāo)識(shí)判定模型構(gòu)建方法，使用該方法構(gòu)建Petri網(wǎng)可達(dá)性偽標(biāo)識(shí)判定模型時(shí)的CPU占用率低、網(wǎng)絡(luò)路徑覆蓋率高、判定效果好；樊海剛等［5］基于Petri網(wǎng)可能出現(xiàn)的狀態(tài)集同構(gòu)馬爾科夫鏈，實(shí)現(xiàn)了定量評(píng)價(jià)地震應(yīng)急協(xié)同能力；徐海軍等［6］則提出基于模糊Petri網(wǎng)的有載分接開關(guān)故障診斷模型，以解決分接開關(guān)實(shí)際發(fā)生故障與結(jié)果之間存在偏差的問題；YANG等［7］使用高級(jí)Petri網(wǎng)處理模糊物聯(lián)網(wǎng)沖突策略的建模和推理；KABASHKIN等［8］利用Petri網(wǎng)評(píng)估環(huán)境、社會(huì)和經(jīng)濟(jì)方面走廊可持續(xù)性的通用方法；CUI等［9］提出了一種基于時(shí)間轉(zhuǎn)移Petri網(wǎng)的描述模型，用于實(shí)現(xiàn)飛機(jī)周轉(zhuǎn)時(shí)間預(yù)測。

在面對(duì)擁有大量零部件的大型工程機(jī)械裝備和存在大量的并行制造過程時(shí)，傳統(tǒng)的柔性制造系統(tǒng)排產(chǎn)模型無法很好地描述制造過程中的復(fù)雜情況?；诖?，本文采用一種基于Petri網(wǎng)的建模方式對(duì)大型工程機(jī)械裝備的柔性制造系統(tǒng)建立模型，通過對(duì)此模型進(jìn)行求解，進(jìn)而得出最優(yōu)的工序路徑。

1.1首次建模

柔性制造系統(tǒng)由各種類型的車間組成，這些車間包括鍛件車間、精加工車間、焊接車間、裝_{aZ0xub/B62nZfnv+CLJCTA==}配車間等，車間中又包含了用于工件工序加工的各種機(jī)床資源?；谌嵝灾圃斓奶匦裕粋€(gè)工序可以由多種機(jī)器路徑實(shí)現(xiàn)，不同的機(jī)器有不同的加工時(shí)間。因此，在建立模型之前需要對(duì)建模流程中的變量進(jìn)行統(tǒng)一定義，具體如下。

1.[JP3]方法charmap（int）是一種映射關(guān)系，該方法接收數(shù)字參數(shù)，將其進(jìn)行唯一映射為該數(shù)字對(duì)應(yīng)的一個(gè)字母，如map（1）->a，表示將數(shù)字1映射為字母a，并且a僅由1映射。

2.機(jī)器的數(shù)量為x，工件的數(shù)量為y。

3.機(jī)器集定義為集合X={Xi|i∈1，2，…，x}。

4.工件集定義為集合Y={Yi|i∈1，2，…，y}。

5.工件Xa的加工工序集定義為集合Pa={Pai|i∈1，2，…，len（Xa）}，集合中的個(gè)體Pab表示工件Xa的第b步加工工序。

6.可以實(shí)現(xiàn)工序Pab的機(jī)床集合定義為集合MTab={MTabi|i=1，2，…，len（MTab）}，集合中的元素MTabc表示可以完成工序Pab的第c個(gè)機(jī)床。

7.庫所集合S={Si|i=1，2，…，len（S）}。

8.變遷集合T={Ti|i=1，2，…，len（T）}。

9.時(shí)延集合Delay={Di|i=1，2，…，len（D）}，表示為同一個(gè)變遷Ti發(fā)射的所有token均必須經(jīng)過Di時(shí)間長度之后，才會(huì)變成可用的token。

10.系統(tǒng)的輸入矩陣為[WTHX]IN[WTBX]（Si，Tj），表示變遷Tj發(fā)射之后，需要庫所Si提供的token的數(shù)量，發(fā)射變遷Ti需要的所有token表示為∑〖DD（〗len（T）〖〗i=1〖DD）〗[WTHX]IN[WTBX]（Si，Tj），只有當(dāng)變遷對(duì)應(yīng)的所有輸入庫所的token數(shù)量不小于輸入矩陣中該變遷對(duì)應(yīng)的值時(shí)，變遷才是可以發(fā)射的。

11.系統(tǒng)的輸出矩陣為[WTHX]OUT[WTBX]（Si，Tj），表示變遷Tj發(fā)射之后，輸出到庫所Si中的token數(shù)量，變遷Tj發(fā)射的token集合表示為∑〖DD（〗len（T）〖〗i=1〖DD）〗[WTHX]OUT[WTBX]（Si，Tj），變遷Tj發(fā)射的所有token經(jīng)過Delay（Si）之后，變成可用token。

基于時(shí)延Petri網(wǎng)的柔性制造系統(tǒng)的排產(chǎn)模型建模算法的邏輯如下。

1.計(jì)算機(jī)器的數(shù)量為x，工件的數(shù)量為y。

2．根據(jù)機(jī)器的數(shù)量和工件的數(shù)量，建立輸入矩陣[WTHX]IN、輸出矩陣OUT[WTBZ]及存放中間數(shù)據(jù)的List集合。

3.遍歷工件集合中的所有的工件：forYiinY（第一層循環(huán)）。

4.創(chuàng)建工件Yi的加工開始庫所Siα，加工結(jié)束庫所Siβ，加工開始變遷Tiα。

5.賦值操作：[WTHX]IN[WTBX]（Siα，Tiα）=1。

6.將變遷Tiα放入List集合中：List.add（Tiα）。

[HJ1.5mm]

7.遍歷工件Yi所有的工序：forPijinPi（第二層循環(huán)）。

8.創(chuàng)建工序選擇庫所Sij。

9.遍歷List集合中的所有元素while（list.iterator（）.hasNext（））。

10.賦值操作[WTHX]OUT[WTBX]（Sij，iterator（）.next（））=1。

11.List集合遍歷結(jié)束后，清空集合中的所有元素：List.clear（）。

12.遍歷可以完成工序Pij的所有機(jī)床集合：forMTabcinMTab（第三層循環(huán)）。

13.創(chuàng)建工序Pij的工序開始變遷Tijk，工序結(jié)束變遷Ti（j+1）map（k），工序加工庫所Sijk。

14.賦值操作：

[WTHX]IN[WTBX]（Sij，Tijk）=1；

[WTHX]IN[WTBX]（Sij，Ti（j+1）map（k））=1；

[WTHX]IN[WTBX]（SMT，Tijk）=1；

[WTHX]OUT[WTBX]（Sijk，Tijk）=1；

[WTHX]OUT[WTBX]（SMT，Tijk）=1。

15.將工序結(jié)束變遷放入List集合中：List.add（Ti（j+1）map（k））。

16.結(jié)束第三層循環(huán)。

17.結(jié)束第二層循環(huán)。

18.遍歷List集合中的所有元素while（list.iterator（）.hasNext（））。

19.賦值操作[WTHX]OUT[WTBX]（Siβ，iterator（）.next（））=1。

20.結(jié)束第一層循環(huán)。

建模算法的輸入為加工機(jī)床集合MT、工件集合Y及所有工件的工序集合P；建模算法的輸出為變遷輸入矩陣[WTHX]IN和變遷輸出矩陣OUT[WTBZ]。首次建模模型如圖1所示。

模型的時(shí)延特性在工序加工庫所Sijk和時(shí)延集合Delay中體現(xiàn)，例如當(dāng)變遷T121發(fā)射后，庫所S121中的token必須等待Delay（S121）時(shí)間之后，才會(huì)變成可用token，因此變遷T12b不會(huì)立即使能，機(jī)器資源庫所S2中token的數(shù)量在Delay（S121）時(shí)長內(nèi)為0，假如此時(shí)工件2同樣需要使用2號(hào)機(jī)床的變遷T221時(shí)，由于沒有滿足變遷發(fā)生條件的token數(shù)量，因此變遷T221不是使能的，此時(shí)工件2有兩個(gè)選擇，即等待變遷T12b發(fā)射，歸還庫所S2的token；或是選擇3號(hào)機(jī)床執(zhí)行變遷T211。

1.2突發(fā)事件重建模方法

在大型工程機(jī)械裝備柔性制造系統(tǒng)運(yùn)行時(shí)，可能會(huì)發(fā)生一些事件干擾當(dāng)前正在進(jìn)行的生產(chǎn)流程，比如出現(xiàn)加工機(jī)床故障、緊急插單等，如果不實(shí)時(shí)修改原來已經(jīng)建立的排產(chǎn)模型，就可能產(chǎn)生工序錯(cuò)誤。

基于此，提出一種針對(duì)突發(fā)事件的重建模方法，該方法可以在發(fā)生機(jī)床故障、緊急插單等突發(fā)事件時(shí)進(jìn)行重新建模，并在突發(fā)事件解決后再次進(jìn)行重建模，以保證最大化地利用柔性制造系統(tǒng)中的資源。

1.2.1安全點(diǎn)機(jī)制

突發(fā)事件重建模方法參考了Java虛擬機(jī)垃圾回收機(jī)制中的安全點(diǎn)思想：在HotSpotJava虛擬機(jī)中，對(duì)內(nèi)存堆區(qū)域中的不可達(dá)對(duì)象進(jìn)行垃圾回收的時(shí)機(jī)不是任意的，需要Java虛擬機(jī)進(jìn)程的所有線程都執(zhí)行到定義的安全點(diǎn)的位置后，虛擬機(jī)開始對(duì)堆中的對(duì)象進(jìn)行可達(dá)性分析，標(biāo)記可達(dá)對(duì)象，再對(duì)不可達(dá)對(duì)象進(jìn)行回收。突發(fā)事件重建模方法同樣定義了安全點(diǎn)機(jī)制：定義安全點(diǎn)集合SP={Si|i=1，2，…，len（SP）}。只有在安全點(diǎn)時(shí)，才可以進(jìn)行重建模。

1.2.2機(jī)器故障重建模

以首次建模的模型為例，當(dāng)發(fā)生機(jī)器故障時(shí)，假設(shè)2號(hào)機(jī)床發(fā)生故障無法使用，此時(shí)模型的加工機(jī)床集合MT發(fā)生了變化，在安全點(diǎn)庫所S11加入暫停邏輯，并按照上文提出的建模算法流程進(jìn)行重建模操作，輸入為當(dāng)前可用的加工機(jī)床集合MT，工件集合Y，所有工件的工序集合P，機(jī)器故障重建模型如圖2所示。

如果故障的機(jī)床在原系統(tǒng)模型中表示正在使用，即工序加工庫所S121中的token數(shù)量不為0，則需要回退到安全點(diǎn)S11，然后進(jìn)行重建模操作。

1.2.3緊急插單重建模

以1.1節(jié)中的模型為例，當(dāng)發(fā)生緊急插單事件時(shí)，當(dāng)工件Y1和工件Y2正在進(jìn)行加工時(shí)，有工件Y3要緊急插單，優(yōu)先級(jí)高于Y1和Y2，此時(shí)模型的工件集合Y、工件的工序集合P均發(fā)生了變化。在安全點(diǎn)庫所S11加入暫停邏輯，并進(jìn)行重建模操作，輸入為按照權(quán)重排序的工件集合Y、加工機(jī)床集合MT、所有工件的工序集合P，緊急插單重建模型如圖3所示。

緊急插單工件排序后，作為工件集合Y中的第一個(gè)元素Y1，原工件Y1在新工件集合中為Y2，原工件Y2在新工件集合中為Y3。同理，工件的工序集合P也相應(yīng)地進(jìn)行修改。

與機(jī)器故障不同，緊急插單不會(huì)進(jìn)行回退操作，假設(shè)原系統(tǒng)工序加工庫所S111中的token數(shù)量不為0，表示該工序?qū)?yīng)的機(jī)床資源1號(hào)機(jī)床正在使用中，此時(shí)插單的工件必須等待該機(jī)床使用完畢，或者使用其他的機(jī)床完成工序。

1.2.4重建模流程

所有變量的意義已在1.1節(jié)中說明，建模算法的輸入為加工機(jī)床集合MT、工件集合Y、所有工件的工序集合P、突發(fā)事件類型Type、原變遷輸入矩陣[WTHX]IN和原變遷輸出矩陣OUT[WTBX]、原模型上下文Context，建模算法的輸出為變遷輸入矩陣[WTHX]IN和變遷輸出矩陣OUT[WTBX]，排產(chǎn)模型重建模算法邏輯如下。

本文提出一種基于遺傳算法和粒子群算法的融合算法，首先使用遺傳算法對(duì)解集中的個(gè)體進(jìn)行選擇、交叉、變異操作，將遺傳算法一次迭代后生成的新種群作為粒子群優(yōu)化算法的初始粒子群，計(jì)算個(gè)體極值和群體極值。其次對(duì)粒子進(jìn)行隨機(jī)擾動(dòng)，判斷此次的粒子是否更優(yōu)，若更優(yōu)，則更新粒子的速度和位置，并更新個(gè)體極值和群體極值。最后開始下一次遺傳算法和粒子群優(yōu)化算法的迭代，最終輸出一個(gè)問題的最優(yōu)解序列。

算法約束條件如下。

（1）根據(jù)Petri網(wǎng)建立的柔性排產(chǎn)系統(tǒng)的運(yùn)行規(guī)則：當(dāng)且僅當(dāng)p∈·t，M（p）≥W（p，t）時(shí)，變遷t是有權(quán)利發(fā)生的，當(dāng)變遷的發(fā)生條件可以得到滿足時(shí)，從·t中轉(zhuǎn)移權(quán)重函數(shù)數(shù)量的token到t·中。

（2）工序順序規(guī)則：在柔性制造系統(tǒng)中進(jìn)行加工的各種零部件，需要遵守事先規(guī)定的加工工序順序。

（3）[JP3]并行加工規(guī)則：當(dāng)柔性制造系統(tǒng)中存在并行加工操作時(shí)，需要根據(jù)融合算法給出的最終解序列，按照順序進(jìn)行工序加工。

算法輸入：基于Petri網(wǎng)的柔性排產(chǎn)模型、工序約束矩陣、最大迭代次數(shù)imax、種群中的個(gè)體數(shù)量Size、交叉概率Mc和變異概率Mm。

算法輸出：當(dāng)前種群最短加工時(shí)間及其對(duì)應(yīng)的染色體序列（加工路徑）。

融合算法流程如下。

1.根據(jù)基于Petri網(wǎng)建立的柔性制造系統(tǒng)模型中變遷的數(shù)量，確定解向量的維度l，通過算法產(chǎn)生初始種群[WTHX]X=［X1，X2，…，X[WTBX]t，…，[WTHX]X[WTBX]size］T，其中每一個(gè)解向量可以表示為[WTHX]X[WTBX]t=［X1t，X2t，…，Xlt］，解向量中的每個(gè)元素的選擇由各工序的生產(chǎn)路徑約束信息決定。算法開始時(shí)的迭代次數(shù)為0，在迭代中不斷增加。

2.若當(dāng)前迭代次數(shù)小于最大迭代次數(shù)，即i<imax，則表示當(dāng)前可以繼續(xù)循環(huán)迭代，通過適應(yīng)度函數(shù)F（[WTHX]X[WTBX]t）計(jì)算解向量表示的總加工時(shí)間F（[WTHX]X[WTBX]t）（t∈［1，size］）；否則，輸出當(dāng)前種群中適應(yīng)度函數(shù)值最大的最優(yōu)解，其中適應(yīng)度函數(shù)為

3實(shí)驗(yàn)（Experiment）

本文的數(shù)據(jù)來源為某大型工程機(jī)械裝備制造企業(yè)的MES制造執(zhí)行系統(tǒng)的圖紙和工藝文件數(shù)據(jù)以及SAP企業(yè)資源管理系統(tǒng)中的生產(chǎn)計(jì)劃數(shù)據(jù)；大型工程機(jī)械裝備以盾構(gòu)機(jī)為例，使用盾構(gòu)機(jī)刀盤的部件及零件的最短加工路徑作為算法的解。

盾構(gòu)機(jī)刀盤模塊零部件包括中心刀、邊刀、滾刀、鏟斗、正刀、輪軸、主驅(qū)動(dòng)，需要經(jīng)過鍛件車間、精加工車間、焊接車間和裝配車間共計(jì)4個(gè)車間進(jìn)行加工。使用柔性制造系統(tǒng)模型和各個(gè)車間的模型，根據(jù)Petri網(wǎng)的變遷使能表達(dá)式和表1所示的變遷約束條件，使用基于遺傳算法和粒子群算法的融合算法對(duì)模型進(jìn)行求解，得到最終的解序列，輸出排產(chǎn)工序流程。同時(shí)，將融合算法在迭代過程中的目標(biāo)函數(shù)值、結(jié)果準(zhǔn)確率與遺傳算法和粒子群算法進(jìn)行比較。

將本文提出的基于時(shí)延的Petri網(wǎng)模型和融合收斂算法與其他方法建立的模型性能進(jìn)行對(duì)比，結(jié)果見表2。從表2中的數(shù)據(jù)可以看出，本文提出的模型在收斂時(shí)間、迭代次數(shù)、準(zhǔn)確率方面均有所改善。

4結(jié)論（Conclusion）

本文提出一種基于時(shí)延Petri網(wǎng)建立大型工程機(jī)械裝備柔性制造系統(tǒng)的建模方法，旨在模擬大型工程機(jī)械裝備的柔性制造系統(tǒng)在實(shí)際生產(chǎn)過程中的各種調(diào)度情況，通過約束矩陣的輔助，能夠很好地描述大型工程機(jī)械裝備多部件、多零件、并行度高的特點(diǎn)。該模型充分發(fā)揮了Petri網(wǎng)邏輯模型用于描述和分析異步并發(fā)系統(tǒng)的優(yōu)勢，具有精確的定義、堅(jiān)實(shí)的基礎(chǔ)支撐，避免了模糊性、不確定性和矛盾性，使原本復(fù)雜的制造系統(tǒng)變得簡單、直觀。

在建立模型之后，本文提出了一種基于遺傳算法和粒子群優(yōu)化的融合算法對(duì)模型求解。這種算法具有遺傳算法中強(qiáng)大的全局搜索能力，以及粒子群優(yōu)化算法具有的通過隨機(jī)擾動(dòng)跳出局部最優(yōu)解的能力。首先通過遺傳算法在解集中獲取較優(yōu)解，其次通過粒子群優(yōu)化對(duì)包含較優(yōu)解的集合進(jìn)行隨機(jī)擾動(dòng)，從而避免陷入局部最優(yōu)解的情況。通過該算法的求解后，可以得到一個(gè)包含最優(yōu)解的解集，其中的個(gè)體相較于傳統(tǒng)的采用單一算法進(jìn)行求解的結(jié)果，具有適應(yīng)度更高、收斂速度更快、誤差更小的優(yōu)勢，在并行度較高的柔性制造系統(tǒng)中可以最大化地提升資源利用率，優(yōu)化企業(yè)在生產(chǎn)過程中的調(diào)度方式。

參考文獻(xiàn)（References）

［1］張寧，林海華，孫亞平，等.魚雷裝備測試維修Petri網(wǎng)模型與指標(biāo)論證分析［J］.兵工學(xué)報(bào)，2023，44（3）：886＼|894.

［2］閆哲，劉偉，杜玉越.基于邏輯博弈概率Petri網(wǎng)的地鐵應(yīng)急決策建模與分析［J］.系統(tǒng)仿真學(xué)報(bào)，2023，35（7）：1602＼|1618.

［3］賈云富，張凱.基于Petri網(wǎng)的機(jī)床座類柔性生產(chǎn)線調(diào)度模型［J］.機(jī)電工程，2022，39（10）：1470＼|1476.

［4］王慧英，周愷卿，周輝.基于約束優(yōu)化的Petri網(wǎng)可達(dá)性FU模型［J］.計(jì)算機(jī)仿真，2022，39（6）：408＼|411，416.

［5］樊海剛，郭紅梅，張瑩，等.隨機(jī)Petri網(wǎng)在地震應(yīng)急協(xié)同能力定量評(píng)價(jià)與動(dòng)態(tài)分析中的應(yīng)用［J］.中國地震，2022，38（2）：248＼|259.

［6］徐海軍，李彥斌，王進(jìn)，等.基于模糊Petri網(wǎng)的有載分接開關(guān)故障診斷方法研究［J］.中國安全生產(chǎn)科學(xué)技術(shù)，2022，18（5）：222＼|228.?;

［7］YANGR，WUM，GUIXQ，etal.IntelligentconflictdetectionofIoTservicesusinghigh＼|levelPetrinets［J］.Complex&intelligentsystems，2024，10（3）：3789＼|3817.

［8］KABASHKINI，SANSYZBAYEVAZ.Methodologicalframeworkforsustainabletransportcorridormodelingusingpetrinets［J］.Sustainability，2024，16（2）：489.

［9］CUIYY，MALY，DINGQM，etal.AircraftturnaroundtimedynamicpredictionbasedonTimeTransitionPetriNet［J］.PLoSone，2024，19（7）：e0305237.