基于赋时有色Petri网离散制造过程建模与仿真

李任江,　曹　阳

(长春工业大学 机电工程学院， 吉林 长春　130012)



基于赋时有色Petri网离散制造过程建模与仿真

李任江,曹阳

(长春工业大学 机电工程学院， 吉林 长春130012)

摘要：针对解决离散制造系统控制过程中可能出现的冲突、死锁等问题，将赋时Petri网和着色Petri网两者相结合，根据柔性制造系统的元素建立了拥有4个CNC机床加工中心，4条工件生产线的赋时着色Petri网模型。仿真结果表明，该方法能有效解决冲突、死锁等问题。

关键词：离散系统; 柔性制造; 赋时有色Petri网

0引言

半导体加工系统是典型的离散制造系统[1]，离散事件动态系统(Discrete Event Dynamic System, DEDS)是指事件瞬时发生，使得系统的状态瞬间转移到另一个状态。其中在制造业范围内，以柔性制造系统(Flexible Manufacturer System, FMS)为离散动态事件系统的典型代表。常见半导体制造系统的结构包含半导体加工中心，在设备之间传输工件的自动导向小车(AGV)以及计算机信息控制单元等。

Petri网技术是由德国Petri博士于1962年在其博士论文里提出的一种系统描述和分析工具，Petri网最大的优势是具有直观的图形表示和严谨的数学模型支持[2]。Petri网技术经过几十年的成长，理论体系日趋完善，尤其在大型复杂的系统中，用其表示系统中的并行、异步、冲突等关系，并以托肯表述其中对象的动态关系。由于基本Petri网的表达能力有限，在基本Petri网理论之上又陆续出现了高级Petri网，如时间Petri网、着色Petri网、随机Petri网等。复杂的FMS中如果系统中的元素安排不合理容易出现冲突、死锁等现象，会严重影响整个系统的效率。如何更快捷地去发现冲突、死锁的位置以及及时解决掉问题是关键所在，Petri网的图形化界面能够提供良好的帮助。冲突的原因即系统在同一时间抢用一个资源，赋时Petri网(Timed Petri Net, TPN)可以给库所(Place)或者变迁(Transition)赋以时延，使之避开在同一时间对同一资源的抢用。随着制造能力的提升，一个系统中的实体对象必然会增加，若依然使用基本Petri网，Petri网节点数量会呈指数增加，则模型的规模将迅速膨胀，反而降低了Petri网的实用性。着色Petri网(Colored Petri Net, CPN)的引入将库所中的托肯赋予颜色，即每个托肯都有其特有或共有的特征值，通过特征值来给PN进行分类，从而大大减小了PN的复杂度而且使PN能够更加直观。

1Petri网简介

1.1　Petri网定义

一个Petri网表示为一个五元组PN=(P,T,I,O,m0)其中：

1)P={p1,p2,…,pn}是库所(Place)的有限集合，n>0为库所的个数；

2)T={t1,t2,…,tm}是变迁(Transition)的有限集合，m>0为变迁的个数；

3)I=P×T→N是输入函数，定义了从P到T的有向弧的集合，N={0,1,2,…}非负整数集；

4)O=T×P→N是输出函数，定义了从T到P的有向弧的集合，N={0,1,2,…}非负整数集；

5)m:P→N是Petri的标识，m描述了被模拟系统的状态，m(i)表示第i个库所中的托肯数。m0则表示系统的初始状态。一个网系统∑=(N,M0)的全部可能的运行情况由它的基网N和初始标识M0完全确定。C=O-I称为关联矩阵。

Petri网的标记与变迁规则：

1)对于一个Petri网PN=(P,T,I,O)的标识为M，变迁ti∈T，如果满足以下条件，则此变迁授权使能

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

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

式中：K(pi)----pi中容纳的最大令牌数。

2)当一个变迁ti使能后,将产生一个新的标识M′，且M′(pi)=M(pi)-#(pi,I(ti))+#(Pi,O(ti))

1.2　赋时Petri网

赋时Petri网是指在普通Petri网的P或者T上加上时间延迟。普通Petri网的变迁发生是瞬时的，即变迁一旦发生，立刻导致标识改变，而得到新的标识。如果Petri网的库所移动托肯到变迁使能需要经过一段时间，都属于赋时Petri网。赋时Petri网可以用一个六元组来表示：

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

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

