李任江,　曹　陽(yáng)

(長(zhǎng)春工業(yè)大學(xué) 機(jī)電工程學(xué)院， 吉林 長(zhǎng)春　130012)

?

基于賦時(shí)有色Petri網(wǎng)離散制造過程建模與仿真

李任江,曹陽(yáng)

(長(zhǎng)春工業(yè)大學(xué) 機(jī)電工程學(xué)院， 吉林 長(zhǎng)春130012)

摘要：針對(duì)解決離散制造系統(tǒng)控制過程中可能出現(xiàn)的沖突、死鎖等問題，將賦時(shí)Petri網(wǎng)和著色Petri網(wǎng)兩者相結(jié)合，根據(jù)柔性制造系統(tǒng)的元素建立了擁有4個(gè)CNC機(jī)床加工中心，4條工件生產(chǎn)線的賦時(shí)著色Petri網(wǎng)模型。仿真結(jié)果表明，該方法能有效解決沖突、死鎖等問題。

關(guān)鍵詞：離散系統(tǒng); 柔性制造; 賦時(shí)有色Petri網(wǎng)

0引言

半導(dǎo)體加工系統(tǒng)是典型的離散制造系統(tǒng)[1]，離散事件動(dòng)態(tài)系統(tǒng)(Discrete Event Dynamic System, DEDS)是指事件瞬時(shí)發(fā)生，使得系統(tǒng)的狀態(tài)瞬間轉(zhuǎn)移到另一個(gè)狀態(tài)。其中在制造業(yè)范圍內(nèi)，以柔性制造系統(tǒng)(Flexible Manufacturer System, FMS)為離散動(dòng)態(tài)事件系統(tǒng)的典型代表。常見半導(dǎo)體制造系統(tǒng)的結(jié)構(gòu)包含半導(dǎo)體加工中心，在設(shè)備之間傳輸工件的自動(dòng)導(dǎo)向小車(AGV)以及計(jì)算機(jī)信息控制單元等。

Petri網(wǎng)技術(shù)是由德國(guó)Petri博士于1962年在其博士論文里提出的一種系統(tǒng)描述和分析工具，Petri網(wǎng)最大的優(yōu)勢(shì)是具有直觀的圖形表示和嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)模型支持[2]。Petri網(wǎng)技術(shù)經(jīng)過幾十年的成長(zhǎng)，理論體系日趨完善，尤其在大型復(fù)雜的系統(tǒng)中，用其表示系統(tǒng)中的并行、異步、沖突等關(guān)系，并以托肯表述其中對(duì)象的動(dòng)態(tài)關(guān)系。由于基本Petri網(wǎng)的表達(dá)能力有限，在基本Petri網(wǎng)理論之上又陸續(xù)出現(xiàn)了高級(jí)Petri網(wǎng)，如時(shí)間Petri網(wǎng)、著色Petri網(wǎng)、隨機(jī)Petri網(wǎng)等。復(fù)雜的FMS中如果系統(tǒng)中的元素安排不合理容易出現(xiàn)沖突、死鎖等現(xiàn)象，會(huì)嚴(yán)重影響整個(gè)系統(tǒng)的效率。如何更快捷地去發(fā)現(xiàn)沖突、死鎖的位置以及及時(shí)解決掉問題是關(guān)鍵所在，Petri網(wǎng)的圖形化界面能夠提供良好的幫助。沖突的原因即系統(tǒng)在同一時(shí)間搶用一個(gè)資源，賦時(shí)Petri網(wǎng)(Timed Petri Net, TPN)可以給庫(kù)所(Place)或者變遷(Transition)賦以時(shí)延，使之避開在同一時(shí)間對(duì)同一資源的搶用。隨著制造能力的提升，一個(gè)系統(tǒng)中的實(shí)體對(duì)象必然會(huì)增加，若依然使用基本Petri網(wǎng)，Petri網(wǎng)節(jié)點(diǎn)數(shù)量會(huì)呈指數(shù)增加，則模型的規(guī)模將迅速膨脹，反而降低了Petri網(wǎng)的實(shí)用性。著色Petri網(wǎng)(Colored Petri Net, CPN)的引入將庫(kù)所中的托肯賦予顏色，即每個(gè)托肯都有其特有或共有的特征值，通過特征值來給PN進(jìn)行分類，從而大大減小了PN的復(fù)雜度而且使PN能夠更加直觀。

