洪 良

(西安电子科技大学机电工程学院,陕西西安 710071)

S3PR网可达标识数的一种有效估算方法

洪 良

(西安电子科技大学机电工程学院,陕西西安 710071)

提出一种近似计算S3PR网可达标识数的代数方法.首先,基于组合学,可以找到一个S3PR网可达标识数的上限;然后,通过计算包含两个资源库所的信标,找到大部分甚至全部不可达标识的数量.这样,可达标识数上限减去不可达标识的数量就是估算的可达标识数.

柔性制造系统;Petri网;信标;可达标识

Petri网作为一种强有力的建模与分析工具,广泛地应用于资源分配系统中.在一个柔性制造系统中,原料通过不同的加工进程进入系统,并按照需求进行下一步的加工.事实上,一种资源往往被不同的加工进程所共用,因此形成的循环等待使系统陷入死锁状态.死锁问题是柔性制造系统中一个不可回避的问题.

人们基于Petri网研究了许多方法来处理柔性制造系统中的死锁问题[1-6].S3PR网是Petri网的一个子类,最早由Ezepeleta[7]提出,用于建模每一个工序只需要一种资源的生产系统.许可标识数是检验一个监督控制器的重要指标.在离散事件系统的监督控制中,区域法[8]成为一种重要的方法.Uzam和Zhou[9]通过对一个S3PR网进行区域分析,得到一个最大许可的监督控制器.但是,他们的方法需要可达图.计算可达图是一个极其耗费时间与资源的工作.当研究一个规模较大的网时,由于内存耗尽,研究者往往在计算机前守候数天、数周甚至数月却得不到任何结果.

因此,在计算可达图之前,最好预先知道待计算网的可达标识数,然后基于当前的计算能力再判断能否得到结果或者权衡是否有进行计算的必要性.基于组合学,笔者等在之前的工作[10]中计算了标识图的可达标识数.S3PR网是一种比标识图更加复杂的网.作为之前工作的一个延伸,笔者下面提出的方法可以在很短的时间内估算出一个S3PR网的可达标识数,为可达图的计算提供帮助.

1 基本定义

Petri网是一个四元组,可表示为N=(P,T,F,W),其中,P代表库所的集合,用圆圈表示;T代表变迁的集合,用方框表示;F⊆(P×T)∪(T×P),称为流关系或者有向弧的集合;W:(P×T)∪(T×P)→N,是一个映射,称为Petri网N的权函数.若f∈F,则W(f)＞0;若f∉F,则W(f)=0.

N的P向量I是映射:I:P→Z,P向量是以P为序标的列向量,Z是整数集.P向量I是Petri网N的P不变式当且仅当I≠0,且ITN=0T,其中N是一个以P×T为序标的整数矩阵,称为关联矩阵.P不变式可以表示为多集形式.P不变式I是N的P半流当且仅当I中的元素均为非负.称为I的支撑.称P不变式I是极小的若其支撑不是N的其他不变式支撑的严格超集,且其元素的最大公因子为1.

Petri网N=(P,T,F,W)的标识M是一个从P到N的映射,N是自然数集,(N,m0)称为网系统,m0称为N的初始标识.从m0可达的所有标识的集合称为(N,m0)的可达集,记为R(N,m0).令X是一个矩阵,它的每一列都是N的一个P半流,表示(N,m0)的不变式标识的集合.标识可以表示为多集形式.

S3PR网是Petri网的一个子类,其特点是每一个工序只需要一种资源参与,一个资源不能连续参与两个工序的加工.S3PR网的具体定义请参见文献[7].由于S3PR网是普通网,一个S3PR网可表示为N= (pA∪P0∪pR,T,F),其中pA代表工序库所的集合,P0代表闲置库所的集合,pR代表资源库所的集合.使用资源库所r的工序库所集合H(r)=··r∩pA,称为r的持有者.令S是N的严格极小信标,[S]称为信标S的补集,其中,SR=S∩P R.极小P半流I称为极小资源P半流或极小P r半流若其支撑仅包含一个资源库所r以及r的持有者,也就是说此时I表示为ir.

2 计算方法

2.1 可达标识数上限的计算

引理1将k个相同元素放到m个不同容器的组合数是C(m+k-1,k)=(m+k-1)! (k!(m-1)!).[11]

定义1令I是S3PR网(N,m0)的P半流,其中是由Y=生成的(N,M)的一个子网,其中NI=0是一个pI到N的映射,m0(p)·p是它的多集形式,其中,pI=这样的子网称为由I导出的(N,m0)的子网.

