基于擴(kuò)展Petri網(wǎng)的飛機(jī)裝配系統(tǒng)設(shè)備調(diào)度方法*

（南京理工大學(xué)機(jī)械工程學(xué)院，南京 210094）

飛機(jī)零部件數(shù)量較多且裝配過(guò)程復(fù)雜，涉及設(shè)備資源較多，有效的建模方法和設(shè)備調(diào)度優(yōu)化策略能夠很好地縮短生產(chǎn)周期并降低成本。目前對(duì)于飛機(jī)裝配建模方法的研究主要包括Petri網(wǎng)、面向?qū)ο?、排?duì)網(wǎng)絡(luò)、事件驅(qū)動(dòng)鏈[1-4]等。文獻(xiàn)[5]提出了基于面向?qū)ο蟮膹?fù)雜產(chǎn)品裝配建模方法，描述了裝配過(guò)程中的主要對(duì)象類及其關(guān)系；張杰等[6]以Petri網(wǎng)為基礎(chǔ)，探討了飛機(jī)裝配系統(tǒng)層次化建模方法，并進(jìn)行鎖死分析，但Petri網(wǎng)存在組合爆炸問(wèn)題需要改進(jìn)；徐開(kāi)元等[7]探討了飛機(jī)分層裝配線、裝配資源模型的構(gòu)建。但是，上述研究更多注重裝配線流程及布局的改善，涉及飛機(jī)裝配設(shè)備調(diào)度優(yōu)化方面較少。

基于此，本文根據(jù)飛機(jī)裝配工藝?yán)妹嫦驅(qū)ο驪etri網(wǎng)（Object-Oriented Petri Nets，OOPN）建立飛機(jī)裝配模型并構(gòu)建裝配元邏輯關(guān)系，將模型高度抽象化模塊化[8]。在OOPN裝配模型基礎(chǔ)上以賦時(shí)Petri網(wǎng)（Timed Petri Nets，TPN）構(gòu)建并擴(kuò)展裝配元-裝配設(shè)備-體化模型，形成擴(kuò)展Petri網(wǎng)（Object-Oriented Timed Petri Nets，OTPN），并以裝配元變遷為基礎(chǔ)，嵌入混合算法用以解決裝配元設(shè)備調(diào)度優(yōu)化問(wèn)題。

1 OTPN定義

1.1 OOPN模型定義

OOPN建模的基本構(gòu)造是對(duì)象，對(duì)象將數(shù)據(jù)結(jié)構(gòu)與行為集成為一個(gè)相對(duì)獨(dú)立的實(shí)體，可表示為S={Ob,R}，此方法能夠抽象化、模塊化裝配單元，且易于理解。其中Ob為系統(tǒng)的對(duì)象集合；R為系統(tǒng)中對(duì)象的關(guān)系集合。Obi和Rij分別定義為：

式中，SPi表示Obi狀態(tài)庫(kù)所的集合；ATi表示Obi活動(dòng)變遷的集合；IMi表示Obi輸入信息庫(kù)所的集合；OMi表示Obi輸出信息庫(kù)所的集合； Ii為輸入映射；Oi為輸出映射；Ci為顏色集；gij表示從Obi到Obj的信息傳遞的門(mén)的集合；Iij表示從OMi到gij的弧集，理解為輸入函數(shù)；Oij表示從gij到IMj的弧集，理解為輸出函數(shù)。

飛機(jī)裝配OOPN模型構(gòu)建主要包括元對(duì)象模型構(gòu)建和邏輯對(duì)象模型構(gòu)建。元對(duì)象是指裝配系統(tǒng)中可模塊化的作業(yè)實(shí)體映射到OOPN中的模型對(duì)象，分為裝配功能元對(duì)象與輔助裝配元對(duì)象。元對(duì)象模型構(gòu)建主要包括內(nèi)部框架（OPN）與信息協(xié)議（OMP）兩部分內(nèi)容，模型構(gòu)建方法如下：