1Petri網(wǎng)簡(jiǎn)介

1.1　Petri網(wǎng)定義

一個(gè)Petri網(wǎng)表示為一個(gè)五元組PN=(P,T,I,O,m0)其中：

1)P={p1,p2,…,pn}是庫(kù)所(Place)的有限集合，n>0為庫(kù)所的個(gè)數(shù)；

2)T={t1,t2,…,tm}是變遷(Transition)的有限集合，m>0為變遷的個(gè)數(shù)；

3)I=P×T→N是輸入函數(shù)，定義了從P到T的有向弧的集合，N={0,1,2,…}非負(fù)整數(shù)集；

4)O=T×P→N是輸出函數(shù)，定義了從T到P的有向弧的集合，N={0,1,2,…}非負(fù)整數(shù)集；

5)m:P→N是Petri的標(biāo)識(shí)，m描述了被模擬系統(tǒng)的狀態(tài)，m(i)表示第i個(gè)庫(kù)所中的托肯數(shù)。m0則表示系統(tǒng)的初始狀態(tài)。一個(gè)網(wǎng)系統(tǒng)∑=(N,M0)的全部可能的運(yùn)行情況由它的基網(wǎng)N和初始標(biāo)識(shí)M0完全確定。C=O-I稱為關(guān)聯(lián)矩陣。

Petri網(wǎng)的標(biāo)記與變遷規(guī)則：

1)對(duì)于一個(gè)Petri網(wǎng)PN=(P,T,I,O)的標(biāo)識(shí)為M，變遷ti∈T，如果滿足以下條件，則此變遷授權(quán)使能

M(pi)≥#(pi,I(ti))

M(pi)+#(pi,O(ti))≤K(pi)

式中：K(pi)----pi中容納的最大令牌數(shù)。

2)當(dāng)一個(gè)變遷ti使能后,將產(chǎn)生一個(gè)新的標(biāo)識(shí)M′，且M′(pi)=M(pi)-#(pi,I(ti))+#(Pi,O(ti))

1.2　賦時(shí)Petri網(wǎng)

賦時(shí)Petri網(wǎng)是指在普通Petri網(wǎng)的P或者T上加上時(shí)間延遲。普通Petri網(wǎng)的變遷發(fā)生是瞬時(shí)的，即變遷一旦發(fā)生，立刻導(dǎo)致標(biāo)識(shí)改變，而得到新的標(biāo)識(shí)。如果Petri網(wǎng)的庫(kù)所移動(dòng)托肯到變遷使能需要經(jīng)過一段時(shí)間，都屬于賦時(shí)Petri網(wǎng)。賦時(shí)Petri網(wǎng)可以用一個(gè)六元組來表示：

PN=(P,T,I,O,m0,D)

1)其中，P,T,I,O,m0與基本PN定義相同；

2)D={d1,d2,…,dn}表示PN中庫(kù)所或變遷的時(shí)延，di為pi(ti)的時(shí)延。

賦時(shí)Petri網(wǎng)有3種類型:第1種是賦時(shí)變遷Petri網(wǎng)(TTPN)，變遷延遲一段時(shí)間后再使能；第2種是賦時(shí)庫(kù)所Petri網(wǎng)(TPPN)，變遷一旦使能立刻激發(fā)，從輸入庫(kù)所中移去托肯，并在輸出庫(kù)所中放入相應(yīng)數(shù)量的托肯，但這些托肯只有延遲一段時(shí)間后才能使用,只有可以被使用的托肯才能激發(fā)變遷[3]；第3種是時(shí)間與輸出有向弧相關(guān)聯(lián)，變遷使能立刻激發(fā)，但輸出托肯要延遲一段時(shí)間再到達(dá)輸出庫(kù)所。

1.3　著色Petri網(wǎng)

CPN是一有向圖，它可以用一五元組來表示：

CPN=(P,T,C,I,O)

1)此中，P，T分別為庫(kù)所、變遷集合，與基本Petri網(wǎng)定義相同；

2)C是與P和T關(guān)聯(lián)的色彩集合，C(p)是關(guān)于P中托肯的顏色的集合，C(t)是關(guān)于變遷的顏色集合。

著色Petri網(wǎng)是一種高級(jí)Petri網(wǎng)，可以看作是普通Petri網(wǎng)的縮寫，其原理就是對(duì)托肯進(jìn)行分類，以完成對(duì)網(wǎng)系統(tǒng)的折疊[4]。

