工藝約束條件下加工順序決策的Petri網(wǎng)T_不變量方法

肖偉躍 羅佑新 廖德崗

湖南文理學(xué)院,常德,415000

0 引言

加工順序決策(即工藝路線決策)是在加工方法決策(即加工鏈決策)的基礎(chǔ)上進(jìn)行的。由于加工順序決策影響因素多、針對性強(qiáng)、涉及面寬、綜合性廣,所以迄今為止都沒有得到很好的解決,成為制約工藝設(shè)計自動化的瓶頸。就創(chuàng)成方法而言,以往的研究大致可以歸納為三種方法：一是將加工順序決策看成是分層次、分階段的約束驅(qū)動過程或者是將決策任務(wù)劃分成若干個決策子任務(wù)的分解合并過程[1-3];二是工藝決策過程的AOV網(wǎng)(activity on vertex network)表示及其拓?fù)渑判蚍椒?或者是以加工工序間的優(yōu)先約束關(guān)系為基礎(chǔ)的加工序列優(yōu)化綜合方法[4-5];三是基于人工神經(jīng)網(wǎng)絡(luò)、基于遺傳算法、基于模擬退火算法等的工藝決策與優(yōu)化方法。第一種方法由于難以提取和表達(dá)獨(dú)立的工藝知識模塊、排序方法與工藝人員思維習(xí)慣不符等問題而導(dǎo)致決策邏輯的實(shí)現(xiàn)存在許多困難[6];第二種方法因?yàn)樾枰_定工藝約束的優(yōu)先關(guān)系,但這種關(guān)系很難根據(jù)工藝知識自動構(gòu)成[6];第三種方法基本還處于理論探索階段,還鮮有實(shí)際的工程應(yīng)用[5]。除此之外,也有基于相似性原理以及基于實(shí)例的工藝路線決策方法,但其應(yīng)用范圍過于狹窄,且零件聚類和實(shí)例提取仍存在問題,當(dāng)然這也不屬于創(chuàng)成方法范疇。

盡管人類目前還不能實(shí)現(xiàn)工藝設(shè)計的完全自動化,但并不排斥對自動工藝決策的探索與追求。由于Petri網(wǎng)易于表達(dá)離散事件動態(tài)系統(tǒng)中系統(tǒng)變化發(fā)生的條件以及變化發(fā)生后的系統(tǒng)狀態(tài),而機(jī)械制造工藝系統(tǒng)又是典型的離散事件系統(tǒng),所以已有學(xué)者將Petri網(wǎng)應(yīng)用于工藝設(shè)計領(lǐng)域,但一般主要是應(yīng)用Petri網(wǎng)來求解加工方法決策問題[7-8],很少有文獻(xiàn)報道Petri網(wǎng)在加工順序決策研究中的應(yīng)用。針對此,本文嘗試采用Petri網(wǎng)來求解加工順序決策問題。首先根據(jù)Petri網(wǎng)原理和產(chǎn)生式規(guī)則建立了一個基于規(guī)則的加工順序決策Petri網(wǎng)模型;然后根據(jù)Petri網(wǎng)T_不變量在考慮工藝約束的條件下,提出了一種新的可選工藝路線T_不變量生成方法;最后通過一個軸套類零件驗(yàn)證了所提方法的有效性。

1 Petri網(wǎng)系統(tǒng)與加工順序決策Petri網(wǎng)模型

1.1 普通Petri網(wǎng)系統(tǒng)

定義1 一個普通Petri網(wǎng)系統(tǒng)PN定義為五元組[7],即 PN=(P,T,I,O,M)。其中,P是PN的有限庫所集,P={p1,p 2,…,p n};T是PN的有限 變遷 集,T ={t1,t2,…,tm}, 且P∩T= ,P∪T ;I是PN中從庫所到變遷的有向弧集,I：P×T→{0,1};O是PN中從變遷到庫所的有向弧集,O：T×P→{0,1};M是PN的標(biāo)識函數(shù),其中M0是初始標(biāo)識,M 0：P →{0,1,2,…}。

