柔性制造系统Petri网模型的化简

摘要: 在一类S3PR网柔性制造系统Petri网模型N中，位置特殊资源不可能出现在网的严格极小信标和基本信标之中.因此，对于包含此类资源的网系统，为了缩小网规模，需要对其化简.化简算法对网模型进行处理，将位置特殊资源及相关操作库所、变迁和弧删去.同原网系统相比，最终得到的网系统具有较少的库所、变迁和较简单的网结构.

关键词: 柔性制造系统;Petri网;信标;资源;化简

中图分类号:TP27

文献标识码:A文章编号:1672-8513(2010)06-0417-06

Reduction for Petri Net Modeling of Flexible Manufacturing Systems

YUE Hao1，LI Wenjie2, 3

（1. Department of Computer Science and Engineering, Zhangzhou Normal University, Zhangzhou 363000, China; 2. College of Mechanical and Electronic Engineering, Shandong University of Science & Technology, Qingdao 266510, China; 3. Northwest Institute of Nuclear Technology, Xi′an 710065, China）

Abstract: In a class of Flexible Manufacturing Systems (FMS) Petri nets (PN) models N named S3PR, it is proved that neither the strict minimal siphons (SMSs) nor the elementary siphons would contain the special location resources. Therefore, the net with special location resources must be reduced in order that a smaller net can be derived. The reduction algorithm deletes the special location resources, the related transitions, as well as the arcs concerned. Finally, the net obtained has less place, less transition and a simpler net structure.

Key words: flexible manufacturing system; Petri net; siphon; resource; reduction

柔性制造系统(Flexible Manufacturing Systems，FMS)中的资源竞争会导致死锁，死锁控制问题近年来倍受关注［1-11］.我们可以选用多种形式化方法来解决死锁问题，如Petri网(Petri Net ，PN)、有限自动机、有向图.其中PN方法因为能用一种模块化和系统化的方法来描述FMS操作的不同方面和多种特征而成为最流行、应用最广泛的工具［3-4］.

文献［1］定义了一种Petri网子类S3PR网，通过给这种网系统的每一个严格极小信标(Strict Minimal Siphon，SMS)添加控制库所，而使得网系统是活的.这一工作被认为是第一次运用结构化分析进行基于监督器(Monitor-Based)的活性使能（Liveness Enforcement）Petri网监控器设计［3］.这种方法需要计算网模型的所有SMS，还有一些如文献［2,7-11］中的方法也需要计算SMS集.众所周知，Petri网信标数目相对于网规模来说是指数级的，理论上讲S3PR网中SMS的数目也是网规模大小的指数级［3］.虽然没有形式化的证明，但大家公认SMS的计算是一件代价高昂的工作［12-13］.

文献［2］提出了基本信标的概念，基本信标理论不仅能极大地减少附加控制库所和连接弧的数目，而且能达到同样或更好的控制效果.人们可以先求一个S3PR网的SMS集，然后从中选出基本信标［2］，也可以直接由一个S3PR网求其基本信标，这方面的工作包括文献［14-16］.但是，不管哪一条途径，基本信标的计算也是一项花费很大的工作.

为了缩小FMS PN模型的规模，减少SMS或基本信标求取中的计算量，本文提出了一个消除位置特殊资源［6］的化简算法.与原模型相比，执行该算法所得到的PN模型具有相同的SMS和基本信标，却具有更少的资源库所操作库所，更少的变迁，以及更简单的网结构.

1 基本概念与定义

A,B为2个集合， A表示集合A的基数，即A中元素的个数，A＼B表示在集合A中除去集合B中的元素所得到的集合.若一个列向量中的元素均为0（1），则记该列向量为[STHZ]0(1)[ST]，在不致发生混淆的情况下依然记为0（1）.

定义1 N=(P,T,F)称为一个网，其中P和T为有限、非空且互不相交的集合，P是库所的集合，T是变迁的集合，F(P×T)∪(T×P)称为流关系或连接弧集合.定义x=y∈P∪T/(y,x)∈F为节点x∈P∪T的前集，而x=y∈P∪T/(x,y)∈F为节点x∈P∪T的后集，一个集合的前集（后集）为它的所有元素的前集（后集）的并集.

定义2 设N=(P,T,F)为一个网，N的关联矩阵A:P×TZ是由P和T按照如下规则形成的,即若p∈t\t，A(p,t)=-1，若p∈t\t，A(p,t)=1，否则对于所有的p∈P和t∈T，有A(p,t)=0.P－向量I:P[WTHZ]Z[WTBX]是以P为序标的列向量，T－向量J:T[WTHZ]Z[WTBX]是以T为序标的列向量，其中[WTHZ]Z[WTBX]是整数的集合.