著色Petri網(wǎng)運(yùn)行規(guī)則：

1)t∈T被使能，當(dāng)且僅當(dāng)?p∈P，c∈C(t)，m(p,c)≥I(p,t,c);

2)若t∈T在標(biāo)識(shí)m下被使能，按照如下激活規(guī)則產(chǎn)生新標(biāo)識(shí)記m：

m′(p,c)=m(p,c)+O(p，t，c)-I(p,t,c)=

m(p,c)+C(p，t，c)

?p∈P，c∈C(t)

2流程設(shè)計(jì)

2.1　工件調(diào)度準(zhǔn)則

系統(tǒng)如果要完成一個(gè)完整的投料、加工、入庫(kù)過程，這就要求各個(gè)對(duì)象之間相互配合，才能保證整個(gè)系統(tǒng)有條不紊準(zhǔn)確運(yùn)行下去[5]。如往AGV中投料這個(gè)動(dòng)作，首先AGV要先從加工中心上釋放，等其到原料倉(cāng)庫(kù)后才可進(jìn)行動(dòng)作；工件在加工中心加工過程中要把握加工時(shí)間以及投料順序，由于多個(gè)工件會(huì)搶用一個(gè)機(jī)床，這些加工動(dòng)作是并發(fā)的，即動(dòng)作會(huì)搶用資源，很容易造成沖突現(xiàn)象，若沖突不解決，加工中心上工件不釋放，容易造成后續(xù)工序的死鎖，則整個(gè)制造系統(tǒng)癱瘓。

管理調(diào)度過程中，遵循的原則一是合理原則，就是要保證工件加工的下一個(gè)工序開始前條件要滿足，以免造成死鎖；二是優(yōu)化原則，在系統(tǒng)是活性的前提下，合理調(diào)度、分析并發(fā)的動(dòng)作、加快工件的加工速度。

2.2　控制流程描述

主要控制流程為：原料裝載AGV流程、AGV分配原材料流程、加工中心加工后工件調(diào)度流程、工件裝配流程、成品入庫(kù)流程。對(duì)于系統(tǒng)的每一個(gè)流程都可以由其對(duì)應(yīng)的狀態(tài)和變遷兩個(gè)角度去分析。變遷是系統(tǒng)中消耗資源、使用及轉(zhuǎn)換對(duì)應(yīng)狀態(tài)的變化，動(dòng)作的發(fā)生由系統(tǒng)的狀態(tài)來控制，而這些狀態(tài)轉(zhuǎn)化可以用變遷來描述。

控制流程中，變遷可能會(huì)同時(shí)發(fā)生，變遷發(fā)生后才可產(chǎn)生狀態(tài)，狀態(tài)的發(fā)生會(huì)使前提條件消失，并且會(huì)產(chǎn)生其它條件。

3基于賦時(shí)Petri網(wǎng)對(duì)DEDS控制系統(tǒng)的建模

3.1　系統(tǒng)構(gòu)成

半導(dǎo)體加工系統(tǒng)以柔性制造系統(tǒng)為代表，F(xiàn)MS的建模方法與DEDS的建模方法類似，本次建模以FMS為背景。FMS的基本構(gòu)成：4臺(tái)以上的加工機(jī)床，自動(dòng)化物料傳輸貯運(yùn)系統(tǒng)，集成加工任務(wù)過程控制器，分布式計(jì)算機(jī)信息管理控制系統(tǒng)，自動(dòng)托盤交換系統(tǒng)，產(chǎn)品檢測(cè)返工系統(tǒng)等。

設(shè)此FMS中共有加工機(jī)床4臺(tái)，2臺(tái)自動(dòng)導(dǎo)引小車，4個(gè)托盤，檢測(cè)站1臺(tái)，機(jī)械手設(shè)備1臺(tái)，總裝配機(jī)床1臺(tái)，堆垛機(jī)和立體倉(cāng)庫(kù)。AGV將原材料運(yùn)送至加工機(jī)床的暫存區(qū)，工件在機(jī)床之間由機(jī)械手進(jìn)行移動(dòng)。當(dāng)加工完最后工序后由傳送帶送至檢測(cè)站，檢測(cè)后裝配再由堆垛機(jī)放置到立體倉(cāng)庫(kù)。系統(tǒng)布局如圖1所示。

圖1　系統(tǒng)布局