在普通Petri網(wǎng)系統(tǒng)中,變遷使能與激發(fā)的規(guī)則是：①變遷t∈T在標(biāo)識M 下使能記為M[t＞,其充要條件是,?p∈P：M(p)＞0∧I(p,t)=1;②變遷t∈T在標(biāo)識M下激發(fā)并到達(dá)新標(biāo)識M′記為M[t＞M′,則新標(biāo)識M′是,?p∈ P ：M′(p)=M(p)+O(t,p)-I(p,t)。

將定義1表示為圖形時,用圓圈表示庫所,用矩形框表示變遷,用帶箭頭的弧線表示輸入輸出關(guān)系,用圓圈中的黑點(diǎn)表示p i中的資源個數(shù),稱之為托肯(Token)。在Petri網(wǎng)系統(tǒng)中,系統(tǒng)的靜態(tài)特性由網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行描述,系統(tǒng)的當(dāng)前狀態(tài)由托肯在庫所中的分布決定,而系統(tǒng)的動態(tài)行為則通過托肯的移動和傳播進(jìn)行控制。

1.2 基于規(guī)則的加工順序決策Petri網(wǎng)模型

在工藝設(shè)計領(lǐng)域,工藝決策知識的表達(dá)方法有多種形式,但表達(dá)能力較強(qiáng)、應(yīng)用范圍較廣的兩種主要形式還是傳統(tǒng)的基于規(guī)則的方法和基于框架的方法。通過對比分析和研究表明,在基于規(guī)則的方法與基于Petri網(wǎng)的方法之間存著明確的對應(yīng)關(guān)系[9]。若將產(chǎn)生式規(guī)則系統(tǒng)映射為Petri網(wǎng)系統(tǒng),則輸入庫所代表前提,輸出庫所代表結(jié)論;托肯代表當(dāng)前事實(shí),標(biāo)識代表當(dāng)前事實(shí)庫,標(biāo)識的變化代表著事實(shí)庫的更新;變遷代表規(guī)則,變遷序列代表基于規(guī)則的推理過程。由此可以給出如下定義：

定義2 一個基于規(guī)則的加工順序決策Petri網(wǎng)模型PD_PN定義為五元組,即PD_PN=(P,T,I,O,M)。其中,P是PD_PN的有限庫所集,P={P op∪P pc},P op代表加工工序庫所子集,P pc代表工藝約束庫所子集。

T的基本含義與定義1相同,一個變遷表示一條規(guī)則,變遷激發(fā)表示規(guī)則啟用;I的基本含義與定義1相同,由輸入庫所指向變遷,表示規(guī)則前提;O的基本含義與定義1相同,由變遷指向輸出庫所,表示規(guī)則結(jié)論;M是PD_PN的標(biāo)識函數(shù),M={Mop∪Mpc}→{0,1},Mop是對應(yīng)于Pop的標(biāo)識,M pc是對應(yīng)于P pc的標(biāo)識。

根據(jù)定義2,一個基于規(guī)則的加工順序決策Petri網(wǎng)單元模型如圖1所示。

圖1 基于規(guī)則的 Petri網(wǎng)單元模型(無自環(huán))

在圖1中,I(t)={p op i,p pc},O(t)={p op k}。當(dāng)輸入庫所含有托肯并使變遷激發(fā)后,托肯就會從輸入庫所移動到輸出庫所。由于圖1所示的單元模型不帶“自環(huán)”,且任一庫所中的托肯數(shù)量只能是0或1,故而由此組成的Petri網(wǎng)系統(tǒng)是單純網(wǎng)并且是安全的,這將有利于后續(xù)可選加工路線生成的T_不變量分析。然而,網(wǎng)系統(tǒng)中的變遷一旦激發(fā),該變遷的所有輸入庫所都會失去托肯,這將使對應(yīng)于加工工序庫所的最終標(biāo)識M op不再包含已激發(fā)變遷的輸入庫所和輸出庫所。為此,需要對模型進(jìn)行必要的修正,可以考慮在圖1中增加一條由變遷指向加工工序輸入庫所的有向弧,從而形成圖2所示的帶有“自環(huán)”的單元模型,這樣在變遷激發(fā)之后,該庫所仍然保留有托肯。

圖2 基于規(guī)則的 Petri網(wǎng)單元模型(帶自環(huán))

2 可選工藝路線生成的T_不變量方法

2.1 狀態(tài)方程與T_不變量[10]

定義3 設(shè)PN為一個Petri網(wǎng),P={p1,p2,…,p n},T={t1,t2,…,tm},則PN 的網(wǎng)結(jié)構(gòu)(P,T,F)(F?(P×T)∪(T×P))可以用一個n行m列矩陣An×m來表示,該矩陣稱為關(guān)聯(lián)矩陣,表達(dá)式如下：

如果將Petri網(wǎng)的標(biāo)識用一個非負(fù)整數(shù)向量來表示,利用關(guān)聯(lián)矩陣就可以將M0[τ＞M這一事實(shí)寫成矩陣方程M 0+AJ=M。其中的τ是將M 0變換為M的變遷序列,M 0和M則成為PN中以庫所集P為序標(biāo)集的列向量,而J是PN中以變遷集T為序標(biāo)集的列向量。該方程稱為狀態(tài)方程,Murata[11]已經(jīng)證明凡是可達(dá)的標(biāo)識必定滿足狀態(tài)方程。

定義4 設(shè)PN為一個Petri網(wǎng),P={p 1,p 2,…,pn},T={t1,t2,…,tm},An×m是PN 的關(guān)聯(lián)矩陣,如果存在非零解的m維非負(fù)整數(shù)列向量J滿足方程An×mJm×1=0,n=|P|,m=|T|,則稱J為PN的一個T_不變量。

根據(jù)定義3和定義4,一個T_不變量就是一個整數(shù)系數(shù)線性方程組的非負(fù)整數(shù)解(全零向量除外)。所以一個T_不變量就意味著存在一個與之對應(yīng)的變遷序列t1,t2,…,tk,使得網(wǎng)系統(tǒng)從初始標(biāo)識M0開始,經(jīng)過該變遷序列之后,其后續(xù)標(biāo)識M又重新恢復(fù)到初始標(biāo)識M 0。T_不變量的存在表明網(wǎng)系統(tǒng)具有對系統(tǒng)狀態(tài)的復(fù)制能力,而此T_不變量中各分量的值就決定了各個變遷的發(fā)生次數(shù)。

2.2 基于T_不變量的可選工藝路線生成算法

由定義2、定義3和定義4可知,根據(jù)方程AJ=0求得的一個 T_不變量就表明Petri網(wǎng)中存在一個變遷序列,而由該變遷序列中所有分量為1的各個變遷的輸入輸出加工庫所鏈接而成的庫所序列就代表了零件的一條工藝路線。因此,為了獲得被加工零件的可選工藝路線,需要完成以下三個步驟的工作：

(1)構(gòu)建決策Petri網(wǎng)模型。根據(jù)加工排序規(guī)則集以及規(guī)則集與Petri網(wǎng)間的映射關(guān)系構(gòu)建加工順序決策Petri網(wǎng)模型PD_PN。該模型中所有的加工工序庫所均帶有自環(huán)(圖2)。

(2)化簡決策Petri網(wǎng)模型。根據(jù)零件特征信息和PD_PN模型,確定工藝約束庫所和加工工序庫所并進(jìn)行初始標(biāo)識。在初始標(biāo)識狀態(tài)下系統(tǒng)激發(fā),當(dāng)系統(tǒng)運(yùn)行結(jié)束后就可從最終標(biāo)識中獲得所有已激發(fā)的變遷。為了降低模型規(guī)模,減少運(yùn)算時間,可以刪除模型中所有的工藝約束庫所,刪除所有未激發(fā)的變遷以及相應(yīng)的輸入輸出庫所,從而得到簡化了的決策Petri網(wǎng)模型SPD_PN。

(3)T_不變量分析與計算。在進(jìn)行T_不變量計算之前,還需對模型進(jìn)行適當(dāng)?shù)男薷暮驼{(diào)整。一方面是由于T_不變量的代數(shù)計算只能應(yīng)用于單純網(wǎng),而SPD_PN帶有“自環(huán)”,所以應(yīng)將模型中輸入庫所與變遷之間帶有自環(huán)的雙向箭頭改為僅指向變遷的單向箭頭;另一方面是為了讓系統(tǒng)循環(huán)運(yùn)行以便于獲取全部T_不變量,這可以通過在初始庫所與每一個葉庫所之間增加一個循環(huán)變遷t′來實(shí)現(xiàn),如圖3所示。

由上述三個步驟可以獲得多個T_不變量。一個T_不變量對應(yīng)一條工藝路線,多個T_不變量就對應(yīng)多條工藝路線。這就使零件的工藝路線選擇從原理上成為可能,其具體的生成算法如下：

(1)根據(jù)規(guī)則集及其映射關(guān)系構(gòu)建加工順序決策Petri網(wǎng)模型PD_PN。

(2)對加工順序決策 Petri網(wǎng)模型進(jìn)行初始標(biāo)識。①根據(jù)零件信息對工藝約束庫所進(jìn)行初始標(biāo)識,得到M pc0;②使初始加工工序庫所p op0獲得一個托肯,其他加工工序庫所均為零,得到加工工序庫所的初始標(biāo)識 M op0,即 M op0(p op0)=1 and M op0(p op j)=0,j≥1。

(3)在初始標(biāo)識M0={Mop0∪Mpc0}下,獲取具有使能的變遷子集T enb,并設(shè)T new=T enb。

(4)如果 T enb=?,則生成算法結(jié)束;如果Tenb≠?,則轉(zhuǎn)到(5)。

(5)激發(fā)T new中的所有變遷,并計算后續(xù)標(biāo)識M,則M(pk)=M(pk)+O(pk,t)-I(pk,t),?p k∈{P op∪P pc}。

(6)在后續(xù)標(biāo)識M下,獲取具有使能的新變遷集 T new。如果T new=?,則轉(zhuǎn)到(7);如果T new≠?,則使T enb={T enb+T new},并返回到(5)。

(7)根據(jù) M0和 T enb對 Petri網(wǎng)模型進(jìn)行化簡。①將模型中所有的雙向箭頭更改為指向變遷的單向箭頭;②刪除模型中所有的約束庫所;③刪除模型中沒有在Tenb中出現(xiàn)的變遷及其相連的輸出庫所。

(8)在初始庫所與所有的葉庫所之間增加一個循環(huán)變遷t′,形成一個簡化的加工順序決策Petri網(wǎng)模型SPD_PN。

(9)根據(jù)M 0和 T enb,計算關(guān)聯(lián)矩陣A。

(10)根據(jù)公式AJ=0,計算簡化模型中所有的T_不變量(全零向量除外)。

(11)根據(jù)每一個T_不變量,求出與之對應(yīng)的庫所序列,則每一個庫所序列就代表了一條工藝路線,全部的工藝路線就構(gòu)成了一個被加工對象的工藝路線集合PR。

(12)根據(jù)實(shí)際生產(chǎn)情況,在PR中選取一條工藝路線作為實(shí)際的工藝路線,其他作為備選的工藝路線。

3 實(shí)例分析與驗(yàn)證

根據(jù)上文提出的基于Petri網(wǎng)的工藝路線生成算法,本節(jié)以軸套類零件的加工順序決策為例,說明在加工方法決策的基礎(chǔ)上采用Petri網(wǎng)模型生成可選工藝路線的T_不變量方法,其他軸類、盤套類、齒輪類、箱體類等零件的工藝路線可以參考本文所提出的方法進(jìn)行計算。

3.1 軸套類零件的加工順序決策及其Petri網(wǎng)模型

根據(jù)機(jī)械制造工藝?yán)碚摵洼S套類零件加工的基本規(guī)律,具有經(jīng)濟(jì)加工精度的普通軸套類零件(包括有色金屬材料)常規(guī)加工工藝規(guī)則如表1所示。在實(shí)際應(yīng)用時,表1中規(guī)則可根據(jù)零件結(jié)構(gòu)差異和工藝習(xí)慣不同進(jìn)行修改和調(diào)整。為節(jié)省篇幅和簡化規(guī)則,表1中的工藝約束只列出了工序條件和設(shè)備條件,而且工序條件省略了IT、Ra、熱處理等約束內(nèi)容。對于鉆孔、鉆鉸孔、鉆擴(kuò)鉸孔、銑鍵槽和銑平面等工序,將其簡化為一個工序(實(shí)際并非如此),并且未列出軸套類零件的精密加工、超精密加工以及特種加工工序)。

表1 軸套類零件常規(guī)加工工藝規(guī)則

根據(jù)表1所列出的軸套類零件常規(guī)加工工藝規(guī)則和定義2,可以得到基于Petri網(wǎng)的軸套類零件加工順序決策模型,如圖4所示。

圖4 基于Petri網(wǎng)的軸套類零件加工順序決策模型

3.2 基于T_不變量的軸套類零件可選工藝路線生成

圖5 是一個軸套類零件,圖6是對應(yīng)于圖5并根據(jù)圖4和第2節(jié)的生成算法,在初始標(biāo)識下網(wǎng)系統(tǒng)運(yùn)行后得到的實(shí)例零件可選工藝路線Petri網(wǎng)簡化模型。

圖5 一個軸套類零件

圖6 實(shí)例零件可選工藝路線Petri網(wǎng)簡化模型

根據(jù)定義3得到的實(shí)例零件關(guān)聯(lián)矩陣A10×11 為

根據(jù)定義4的A10×11J11×1=0計算實(shí)例零件所有的T_不變量(計算從略)：

在兩個T_不變量中,由分量為1的變遷庫所對應(yīng)的輸入和輸出加工庫所連接而成的庫所鏈即為實(shí)例零件的加工工藝路線,即：

(1)毛坯(鍛造)—退火或正火 —粗車 —半精車 —鉆鉸孔 —銑平面 —淬火 —磨平面 —磨削;

(2)毛坯(鍛造)—退火或正火 —粗車 —半精車 —鉆鉸孔 —銑平面 —淬火—磨平面—粗磨 —精磨。

在兩條工藝路線中選擇一條作為實(shí)例零件的實(shí)際加工路線,另外一條工藝路線作為該零件的備選加工方案。

4 結(jié)論

(1)采用Petri網(wǎng)T_不變量方法和產(chǎn)生式規(guī)則能夠?qū)崿F(xiàn)工藝約束條件下的加工順序決策,并通過實(shí)例驗(yàn)證了基于T_不變量的可選工藝路線生成算法的合理性和有效性。與傳統(tǒng)的方法相比較,本文提出的決策方法不僅考慮了工藝約束條件,而且能夠獲得所有可能的零件工藝路線,從而能夠?qū)崿F(xiàn)從可選工藝路線中得到最優(yōu)/次優(yōu)的工藝路線。