步驟1：按照飛機(jī)裝配工藝對(duì)模型進(jìn)行層次劃分；

步驟2：將飛機(jī)裝配工序轉(zhuǎn)換為OPN變遷序列；

步驟3：變遷序列中融入庫(kù)所，形成狀態(tài)庫(kù)所集；

步驟4：將裝配作業(yè)資源賦予相應(yīng)工序變遷，形成資源庫(kù)所集合；

步驟5：連接內(nèi)部變遷與庫(kù)所，形成OPN模型；

步驟6：建立各個(gè)邏輯門(mén)Gi，整合元對(duì)象的IMi和OMi形成 OMP；

步驟7：依據(jù)門(mén)變遷和關(guān)系集，對(duì)元對(duì)象的進(jìn)一步組合形成邏輯對(duì)象，如圖1所示；

步驟8：建立初始標(biāo)識(shí)Mo，表示出所有庫(kù)所的初始標(biāo)識(shí)。

1.2 OTPN模型構(gòu)建

TPN是在基本Petri網(wǎng)中融入時(shí)間因素，可用于描述含有時(shí)間因子的制造系統(tǒng)模型，對(duì)于設(shè)備調(diào)度有著較好的指導(dǎo)意義，定義為T(mén)P=（P,T），其中P為基本Petri網(wǎng)，T為變遷ti的時(shí)間集合。

實(shí)際飛機(jī)裝配OOPN模型中設(shè)備資源的使用沖突分為兩類：多個(gè)裝配單元請(qǐng)求同一設(shè)備；某個(gè)裝配變遷的完成可有多種設(shè)備選擇方案。為此首先建立裝配元-裝配設(shè)備關(guān)系表，用來(lái)描述各個(gè)裝配元可以由哪些設(shè)備來(lái)完成，以及設(shè)備在完成裝配的時(shí)間，如表1所示。

表1 裝配元-裝配設(shè)備關(guān)系表

圖1 邏輯對(duì)象Fig.1 Logical objects

表 1 中，t1表示裝配變遷，m1、m2、m3、m4表示設(shè)備，從表1可得裝配變遷有3種設(shè)備選擇方案，第一種方案m1設(shè)備耗時(shí)5個(gè)工時(shí)，m3耗時(shí)7個(gè)工時(shí)。

利用裝配元-裝配設(shè)備關(guān)系表對(duì)裝配元變遷進(jìn)行擴(kuò)展并建立設(shè)備選擇庫(kù)所集，形成變遷TPN模型。模型包括的信息為設(shè)備配置方案（見(jiàn)表1），庫(kù)所與配置方案相對(duì)應(yīng)。實(shí)際裝配過(guò)程中，只有一種設(shè)備配置方案被選中，故庫(kù)所集中只有一個(gè)庫(kù)所托肯數(shù)是1。

將變遷TPN模型整合融入飛機(jī)裝配OOPN模型中形成OTPN模型，圖2表示對(duì)裝配元變遷t1擴(kuò)展形成的OTPN模型。

2 混合算法設(shè)計(jì)

設(shè)備調(diào)度涉及因素較多，屬于典型的NP問(wèn)題[9]。依據(jù)OTPN模型中的裝配元變遷序列及其設(shè)備庫(kù)所選擇集，在遺傳算法中（Genetic Algorithm，GA）引入模擬退火算法（Simulated annealing Algorithm，SA），從選擇庫(kù)所集中選擇最佳配置方案，進(jìn)而提高設(shè)備利用率，減少裝配時(shí)間，算法流程如圖3所示。

混合算法從算法機(jī)制、結(jié)構(gòu)、操作等方面融合了單一算法的缺點(diǎn)，能夠擴(kuò)充全局空間并增大搜索能力，有效克服初值依賴性、過(guò)早收斂等缺陷，同時(shí)引入自適應(yīng)交叉和變異概率，使算法在優(yōu)化過(guò)程中避免盲目交叉從而提高搜索效率[10-11]。