從柔性制造系統(tǒng)的機(jī)構(gòu)上來看，半導(dǎo)體的調(diào)度系統(tǒng)是最重要的部分，從原料倉(cāng)庫(kù)到加工機(jī)床的加工，再到各個(gè)加工機(jī)床之間工件的調(diào)度，最后到裝配以及成品入庫(kù)都由它來指令調(diào)度。因此，柔性制造系統(tǒng)自動(dòng)化程度、調(diào)度準(zhǔn)確度，以及整個(gè)系統(tǒng)效率高低與否均與控制系統(tǒng)有關(guān)。

4種半導(dǎo)體加工順序見表1。

表1　半導(dǎo)體種類及加工順序

3.2　控制對(duì)象

柔性制造系統(tǒng)的主要控制對(duì)象有如下幾個(gè)部分：

1)自動(dòng)導(dǎo)向小車(AGV)：它用于從原材料倉(cāng)庫(kù)取出原材料并按工件的加工要求，把原材料放置在加工機(jī)床前的緩沖區(qū)。

2)機(jī)械臂1：它是整個(gè)柔性制造系統(tǒng)中工件路徑調(diào)度最為關(guān)鍵的部分。它負(fù)責(zé)每個(gè)工件從第二個(gè)工序直到最后一個(gè)工序過程中，在加工機(jī)床之間的流向控制。它的效率直接影響整個(gè)加工系統(tǒng)的效率。

3)堆垛機(jī)：控制成品入庫(kù)。

3.3　建立模型

根據(jù)上述描述，先用賦時(shí)Petri網(wǎng)對(duì)半導(dǎo)體J1生產(chǎn)路線進(jìn)行建模，如圖2所示。

圖2　工件1生產(chǎn)路線

每個(gè)庫(kù)所和變遷具體說明見表2。

表2　庫(kù)所及變遷含義

為了更清晰展示網(wǎng)的模型，P3出現(xiàn)了兩次，它們是同一庫(kù)所[6]。對(duì)J1工件加工路線建立賦時(shí)Petri網(wǎng)模型，對(duì)模型輸入初始化變量[7]。初始標(biāo)識(shí)M0=(1,1,0,1,0,1,0,1,0,0,0,0,1,0,0),延遲時(shí)間DT=(t0t1t2t3t4t5t6t7t8t9)T。

同理，也可以得到其它工件的加工路線Petri網(wǎng)模型。庫(kù)所中的托肯為系統(tǒng)當(dāng)前的一個(gè)動(dòng)態(tài)對(duì)象，當(dāng)變遷的使能條件滿足時(shí)，托肯從輸入庫(kù)所移動(dòng)到出變遷后庫(kù)所。若某個(gè)庫(kù)所中有托肯，那就表明該庫(kù)所控制的對(duì)象處于當(dāng)前狀態(tài)。根據(jù)Petri網(wǎng)的運(yùn)行規(guī)則，變遷前的輸入庫(kù)所擁有托肯，則該變遷使能。

工件的調(diào)度分為設(shè)備選工件調(diào)度和工件選設(shè)備調(diào)度[8]。兩種狀態(tài)的觸發(fā)由一決策庫(kù)所Pd來完成。當(dāng)加工機(jī)床加工完一個(gè)工件時(shí)，機(jī)床處于空閑狀態(tài)，若輸入緩沖區(qū)中等待加工的工件不止一個(gè)，這時(shí)可以通過嵌入算法來對(duì)工件的調(diào)度進(jìn)行尋優(yōu)[9]。工件調(diào)度如圖3所示。

圖3　工件調(diào)度模塊

工件的路徑模塊用來表示工件在加工系統(tǒng)中工藝加工路線過程，半導(dǎo)體在機(jī)床中加工的過程可以看作是工件在各個(gè)加工中心的流動(dòng)路徑，即當(dāng)工件在一臺(tái)加工機(jī)床上加工完成后，下一步需要在哪一臺(tái)機(jī)床上加工[10]。工件進(jìn)入加工系統(tǒng)，首先要進(jìn)入輸入緩沖區(qū)等待，工件加工完成后，進(jìn)入輸出緩沖區(qū)。再根據(jù)產(chǎn)品的工藝規(guī)程，使工件進(jìn)入對(duì)應(yīng)的下一個(gè)緩沖區(qū)。要加工4個(gè)工件，所以有4條路徑，用4種顏色來標(biāo)記。在機(jī)床層面內(nèi)建立不同工序與加工設(shè)備之間對(duì)應(yīng)的工藝加工關(guān)系。路徑調(diào)度模塊如圖4所示。