(2)基于Petri網(wǎng)的規(guī)則集與傳統(tǒng)的規(guī)則集在知識庫設(shè)計中是有差別的。后者的規(guī)則之間彼此獨(dú)立、互不調(diào)用,導(dǎo)致規(guī)則間的相互關(guān)系不太明確、相互作用難以理解,規(guī)則的啟用完全依賴于當(dāng)前數(shù)據(jù)庫,使知識庫的整體功能難以把握,而前者的所有規(guī)則以網(wǎng)狀結(jié)構(gòu)鏈接成一個整體,規(guī)則的啟用只取決于前提條件。這對于工藝知識庫中規(guī)則子集的劃分提供了一種有效方法,即根據(jù)規(guī)則之間的鏈接關(guān)系來劃分規(guī)則子集,而且對任一規(guī)則子集的修改和調(diào)整并不影響其他規(guī)則子集。

[1] 肖偉躍.CAPP中工藝規(guī)程主干生成的約束匹配算法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2001,13(1)：40-43.

[2] 邵新宇,蔡力鋼.現(xiàn)代CAPP技術(shù)與應(yīng)用[M].北京：機(jī)械工業(yè)出版社,2004.

[3] 張振明,許建新,賈曉亮,等.現(xiàn)代CAPP技術(shù)與應(yīng)用[M].西安：西北工業(yè)大學(xué)出版社,2003.