定义3 设N=(P,T,F)为一个网，则P－向量I是P－不变式的充要条件为I≠0且I[WTBZ]T[WTBX]A=0成立.不变式I的支撑为I={p∈P/I(p)≠0}.

定义4 设N=(P,T,F)为一个网，称非空集合SP是一个信标(siphon)，当且仅当SS成立.一个信标是极小的，当且仅当它不包含任何其它信标，若一个极小信标不包含任何P－不变式的支撑，则称它为严格极小信标(SMS).网N的所有SMS组成的集合记为Π.

本文研究对象为一类S3PR网FMS的PN模型，有关S3PR网的相关定义及性质详见文献［1］，S3PR网的一个实例见图1.基本信标的定义及性质详见文献［2］，网N的所有基本信标组成的集合记为ΠE.

如图1所示的S3PR网N的操作库所集为P=p2,p3,p4,p5,p6,p7,p8,p9，PR=p11,p12,p13,p14,p15，进程空闲库所为P0=p1,p10，资源库所为PR=p11,p12,p13,p14,p15.

2 位置特殊资源定义及其性质

根据文献［6］，本节首先定义了一类FMS Petri网模型S3PR网N中的位置特殊资源，证明了N的任意一个SMS都不包含位置特殊资源和使用这些资源的操作库所.

定义5［1］ 设N=(P∪P0∪PR,T,F)是一个S3PR网，集合XP∪P0∪PR，则以(P∪P0∪PR)为序标的0,1向量eX的各分量为

eX(p)=1,若p∈X 0,若pX

引理1［1］ 设N=ki=1Ni=(P∪P0∪PR,T,F)是一个S3PR网，则N的所有极小P－不变量的集合为

ePi∪P0i/i∈{1,2,…,k}∪eH(r)∪{r}/r∈PR

定义6［6］ 设N=(P∪P0∪PR,T,F)是一个S3PR网，称(P0)中的变迁为第1个操作工序变迁，所有第1个操作工序变迁所组成的集合记为Tb，即Tb=(P0)，对于r∈PR，若rTb，即r后集中的变迁均为第1个操作工序变迁，则称r为N的位置特殊资源，N的所有位置特殊资源库所组成的集合记为PdrR(N).[HJ]

定义7［6］ 设N=(P∪P0∪PR,T,F)是一个S3PR网，S是N的一个信标，设SR={r0,r1,r2,…,rn}，则定义L(ri)=SP∩H(ri)，i=0,1,2,…,n.若对于p∈SP，都有pP0且R(p)∈SR，则称S满足RH－条件；如果S不包含N的任何一个P－不变量的支集，则称S满足P－条件.

由定义7和严格极小信标（SMS）的定义知S是N的一个极小信标且S满足P－条件，当且仅当S是N的一个SMS.下面的引理说明若一个信标S满足RH－条件而一个资源库所r0不在S之中，则任何使用r0的操作库所也不在S之中.

引理2［6］ 设N=(P∪P0∪PR,T,F)是一个S3PR网，S是N的一个信标，S满足RH－条件，r0∈PR，且r0S，则S∩(r0∪H(r0))=.

引理3［6］ 设N=(P∪P0∪PR,T,F)是一个S3PR网，S是N的一个信标，S满足RH－条件，设SR={r0,r1,r2,…,rn}，则SP=∪ni=0L(ri).

引理4［6］ 设S是S3PR网N的一个信标，则S不包含N的任何一个P－不变量的支集当且仅当S不包含N的任何一个极小P－不

变量的支集.

引理5［1］ 设N=(P∪P0∪PR,T,F)是一个S3PR网，S(≠)是一个不包含N的任何一个P－不变量支集的信标，则S∩PR>1.

这个引理告诉我们，不包含N的任何一个P－不变量支集的信标（即信标满足P－条件）至少包含2个资源库所.下面的引理说明任何一个第1个操作工序变迁，其后集中没有资源库所.

引理6［6］ 设N=(P∪P0∪PR,T,F)是一个S3PR网，则t∈Tb，t(r)=.

引理7［1］ 设N=(P∪P0∪PR,T,F)是一个S3PR网，则对于S∈Π，都有S∪CS=SR∪(∪r∈SRH(r)).

引理8［6］ 设N=(P∪P0∪PR,T,F)是一个S3PR网，则对于S∈Π，p∈SP，都有pP0且R(p)∈SR.