2.1 染色體編碼

編碼是將飛機(jī)裝配系統(tǒng)中的設(shè)備使用順序依照裝配元變遷映射到染色體上。從每個(gè)裝配元的多個(gè)配置方案中選擇一個(gè)作為基因，所有被選擇的配置方案按序排列，形成一條染色體。

圖2 裝配元變遷OTPN模型Fig.2 OTPN model of assembly element transition

2.2 適應(yīng)度函數(shù)

本文以裝配元裝配完成時(shí)間和輔助設(shè)備利用率為優(yōu)化目標(biāo)。裝配時(shí)間指的是以選定的設(shè)備配置方案配置裝配元進(jìn)行裝配操作，完成A-OOPN模型中所有裝配的時(shí)間。設(shè)備利用率UT是指設(shè)備實(shí)際工作時(shí)間與全部工作時(shí)間的比值，是一個(gè)隨時(shí)間變化的離散統(tǒng)計(jì)量，定義為：

式中，B（t）代表工作時(shí)間，t代表時(shí)刻。

2.3 選擇算子

選擇操作用于優(yōu)勝劣汰，這里選用輪盤(pán)賭的方法，即每個(gè)個(gè)體被選中的概率與適應(yīng)度函數(shù)值的大小成比例關(guān)系。設(shè)種群大小為N，個(gè)體xi適應(yīng)度為f(xi)，則個(gè)體xi被選中的概率為：

圖3 混合算法流程Fig.3 Flow of hybrid algorithm

2.4 模擬退火算法規(guī)劃

為避免過(guò)早收斂，在GA中引入SA，運(yùn)用Metropolis準(zhǔn)則判斷是否產(chǎn)生并選擇新的個(gè)體。Metropolis準(zhǔn)則依照公式（6）對(duì)經(jīng)過(guò)GA算法的新個(gè)體進(jìn)行篩選，具體公式如下：

式中，Q表示SA溫度；Δf表示當(dāng)前新個(gè)體與原個(gè)體適應(yīng)度值之差，若Δf＞0，則以概率1接受更好的個(gè)體。將當(dāng)前最優(yōu)解與下一代比較并進(jìn)行退溫操作Qk=aQk-1，再返回遺傳算法直至滿足終止迭代條件。SA中的初始溫度值越大，獲得優(yōu)秀解的概率越大，但所需運(yùn)算時(shí)間也越長(zhǎng)，所以初溫設(shè)置從運(yùn)算效率與優(yōu)化效果兩方面進(jìn)行考慮。

3 實(shí)例應(yīng)用與分析

機(jī)身裝配涵蓋了飛機(jī)裝配的眾多特性，如串行裝配和并行裝配等，是脈動(dòng)生產(chǎn)線的重要環(huán)節(jié)。論文以某型號(hào)飛機(jī)中機(jī)身裝配過(guò)程為對(duì)象，建立OTPN模型并對(duì)裝配設(shè)備進(jìn)行調(diào)度優(yōu)化，由于其并行裝配為主，故存在眾多設(shè)備資源的競(jìng)爭(zhēng)使用。中機(jī)身裝配元信息見(jiàn)表2。

裝配元涉及的公共資源有4個(gè)，1個(gè)輸送平臺(tái)m1，2套工業(yè)夾具m2和m3，1輛小車m4。裝配順序及其設(shè)備關(guān)系如表 3 所示，裝配元變遷T={T11，T12，T13，T14，T15，T16，T17，T18}對(duì)應(yīng)表 3 中裝配 {1，2，3，4，5,6，7，8}。

表2 中機(jī)身裝配元信息

表3 裝配設(shè)備關(guān)系表

表3中每個(gè)裝配可能有多個(gè)選擇，例如裝配2有兩種配置方案，分別是方案2.1和2.2。中機(jī)身OTPN模型如圖4所示。