[4] 趙學(xué)軍,喬紅兵.CAPP系統(tǒng)工藝決策過程的AOV網(wǎng)表示法及拓?fù)渑判蚍治鯷J].機(jī)電一體化,1998,4(4)：29-32.

[5] 胡于進(jìn),張正義,凌玲,等.基于工藝約束矩陣的加工序列優(yōu)化[J].中國機(jī)械工程,2009,20(9)：1062-1066.

[6] 王細(xì)洋.計算機(jī)輔助零件工藝過程設(shè)計原理[M].北京：航空工業(yè)出版社,2004.

[7] Lee K H,Jung M Y.Flexible Process Sequencing Using Petr Net Theory[J].Computers&Industrial Engineering,1995,28(2)：279-290.

[8] Wu R R,M a L,Mathew J,et al.Optimal Operation Planning Using Fuzzy Petri Nets with Resource Constraints[J].International Journal of Computer Integrated Manufacturing,2002,15(1)：28-36.

[9] Nazareth D L.Investigating the Applicability of Petri Nets for Rule-based System Verification[J].IEEE Transactions on Knowledge and Data Engineering,1993,5(3)：402-415.

[10] 吳哲輝.Petri網(wǎng)導(dǎo)論[M].北京：機(jī)械工業(yè)出版社,2006：53-58,79-86.

[11] Murata T.Petri Nets：Properties,Analysis and Applications[J].Proceedings of the IEEE,1989,77(4)：541-580.