定义2令是由I导出的S3PR网(N,m0)的子网.NI的P向量IΔ是映射pI到Z的映射的列向量,其中pI=Z是整数集.iIΔ表示的?不变式标识的集合表示该子网不变式标识的数量.

定理1令是由I导出的S3PR网(N,m0)的子网.假定NI拥有m个库所并且在其初始标识下有k个托肯,则

证明 由引理1引出.

性质1基于组合学的乘法法则,一个S3PR网(N,m0)的不变式标识数是它所含有的所有极小pr半流ir导出的子网不变式标识数的乘积,表示为

2.2 不可达标识的移除

定义3令iX(N,m0)和R(N,m0)分别表示S3PR网(N,m0)的不变式标识的集合和可达标识的集合.(N,m0)的一个不可达标识是一个属于iX(N,m0)但不属于R(N,M)的标识.(N,m0)的不可达标识的集合可表示为U(N,m0)={M|M∈iX(N,m0)∧M∉R(N,m0)}.

定义4令irm和irn是一个S3PR网的两个极小pr半流.G=irm+irn,称为一个结构体若存在一个严格极小信标S包含资源库所rm和rn并且

定理2令G=ir+ir,是S3PR网(N,m0)的一个结构体,ri和rj是它的两个资源库所,ij是由G导出的子网.假定NG在初始标识下的托肯均在资源库所中,则·pi+m0(rj)·pj,是(NG,的一个不可达标识,其中pi∈{p|p∈H(ri),∀pk∈··p∩pA,pk∈H(rj)}和pj∈{p|p∈ H(rj),∀pk∈··p∩pA,pk∈H(ri)}.的不可达标识的集合记为

证明 应用反证法,假设iri和ir是结构体j的两个极小P r半流;分别是iri和ir中的资源库所.假设j是的一个可达状态,那么它之前的状态一定是

或者

其中,Pi={p|p∈··pi∩pA},Pj={p|p∈··pj∩pA}.假如从m1可达,根据定义有∀p∈Pi, p∈H(rj),此时中的托肯数必定大于m0(rj),这与ir是一个P不变式,其支撑中的托肯数是恒定的事实j相矛盾.因此,不可能从m1到达.同理,同样不能从M 2到达.所以,是的一个不可达标识.

定义5令G是S3PR网(N,m0)的一个结构体,是由G导出的(N,m0)的子网. UG(N,m0)={M∈iX(N,m0)称为由G导出的(N,m0)的不可达标识的集合,其元素数量记为

性质2令(N,m0)是一个含有n(n≥3)个资源库所的S3PR网,其中N=(P0∪pA∪pR,T,F),G是(N,m0)的一个结构体,RO={r|r∈pR∧r∉G}.那么,有

定理3令Gi和Gj是S3PR网(N,m0)中的两个结构体.若存在资源库所也就是说r是Gi和Gj的共享资源,则有(N,m0)∩UGj(N,m0)=ø.反之,若不存在共享资源,则有:

(2)若没有共享资源,说明两个结构体是一个网中两个独立的部分,类似于性质2,可以得到

3 算 例

图1所示的网是一个典型的S3PR网.应用笔者提出的方法来计算此网的可达标识数.此网包含7个极小pr半流.首先,根据定理1分别找到这7个pr半流导出的子网的不变式标识数,进而通过性质1得到此网的不变式标识数为34 992个.接着,可以找到4个包含两个资源库所的严格极小信标,并找到这4个严格极小信标对应的结构体,进而根据定理2可分别计算出这4个结构体导出的不可达标识数.这些不可达标识数的总和为4 860.通过分析发现,这些结构体中有两对结构体是没有共享资源库所的,根据定理3可以得到这些结构体联合导出的不可达标识的数量总共是108个.这样,得出此网的不可达标识数是4 752个.最后,从此网的不变式标识数中减掉不可达标识数,得出此网的可达标识数总共是30 240个.而实际上,此网的可达标识数是26 750个.因此,笔者估算出来的结果跟实际结果是接近的.

接下来通过表1表现笔者提出的方法计算可达标识数的准确率.表1分析了10个S3PR网的例子,计算出了每个例子的实际可达标识数和通过笔者提出的方法计算出来的可达标识数,并给出了笔者提出的方法计算可达状态数的准确率(准确率是实际可达标识数与笔者提出的方法计算的可达标识数的比值).

图1 一个S3PR网例子

表1 笔者提出的方法计算可达标识数的性能分析

从表1可以看出,通过对这10个例子的分析,由笔者提出的方法计算的可达状态数的准确率还是比较高的.但是,此文找出的不可达状态并不包括所有的不可达状态,也就是说有一部分的不可达状态可能没有找出来,所以结果只能是一个估算值.从理论上讲,此文找到的可达状态数肯定是大于或者等于准确的可达状态数.尽管如此,笔者提出的方法的时间优势还是显而易见的.通过算例分析,鉴于INA计算可达标识能力的有限性,可以应用笔者提出的方法来估算一个S3PR网的可达标识数,进而判定是否有必要通过INA来计算该网的可达图.

4 结束语

基于组合学,给出一种估算S3PR网可达标识数的方法.首先,计算网的不变式标识数;然后,通过含有两个资源库所的信标确定不可达标识数,两者的差值即为所求的结果.由于引入了组合学,此方法具有相当低的计算复杂度,可以作为计算可达图或者其他工作的前期工作.

[1] 陈玉峰,李志武.安全Petri网事件分离状态的BDD算法[J].西安电子科技大学学报,2010,37(1):119-124. Chen Yufeng,Li Zhiwu.Computation of Marking/Transition Separation Instances for Safe Petri Nets Using BDD[J]. Journal of Xidian University,2010,37(1):119-124.

[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 Systems,Man and Cybernetics:Systems,2004,34(1):38-51.

[3] Li Z W,Liu G Y,Hanisch H M,et al.Deadlock Prevention Based on Structure Reuse of Petri Net Supervisors for Flexible Manufacturing Systems[J].IEEE Transactions on Systems,Man and Cybernetics:Systems,2012,42(1): 178-191.

[4] Li Z W,Zhou M C.Two-stage Method for Synthesizing Liveness-enforcing Supervisors for Flexible Manufacturing Systems Using Petri Nets[J].IEEE Transactions on Industrial Informatics,2006,2(4):313-325.

[5] Wang S G,Wang C Y,Zhou M C,et al.A Method to Compute Strict Minimal Siphons in S3PR Based on Loop Resource Subsets[J].IEEE Transactions on Systems,Man and Cybernetics:Systems,2012,42(1):226-237.

[6] Wang S G,Wang C Y,Zhou M C.Controllability Conditions of Resultant Siphons in a Class of Petri Nets[J].IEEE Transactions on Systems,Man and Cybernetics:Systems,2012,42(5):1206-1215.

[7] Ezpeleta J,Colom J M,Martinez J.Petri Net Based Deadlock Prevention Policy for Flexible Manufacturing Systems[J]. IEEE Transactions on Robotics and Automation,1995,11(2):173-184.

[8] Ghaffari A,Rezg N,Xie X L.Design of a Live and Maximally Permissive Petri Net Controller Using the Theory of Regions[J].IEEE Transactions on Robotics and Automation,2003,19(1):137-142.

[9] Uzam M,Zhou M C.An Iterative Synthesis Approach to Petri net-based Deadlock Prevention Policy for Flexible Manufacturing Systems[J].IEEE Transactions on Systems,Man and Cybernetics:Systems,2007,37(3):362-371.

[10] Hong L,Chao D Y.Enumeration of Reachable States for Arbitrary Marked Graphs[J].IET Control Theory and Applications,2012,6(10):1536-1543.

[11] Roberts F S,Tesman B.Applied Combinatorics[M].Oxford:Taylor&Francis,2009.

(编辑:郭 华)

On efficient estimation of reachable markings for S3PR

HONG Liang
(School of Mechano-electronic Engineering,Xidian Univ.,Xi’an 710071,China)

This paper proposes a method that deals with an approximate calculation of the number of reachable markings of an S3PR in an algebraic way.Based on combinatorics,we find an upper bound of reachable markings of an S3PR.Then we try to find the number of unreachable markings by extracting siphons with two resource places.The obtained number covers most or even all of the unreachable markings.Finally,we can estimate the number of reachable markings by removing the unreachable ones from the upper bound.Calculations and analyses verify the effectiveness of the proposed method.

flexible manufacturing system;Petri net;siphon;reachable marking

TP13

A

1001-2400(2014)03-0169-05

10.3969/j.issn.1001-2400.2014.03.025

2013-01-31< class="emphasis_bold">网络出版时间:

时间:2013-11-22

国家自然科学基金资助项目(61074035);中央高校基本科研业务费资助项目(JY10000904001);教育部高等学校博士点基金资助项目(20090203110009)

洪 良(1984-),男,博士,E-mail:hongliang20030605@163.com.

http://www.cnki.net/kcms/detail/61.1076.TN.20131122.1628.201403.182_020.html