2)D={d1,d2,…,dn}表示PN中库所或变迁的时延，di为pi(ti)的时延。

赋时Petri网有3种类型:第1种是赋时变迁Petri网(TTPN)，变迁延迟一段时间后再使能；第2种是赋时库所Petri网(TPPN)，变迁一旦使能立刻激发，从输入库所中移去托肯，并在输出库所中放入相应数量的托肯，但这些托肯只有延迟一段时间后才能使用,只有可以被使用的托肯才能激发变迁[3]；第3种是时间与输出有向弧相关联，变迁使能立刻激发，但输出托肯要延迟一段时间再到达输出库所。

1.3　着色Petri网

CPN是一有向图，它可以用一五元组来表示：

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

1)此中，P，T分别为库所、变迁集合，与基本Petri网定义相同；

2)C是与P和T关联的色彩集合，C(p)是关于P中托肯的颜色的集合，C(t)是关于变迁的颜色集合。

着色Petri网是一种高级Petri网，可以看作是普通Petri网的缩写，其原理就是对托肯进行分类，以完成对网系统的折叠[4]。

着色Petri网运行规则：

1)t∈T被使能，当且仅当∀p∈P，c∈C(t)，m(p,c)≥I(p,t,c);

2)若t∈T在标识m下被使能，按照如下激活规则产生新标识记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流程设计

2.1　工件调度准则

系统如果要完成一个完整的投料、加工、入库过程，这就要求各个对象之间相互配合，才能保证整个系统有条不紊准确运行下去[5]。如往AGV中投料这个动作，首先AGV要先从加工中心上释放，等其到原料仓库后才可进行动作；工件在加工中心加工过程中要把握加工时间以及投料顺序，由于多个工件会抢用一个机床，这些加工动作是并发的，即动作会抢用资源，很容易造成冲突现象，若冲突不解决，加工中心上工件不释放，容易造成后续工序的死锁，则整个制造系统瘫痪。

管理调度过程中，遵循的原则一是合理原则，就是要保证工件加工的下一个工序开始前条件要满足，以免造成死锁；二是优化原则，在系统是活性的前提下，合理调度、分析并发的动作、加快工件的加工速度。

2.2　控制流程描述

主要控制流程为：原料装载AGV流程、AGV分配原材料流程、加工中心加工后工件调度流程、工件装配流程、成品入库流程。对于系统的每一个流程都可以由其对应的状态和变迁两个角度去分析。变迁是系统中消耗资源、使用及转换对应状态的变化，动作的发生由系统的状态来控制，而这些状态转化可以用变迁来描述。

控制流程中，变迁可能会同时发生，变迁发生后才可产生状态，状态的发生会使前提条件消失，并且会产生其它条件。

3基于赋时Petri网对DEDS控制系统的建模

3.1　系统构成

半导体加工系统以柔性制造系统为代表，FMS的建模方法与DEDS的建模方法类似，本次建模以FMS为背景。FMS的基本构成：4台以上的加工机床，自动化物料传输贮运系统，集成加工任务过程控制器，分布式计算机信息管理控制系统，自动托盘交换系统，产品检测返工系统等。

设此FMS中共有加工机床4台，2台自动导引小车，4个托盘，检测站1台，机械手设备1台，总装配机床1台，堆垛机和立体仓库。AGV将原材料运送至加工机床的暂存区，工件在机床之间由机械手进行移动。当加工完最后工序后由传送带送至检测站，检测后装配再由堆垛机放置到立体仓库。系统布局如图1所示。

图1　系统布局

从柔性制造系统的机构上来看，半导体的调度系统是最重要的部分，从原料仓库到加工机床的加工，再到各个加工机床之间工件的调度，最后到装配以及成品入库都由它来指令调度。因此，柔性制造系统自动化程度、调度准确度，以及整个系统效率高低与否均与控制系统有关。

4种半导体加工顺序见表1。

表1　半导体种类及加工顺序

3.2　控制对象

柔性制造系统的主要控制对象有如下几个部分：

1)自动导向小车(AGV)：它用于从原材料仓库取出原材料并按工件的加工要求，把原材料放置在加工机床前的缓冲区。

2)机械臂1：它是整个柔性制造系统中工件路径调度最为关键的部分。它负责每个工件从第二个工序直到最后一个工序过程中，在加工机床之间的流向控制。它的效率直接影响整个加工系统的效率。