為保證群體多樣性及進(jìn)化能力，在計(jì)算量許可情況下，混合算法參數(shù)設(shè)計(jì)如下：種群個(gè)體數(shù)目N為80個(gè)，代溝G為0.9，交叉概率Pc為0.9，變異概率Pm為0.05，進(jìn)化代數(shù)100，模擬退火冷卻系數(shù)q為0.9，終止溫度Tend為0.001℃，退溫次數(shù)為50。以上面參數(shù)為依據(jù)，以MATLAB為工具計(jì)算分析，算法求解收斂曲線如圖5所示。

從圖5中可發(fā)現(xiàn)，算法經(jīng)過(guò)50代完成運(yùn)算求解過(guò)程。與單一算法相比較，混合算法收斂較為平緩，相對(duì)GA算法避免了早熟，相對(duì)SA算法能控制求解方向并進(jìn)行全局搜索，且具有較快的搜索效率。

圖4 中機(jī)身OTPN模型Fig.4 Fuselage OTPN model

圖5 混合算法求解收斂曲線Fig.5 Convergence curve of hybrid algorithm solving

表4 試驗(yàn)運(yùn)算結(jié)果

圖6 設(shè)備調(diào)度順序圖Fig.6 Diagram of equipment scheduling sequence

為避免隨機(jī)等因素干擾，本次試驗(yàn)運(yùn)算40次，結(jié)果如表4所示。從表4可得，其中1次獲得工時(shí)76，1次獲得工時(shí)77，38次獲得工時(shí)74，平均利用率為50.68%，工作時(shí)間設(shè)備1、設(shè)備2、設(shè)備3、設(shè)備4分別為 54、34、40、22。最佳染色體為P={P1，P2.2，P3.1，P4.1，P5.1，P6.2，P7.1，P8.1}，Pi.k表示第i個(gè)裝配的第k種方案。調(diào)度結(jié)果如圖6所示，Td表示工序， 對(duì)甘特圖分析可得，夾具設(shè)備是生產(chǎn)作業(yè)瓶頸。

4 結(jié)束語(yǔ)

針對(duì)飛機(jī)裝配過(guò)程設(shè)備調(diào)度的復(fù)雜性，提出了將面向?qū)ο驪etri網(wǎng)與賦時(shí)Petri網(wǎng)相結(jié)合構(gòu)建設(shè)備調(diào)度模型的新方法，該方法能夠有效地將裝配元變遷與輔助設(shè)備關(guān)聯(lián)，且有效解決了模型的“空間爆炸問(wèn)題”。同時(shí)在TPN模型中嵌入混合算法，利用裝配元變遷和裝配元設(shè)備庫(kù)所集為染色體編碼，以多目?jī)?yōu)化為基礎(chǔ)對(duì)設(shè)備調(diào)度進(jìn)行求解。實(shí)例應(yīng)用與分析表明算法可行，能夠縮短裝配時(shí)間。本文下一步將繼續(xù)研究OTPN模型中裝配發(fā)生意外變更時(shí)設(shè)備調(diào)度的相關(guān)問(wèn)題。

參 考 文 獻(xiàn)

[1] 孫星.基于Petri網(wǎng)和eM-Plant的飛機(jī)裝配線建模與仿真研究[D].南京：南京航空航天大學(xué),2011.

SUN Xing. Modeling and simulation of aircraft assembly line based on Petri net and eM-Plant[D]. Nanjing: Nanjing University of Aeronautics &Astronautics, 2011.

[2] XU K, WANG C, ZHANG W, et al. Object-oriented aircraft assembly model[C]//International Conferece on Computer, Networks and Communication Engineering, Beijing, 2013.

[3] 謝志強(qiáng)，辛宇，楊靜. 基于設(shè)備空閑事件驅(qū)動(dòng)的綜合調(diào)度算法[J]. 機(jī)械工程學(xué)報(bào), 2011, 47(11):139-147.

