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

肖偉躍 羅佑新 廖德崗

湖南文理學院,常德,415000

0 引言

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

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

1 Petri網系統與加工順序決策Petri網模型

1.1 普通Petri網系統

定義1 一個普通Petri網系統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的標識函數,其中M0是初始標識,M 0：P →{0,1,2,…}。

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

將定義1表示為圖形時,用圓圈表示庫所,用矩形框表示變遷,用帶箭頭的弧線表示輸入輸出關系,用圓圈中的黑點表示p i中的資源個數,稱之為托肯(Token)。在Petri網系統中,系統的靜態特性由網絡結構進行描述,系統的當前狀態由托肯在庫所中的分布決定,而系統的動態行為則通過托肯的移動和傳播進行控制。

1.2 基于規則的加工順序決策Petri網模型

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

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

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

根據定義2,一個基于規則的加工順序決策Petri網單元模型如圖1所示。

圖1 基于規則的 Petri網單元模型(無自環)

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

圖2 基于規則的 Petri網單元模型(帶自環)

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

2.1 狀態方程與T_不變量[10]

定義3 設PN為一個Petri網,P={p1,p2,…,p n},T={t1,t2,…,tm},則PN 的網結構(P,T,F)(F?(P×T)∪(T×P))可以用一個n行m列矩陣An×m來表示,該矩陣稱為關聯矩陣,表達式如下：

如果將Petri網的標識用一個非負整數向量來表示,利用關聯矩陣就可以將M0[τ＞M這一事實寫成矩陣方程M 0+AJ=M。其中的τ是將M 0變換為M的變遷序列,M 0和M則成為PN中以庫所集P為序標集的列向量,而J是PN中以變遷集T為序標集的列向量。該方程稱為狀態方程,Murata[11]已經證明凡是可達的標識必定滿足狀態方程。

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

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

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

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

(1)構建決策Petri網模型。根據加工排序規則集以及規則集與Petri網間的映射關系構建加工順序決策Petri網模型PD_PN。該模型中所有的加工工序庫所均帶有自環(圖2)。

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

(3)T_不變量分析與計算。在進行T_不變量計算之前,還需對模型進行適當的修改和調整。一方面是由于T_不變量的代數計算只能應用于單純網,而SPD_PN帶有“自環”,所以應將模型中輸入庫所與變遷之間帶有自環的雙向箭頭改為僅指向變遷的單向箭頭;另一方面是為了讓系統循環運行以便于獲取全部T_不變量,這可以通過在初始庫所與每一個葉庫所之間增加一個循環變遷t′來實現,如圖3所示。

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

(1)根據規則集及其映射關系構建加工順序決策Petri網模型PD_PN。

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

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

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

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

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

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

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

(9)根據M 0和 T enb,計算關聯矩陣A。

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

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

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

3 實例分析與驗證

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

3.1 軸套類零件的加工順序決策及其Petri網模型

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

表1 軸套類零件常規加工工藝規則

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

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

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

圖5 是一個軸套類零件,圖6是對應于圖5并根據圖4和第2節的生成算法,在初始標識下網系統運行后得到的實例零件可選工藝路線Petri網簡化模型。

圖5 一個軸套類零件

圖6 實例零件可選工藝路線Petri網簡化模型

根據定義3得到的實例零件關聯矩陣A10×11 為

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

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

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

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

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

4 結論

(1)采用Petri網T_不變量方法和產生式規則能夠實現工藝約束條件下的加工順序決策,并通過實例驗證了基于T_不變量的可選工藝路線生成算法的合理性和有效性。與傳統的方法相比較,本文提出的決策方法不僅考慮了工藝約束條件,而且能夠獲得所有可能的零件工藝路線,從而能夠實現從可選工藝路線中得到最優/次優的工藝路線。

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

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

[2] 邵新宇,蔡力鋼.現代CAPP技術與應用[M].北京：機械工業出版社,2004.

[3] 張振明,許建新,賈曉亮,等.現代CAPP技術與應用[M].西安：西北工業大學出版社,2003.

[4] 趙學軍,喬紅兵.CAPP系統工藝決策過程的AOV網表示法及拓撲排序分析[J].機電一體化,1998,4(4)：29-32.

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

[6] 王細洋.計算機輔助零件工藝過程設計原理[M].北京：航空工業出版社,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網導論[M].北京：機械工業出版社,2006：53-58,79-86.

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