3)堆垛机：控制成品入库。

3.3　建立模型

根据上述描述，先用赋时Petri网对半导体J1生产路线进行建模，如图2所示。

图2　工件1生产路线

每个库所和变迁具体说明见表2。

表2　库所及变迁含义

为了更清晰展示网的模型，P3出现了两次，它们是同一库所[6]。对J1工件加工路线建立赋时Petri网模型，对模型输入初始化变量[7]。初始标识M0=(1,1,0,1,0,1,0,1,0,0,0,0,1,0,0),延迟时间DT=(t0t1t2t3t4t5t6t7t8t9)T。

同理，也可以得到其它工件的加工路线Petri网模型。库所中的托肯为系统当前的一个动态对象，当变迁的使能条件满足时，托肯从输入库所移动到出变迁后库所。若某个库所中有托肯，那就表明该库所控制的对象处于当前状态。根据Petri网的运行规则，变迁前的输入库所拥有托肯，则该变迁使能。

工件的调度分为设备选工件调度和工件选设备调度[8]。两种状态的触发由一决策库所Pd来完成。当加工机床加工完一个工件时，机床处于空闲状态，若输入缓冲区中等待加工的工件不止一个，这时可以通过嵌入算法来对工件的调度进行寻优[9]。工件调度如图3所示。

图3　工件调度模块

工件的路径模块用来表示工件在加工系统中工艺加工路线过程，半导体在机床中加工的过程可以看作是工件在各个加工中心的流动路径，即当工件在一台加工机床上加工完成后，下一步需要在哪一台机床上加工[10]。工件进入加工系统，首先要进入输入缓冲区等待，工件加工完成后，进入输出缓冲区。再根据产品的工艺规程，使工件进入对应的下一个缓冲区。要加工4个工件，所以有4条路径，用4种颜色来标记。在机床层面内建立不同工序与加工设备之间对应的工艺加工关系。路径调度模块如图4所示。

图4　路径调度模块

AGV系统中只有两辆，对AGV的控制调度关系到整个系统物料流动。AGV从原材料仓库取料，工具所装载的原材料加工工艺派发到相应的机床，AGV的调度控制由颜色匹配进行控制。因此，提高AGV的利用率是提高系统运行效率的前提。

AGV的调度模块如图5所示。

图5　AGV调度模块

4结语

运用Petri网对半导体生产系统的控制系统进行建模，可以有效解决系统中所出现的异步、并发等状态。通过赋时Petri网，对库所或变迁进行赋予时延，可解决系统中的冲突问题。柔性制造系统的运行是复杂的制造过程，通过模块化和运用颜色Petri网的方法，大大降低了建模的规模。模块化的分析可以嵌入相关调度的智能算法，使Petri网与Flexsim仿真软件相结合，可运用于更复杂的系统建模，具有很强的通用性。

参考文献：

[1]曹政才.基于有色赋时Petri网的半导体生产线建模技术研究[J].系统仿真学报，2007，8：201-213.

[2]徐杜，蒋永平，张宪民.柔性制造系统原理与实践[M].北京：机械工业出版社，2001.

[3]陶丽华.基于赋时Petri网的批处理系统建模[J].设计与研究，2006，5：19-22.

[4]吴哲辉.Petri网导论[M].北京：机械工业出版社，2006.

[5]徐兵，于淼.医学检验分析仪控制系统Petri网建模[J].长春工业大学学报：自然科学版，2013，34(6)：698-703.

[6]金炳娥.基于Petri网的柔性制造系统调度问题的研究[D]：[硕士学位论文].西安：西安电子科技大学，2010：21-23.

[7]袁崇义.Petri网原理与应用[M].北京：电子工业出版社，2005.

[8]肖兵.着色Petri网及其在系统建模与仿真中的应用[J].计算机工程，2001，27：30-32.

[9]谢莹.基于Petri网和stateflow的柔性制造系统仿真[D]：[硕士学位论文].成都：西南交通大学，2003:4-9.

[10]黄波.基于Petri网的FMS建模与调度研究[D]：[硕士学位论文].南京：南京理工大学，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.

中图分类号：TP 278

文献标志码：A

文章编号：1674-1374(2015)01-0038-06

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