肖偉躍 羅佑新 廖德崗
湖南文理學院,常德,415000
加工順序決策(即工藝路線決策)是在加工方法決策(即加工鏈決策)的基礎上進行的。由于加工順序決策影響因素多、針對性強、涉及面寬、綜合性廣,所以迄今為止都沒有得到很好的解決,成為制約工藝設計自動化的瓶頸。就創(chuàng)成方法而言,以往的研究大致可以歸納為三種方法:一是將加工順序決策看成是分層次、分階段的約束驅動過程或者是將決策任務劃分成若干個決策子任務的分解合并過程[1-3];二是工藝決策過程的AOV網(wǎng)(activity on vertex network)表示及其拓撲排序方法,或者是以加工工序間的優(yōu)先約束關系為基礎的加工序列優(yōu)化綜合方法[4-5];三是基于人工神經(jīng)網(wǎng)絡、基于遺傳算法、基于模擬退火算法等的工藝決策與優(yōu)化方法。第一種方法由于難以提取和表達獨立的工藝知識模塊、排序方法與工藝人員思維習慣不符等問題而導致決策邏輯的實現(xiàn)存在許多困難[6];第二種方法因為需要確定工藝約束的優(yōu)先關系,但這種關系很難根據(jù)工藝知識自動構成[6];第三種方法基本還處于理論探索階段,還鮮有實際的工程應用[5]。除此之外,也有基于相似性原理以及基于實例的工藝路線決策方法,但其應用范圍過于狹窄,且零件聚類和實例提取仍存在問題,當然這也不屬于創(chuàng)成方法范疇。
盡管人類目前還不能實現(xiàn)工藝設計的完全自動化,但并不排斥對自動工藝決策的探索與追求。由于Petri網(wǎng)易于表達離散事件動態(tài)系統(tǒng)中系統(tǒng)變化發(fā)生的條件以及變化發(fā)生后的系統(tǒng)狀態(tài),而機械制造工藝系統(tǒng)又是典型的離散事件系統(tǒng),所以已有學者將Petri網(wǎng)應用于工藝設計領域,但一般主要是應用Petri網(wǎng)來求解加工方法決策問題[7-8],很少有文獻報道Petri網(wǎng)在加工順序決策研究中的應用。針對此,本文嘗試采用Petri網(wǎng)來求解加工順序決策問題。首先根據(jù)Petri網(wǎng)原理和產生式規(guī)則建立了一個基于規(guī)則的加工順序決策Petri網(wǎng)模型;然后根據(jù)Petri網(wǎng)T_不變量在考慮工藝約束的條件下,提出了一種新的可選工藝路線T_不變量生成方法;最后通過一個軸套類零件驗證了所提方法的有效性。
定義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的標識函數(shù),其中M0是初始標識,M 0:P →{0,1,2,…}。
在普通Petri網(wǎng)系統(tǒng)中,變遷使能與激發(fā)的規(guī)則是:①變遷t∈T在標識M 下使能記為M[t>,其充要條件是,?p∈P:M(p)>0∧I(p,t)=1;②變遷t∈T在標識M下激發(fā)并到達新標識M′記為M[t>M′,則新標識M′是,?p∈ P :M′(p)=M(p)+O(t,p)-I(p,t)。
將定義1表示為圖形時,用圓圈表示庫所,用矩形框表示變遷,用帶箭頭的弧線表示輸入輸出關系,用圓圈中的黑點表示p i中的資源個數(shù),稱之為托肯(Token)。在Petri網(wǎng)系統(tǒng)中,系統(tǒng)的靜態(tài)特性由網(wǎng)絡結構進行描述,系統(tǒng)的當前狀態(tài)由托肯在庫所中的分布決定,而系統(tǒng)的動態(tài)行為則通過托肯的移動和傳播進行控制。
在工藝設計領域,工藝決策知識的表達方法有多種形式,但表達能力較強、應用范圍較廣的兩種主要形式還是傳統(tǒng)的基于規(guī)則的方法和基于框架的方法。通過對比分析和研究表明,在基于規(guī)則的方法與基于Petri網(wǎng)的方法之間存著明確的對應關系[9]。若將產生式規(guī)則系統(tǒng)映射為Petri網(wǎng)系統(tǒng),則輸入庫所代表前提,輸出庫所代表結論;托肯代表當前事實,標識代表當前事實庫,標識的變化代表著事實庫的更新;變遷代表規(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ī)則結論;M是PD_PN的標識函數(shù),M={Mop∪Mpc}→{0,1},Mop是對應于Pop的標識,M pc是對應于P pc的標識。
根據(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}。當輸入庫所含有托肯并使變遷激發(fā)后,托肯就會從輸入庫所移動到輸出庫所。由于圖1所示的單元模型不帶“自環(huán)”,且任一庫所中的托肯數(shù)量只能是0或1,故而由此組成的Petri網(wǎng)系統(tǒng)是單純網(wǎng)并且是安全的,這將有利于后續(xù)可選加工路線生成的T_不變量分析。然而,網(wǎng)系統(tǒng)中的變遷一旦激發(fā),該變遷的所有輸入庫所都會失去托肯,這將使對應于加工工序庫所的最終標識M op不再包含已激發(fā)變遷的輸入庫所和輸出庫所。為此,需要對模型進行必要的修正,可以考慮在圖1中增加一條由變遷指向加工工序輸入庫所的有向弧,從而形成圖2所示的帶有“自環(huán)”的單元模型,這樣在變遷激發(fā)之后,該庫所仍然保留有托肯。
圖2 基于規(guī)則的 Petri網(wǎng)單元模型(帶自環(huán))
定義3 設PN為一個Petri網(wǎng),P={p1,p2,…,p n},T={t1,t2,…,tm},則PN 的網(wǎng)結構(P,T,F)(F?(P×T)∪(T×P))可以用一個n行m列矩陣An×m來表示,該矩陣稱為關聯(lián)矩陣,表達式如下:
如果將Petri網(wǎng)的標識用一個非負整數(shù)向量來表示,利用關聯(lián)矩陣就可以將M0[τ>M這一事實寫成矩陣方程M 0+AJ=M。其中的τ是將M 0變換為M的變遷序列,M 0和M則成為PN中以庫所集P為序標集的列向量,而J是PN中以變遷集T為序標集的列向量。該方程稱為狀態(tài)方程,Murata[11]已經(jīng)證明凡是可達的標識必定滿足狀態(tài)方程。
定義4 設PN為一個Petri網(wǎng),P={p 1,p 2,…,pn},T={t1,t2,…,tm},An×m是PN 的關聯(lián)矩陣,如果存在非零解的m維非負整數(shù)列向量J滿足方程An×mJm×1=0,n=|P|,m=|T|,則稱J為PN的一個T_不變量。
根據(jù)定義3和定義4,一個T_不變量就是一個整數(shù)系數(shù)線性方程組的非負整數(shù)解(全零向量除外)。所以一個T_不變量就意味著存在一個與之對應的變遷序列t1,t2,…,tk,使得網(wǎng)系統(tǒng)從初始標識M0開始,經(jīng)過該變遷序列之后,其后續(xù)標識M又重新恢復到初始標識M 0。T_不變量的存在表明網(wǎng)系統(tǒng)具有對系統(tǒng)狀態(tài)的復制能力,而此T_不變量中各分量的值就決定了各個變遷的發(fā)生次數(shù)。
由定義2、定義3和定義4可知,根據(jù)方程AJ=0求得的一個 T_不變量就表明Petri網(wǎng)中存在一個變遷序列,而由該變遷序列中所有分量為1的各個變遷的輸入輸出加工庫所鏈接而成的庫所序列就代表了零件的一條工藝路線。因此,為了獲得被加工零件的可選工藝路線,需要完成以下三個步驟的工作:
(1)構建決策Petri網(wǎng)模型。根據(jù)加工排序規(guī)則集以及規(guī)則集與Petri網(wǎng)間的映射關系構建加工順序決策Petri網(wǎng)模型PD_PN。該模型中所有的加工工序庫所均帶有自環(huán)(圖2)。
(2)化簡決策Petri網(wǎng)模型。根據(jù)零件特征信息和PD_PN模型,確定工藝約束庫所和加工工序庫所并進行初始標識。在初始標識狀態(tài)下系統(tǒng)激發(fā),當系統(tǒng)運行結束后就可從最終標識中獲得所有已激發(fā)的變遷。為了降低模型規(guī)模,減少運算時間,可以刪除模型中所有的工藝約束庫所,刪除所有未激發(fā)的變遷以及相應的輸入輸出庫所,從而得到簡化了的決策Petri網(wǎng)模型SPD_PN。
(3)T_不變量分析與計算。在進行T_不變量計算之前,還需對模型進行適當?shù)男薷暮驼{整。一方面是由于T_不變量的代數(shù)計算只能應用于單純網(wǎng),而SPD_PN帶有“自環(huán)”,所以應將模型中輸入庫所與變遷之間帶有自環(huán)的雙向箭頭改為僅指向變遷的單向箭頭;另一方面是為了讓系統(tǒng)循環(huán)運行以便于獲取全部T_不變量,這可以通過在初始庫所與每一個葉庫所之間增加一個循環(huán)變遷t′來實現(xiàn),如圖3所示。
由上述三個步驟可以獲得多個T_不變量。一個T_不變量對應一條工藝路線,多個T_不變量就對應多條工藝路線。這就使零件的工藝路線選擇從原理上成為可能,其具體的生成算法如下:
(1)根據(jù)規(guī)則集及其映射關系構建加工順序決策Petri網(wǎng)模型PD_PN。
(2)對加工順序決策 Petri網(wǎng)模型進行初始標識。①根據(jù)零件信息對工藝約束庫所進行初始標識,得到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)激發(fā)T new中的所有變遷,并計算后續(xù)標識M,則M(pk)=M(pk)+O(pk,t)-I(pk,t),?p k∈{P op∪P pc}。
(6)在后續(xù)標識M下,獲取具有使能的新變遷集 T new。如果T new=?,則轉到(7);如果T new≠?,則使T enb={T enb+T new},并返回到(5)。
(7)根據(jù) M0和 T enb對 Petri網(wǎng)模型進行化簡。①將模型中所有的雙向箭頭更改為指向變遷的單向箭頭;②刪除模型中所有的約束庫所;③刪除模型中沒有在Tenb中出現(xiàn)的變遷及其相連的輸出庫所。
(8)在初始庫所與所有的葉庫所之間增加一個循環(huán)變遷t′,形成一個簡化的加工順序決策Petri網(wǎng)模型SPD_PN。
(9)根據(jù)M 0和 T enb,計算關聯(lián)矩陣A。
(10)根據(jù)公式AJ=0,計算簡化模型中所有的T_不變量(全零向量除外)。
(11)根據(jù)每一個T_不變量,求出與之對應的庫所序列,則每一個庫所序列就代表了一條工藝路線,全部的工藝路線就構成了一個被加工對象的工藝路線集合PR。
(12)根據(jù)實際生產情況,在PR中選取一條工藝路線作為實際的工藝路線,其他作為備選的工藝路線。
根據(jù)上文提出的基于Petri網(wǎng)的工藝路線生成算法,本節(jié)以軸套類零件的加工順序決策為例,說明在加工方法決策的基礎上采用Petri網(wǎng)模型生成可選工藝路線的T_不變量方法,其他軸類、盤套類、齒輪類、箱體類等零件的工藝路線可以參考本文所提出的方法進行計算。
根據(jù)機械制造工藝理論和軸套類零件加工的基本規(guī)律,具有經(jīng)濟加工精度的普通軸套類零件(包括有色金屬材料)常規(guī)加工工藝規(guī)則如表1所示。在實際應用時,表1中規(guī)則可根據(jù)零件結構差異和工藝習慣不同進行修改和調整。為節(jié)省篇幅和簡化規(guī)則,表1中的工藝約束只列出了工序條件和設備條件,而且工序條件省略了IT、Ra、熱處理等約束內容。對于鉆孔、鉆鉸孔、鉆擴鉸孔、銑鍵槽和銑平面等工序,將其簡化為一個工序(實際并非如此),并且未列出軸套類零件的精密加工、超精密加工以及特種加工工序)。
表1 軸套類零件常規(guī)加工工藝規(guī)則
根據(jù)表1所列出的軸套類零件常規(guī)加工工藝規(guī)則和定義2,可以得到基于Petri網(wǎng)的軸套類零件加工順序決策模型,如圖4所示。
圖4 基于Petri網(wǎng)的軸套類零件加工順序決策模型
圖5 是一個軸套類零件,圖6是對應于圖5并根據(jù)圖4和第2節(jié)的生成算法,在初始標識下網(wǎng)系統(tǒng)運行后得到的實例零件可選工藝路線Petri網(wǎng)簡化模型。
圖5 一個軸套類零件
圖6 實例零件可選工藝路線Petri網(wǎng)簡化模型
根據(jù)定義3得到的實例零件關聯(lián)矩陣A10×11 為
根據(jù)定義4的A10×11J11×1=0計算實例零件所有的T_不變量(計算從略):
在兩個T_不變量中,由分量為1的變遷庫所對應的輸入和輸出加工庫所連接而成的庫所鏈即為實例零件的加工工藝路線,即:
(1)毛坯(鍛造)—退火或正火 —粗車 —半精車 —鉆鉸孔 —銑平面 —淬火 —磨平面 —磨削;
(2)毛坯(鍛造)—退火或正火 —粗車 —半精車 —鉆鉸孔 —銑平面 —淬火—磨平面—粗磨 —精磨。
在兩條工藝路線中選擇一條作為實例零件的實際加工路線,另外一條工藝路線作為該零件的備選加工方案。
(1)采用Petri網(wǎng)T_不變量方法和產生式規(guī)則能夠實現(xiàn)工藝約束條件下的加工順序決策,并通過實例驗證了基于T_不變量的可選工藝路線生成算法的合理性和有效性。與傳統(tǒng)的方法相比較,本文提出的決策方法不僅考慮了工藝約束條件,而且能夠獲得所有可能的零件工藝路線,從而能夠實現(xiàn)從可選工藝路線中得到最優(yōu)/次優(yōu)的工藝路線。
(2)基于Petri網(wǎng)的規(guī)則集與傳統(tǒng)的規(guī)則集在知識庫設計中是有差別的。后者的規(guī)則之間彼此獨立、互不調用,導致規(guī)則間的相互關系不太明確、相互作用難以理解,規(guī)則的啟用完全依賴于當前數(shù)據(jù)庫,使知識庫的整體功能難以把握,而前者的所有規(guī)則以網(wǎng)狀結構鏈接成一個整體,規(guī)則的啟用只取決于前提條件。這對于工藝知識庫中規(guī)則子集的劃分提供了一種有效方法,即根據(jù)規(guī)則之間的鏈接關系來劃分規(guī)則子集,而且對任一規(guī)則子集的修改和調整并不影響其他規(guī)則子集。
[1] 肖偉躍.CAPP中工藝規(guī)程主干生成的約束匹配算法[J].計算機輔助設計與圖形學學報,2001,13(1):40-43.
[2] 邵新宇,蔡力鋼.現(xiàn)代CAPP技術與應用[M].北京:機械工業(yè)出版社,2004.
[3] 張振明,許建新,賈曉亮,等.現(xiàn)代CAPP技術與應用[M].西安:西北工業(yè)大學出版社,2003.
[4] 趙學軍,喬紅兵.CAPP系統(tǒng)工藝決策過程的AOV網(wǎng)表示法及拓撲排序分析[J].機電一體化,1998,4(4):29-32.
[5] 胡于進,張正義,凌玲,等.基于工藝約束矩陣的加工序列優(yōu)化[J].中國機械工程,2009,20(9):1062-1066.
[6] 王細洋.計算機輔助零件工藝過程設計原理[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)導論[M].北京:機械工業(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.