XIE Zhiqiang, XIN Yu, YANG Jing. Integrated scheduling algorithm based on event-driven by machines’ idle[J]. Journal of Mechanical Engineering, 2011, 47(11):139-147.

[4] 孔令革，魯建廈，詹燕.基于排隊(duì)網(wǎng)絡(luò)的生產(chǎn)物流瓶頸轉(zhuǎn)移研究[J]. 浙江工業(yè)大學(xué)學(xué)報(bào)，2011，39(6): 644-647.

KONG Lingge, LU Jiansha, ZHAN Yan. Study on bottleneck shifting of production logistics based on queueing networks[J]. Journal of Zhejiang University of Technology, 2011, 39(6):644-647.

[5] 王成恩，于宏，張聞雷，等. 面向?qū)ο蟮暮娇瞻l(fā)動(dòng)機(jī)裝配模型[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2010，16(5):942-948.

WANG Cheng’en, YU Hong, ZHANG Wenlei, et al. Object-oriented aero-engine assembly models[J]. Computer Integrated Manufacturing Systems, 2010, 16(5): 942-948.

[6] 張杰，李原，張開(kāi)富，等. 基于關(guān)系對(duì)象Petri網(wǎng)的飛機(jī)裝配系統(tǒng)模型快速構(gòu)建方法[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2010，16(6): 1195-1201.

ZHANG Jie, LI Yuan, ZHANG Kaifu, et al. Rapid modeling method for aircraft assembly system based on relation-based object Petri nets[J].Computer Integrated Manufacturing Systems, 2010, 16(6):1195-1201.

[7] 徐開(kāi)元，曲蓉霞，王健熙. 基于多域集成Petri網(wǎng)的飛機(jī)裝配系統(tǒng)模型[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2015，21(8): 2022-2032.

XU Kaiyuan, QU Rongxia, WANG Jianxi. An aircraft assembly system model based on multi domain integrated Petri net[J]. Computer Integrated Manufacturing System, 2015, 21(8): 2022-2032.

[8] 顧妍午，王遵彤，吳啟迪. 面向?qū)ο驪etri網(wǎng)技術(shù)在系統(tǒng)建模中的應(yīng)用[J]. 同濟(jì)大學(xué)學(xué)報(bào)（自然科學(xué)版），2010，38(3): 437-441.

GU Yanwu, WANG Zuntong, WU Qidi. Application of object oriented Petri net technology in system modeling[J]. Journal of Tongji University(Natural Science Edition), 2010, 38(3): 437-441.

[9] 劉維來(lái)，孔凡讓，劉志剛，等. 基于遺傳算法和延時(shí)Petri網(wǎng)的柔性裝配系統(tǒng)的設(shè)備調(diào)度方法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2006,12(8): 1246-1251.

LIU Weilai, KONG Fanrang, LIU Zhigang, et al. Facilities assignments of flexible assembly system based on GA and TPN[J]. Computer Integrated Manufacturing Systems, 2006, 12(8): 1246-1251.

[10] 彭勇剛，羅小平，韋巍. 一種新的模糊自適應(yīng)模擬退火遺傳算法[J]. 控制與決策, 2009, 24(6): 843-848.

PENG Yonggang, LUO Xiaoping, WEI Wei. A new fuzzy adaptive simulated annealing genetic algorithm[J]. Control & Decision, 2009, 24(6):843-848.

[11] 楊萌, ALMAINI A E A. 基于整體退火遺傳算法的最佳混合極性搜索[J]. 復(fù)旦學(xué)報(bào)（自然科學(xué)版）, 2013, 52(3):303-308.

YANG Meng, ALMAINI A E A. Optimization of mixed polarity reedmuller functions based on whole annealing genetic algorithm[J]. Journal of Fudan University (Natural Science), 2013, 52(3): 303-308.