推论1［6］ 设N是一个S3PR网，S是N的任意一个SMS，则S满足RH－条件.

上面的推论告诉我们，N的任何一个SMS都满足RH－条件，下面的引理说明位置特殊资源库所不在任何一个SMS中.

引理9［6］ 设N是一个S3PR网，若r0是N的任意一个位置特殊资源，则对N的任意一个SMS，S∈Π，都有r0S.

下面的推论告诉我们，N的任何一个SMS都不包含使用位置特殊资源的操作库所.

推论2［6］ 设N是一个S3PR网，若r0是N的任意一个位置特殊资源，S是N的任意一个SMS，即S∈Π，则H(r0)∩S=.

3 除去位置特殊资源及相关网元素

本节首先给出一个化简函数Reduction(N,r0)，用来删除N中的一个位置特殊资源r0，使用这个资源的操作库所，以及相关的变迁和连接弧.随后，文中又证明了化简得到的网N′同原网N具有相同的SMS和基本信标.

定义8［1］ 设N=(P,T,F)是一个网，XP∪T，则记NX=(PX,TX,FX)为N的由X生成的网，其中PX=P∩X，TX=T∩X，FX=F∩(X×X).

函数1 N′=Reduction(N,r0)

输入 带有位置特殊资源r0的FMS Petri网模型N，N是一个S3PR网，N=ki=1Ni=(P∪P0∪PR,T,F).

输出 消去r0之后的S3PR网N′=(P′∪P0∪P′R,T′,F′).

Tb(r0)r0，H(r0)=(Tb(r0))，Tc(r0)=r0； // Tb(r0)是要被删去的变迁集合，这时其中的任何一个变迁t都是第1个操作工序变迁，由引理6知t(r)=，因此使用r0的操作库所集为H(r0)=r0∩P=（Tb(r0)）∩P=（Tb(r0)），Tc(r0)是新产生的N′中的第1个操作工序变迁集合；

for(Tc(r0)中的每一个变迁t) do //对于t∈Tc(r0)；if(t∩P0≠) then //若t后集中有进程空闲库所，则t应当被删去；

Tc(r0)=Tc(r0)＼{t};

Tb(r0)=Tb(r0)∪{t};

end if

X=P0∪(P＼ H(r0))∪(PR＼ {r0})∪(T＼Tb(r0));//在N中删去资源库所r0,以及H(r0)和相关变迁；N=NX=(PX,TX,FX);

for (i=1 to k) do //对于组成N的每一个S2PR Ni;

在N中加上弧集P0i×(Tc(r0)∩Ti);

return N.

例如图1的S3PR网N，由定义6，Tb=t1,t8，由于(p11)=t1Tb，因此p11是N的一个位置特殊资源，调用函数Reduction(N,p11)，Tb(p11)=t1，Tc(p11)=t2,t6，H(p11)=p7，由于t2∩P0=t6∩P0=，所以函数Reduction(N,p11)中的第1个for循环不执行:

X=P0∪(P\p7)∪(PR\p11)∪(T\t1).

由X得出NX后再加上弧(p1,t2),(p1,t6)，最后的得到N′，如图2所示.

函数1对S3PR网N处理后得到N′=(P′∪P0∪P′R,T′,F′)，N′也是一个S3PR网，N与N′的关系如下：N′中的资源库所比N少了一个r0，即P′R=PR－{r0}，对于r∈PdrR(N)＼ {r0}，r∈PdrR(N′)；空闲库所集不变，都是P0，操作库所少了H(r0)，即P′=P＼H(r0)，变迁集中少了Tb(r0)，即T′=T＼Tb(r0)，相关的每一个加工路径上少了一个操作库所p∈Pi∩H(r0)，对于资源r∈P′R而言，在N′中的H(r)同在N中的H(r)是相同的.

定义9 设N=(P∪P0∪PR,T,F)是一个S3PR网， N′是由N经过函数1化简后得到的S3PR网，设化简过程中除去的位置特殊资源库所为r0，r0∈PdrR(N)，则N的不包含PdrR(N)中库所的且满足RH－条件和P－条件的信标组成的集合记为Π1，Π1中所有极小元素组成的集合记为Π2；N′不包含PdrR(N)中库所的且满足RH－条件和P－条件的信标组成的集合记为Π3，Π3中所有极小元素组成的集合记为Π4，N′的所有SMS组成的集合记为Π′，N′的所有基本信标组成的集合记为Π′E.

定理1 设N=(P∪P0∪PR,T,F)是一个带有位置特殊资源r0的S3PR网，N′是由N经过函数1化简除去r0后得到的S3PR网:

N′=(P′∪P0∪P′R,T′,F′)

=(P0∪(P＼H(r0))∪(PR＼r0),T′,F′).

Π1，Π3如前文定义，则有Π1=Π3.

证明

1)首先证明Π1Π3.

①本节证明对于S∈Π1，S在N′中也是一个信标.由S∩PdrR=，r0∈PdrR知r0SR，由S满足RH－条件结合引理3知SP=∪ni=1L(ri)，S具有S=Sr∪(∪ni=1L(ri))的形式，其中Sr={r1,r2,…,rn}，r0Sr.由S是N的一个信标知在N中，对p∈S，t∈p，p1∈S，使得.对于p∈S，分2种情况讨论.

情况1：若p∈Sr，由于r0Sr，所以p≠r0，N中的变迁集[KG-*3]p，库所集[KG-*3]p，以及弧集F∩((p×{p})∪(p×p))在N′中都保留下来，所以在N′中也有p∈Sr，t∈p，p1∈S，使得t∈p1.

情况2：若p∈∪ni=1L(ri)，即存在j∈{1,2,…,n}，使得p∈L(rj)H(rj)，在N中，t∈p，rj=(r)t，由r0≠rj知变迁集p，库所集(r)(p)，以及弧集F∩((p×{p})∪((r)(p)×p))在N′中都保留下来，所以在N′中也有p∈∪ni=1L(ri)，t∈p， r∈SrS，使得r=(r)t，t∈r.

由情况1及情况2知，Π′=在N′中也是一个信标.

②本节证明S在N′中满足RH－条件和P－条件.由函数1知N′也是一个S3PR网，并且资源库所集为P′R=PR＼{r0}，对于资源r∈P′R而言，在N′中的H(r)同在N中的H(r)是相同的，S在N中满足RH－条件知S∩P0=，S在N中满足RH－条件且r0S，由引理2知S∩(r0∪H(r0))=，结合S∩P0=知SP′R∪(∪r∈P′RH(r))，又N′与N的进程空闲库所集均为P0，所以由S在N中满足RH－条件知S在N′中也满足RH－条件；由引理1知网N的极小P－不变量的集合为:

由S在N中满足P－条件知信标S不包含INVP(N)中任何一个元素的支集，结合S∩P0=和INVP(N)与INVP(N′)之间的关系，知S不包含INVP(N′)中任何一个元素的支集，由引理4知S在N′中满足P－条件.

对于S∈Π1，S∩PdrR(N)=并且由①知S在N′中也是一个信标，由②知S在N′中也满足P－条件和RH－条件，因此S∈Π3.有Π1Π3成立.

2)类似可证Π3Π1.

由1)，2)知Π3＝Π1.

推论3 设N=(P∪P0∪PR,T,F)是一个带有位置特殊资源r0的S3PR网，N′是由N经过函数1化简除去r0后得到的S3PR网，则有Π2=Π4.

证明 由定理1知Π1=Π3，由于Π2和Π4分别是Π1，Π3中的极小元素组成的集合，因此有Π2=Π4.

定理2 设N=(P∪P0∪PR,T,F)是一个S3PR网，则对于N来说，Π=Π2.

证明 1）首先证明Π2Π.对于S∈Π2，假设SΠ，则由于S满足P－条件而SΠ,所以S不是N的极小信标，从S出发可以找到一个极小信标S′，S′S，由S′S知S′满足P－条件，所以S′是N的一个SMS，由推论1知S′满足RH－条件，由引理9知S′∩PdrR(N)=，所以S′∈Π1.由S′S且S′∈Π1知，S不是Π1中的极小元素，即SΠ2，矛盾.故若S∈Π2，则S∈Π.

2）其次证明ΠΠ2.对于S∈Π，则S满足P－条件，S∈Π结合推论1知S也满足RH－条件，又由引理9知对于任意一个位置特殊资源r0，都有r0S,所以S∈Π1，假设S不是Π1中的极小元素，则存在S′∈Π1，S′S，S′是N的一个信标，这同S是N的一个极小信标矛盾，因此S∈Π2.ΠΠ2成立.

定理3 设N=(P∪P0∪PR,T,F)是一个S3PR网，则对于N′来说，Π′=Π4.

证明 同定理2的证明类似.

定理4 设N=(P∪P0∪PR,T,F)是一个带有位置特殊资源r0的S3PR网，N′是由N经过函数1化简除去r0后得到的S3PR网，则有Π=Π′.