圖4　路徑調(diào)度模塊

AGV系統(tǒng)中只有兩輛，對(duì)AGV的控制調(diào)度關(guān)系到整個(gè)系統(tǒng)物料流動(dòng)。AGV從原材料倉(cāng)庫(kù)取料，工具所裝載的原材料加工工藝派發(fā)到相應(yīng)的機(jī)床，AGV的調(diào)度控制由顏色匹配進(jìn)行控制。因此，提高AGV的利用率是提高系統(tǒng)運(yùn)行效率的前提。

AGV的調(diào)度模塊如圖5所示。

圖5　AGV調(diào)度模塊

4結(jié)語

運(yùn)用Petri網(wǎng)對(duì)半導(dǎo)體生產(chǎn)系統(tǒng)的控制系統(tǒng)進(jìn)行建模，可以有效解決系統(tǒng)中所出現(xiàn)的異步、并發(fā)等狀態(tài)。通過賦時(shí)Petri網(wǎng)，對(duì)庫(kù)所或變遷進(jìn)行賦予時(shí)延，可解決系統(tǒng)中的沖突問題。柔性制造系統(tǒng)的運(yùn)行是復(fù)雜的制造過程，通過模塊化和運(yùn)用顏色Petri網(wǎng)的方法，大大降低了建模的規(guī)模。模塊化的分析可以嵌入相關(guān)調(diào)度的智能算法，使Petri網(wǎng)與Flexsim仿真軟件相結(jié)合，可運(yùn)用于更復(fù)雜的系統(tǒng)建模，具有很強(qiáng)的通用性。

參考文獻(xiàn)：

[1]曹政才.基于有色賦時(shí)Petri網(wǎng)的半導(dǎo)體生產(chǎn)線建模技術(shù)研究[J].系統(tǒng)仿真學(xué)報(bào)，2007，8：201-213.

[2]徐杜，蔣永平，張憲民.柔性制造系統(tǒng)原理與實(shí)踐[M].北京：機(jī)械工業(yè)出版社，2001.

[3]陶麗華.基于賦時(shí)Petri網(wǎng)的批處理系統(tǒng)建模[J].設(shè)計(jì)與研究，2006，5：19-22.

[4]吳哲輝.Petri網(wǎng)導(dǎo)論[M].北京：機(jī)械工業(yè)出版社，2006.

[5]徐兵，于淼.醫(yī)學(xué)檢驗(yàn)分析儀控制系統(tǒng)Petri網(wǎng)建模[J].長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，34(6)：698-703.

[6]金炳娥.基于Petri網(wǎng)的柔性制造系統(tǒng)調(diào)度問題的研究[D]：[碩士學(xué)位論文].西安：西安電子科技大學(xué)，2010：21-23.

[7]袁崇義.Petri網(wǎng)原理與應(yīng)用[M].北京：電子工業(yè)出版社，2005.

[8]肖兵.著色Petri網(wǎng)及其在系統(tǒng)建模與仿真中的應(yīng)用[J].計(jì)算機(jī)工程，2001，27：30-32.

[9]謝瑩.基于Petri網(wǎng)和stateflow的柔性制造系統(tǒng)仿真[D]：[碩士學(xué)位論文].成都：西南交通大學(xué)，2003:4-9.

[10]黃波.基于Petri網(wǎng)的FMS建模與調(diào)度研究[D]：[碩士學(xué)位論文].南京：南京理工大學(xué)，2006：1-7.

Timed colored Petri net based discrete manufacture

process modeling and simulation

LI Ren-jiang,CAO Yang

(School of Mechatronic Engineering, Changchun University of Technology, Changchun 130012， China)

Abstract：To solve the problems such as such as conflict and deadlock in the discrete manufacture process control system, we combine the timed Petri nets with the colored Petri net to establish a timed and colored Petri net model, which includes 4 operation centers and 4 product lines according the elements of the flexible manufacturing system. Simulation results show that the model can solve the above mentioned problems.

Key words：discrete system; flexible manufacture; timed and colored Petri nets.

中圖分類號(hào)：TP 278

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1674-1374(2015)01-0038-06

DOI:10.15923/j.cnki.cn22-1382/t.2015.1.08