（机械电子工程专业论文）基于petri网的柔性制造系统死锁预防策略.pdf

摘要 一类基于p e t r i 网来防止柔性制造系统出现死锁的方法是通过给每一个严格极 小信标添加一个控制库所和连接弧来保证每一个严格极小信标不会被清空。通常， 随着网规模的增大，极小信标的的数目会激增该方法的缺点是绐网系统添加了 过多的控制库所，这样便会使导致最终网系统比初始网系统复杂很多。本文致力 于在得到同样控制效果的同时减少新添加库所的研究。 本文基于已有不变式法、区域法，根据基本信标、冗余信标的概念，提出两 种死锁预防策略。在策略一中，通过将网系统中控制库所的流出弧提前来简化控 制策略。在策略二中，通过数学计算为每一个可被清空的严格极小信标添加多个 控制库所，在这几个库所的共同作用下来保证该信标不被清空，添加的控制库所 还对别的可被清空的信标起一定的控制作用，最终使受控网系统中所有严格极小 信标不被清空，同时受控网系统为普通网且不生成可达图，以达到简化控制策略 的目的。与现有方法相比，策略一添加较少的控制库所和连接弧，策略二对网系 统的行为限制尽可能的少。最后，我们将用柔性制造系统的例子来说明这两种策 略同以往方法相比的优点。 关键词：p o t ri 网柔性制造系统死锁预防基本倍标s 3 p r a b s t r a c t a v a r i e t yo fi m p o r t a n tp e t f i n e t b a s e dm e t h o d st o p r e v e n td e a d l o c k sa r i s i n gi n f l e x i b l em a n u f a c t u r i n g s y s t e m s ( f m s ) a r e t oa d ds o m ec o n t r o lp l a c e sa n dr e l a t e d8 1 1 2 8t o s t r i c tm i n i m a l s i p h o n sr s m s ) s u c h t h a tn os i p h o nc a nb ee m p t i e d s i n c et h en u m b e ro f s i p h o n sg r o w s i n g e n e r a le x p o n e n t i a l l y w i t h r e s p e c t t oap e t r in e t s i z e ，t h e i r d i s a d v a n t a g e sl i ei nt h a tt h e yo f t e na d dt o om a n y a d d i t i o n a lp l a c e st ot h en e t ，t h e r e b y m a k i n gt h er e s u l t i n gn e ts u p e r v i s o rm o r ec o m p l e xt h a nt h eo r i g i n a l l yb u l i to n e t h i s t h e s i se x p l o r e sw a y st om i n i m i z et h en e wa d d i t i o n so f p l a c e sw h i l ea c h i e v i n gt h es a m e c o n t r o lp u r p o s e b a s e do nt h e e x i s t i n gp o l i c i e s o fp - i n v a r i a n t sa n dt h e t h e o r y o fr e g i o n s ，t w o d e a d l o c kp r e v e n t i o np o l i c i e sa r ed e v e l o p e d w ef i n a l l yc a ng e t ad e a d l o c k f r e ep e t r in e t s u p e r v i s o ru s i n gt h ef i r s tm e t h o di nw h i c ht h ef l o w i n ga r c so ft h ec o n t r o lp l a c e sa r e b r o u g h tf o r w a r d i nt h e s e c o n dm e t h o d ，w ea d dp l a c e sf o re a c hs m st h a tc a nb e e m p t i e d t op r e v e n ti tf r o mb e i n gu n m a r k e da n dt h ep l a c e sa d d e dc a na l s oc o n t r o lo t h e r s s m s f i n a l l y a l ls m si nt h en e tc a n n o tb ee m p t i e d w ed on o th a v et og e n e r a t e r e a c h a b i l i t yg r a p hi nt h i sm e t h o d a s m a l ln u m b e ro fc o n t r o lp l a c e sa n dr e l a t e da r c sa r e a d d e di nt h ef i r s ta p p r o a c h t h eh e h a v i o ro ft h en e ti sf a rl e s sr e s t r i c t e du s i n g t h es e c o n d a p p r o a c h e x a m p l e s o ff l e x i b l e m a n u f a c t u r i n gs y s t e m s a r e g i v e n t oi l l u s t r a t et h e a d v a n t a g e so f o u r a p p r o a c h e s o v e rt h ee x i s t i n gw o r k k e y w o r d s ：p e t r in e t sf m sd e a d l o c k p r e v e n t i o n e l e m e n t a r ys i p h o n s 3 p r 独创性( 或创新性) 声明 y 5 8 3 6 8 1 本人声明所呈交的论文是我个人在导师指导下进行的研究丁作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文r l - r 不 包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名 下毒苎 k ，口日期2 口弹3 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。本人保证 毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 本人签名：王谐日期2 0 州 导师签名 笫一章绪论 第一章绪论 1 1 研究背景与意义 在柔性制造系统中，不同类型的原料在离散的时间点进入系统，进行加丁，它 们共享诸如机床、机器人、夹具等有限的资源。每种原料按照特定的生产流程来 使用系统中的资源。所有的生产流程并发执行，这样便会引起共享资源的竞争资 源竞争便会产生死锁，此时两个或多个工序便会分别等待其它工序释放资源，我们 不希望出现死锁。死锁通常出现在一一个系统的几个并行进行的复杂加工进程的最 终状态，我们一散很难预先知道系统在什么情况下出现死锁。所以提出种有效的 柔性制造系统控制策略，使系统不再发生死锁十分必要。在处理各种不同的柔性制 造系统时，人们很关心如何有效处理发生死锁的问题。本文研究就是柔性制造系统 的死锁问题。 1 9 6 2 年，c a p e t r i 提出了p e 埘网理论。p e 埘网作为一种数学方法，在离散事 件系统建模、分析、性能评价和控制设计中得到了广泛的应用。作为一种控制系 统的设计手段，从2 0 世纪7 0 年代开始，p e t r i 网以其能够模拟系统的并发和冲突行 为以及反映系统动态特性而受到了广泛关注。柔性制造系统作为1 种典型的离散 事件系统一直是p e t r i 网的重要应用领域。 基于p e t r i 网人们研究了很多方法来处理柔性制造系统中的死锁问题。大致可 归为以下几类：死锁避免方法；死锁校正方法；综合法；死锁预防方法。 死锁避免方法是通过控制对资源的申请使系统避免产生死锁，其思路是如果 许可1 个资源的请求会导致死锁，那么就不能允许该申请有效。对网模型而肓，这 种方法实际上是有意地控制某些可使能的变迁发射，以免p e t r i 网系统陷入死锁。 这种限制资源分配的策略也具有一定的保守性。最著名的死锁避免算法是银行家 算法。 。 5 】中的方法是通过向前搜索网系统的可达标识图来避免死锁的。当给定一个 网系统的当前标识后，算法就会确定所有规定搜索长度内的标识状态：通过判断 这些标识是否是死锁标识，就可以找到那些发射后会导致系统死锁的变迁。在网 系统运行的时候，只要不使能这类变迁就可以避免系统产生死锁。这种方法可以 使系统有限度地避免死锁，但确定搜索步数有很大困难；而且还必须提供系统出 现死锁时的修复策略。 8 】中提供了一种针对柔性制造系统的死锁避免算法，称为d d a 算法。这种方 法通过执行以下两个策略来避免系统死锁。其一是使p e t r i 网系统q 1 的某个库所集 合r 1 的托肯数不能超过该库所集合未占用的资源中的托肯总数；其二是当该库所 基十p e t r i 删的案件制造系缝死锁预j l j ：i 毁略 集合中的片所同时申请多个资源并且这些资源都可以申请到时，它只能占用个 资源。d d a 算法在每工步开始申请共享资源时，通过有意的不使能某螳变迁， 来保证以上两条策略的实施。 9 川i 的死锁避免算法是建立在最小资源需求的概念的基础之上，即使得系统 l 占用共享资源最少的工序优先发射。这种算法具有多项式复杂度，并且放松了 对系统的约束，因而比 6 】中的方法具有更广泛的应用。 【8 8 【9 中的方法比较类似。它们都是从死锁结构的概念出发，明确了死锁产生 的条件，即! 系统的死锁结构中占月j 的资源等于资源的总数时，系统就会陷入死 锁状态；并在此皋础上形成了自身的死锁避免算法。 由于需要考虑大型的柔性制造系统，【1 0 】在p e t r i 网模型的基础上针对资源分 配系统开发了。4 种专门的新颖的建模和分析方法。它用整数规划的方法来避免系 统死锁。但是由于它考虑了资源分配系统中的大部分情况，从而使得网模型不再 只是适用于”般网，这就大大限制了它的应用。 第二种是死锁校正方法 1 1 】 1 2 。这种方法并不刻意去追求系统的无死锁性或 活性，而是4 日检测到系统发生了死锁，通过自动或人工的方法解锁。这种方法往 往会达到较高的生产率和资源利用率，但控制工程师必须对可能发生死锁的生产 环节有充分的认识，在设计单机( 如机器人，机床) 控制器时，需要设计相应的控制 程序以便解锁时应用。此外，可能还需要一些附加的设备供解锁时使用，其结果 又是要加大投入。 综合法的思路是建立。些具有某种性质的子网模型，使得在某类p e t r i 网中， 针对这些特殊的性质，可以采用特定的综合策略使得最终的网模型具有希望的性 质【1 3 】【1 4 】 1 5 】。其优点在于控制策略简单实用，但只能用在p e t r i 网的特定子类中。 死锁预防方法【4 】 1 1 的目标是设计一个系统，该系统所对应的p e t r i 网模型 本身就是无死锁的或者是活的。这种方法从逻辑上保证了系统中不会出现死锁， 因而不必再去控制系统运行过程中对资源的申请。【1 1 】是通过限制进入系统工件的 数量( 对于网系统而言，就是控制网系统的初始标识) ，使系统的p e t r i 网模型是活的， 从而在原则上保证系统不会陷入死锁。这种方法从确保系统不存在任何死锁的角 度出发，相应地静态调配资源( 设置初始标识) ，从而提高资源的利用率。应该指出， 这种方法尽管保证了系统的全局活性，但具有较大的保守性，从而降低了系统的 生产率和资源的利用率。 近年来出现的死锁预防方法大都采用在目标p e t r i 网模型中增加新的控制库所 的方法。通过增加控制库所限制网系统的行为，从而保证网系统是无死锁的。 e z p e l e t a 等人 6 应用p e t r i 网结构理论为柔性制造系统设计了控制器，最终得到 无死锁的网系统。他们定义了，类普通保守网的子类一s 3 p r 网，即含有资源的简 单加t 进程系统，他们要求目标p e t r i 网为s 3 p r 网。并且为每个严格极小信标( 简 第章绪论 3 记为s m s ，。个s m s 就是一个能被清空的极小信标) 添加个监控库所米强制保证 网的活性。该方法简单有效，然而，由于添加了过多的监督器和弧，使得p e t r i 网 控制器比原先先建立的p e t r i 网模型复杂很多。同时，系统的行为也受到了极大的 限制。 如果在一个p c t r i 网中没有s m s 被清空，则该p e t f i 网是无死锁的。同时它也 是一些p c t r i 网子类( 如自由选择网和非对称自由选择网) 活的充分条件。论文将引 用冗余信标和基本信标的概念【l 】。结论表明在一定的条件下，如果使得个p e t r i 网中所有的基本信标不被清空，则其冗余信标也不会被清空，进步说其所有的 s m s 都不会被清空。这意味着如果要使一个p e t r i 网没有信标被清空时，并不需要 对所有的s m s 都添加控制。因此，基于基本信标，可以得到一个较为简单的p e t r i 网控制模型，这个模型中包含较少的添加库所和有向弧，达到简化控制器设计的 目的。 基于p e t r i 网研究系统的死锁问题取得了不少成果 6 】 7 】 1 6 】 1 7 】 1 8 】，但是仍 然有许多问题需要进一步研究和解决。此外许多控制方法和策略对系统的行为施 加了过多的限制，降低了系统的性能。 论文致力于死锁预防方法的研究，通过分析p e t r i 网的结构特性，运用代数的 方法保证系统的p e t r i 网模型是无死锁的。 1 2 本文完成的主要工作 论文系统地论述了现有的两种预防死锁策略，通过对网结构的分析，研究了 两种针对s 3 p r 网的新死锁预防策略。 在策略一中，着重针对具有分支结构的s 3 p r 网模型，将网系统中控制库所的 流出弧提前，使得在同样得到无死锁网系统的前提下，减小对原网系统行为的限 制，同时简化控制策略。表现在网模型上，便是网系统的可达状态明显增加，控 制库所的连接弧减少。 在策略二中，原先，对于一个可被清空的严格极小信标添加一个控制库所v s ， r - 个v s 也只能控制与之对应的信标，而不能控制别的严格极小信标，即控制库所 v s 和信标之间是一一对应的关系，这样当发射某个变迁后，若信标中的托肯数变 化量大于等于2 时，则与该信标对应的控制库所v s 的连接弧的权值会大于等于2 ， 得到的受控网系统必定不是普通网。根据以上分析，我们对一个可被清空的严格 极小信标添加多个控制库所，在这几个库所的共同作用下来保证该信标不被清空， 添加的控制库所还对别的可被清空的严格极小信标起一定的控制作用。即控制片 丛j | p e l r i 划的柔十牛制造系统死锁预胁籀峪 所和信标之间是多多对应的关系，最终使受控网系统为普通网。我们通过数学计 算添加控制库所，使可被清空的严格极小信标在新网中受到p 不变式的控制，最 终得到受控的网系统，同时受控网系统为普通网，且在计算过程中不需要牛成可 达图，成功避免了状态爆炸的问题，达到简化控制策略的目的。 总之，论文主要研究了柔性制造系统p e t r i 网的死锁预防策略，得到了定的 成果。相信这些工作对p e t r i 网理论的进一步应用和发展都是十分有益的。限于时 间、条件和个人的认识，文中很多方面一定有所欠缺，恳请指正。 第二章p e t r i 网的基本概念 第二章p e t ri 网的基本概念 本章给出p e t r i 网的摹本概念和形式定义 1 ，【2 】， 1 9 】，以及后面所要刖到的 些定理和推论。 2 1p e t r i 网的基本理论 2 1 1p e t r i 网的基定义 【定义2 1 】库所变迁网( 简称引，网) 是。个四元组，= ( p ，lf ，功，其 中p 代表库所的集合，r 代表变迁的集合，并且p 和r 是有限非空和不相交的集 合；f c ( p x l ) u ( 7 k p ) 称为有向弧集；w ：f - - i a o 称为f 中弧上的权，胙 o ，1 ， 2 ，) 。 称n = ( p ，t ，f ，叨为普通网( o r d i n a r yn e t ) ，当且仅当v ，f ，蹄们一1 ，普通 网可以记做= 妒，t ，叼。v p e p ，v f e n 如果0 。f ) r 且坤劬，0 = 1 ，则称| v 为普通p t i 嘲( 尸t o r d i n a r y n e t ) 。一个普通网肯定是一个普通p t 网。当j ，三p ，0e f , 晰 l 时，称n = 妒，t ，f ，r e ) 为一般网( g e n e r a l n e t ) 。 【定义2 2 】令n = ( p ，t ，f ，聊是个p e t r i 网，节点x e l ：，u t 的前置集定义 为 x = y p u t f ( y ，曲用。其后置集定义为x = y e p o t f 亿y ) e 日。节点的集合 h e _ p u t 的前置集( 后置集) 定义为日= 。h * x ( t c = u 。h r ) 。 【定义2 3 】如果n = ( ，t ，f ，哟是普通网，且vt e t , f t l = l t i = t ，则称是 状态机( s t a t em a c h i n e ) 。 【定义2 4 】如果= ( p ，lf ，叨是普通网，并且有v p p ，l p l = i p 。i = l ，则称 是标识图( m a r k e dg r a p h ) 。 【定义2 5 】如果一个p e t r i 网系统c ，m o ) 的任意一个节点和其它节点中的任意 一个之间总存在一条连接路径则称该网是强连通的。 【定义2 6 】如果一个p e t r i 网系统( ，m o ) 既是一个状态机又是强连通的，则称 其为强连通的状态机。 【定义2 7 】网= ( p ，t ，f ，聊称为纯的，当且仅当- - , 3 ( x ，力( p x t ) u ( t x p ) ：o ， 力f ( y ，曲f 非纯网可以在保持动态性质不变的情况下化为纯网。下面要讨论的网都是纯 网。 【定义2 8 】令n ；( p ，nf ，聊是个网。 1 1n 的标识是映射膨：p - - ) i n ； 2 1 一个变迁t e t 在m 下称为使能的记为m o ，当且仅当v p 。f ：m ( p ) 阡q ，f ) ： 3 ) 若研p 成立，则t 发射后，产生另一新标识m ，记为m i t ) m ，有 兰 苎主! 坐! l ! 塑垂壁型堕墨丝至塑堡堕篁堕 m ( p ) 吖( p ) w ( p ，t ) m ( p ) + ( p ，t ) m ( p ) 一w ( p , t ) + ( t , p ) 肘( p ) 4 ) 网n 从标识开始的所有可达标识的集合记为r ( n ，g o ) 或m o d 。它是r 个 最小集，即m o e r ( n ，m o ) ，m e 露( ，m o ) a m z 渺圳，r ( n ，娲) ； 5 ) j t l ，t 2 ，“r 时，俨t i t 2 “称为出现序列，当且仪! b 存在标识m o ，m ， 霸满足) 1 o 【哟i t ) 鸠； 6 ) 对于网和标识m o ，( ，m o ) 称为一个网系统； 7 ) 网n = ，t ，f ，j r ) 的关联矩阵定义为以p 和，为序标的矩阵m ：尸n z ，z 是整数的集合，且 【 ( p ，r ) = ( p , t ) 矽( t , p ) 一矿( p f ) + 矿( t j 口) 0 p 。t i t 。 p 九t p t i t 其它 2 1 2p e t r i 网的活性及不变式 定义2 9 】令p ，l 只聊是一个网，m o 是的一。个标识 1 )一个变迁t 在标识m o 下是活的，当且仅当v m r ( n ，m o ) ，了m r ( ，g o ) ： m i o 成立； 2 ) ( ，g o ) 是死锁的，当且仅当- 、3 t e rm oi d 成立； 3 ) ( ，m o ) 是无死锁( 弱活) 的，当且仅当 q m e r ( ，肘o ) ，3 t e t ：m f ) 成立； 4 ) ( n ，m 0 是活的，当且仅当v f t - t 在标识m o 下是活的； 5 ) ( j v ，m o ) 是有界的，当且仅当j 赡j m o ) ，v m r ( n ，m o ) ，v p p ：m ) 豇 6 ) ( ，m o ) 是结构有界的当且仅当对于任意的有限的初始标识，它都是有界的； 值得说明的是，对于资源有限的实际系统而言，它的p e t a - i 网模型一般都是结 构有界的。所有元素均为o ( 1 ) 的列向量记为0 ( 1 ) 。 【定义2 1 0 】令n = ( p ，t ，f ，叻是一个网。 1 ) 以p 为序标的列向量v ：p - - ) z 称为的p - 向量。 2 ) 以丁为序标的列向量j ：t - z 称为的p 向量。 3 ) 称尸- 向量，是一个p - 不变式( 库所不变式) 当且仅当j 卸且j t 咖= 0 7 。 l i l = p e p l l ( p ) 0 称为j 的支撑。 4 1 称个p 一不变式是极小的当且仅当它的支撑中不包含任何其它p - 不变式的支 撑。本文1 - 的p 不变式，如果没有特别声明，则都是极小只不变式。 扩- 二n 坤州砷舵 第二章p e t rl 屑的基本概念 5 ) 称f 向量l ，是一一个p 不变式( 变迁不变式) 当且仪当j o 且 1 j = o 。 | | i ，| f f 卸j ( f ) o ) 称为t ，的支撑， 6 ) 称是被p - 不变式( r - 不变式j ) 覆盖的当且仪当v p e p ：j ) o ( v r 弘以r ) 0 ) 。 被p 不变式覆盖的的网也称为是保守的。 【定义2 1 1 】( m o ) 是个网系统，n = ( p ，t ，f ，聊。 1 1 称个非空集台s c _ p 是个信标( s i p h o n ) ，! 且仅二s o _ s 成立i 2 ) 称一一个非空集台s o p 是一个陷阱( t r a p ) ，当且仅当s j r 成立； 3 ) 称个信标( 陷阱) 是极小的，当且仅当不存在其它信标( 陷阱) 是它的真子集； 4 ) 称p e p 是被标识m 标记的，当且仅当肘p ) o 。称一个集合s o p 是被标识m 标记的，当且仅当s 中至少有一个元素被j 】i f 标记。s 中的托肯数麒i s = 乙e p f 如) ； 5 1 不包含任何p 一不变式支撑的信标称为严格信标。一个严格信标有可能被清空； 6 1一个既是极小又是严格的信标，称为严格极小信标( s i m s ) 。 2 1 3p e t r i 网的一些基本性质 【性质2 1 】网系统( ，m o ) ，i 是= ( p ，t ，f 叨的一个p 一不变式，v m e r ( n , m 曲：p - m = 1 w m o 。 【性质2 2 1 网系统( ，m o ) ，j 是= p ，lf ，叻的一个7 - 不变式，0 j i 中所 有的变迁发射一次，可能会使网系统回到初始标识。 【性质2 3 】网系统( ，m o ) ，j v = ( p ，t ，f ，叻，s _ c p 是一个信标，若3 m e r ( n , d 毛) ： 心鄙= 0 ，则s 以后永远不会被标记，称为被清空。 【性质2 4 】网系统c ，3 1 0 ) ，= ( p ，lf ，叻，s 譬p 是一个陷阱，若3 m e r ( m o ) ， 心两 0 ，则s 以后总是被标记。 【性质2 s l 网n = ( 尸，nf ，叻的p - 不变式j 的支撑i i i i i 既是个信标又是 一个陷阱。 【性质2 6 】( ，m o ) 是一个网系统，其中 降( p ，瓦f ，聊，j 是一个p _ 。不变式，s 0 2 是的一个信标，那么此信标s 是在慨下被p 一不变式f 控制的，当且仅当，m o 0 且对于所有的p 尸岱，j p ) 0 c s e 如果s 是一个在肘j 下被p 不变式j 控制的信标，则s 不可能被清空也就是说，v m e r ( ， 朋曲：s 在标识肘i 下是被标记的。 【性质2 7 i ( n ，肘i ) 是一个普通网系统， 仁( p f 固，若在艇下是死( 锁) 的，则 所有未被标记的库所形成一个信标i 如果网j 】、r 中没有信标可能被清空，则称( ， m o ) 是无死锁的( d e a d l o c k - f r e e ) e 【性质2 8 l 对于普通网系统( ， d ， 卢( p ld ，死锁的必要条件是所有的极 小信标都被清空； 该性质是一一般死锁分析方法的基础。需要说明的是，本中主要讨论普通有界 兰一些主! ! ! ! ! 竖竺鲞竺! ! 鎏墨竺! ! 堂堡些堕堕 网。除非特别说明，f 文提到的网模型是普通有界嘲。 2 2 举例 以图2 1 为例说明p e t r i 网的有关概念和性质。 图2 1 一个p e t r i 网实例 1 0 图2 1 中的p e t r i 网= ( p ，t ，f ，吩，其中p = - p l ，p 2 ，p 3 ，p 4 ，p 5 ，p 6 , p 7 ，p s , p g , p 1 0 ， p 1 1 ，p 1 2 ，p 1 3 ，p 1 4 ，p 1 5 ，仁f 2 ，t 3 ，t 4 ，t 5 ，t 6 ，札t 8 ，t 9 ，6 0 ，t l l 。v 斥f ，w f f ) = l ，所以它是 一个普通网，记做= ( p ，乃乃。 网n 有7 个极小p - 不变式，它们的支撑分别是：j l i d l = p j ，p 2 ，p 3 ，p s ，p 6 ，p 7 ) ； i 忙p 4 ，p s ，p 9 ，p l o ) ；1 | 毛1 1 2 p 2 ，p 1 5 ；i l l l l = 妇7 ，p 1 1 ) ；i i h l l = 伽3 p 9 ，p 1 2 ；1 1 1 6 1 1 = t p 4 ，p 5 ， p 1 3 ；1 1 1 7 1 1 = 仞6 ，p s ，p 1 4 ； 网中有3 个严格极小信标：s l = p 4 ，p 6 ，p 1 3 ，p 1 4 ，s 2 = j o s ，p 9 ，p 1 2 ，p 1 3 ) ，岛= t 邯， p 9 ，p 1 2 ，p 13 p 1 4 ) 。以s l 为例，蜀文弗e s l p = e p 4 t j p 6 k j l p l 3 l j p 1 4 = 1 9 l j 4 u t 4 ，t 1 0 u ( f 5 ， f 9 ) = “，如，t 9 ，t i n ) ，s 】。= l 扫j 垆。= m 。l p 6 l p l ，t a p t 4 = 如，岛，如，t s ，玛，t ) o ) ，所以5 l ( = s i 。 故s 是。个信标，而且它不包含任何p 不变式的支撑，也不包含任何其它信标，所 以是个严格极小信标。同样品和蜀也是严格极小信标。潮的初始标识m o = 7 ，0 ， 0 ，0 ，0 ，0 ，0 ，0 ，0 ，5 ，l ，2 ，l ，2 ，l 】。网的关联矩阵啪为： 第二章p e t r i 网的基本 旺念 2 3 自动制造系统的p e t r i 网模型 制造系统p e t r i 网模型中的库所可分为三类，假定= 化zf j 是一个制造系统 的网模型，p 是一个库所，m o 是的初始标识。 p 称为a - p l a c e ，当且仅当眠例= o 。p 称为b - p l a c e ，当且仅当m o ( p ) 是一个正 的常数( 整数) 。p 称为c - p l a c e ，当且仅当m o 是个变量。a - p l a c e ，b - p l a c e 和c - p l a c e 与初始标识相关且具有明显的物理含义。 自动制造系统中a - p l a c e 又称为工序库所，用于建模个任务包含的加t t 序。 b - p l a c e 又称为固定资源库所，用于建模机床，机器人，物料传输系统等。c - p l a c e 又称为可变资源库所，用于建模加工原料夹具和托盘等。个p e t r i 网中的a - p l a c e ， b - p l a c e 和c - p l a c e 的集合分别记为兄，尸e 。例如，图2 1 中p a = ( 玩，p 3 ， p 4 ，p 5 ，p 6 ，7 ，p 8 ，j 的，) ，p b = p l l ，pz 2 ，p 1 3 ，p 1 4 ，p 1 5 ，p c = ( p 1 ，pj o ) 。 在自动制造系统中，一+ 个工序至少需要一个固定资源参与。从p e t r i 网角度来 看，a - p l a c e 和与之对应的b - p l a c e 构成4 个p ，不变式。同样， 一个加t 原料要经 过若干工序成为产品，所以c - p l a c e 和其对应的a - p l a c e 也构成一个p 不变式。根 据a - p l a c e ，b - p l a c e 和c - p l a c e 的定义，可以看到自动制造系统的网模型被p 不 变式覆盖，且这些不变式中肯定含有托肯。 一般地，s 是自动制造系统p e t r i 网模型mm o ) 的个信标，我们有m o ( s ) - 2 。 下面心例子来说明如何建立p e t r i 网模型。考虑个柔性制造单儿包括3 台 0 o 0 o 0 0 o o o 0 0 o 0 o o o o 0 o o o ，o 0 ，o o o o o o o o o o 0 o o一，o o o o o o 0 o ，o o o 0 o o o o o o 0 o 0 o 0 o o o o 0 ，o o o o 一0 0 o 1 o o o o o 0 o o o o o 0 0 o 0 o ，o o o o o o o o o o o o o 0 o 0_o，o 0 o o o 0 o o o 0 o o 0 o o o o o o o o o o o 0 o o o o o o o o o o 凡既儿儿既风n风岛儿几几几 l i f ) j 止fp e l r i 刚的柔卡牛制造系统死锁预胁攘略 机床( m 1 ，m 2 ，m 3 ) ，2 台j ：下料机器人( r 1 ，r 2 ) ，两个输入缓存库1 1 ，1 2 和三个 输出缓存库o l ，0 2 ，0 3 ，该单冗可生产三利一零件类p i ，p 2 ，p 3 ，它们的t 艺流 程如下： p i ：i l 斗r l o m 3 0 0 l ； p 2 ：1 1 斗r 1 斗m l 斗r 2 斗m 2 斗0 2 ： p 3 ：1 2 _ m 2 斗r 2 斗m l 0 0 3 ： 该举7 的p e t r i 网模型如图2 1 所示。 明。 2 4 小结 本章主要对p e t r i 网的基本概念及性质进行了叙述，并结合例子对它们进行了说 第三章姊r 网模型爱基本信标理论 第三章s 3 p r 网模型及基本信标理论 s 3 p r 6 是p e t r i 网的子类，它可以为。大类f m s 建模，代表性很强。基本信标 【1 1 是种特殊的严格极小信标( s m s ) ，对于一个p e t r i 网，当其全部基本信标不被清 空时，其所有的黝枢有可能不被清空。一个p e t r i 网的基本信标的数量比其s m s 的数 量要少得多，尤其当p e t r i 网规模大而复杂时这一点变得更加显著。因此能否通过控 制s m s 中的一少部分而不是全部就可获得一个无死锁的或者活的p e t f i 网，对死锁预 防来说，显得特别重要。本章引用的基本信标概念，提供了解决这个问题的把 钥匙。进步的研究表明，将基本信标的概念引入p e l r i 网可以使得现有许多控制 算法得到简化，可以设计出更简单( 具有少量的控制库所和连接弧) 的监督控制器。 本章主要有四部分：第1 节介绍了介绍s 3 p r 网的概念；第2 节介绍了p e t r i 网的 基本信标理论，给出了基本信标和冗余信标的概念；第3 节给出了基于基本信标的 信标控制方法；第4 节对本章进行了概括总结。 3 1 一类f i d s 的p e t r i 网模型一s 3 p r 简介 f m s 通常是由多个加工中心和个物料运输系统组成。个f m s 要求能够完 成不同种类的零件加工，每个零件按照事先制订的加工工艺以一定的顺序使用 f m s 中的资源。所谓资源，是指f m s 中的机床、机器人、卡盘、储存箱等。每种 零件的加工顺序称为加工进程，在f m s 中允许存在不同的加工进程，这些加工进 程可以并行操作，因此存在资源竞争，导致冲突发生，从而可能产生死锁。死锁， 简单地说，就是系统中的一些加工进程总是不可能完成的。在f m s 领域，死锁状 态的出现是由于资源分配不合理，资源得不到释放而引起的，这意味着一系列的 资源处于循环等待之中。 如果用p e 啪网来模拟加工进程，其中库所表示加工进程中的工序状态和系统 中的资源，资源库所中的标志数表示可供使用的该资源的个数或加工能力；用变 迁表示工序状态之间的转换。 由文献 6 】提出的s 3 p r 是p e t r i 网的子类，它可以为一大类f m s 建模，具有相 当的代表性。 【定义3 1 1 【6 】一个简单加工进程( s i m p l es e q u e n t i a lp r o c e s s ) s 2 p 是个p e t r i 网 仨( a j 扫o ，而，瞄是n 的初始标识，矿称为闲置库所( 加工进程的开始和结 束工序状态) ，p p 称为工序状态库所。( m o ) 满足以下条件：( 1 ) p 0 ，p o p ， 知p o ) l ，即只眠p ) = o ；( 2 ) n 是一个强连通的状态机，即v f z1 。t l = l t t = 1 ；( 3 ) n 的每一一个回路包含矿。 基十p e t r i 删肿柔牲制造系统死锁预防蕊略 【定义3 2 】 6 】个拥有资源的简甲加t 进程( s 2 p w i t hr e s o u r c e s ) s 2 p r 是 个网a 。( 尸u 加” u p r ，l 一，是_ 的初始标识。c ，m o ) 满足以下条件：( 1 ) 令 p o = p o ) ，由舴矿) u 丁生成的子网n x = ( p x , t x , 嘲是一个s 2 p ，其- 舭p x = b j p o ， t x = t , f x = f & ( p x x t x ) ：( 2 ) r e p r 称为资源，尸k 是资源的集合，p r o ，( a j 妇。 ) n 艮= 中； ( 3 ) v p e p ，v t e ，v t 印。，3 r p e p r ，。t c d a r = t 4 n = r p ) ；( 4 ) v r e p r ，m o ( o l ；v re p r ， ”价p = r n p o ；v r e p r ，h 1 ，= o ；( 5 ) ”r 诹= p o ) 。n p r = m ；( 6 ) 对于个给定的 r e p r ，川，) = ( ”一n p 称为资源r 的持有者集合。对于一个资源集合倪= r l ，r 2 ，r 胂 ， 用u h ( r ) l r e 豫 或k - ) r 。m 硪力表示以n ) u 域r g u u 硪，卅) 。 【定义3 3 】【6 】1 一个拥有资源的简单加工进程系统( s y s t e mo fs 2 p r ) s 3 p r 是 艇女枞 o ) 个s 2 p r 通过共享资源复合而成的p e t r i 网n = o # l 嗨( 几u 玮，互d 。 记n k = 1 ，2 ，k ) 。s 3 p r 网系统( ，m o ) 满足以下条件：( 1 ) 个s 2 p r 也是个特 殊的s 3 p r ；( 2 ) v f e m ，w n k q i ) ，( p i u 尸0 0 n ( 聃码) = 中，且存在n j n 尸旷尸q 中， 斩驴巾；( 3 ) p = - u = 1 k p i ，p o = u ，l p ，p r - - u # i 饥；r 划，l 正p u 产l 碱；( 4 ) v i e n k ， v p e t u p o ，( p ) = m o i ；v i e m ，v r p r i p o ，胁( r ) 2 坛；v r e p c u ，m o ( o = m a x 1 4 0 l ( r ) ，m o b ( r ) ) ；( 5 ) 符号可表示组成第i 个s 2 p r 网m 的s 2 p a 【定义3 4 】【6 】设个s 3 p r 网系统( ) ，其中- ( i u p o w p r ，t 刁，s 是 网j v 的- 个信标。岛表示信标s 中的资源。s s = s t x p t 。：s e 表示信标s 中的工序状 态库所，耻s h 尸。明显地，s ! s n u s e 。 【定理3 1 】【6 设j e ( p u j d 0 u 靠，t 毋是一个s 3 p r ，躔网的一个严格信标， 即环包含任何p 不变式的支撑。那么i s c 、p r i i ，也就是说，s 中至少包含两个资源。 证明：参见文献 6 。 3 2p e t r i 网的基本信标理论 3 2 1 p e t r i 网的基本信标【1 】 【定义3 s l 设 k ( p 瓦刃为一个p e t r i l 网，且邋? 是的一个信标，p - 向量凡称 为信标s 的特征p - 向量，当且仅当v p e s ：枷) = l ；否则，九( p 声0 。 【定义3 6 1 设 ，_ ( p ，t 用是个p e t r i 网，s ，是 哟一个信标，五是s 的特征 p 向量，称r s 是s 的特征p 向量，凇1 = 叁。口v 】。 【定理3 2 】一个只不变式的支撑的特征d 向量为0 。 例如，在图2 1 中，s = 舻i 护2 扔奶挑护7 ，) 。这样我们得到凡= ( 1 ，l ，1 ，0 ，1 ， 1 ，1 ，0 ，0 ，0 ，0 ，0 ，0 ，0 ，0 ) 7 样我以及嵇| 掰 n l = 0 1 这是因为躔肿p - 不变 式的支撑。 【定理3 3 】s 是 k 以e 即的个信标且珊是该信标的特征t - 向量n 发射 f 7 1 叩“f ) o ) 中的变迁f 会使s 中的标志数增加艰“f ) 个a 发射 f t i 似f ) 卸川。的变迁f 第三章s 3 p r 网模型及基本信标理论 _ i 会改变s 巾的标志数。发射 t e ：q r s ( t ) 二，a i 坻一