证明 由定理2知Π=Π2，由定理3知Π′=Π4，而由推论3知Π2=Π4，因此有Π=Π′.

推论4 N与N′定义如定理4，则ΠE=Π′E.

证明 由网基本信标的定义结合定理4易知.

4 结语

解决柔性制造系统中的死锁控制问题，需要处理系统的Petri网模型.由于处理算法的时间复杂度大部分都是非多项式（例如，是指数级的），因此，网模型规模大小往往会对计算量和处理时间产生重大影响.

本文考查包含一类位置特殊资源的S3PR网柔性制造系统Petri网模型，提出了一个化简算法,删去一个位置特殊资源，以及相关操作库所、变迁和弧删去,最终得到的网系同原网系统拥有相同的严格极小信标和基本信标.同时，与原网系统相比，最终得到的网系统具有更少的库所、变迁和较简单的网结构.

当然，如文献［11］的作者邢科义教授指出，文中算法能在多大程度上简化系统，这需要有一个定量的描述或结论（对有些系统简化好像很有限）.另外，对本文中算法的时间复杂度的分析，笔者将另文讨论.

参考文献:

［1］EZPELETA J, COLOM J M, MARINEZ J. A Petri net based deadlock prevention policy for flexible manufacturing systems［J］.IEEE Trans Robot Automat, 1995,11:173-184.

［2］LI Z W, ZHOU M C. Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems［J］.IEEE Transactions on Sytems, Man, and Cybernetics,Part A:Systems and Humans, 2004,34(1): 38-51.

［3］LI Z W, ZHOU M C, WU N Q. A Survey and comparison of Petri net based deadlock prevention policies for flexible manufacturing systems［J］.IEEE Transactions on Sytems, Man, and Cybernetics,Part C:Applications and Reviews, 2008,38(2):173-185.

［4］FANTI M P, MAIONE B, TURCHIANO B. Comparing digraph and Petri net approaches to deadlock avoidance in FMS［J］.IEEE Transactions on Sytems, Man, and Cybernetics,Part B: Cybernetics, 2000,30(5):783-795.

［5］李志武.徐平江.柔性制造系统活性监督控制器的简化设计［J］.西安电子科技大学学报:自然科学版，2006，33(3):442-447.

［6］YUE H.One type of special resources in Petri nets models of flexible manufacturing systems［C］// Proc of the 8th World Congress on Intelligent Control and Automation. Shandong, 2010: 2319-2322.

［7］ABDALLAH I B, ElMARAGHY H A.Deadlock prevention and avoidance in FMS: A Petri net based approach［J］.Int J Adv Manuf Tech, 1998. 14:704-715.

［8］BARKAOUI K, ABDALLAH I B.A deadlock prevention method for a class of FMS［C］ //Proc IEEE Int Conf Syst, Man, Cybern.Vancouver, 1995, 4119-4124.

［9］BARKAOUI K, CHAOUI A, ZOUARI B.Supervisory control of discrete event systems based on structure theory of Petri nets［C］// Proc IEEE Int Conf Syst, Man, Cybern.Orlando, 1997, 3750-3755.

［10］HUANG Y S. Design of deadlock prevention supervisors using Petri nets［J］.Int J Adv Manuf. Tech, 2007, 35(3-4): 349-362.

［11］XING K Y, HU B S.Optimal liveness Petri net supervisor synthesis for automated manufacturing systems［C］//Proc IEEE Int Conf Syst, Man, Cybern.Hawaii, 2005:282-287.

［12］CORDONE R, FERRARINI L, PIRODDI L. Enumeration algorithms for minimal siphons in Petri nets based on place constraints［J］. IEEE Transactions on Sytems, Man, and Cybernetics,Part A:Systems and Humans, 2005,35(6):844-854.

［13］TRICAS F, EZPELETA puting minimal siphons in Petri net models of resource allocation systems: a parallel solution［J］. IEEE Transactions on Sytems, Man, and Cybernetics,Part A:Systems and Humans, 2006, 36(3):532-539.

［14］LI Z W, HU H, ZHOU M C. A polynomial algorithm to find a set of elementary siphons in a class of Petri nets［C］//Proc IEEE Int Conf Syst, Man, Cybern. Hague, 2004:4861-4866.

［15］CHAO D putation of elementary siphons in Petri nets for deadlock control［J］ .British Computer Society,2006, 49(4):470-479.

［16］CHAO D Y.Incremental approach to computation of elementary siphons for arbitrary simple sequential processes with resources［J］.IET Control Theory Appl, 2008, 2(2):168-179.