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

摘要 论文主要致力于柔性制造系统中死锁预防问题的研究。现有的大部分死锁预 防策略的主要缺点是对原网添加了过多的控制库所和弧，最终使得受控网的结构 非常复杂。鉴于此论文针对p e t r i 网的一个子类- - e s 3 p r 网提出了一种基于基本 信标的死锁预防策略。在此策略中，对基本信标添加控制库所后，可使其被尸不 变式控制且不会产生新的可被清空的信标。通过调整某些基本信标的控制深度变 量可使从属信标达到可控。因此，可以得到结构较为简单的网系统。最后，分析 并论证了控制器的活性。 基于区域法虽然可以获得最佳的活性控制器，但其计算量比较大，而且一旦 原网的初始标识变化时，就需要重新计算以获得新的控制器。第二种死锁预防策 略给出了网系统无死锁时，初始标识之阳j 应满足的关系因此在已知控制器的情 况下，当原网的初始标识变化时，无需重新计算，只需调整控制库所中的托肯数， 便可容易地设计出新的控制器。 这两种死锁预防策略应用到柔性制造系统实例中后，所得控制结果充分体现 了这两种死锁预防策略的优越性。 关键词：柔性制造系统p e t r i 网死锁预防基本信标e s a p r a b s t r a c t t h i st h e s i sf o c u s e so nt h ed e a d l o c kp r e v e n t i o np r o b l e m si nf 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 ) t h em a j o rd i s a d v a n t a g eo ft h ee x i s t i n ga p p r o a c h e si st h a tt o om a n y m o n i t o r sa n da r c sh a v et ob ea d d e d ，l e a d i n gt oam u c hm o r e s t r u c t u r a l l yc o m p l e x p e t r i n e ts u p e r v i s o r t of i n das o l u t i o nt ot h i sp r o b l e m ，an o v e ld e a d l o c k p r e v e n t i o na p p r o a c h b a s e do ne l e m e n t a r ys i p h o n si sp r o p o s e df o rac l a s so fp e t r in e t s c a l l e de s 3 p r i n t h i s a p p r o a c h ，a m o n i t o ri sa d d e dt oe a c h e l e m e n t a r ys i p h o n s u c ht h a ti ti s i n v a r i a n t c o n t r o l l e dw i t h o u t g e n e r a t i n ge m p t i a b l e c o n t r o l i n d u c e d s i p h o n s t h e c o n t r o l l a b i l i t yo fad e p e n d e n ts i p h o nc a nb ee n s u r e db yc h a n g i n gt h ec o n t r o ld e p t h v a r i a b l e so fi t sr e l a t e de l e m e n t a r ys i p h o n s h e n c ew ec a n g e tas t r u c t u r a l l ys i m p l ep e t r i n e t s u p e r v i s o r f i n a l l y ，t h el i v e n e s so f t h es u p e r v i s o ri sa n a l i z e da n dd e m o n s t r a t e d b a s e do nt h et h e o r yo f r e g i o n s ，a no p t i m a ll i v e n e s s - e n f o r c i n gp e t r in e ts u p e r v i s o r y c a l lb eo b t a i n e d h o w e v e r , w h e nt h ei n i t i a l m a r k i n go ft h eo r i g i n a lp e t r in e tm o d e l c h a n g e s ，t h es u p e r v i s o r ym a y n o tb ed e a d l o c k f l e ea g a i n i nt h es e c o n da p p r o a c h w e c a l ls e et h a tt h en e ts y s t e mw i l lb ed e a d l o c k f l e ei ft h ei n i t i a lm a r k i n go ft h es u p e r v i s o r s a t i s f i e sas e to fl i n e a ri n e q u a l i t i e s t h e r e f o r e ，w h e nc h a n g i n gt h ei n i t i a lm a r k i n go ft h e o r i g i n a lp e t r in e tm o d e l ，an e ws u p e r v i s o rc a nb eo b t a i n e db ya d j u s t i n gt h en u m b e ro f t o k e n si nt h em o n i t o r s ，w h i c hc a na l l e v i a t et h ec o m p u t a t i o nb u r d e n f m se x a m p l e sa r eu s e dt oi l l u s t r a t et h ep r o p o s e dc o n c e p t sa n da p p r o a c h e sa n d s h o wt h es i g n i f i c a n ta d v a n t a g e so v e rt h ep r e v i o u sm e t h o d s k e y w o r d s ：f m sp e t r in e td e a d l o c kp r e v e n t i o n e l e m e n t a r ys i p h o n e s 3 p r 独创悭( 或创毅性) 声明 v 6 9 5 5 3 8 本人声明所呈交的论文是我令人在导师指导下遴霉亍的职究工 乍及取镄的磺究 成果。尽我所知，除了文中特n d r l 以标注和致谢中所萝列的内容以外。论文中不 链含其她大溅经发表或撰写过熬辨究成累；承不龟含为获褥嚣安奄子辩镀大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的 壬褥秀献鞠已奁论文中傲了瞬麓豹诡秘并表示了谢意。 申请学位论文与资料嚣有不实之处，本人承担一切相关责任。 本人签名：送盈竺：叁 关于论文使用授投的说踞 本人完全了解两安电予科技大学有关保留和使用学位论文的规定，即：研究 ，圭在校孜读学位期间论文工作的知识产权单位属予西安电予科技大学。本人保证 毕业离校质，发表论文或使用论文工作成果时爨名单位仍然为嚣安电子辩技大学。 学校有权保留送交论文的复印件，允许镬阅和借阅论文；学校可以公布论文的企 部或黧分肉容，霹苏竞诲袋鼹影露、缩印或其宅复耧手段镲存论文。( 保寮戆论文 在解密后遵守此规定) 本学谴论文耩予傈密。在年解密蒋适篇本授权书。 本人签名：逡鱼辱 翩签帜 日期堕2 ：兰； f ij i 7 7 订。2 ，。j 第一章绪论 第一章绪论 1 1 研究背景与意义 随着社会进步和人类生活水平的提高，市场更加需要具有特色、符合顾客个 人要求样式和功能干差万别的产品。然而传统的制造系统主要实现单一品种的大 批量生产，如果想要获得其他品种的产品，则必须对其结构进行大调整，重新配 置系统内各要素，其工作量和经费投入与构造一个新的生产线往往不相上下。因 此传统的制造系统不能满足市场对多品种小批量产品的需求，激烈的市场竞争迫 使传统的大规模生产方式发生改变，要求对传统的零部件生产工艺加以改进，这 就使系统的“柔性”对系统的生存越来越重要。柔性制造系统便应运而生。 柔性制造系统( f m s f l e x i b l em a n u f a c t u r i n gs y s t e m ) 是由统一的信息控制系 统、物料储运系统和一组数字控制加工 设备组成，能适应加工对象变换的自动 化机械制造系统。f m s 的工艺基础是成 组技术，它按照成组的加工对象确定工 艺过程，选择相适应的数控d h i 设备和 工件、工具等物料的储运系统，并出计 算机进行控制，故能自动调整并实现一 定范围内多种工件的成批高效生产( 即 具有“柔性”) ，并能及时地改变产品以 满足市场需求。幽1 1f m s 示例 柔性制造系统作为计算机集成制造系统( c i m s ) 的主要组成部分。标志着传统 的机械制造行业进入了一个发展变革的新时代。自其诞生以来就显示出强大的生 命力。它克服了传统的刚性自动线只适用于大量生产的局限性，表现出了对多品 种、中小批量生产制造自动化的适应能力。 在柔性制造系统中，各种工件在离散时间点上进入系统，系统对它们进行并行 加工处理，各加工进程共享一定数量的资源，如机床、机器人、夹具、托盘等。各 种工件有自己的特殊加工路径，即资源需求序列，在加工过程中，各种工件的并 行处理流竞争着有限的资源，从而可能会导致系统运行和控制的许多问题，其中最 为突出的问题是f m s 的死锁问题 4 。f m s 的死锁是制约系统控制和调度实现的关 键因素，因此避免f m s 死锁的研究是f m s 目前研究的热点之一。 从目前的文献来看，很多学者对f m s 6 p 的死锁问题以及死锁产生的充分必要 基于p e t r i 网的柔性制造系统死锁预防研究 条件作了深入的研究 7 2 3 2 4 。特别是c o f f m a n 等人 7 给出了死锁发生的四个 必要条件： 互斥：资源只能分配给某个确定的任务或是空闲，资源不能同时被两个任 务占据。 非抢占：资源不可抢占，只能被占用它的任务自愿释放( 任务完成了相应 工序) 。 占用并等待：占据某些资源的任务请求另外的新资源，而这些资源为其他 任务占据。 循环等待：存在一组资源请求 p l ，p 2 ，p n ，其中p l 等待尸2 占据的资 源，p 2 等待p 3 占据的资源，n 等待p 1 占据的资源。 f m s 的实时调度和控制使得人们很难事先准确地描述系统的运行状况。近年 来，p e t r i 网以其能够模拟系统的并发和冲突行为以及能反映出系统的动念特性而倍 受广泛关注。p e t r i 网是由德国的c a r la d a mp e t r i 在1 9 6 2 年提出的。后来出p e t e r s o n 加以阐述。它是一种适用于多种系统的图形化、数学化建模工具，为描述和研究 具有并行、异步、分布式和随机性等特征的信息加工系统提供了强有力的工具。 作为一种图形化工具，可以把p e t r i 网看作与数据流图相似的通讯辅助方法；作为一 种数学化工具，它可以建立状态方程、代数方程和其他描述系统行为的数学模型。 f m s 作为一种典型的离散事件动态系统一直是p e t r i 网的重要应用领域。p e t r i 网是描 述和分析自动制造系统的一个有力工具，它可以很清楚地反映出系统运行中变迁 之问的顺序、并发、同步及死锁等现象。 基于p e t r i 网 1 2 人们研究了很多方法来处理柔性制造系统中的死锁问题。 大致可归为以下几类： 死锁避免方法； 死锁检测与校正方法； 死锁预防方法； 死锁避免方法 5 6 8 9 1 1 是通过控制对资源的申请使系统避免产生死 锁，其思路是如果许可一个资源的请求会导致死锁那么就不能允许该申请有效。 对网模型而言，这种方法实际上是有意地控制某些可使能的变迁发射以免p e t r i 网系统陷入死锁。这种限制资源分配的策略也具有一定的保守性。 v i s w a n a d h a m 等人 5 提出的方法是通过向前搜索网系统的可达标识图来避免 死锁的。当给定一个网系统的当前标识后，算法就会确定所有规定搜索长度内的 标识状态：通过判断这些标识是否是死锁标识，就可以找到那些发射后会导致系 统死锁的变迁。在网系统运行的时候，只要不使能这类变迁就可以避免系统产生 死锁。这种方法可以使系统有限度地避免死锁，但确定搜索步数有很大困难，而 且还必须提供系统出现死锁时的修复策略。 第一牵绪论 3 b a n a s z a k 等人 6 提供了一秘针对粱性制造系统的死镟避免算法。栋为d d a 算法。这种方法通过执行以下两个策略来避免系统死锬。其一是靛p e t r i 网系统中 麴菜令虐酝集会孛瓣李乏鸯数虿超过该疼掰集会来占霜豹资源中瓣托蠢总数；其 二是当该库所集合中的库所同时申请多个资源并且这些资源都可以申请到时，它 哭能蛊矮一令资添。d d a 葬法农簿一王痔l 开始串请蘩享资源时，逶过有意静不使 能某些变迁，来保诞以上两条策略的实施。 h s i e h 等人c 8 提出的死锁避免算法是建立在墩小资源需求的概念的基础之 上，即使褥琢统中占餍共享资源最少躲工廖优先发射。这萃孛算法具有多项式笈杂 度，并且放松了对系统的约束，因而比c 6 中的方法具有更广泛的应用。 【翻【8 】孛豹方法笼较嶷曩殳。宅钠帮是鼓裂镂结构酌援忿出发，骧确了死镂产 生的条件，即当系统的死锁结构中占用的资源等于资源的总数时，系统就会麟入 死铰狻态，势在我蒸穑上形成了自身豹死锬避免算法。 出于需要考虑犬型的黍性制造系统，p a r k 1 l 】在p c t r i 网模型的基础上针对资 源分配系统歼发了种专门的新颖的建摸和分析方法。它用整数规划的方法来避 免系统甄镂。但是囊予它考虑了资源分配系统中豹火部分媾；显，跌瑟搜褥网模型 不再只是适用于一般网，遮就大大限制了它的应用。 繁二秘楚死镂梭溅与校爱方法 1 2 3 1 3 】。这静方法并不裂意去追求系统豹无 死锁能或活憔，而是一旦检测到系统发生了死锁，通过自动或人工的方法解锁。 这种方法往後会达到较高的生产率和资源利鞠率，证控制工程师必须对可能发生 死锁的生产环节有充分的认识，在设计攀机( 如机器人、机床) 控制器时，器要设计 相应豹控制程序以便解锁时应用。此外，可能还需要一些附加的设备供解锁时使用。 其缝巢又是娶嬲大投入。 第三种怒死锁预防方法 2 1 4 儿1 5 】 1 6 1 7 2 5 。这种方法的目标是设计一 个系统，该系统所辩应静p e t r i 网模鳌本身蒜怒无死镞静或者是滔静。这种方法扶 逻辑土保证了系统中不会出现死锁。因而不必再去控制系统运行过程中对资源的 申请。m c z h o u 等人【1 7 通过限制进入系统工件的数量( 对于网系统而吉，就是 控制嬲系统的翅始挺识) ，使系统的p c t r i 网摸型是活豹，扶褥在爨粼上保涯系绫不 会昭入死锁。这种方法从确保系统不存在任何死锁的角度出发，相应地静态调配 资源f 浚霆裙始猿谈) ，麸纛提燕滚源懿秘焉率。应该撂遗，这种方法尽管保证了系 统的垒局活性但舆有较大的保守性，从而降低了系统的生产率和资源的利用窀。 萄前出璃的死锨顸簖方法犬酃采用在嚣称p e t r i 网模整串增翮新翦控制库所的 方法 1 8 1 9 】 2 0 2 2 。通过增加控制痒所限制网系统的 亍为，从两保证网浆统 是无死锁的。如果在一个p e t r i 网中没有严格极小信标( 简记为s m s ，一个s m s 就 是一个能鼓潺空豹极小蕊标) 技凌空，烈该轻i 霹跫无残锬兹。冠露宅 垒是一些 p e t r i 网子类( 如自由选择网和非对称自出选择网) 活的充分条件。e z p e l e t a 等人 1 8 4 蓥予p e t r i 瓣的黍缝皋遮袭缓矩铰颈涛垂菇究 应用p e t r i 网结构瑷论为柔性制潴系统设计了控锖r 器，最终得到无死锁的网系统。通 过为镶个严格极小信标添加一个监控库所来探证网豹活性。该方法简单有效，然 嚣，凌予添鸯羹了j 霪多豹鼗瞽器取蔽， 雯褥p e t r i 溺控澍器魄强先建立豹p e t r i 溺筷鍪复 杂很多。同时，系统的行为也受到了极大的限制。采用遮代法 1 9 2 1 【2 2 虽然可 以获得更多的行为特性，但燕此方法不适台复杂或大规横的网系统。这是因为网 系统巾豹绩提个数建随鄹援模戒指数递臻躲，敷以每进纾一次迭代，潮系统孛都 会产舷很多倍标，相应的就要绷很多控裁瘁所，最螽将穗 葶迭代无法遴行下去。 近年来。在离敝事件动态系统的监督控制中，区域法 2 6 2 7 成为一种重要的 方法。此方法最大的优点是通过添加控制滕所使事件与魑险状态和死状悉分离， 霉激获褥最佳瓣帮缀大行秀谗磷懿p e t r i 瓣羧麓器。因必簧产奎霹这强，嗣霹要释 大缀的不等式。所以其主要缺点在于计算量避大。 旗本信标理论 3 的提出大火优化了控制器的设计，玄将网中的严格极小信标 分为蒸零售标窝从潢售耘嚣大炎。缝论表翳农一定豹条l 孛下，如果使褥令p e t r i 网中所有的基本债标不被清空，剿其飙属信标也不会被漓空，进而网中掰有的s m s 都不会被清空。遨就意味着耍使一个p e t r i 网没有信标被漓空，并不霈簇对所有的 s m s 都添加控制瘁所。因此，旗子基本信标，可以褥到个较为简单的p e 垴弼控 潮楱整。 练上所述，柔性制造系统中的死锁控制问题已经成为一个刻不容缓待需解决的 课蹶。基于p e t r i 网，虽然此问越已取得了不出研究成果，但目前的解决方案还需 要逡步遮磅究黩竞善。嚣憩，寻求一秘瑟骞效熬瑟锬援铡方法其毒嚣鬻重要熬 意义。 1 2 零文完成的主要工作 本文主要基予p e 哦网，对柔性制造系统中的死锁控制问题做了避一步的研究。 文中提出了两种张锁预防方法，并对方法中的理论体系进幸子了完善。最尉结合f m s 应用实例对其做了验证，结聚袋明与现有的预防策略相比，这两种方法都取得了 较鲑豹控澍藏采。本文工 笮主黉毽含鞋下氕方瑟内容： 1 针对p e t r i 网的个比较广泛的子类一e s 3 p r 网，基于基本信标提出了一种死 锁预防策略，在此策略中； 将售标豹蛰集敬多集煞形式定义。 证明e s 3 p r 网中的基本信标数耳不多于| 尸i 。 给出一种信标控制算法。 证明了按照既信标控制舞法添加控制库所螽，信橡被a 不交式控制。 涯明了添绷控带l 库所露，不会产生薪的可被清空的信标。 第一章绪论 缭出一种死锁预防算法，只霈控制基本信标，便可使网最终受控。 努毫 了受控裁翁活瞧，褥爨受控霹是活溺。 2 在已知控制器中，当原网模型的初始标识变化时，基于无死镇初始标识提出了 一种死锁预防算法： 求磁了网系绕冤死锁时，襁始标识之间疲满足的关系条传。 绘出了一秘求瓣上述条 争静方法。 掇出了一种死锁预防算法，当原网模型卡刀始标识变化时，只需改燮控制库 所中的托肯数即可设计出新的控制器。 蒽之，论文主要疆究了柔毪裁逡系统孛数残锬预茨目题，并彀褥了一定黪或采。 其中通过方法一可以大大简化控制器的结构，特别是对于大规模p e t r i 网，这种方 法的优势尤其显著。方法- - n 可以猩f m s 中的资源作出调整时。避免复杂的计算 便可获缮瓶的控制嚣。陵予时闻、条馋和个人戆认识，不霹避免会存在一袋不是 之处，愁请指正。 6 基于p , - t r i 网的柔性制造系统死锁预防研究 第二章p e t r i 网的基本概念 2 1p e t r i 网的基本定义和性质“加”8 2 1 1p e t r i 网的结构定义 。 【定义2 1 】p e t f i 网( 或库所变迁网) 是一个四元组，可表示为 仁( p ，tri 叼， 其中： “ 1 ) p 代表库所的集合，库所用圆圈表示： 2 ) 丁代表变迁的集合，变迁用长方框表示，且p 和r 是有限非空和不相交的集合： 3 ) f c ( p t ；u ( t p ) 称为有向弧集； 4 ) 胪n i n o ) 称为f 中弧上的权，z ，= f 0 ，1 ，2 ，) ； 当且仅当可批r 蹦【7 = l ，称_ c p ，leg o 为普通网( o r d i n a r yn e t ) ，记作 k ( ，) ， l n 。 【定义2 2 】令= ( p ，l 只叼是一个p e t r i 网，节点x p u 丁的前置集定义为 x = y p u t i x ) n ，其后置集定义为r = 抄j p u 引o ，y ) 一。可将该定义进一 步推广为节点集的前置集( 后置集) ：给定x _ c _ p w t , 则：壮u e x 吖( 。= 。x x ) 。 【定义2 3 】如果 7 兰( p ，l 只g o 是普通网，且vt e t ，| t l = t i = l ，则称是状 态机( s t a t em a c h i n e ) 。 【定义2 4 】如果n p ，lf ，即是普通网，并且有即尸，l p l = l o 。i = 1 ，则称 是标识图( m a r k e dg r a p h ) 。 【定义2 s 】称网n = ( p ，瓦只聊为纯网，当且仅当，i ，力( p x d u ( 孤d ：0 ， 力卧o ，曲f 。 非纯网可以在保持动态性质不变的情况下化为纯网，下面讨论的网都是纯网。 【定义2 6 】网胪= ( p ，t 只聊的关联矩阵定义为以p 和7 为序标的矩阵c ： p x t - , z ，z 是整数的集合，且 c ( p , t ) = 一矿( p ，f ) ( t , p ) 一矽( d f ) + 矽( p ) o p e t i t 。 p f t p t i t 。 其它 【定义2 7 1 令n - - ( p ，tf ，即是一个p e t f i 网， 1 ) n 的标识是映射mp z ，m 表示库所p 中的托肯数，托肯用实心圆点表示： 2 ) 给定s _ c e w r ，则m = p 酣j 】l 知) ； 3 ) 称( m o ) 为网系统或标识网，其中硒为网n 的初始标识。 第二二章p e t r i 两的基本溉念 2 1 2p e t r i 网变迁的发射规则 【定义2 。8 】令燃霉疋秘蹩一个藏， 1 ) 一个炎迁f r 在吖下称为使能的，记为研，) ，尚且仅当，+ ，：m ( p ) - w ( p ，) 2 ) 若 虹f ) 成立，则t 发射后，产生另一新标识m ，记为 饥，) m ，有 m ( p ) = 掰( p ) 一( p , t ) 村( p ) + 矽( p , t ) 肘( p ) 一w ( p , t ) + 矿( t , p ) m ( p ) p 斑。 p 琶t l 。t p 。，n f 其它 了 3 ) 溺秩耩谈蝎开娥豹掰有霹这豁谖的集合记为霞( 致m o ) 鬣m d ) 。它筵一个最 小集即m o er ( ，m o ) ，m er ( ，) m 【，) m 鼢 er ( ) ； 4 ) 当且仪当存在标识m o ，m ， 厶满足【f i ) ) m ，。萨t i t 2 k 为发射序列； 5 蓑存在标识掰使缮m o a ) m , 粼m = m o + c y , 獒孛c 为关联靛簿，y 为笈瓣序 列矢爨，其第i 个数值代表第f 个变迁在序列盯巾出现的次数。 2 1 3p e t r i 网的特性 【定义2 。9 】令泓妒，t 曩聊蹩一个两。m o 怒n 夔一个稼鼋l ： ， 1 ) 一个变迁t 在标识编下是疆豹，巍且仅当v m 畦露( m o ) ，j 凹宾( m o ) 使得 m 【棚览斑； 2 ) ( m o ) 爨死锁的，獭鼠仅当，j r 謦叠m o o 成立； 3 ) 蕊m o ) 是无死竣弱灞 靛，当基仪巍v m e 最越m o ) ，3 t e t ：m 【掰蓖立； 4 ) ( m o ) 是活的，当烈仅当v t t ：t 谯标识下鼹活的： 【定义2 1 0 1 令 胁妒，只只聊怒一个网， 如怒的一个橼识， 1 ) ( 楚m o ) 楚骞赛豹，巍饺当3 k e l n 、 o ，v 掰基教e 麓a l t o ) ，v p e p ：鑫蟊西垫； 2 ) ( m o ) 是结构有界构，当且仅当对于任意的脊戳的初始标议，它都是有羿的： 值得说明的是，对于资源有限的实际系统而言，像的p e t r i 网模型一般都是结构有 赛的。所鸯元索均为0 0 ) 的列向量诡为0 0 ) 。 【定义2 1 l 】令n 只t 最的燕一个弼，m o 是n 静一个标识，( 豫m o ) 是可 逆的，当鼠仅当v m e r ( n , g o ) ，3 a 使得m a ) m o 。 2 1 4 不变式的定义及其性质 【定义2 1 2 】令n 一汐，夏曩粉怒一令援， n 以p 为序标的列向爨v ：p z 称为的弘向擞，z 是整数的集合。 2 ) 以r 为序标的列向擞w ：n z 称为的d 向鼓。 【定义2 。1 3 1 令f 秘j 分鬟蠢爨= ( 奠不只妁躲p 囱囊粒弘窝量， 1 ) 称a 融最刊黾一个肛不变式，当鼠仅当知o 盛 c = - o 。m 产伽，i 删o 称为 8 蓉y - p e t r i 释药柔瞧囊l 逡系统琵镶疆臻羲舞究 ，的支撑。 2 ) 称n 向量，魁一个t - 7 5 变式，当且仅幽j o 且c 扣o 。m l = ，e 凇f ) o ) 称为j 豹支撑。 3 ) 称一个只不变式( t - 不变式) 是极小的，当且仅当京的支撑中不包含任何其它 p - 不变式( 7 - 不变式) 的支撑。 4 ) 称是被弘不变式1 ( r - 不变式力覆盖鲍，当且仅警勖尹：酗o ( 嵌0 o ) 。 本文中的a 不交式，如聚没有特剐声明，剐都是辍小只不变式。 【性质2 1 】网系统( ， 而) ，是= ( j d ，一只即的一个j p - 不变式，v m e r ( n , 锄： p - 掩世硪。 【性震2 2 1 翘系统( 甄m o ) ，j 是矗气爨疋劲懿令弘不变式，l 歹l 巾瑗鸯 的变迁发射一次，可能会使网系统回到初始标识。 2 1 5 信标和陷阱的定义和性质 1 ) 2 ) 3 ) 4 ) 【定义2 。1 4 1 ( 效m o ) 是一个瓣系统，a 冀霉式酾， 称一个非空煞合s c _ p 是一个信标( s i p h o n ) ，当且仅灏i 筵f 成立； 称一个非空懿合s _ _ c p 是一个陷阱( t r a p ) ，当且仅当j s 耋心成立； 称一个信标( 熬辫) 是极小的，当且仅当不存在其它镶标( 隆辨) 是它的真子集； 称p e p 是被稼谈膨标谗的。当盈仅警斌p ) 0 。称一个集会趣是授标谖掰 标记的，当凰仅当s 中楚少有一个既索被m 标记。s 中的撼肯数m ； t p 勋) ； 苓包含 王餐p 苓变式支撂翡售拣称菇严缮经标，一令严格痿据窍霹能袭涛空； 一个既是极小又是严格的信标，称为严格极小信标( s m s ) 。 【性质2 3 】网系统( ，m o ) ， ，_ ( 尸，l 凡聊，踺p 是一个信标，若3 m e r ( n , 而) ： 翻渤锄，羹| js 以瑟庆遂不会拔标记，舔隽皱瀵空。 【性质2 4 】黼系统( m o ) ， 岳( 只瓦e 溯，s 量p 是一个陷阱，若3 m e r ( n , m o ) 。 肘磷) o 则s 以后总是被标识。 【性质2 5 】网 每( p t 苁聊豹只不变式，的支撑i ，i 既是信标又是陷阱。 【往震2 。6 】( 敞m o ) 是一令弱系统，蒸审a k ( 只霉式的，；是一令p 不变式， 熙护是的一个信标，那么此信标s 是摄 而下被b 不变式，控制的，当且仅当 ，m o 0 且对于所有的p ，妇) o 且 p e p l l ( p ) 0 _ c s 。 磐袋s 是一拿在磊悫下鼓p 不变式j 控潮豹镲耘，曩| j s 零霹舞羧i i 孽空，瞧就是说， v m e r ( n , 硒) ：s 在标识 南下是被标记的。 【性质2 7 1c m o ) 是一个普通网系统， ，_ ( p ，正d ，若在m 下是死锁的， 则掰有未被标记的痒所形成个羡据。 【性质2 。8 】( ，硒) 是个普通丽系统，n - - ( p ，t 乃，磐鬻隧串没有信标哥 第= 辩p e t r i 弼的蕊本概念 能被清空，则称( ， 痈) 是无死锁的( d e a d l o c k - f r e e ) 。 2 2p e t r i 两的实例分析 2 2 1p e t r i 网模型的建立 隰2 i 个f m s 实例 p i t 4 图2 2 豳2 1 的p e t r i 网模型 9 阉2 1 所示静f m s 由执臻m ，机器入爻，输入缓存瘁i 帮输出缓存瘁o 组成， 且机廉m 每次只加工一个工件。机器人r 每次只能夹持一个工件。机器人r 可以 将输入缓存库l 中的零件装载到机床m 上，也可以将机床m 上的零件卸载到输出 缓存滗0 孛。该擎露廷毽客一拿擞王遭程，萄垒产一类王黪。其麓工遴疆隽：p i ： l _ r _ m 寸r j o 与乏对应的p e t r i 网模型如豳2 2 所示，其中机床m 和机器人r 分别由郧和 娜表承，出于m 秘r 的持毒能力必每次一令，艨鞋邸窝热审於托鸯数埝隽l ，段 代表枫器入聂在装载工件，船代袭机床正在绷王工徉，烈代表机器人疆在卸载工 件。 2 2 ，2p e t r i 网模型的努柝 ( 1 ) 麓先分析诧模擞的结稳特投 在豳2 2 所示的p e t r i 网 ，- p ，e 只叼中： 尸= 扣l ，p 2 ，p 3 ，p 4 ，p 5 ，p 6 ) ，t = t t ，t z ，t 3 ，t 4 tv f e f , w q ) 产l ，所以它是一个普 逶阏。 i = “) ，。p 2 = t i ) ，h = f 2 ，h = t 3 ，h = r 3 ) ，p 6 = t 2 ，t 4 ， p l = f l ，p 2 ； f 2 ) ，p 3 - - t 3 ，p 4 = t 4 ，胁叠 如 鼢，m ，l ，6 ) l o 基 p e t r i 霸嚣柔性露德系统毵镀黢结疆究 。f l _ 和l p 6 ) ，。t 2 = 她，p 5 ，t 3 = 慨，p 6 ) ，。1 4 = 慨 f l 匕锄 ，t 2 。= 勘，弘 ，3 = 汹，p 5 j ，t 4 = p i ，热卜 裙戆椽谈m o = 4 0 0 0 ll 】7 ，( 甄鼻奄) 为溺系统或标漩丽。 网的关联矩阵为： 只 热 c ：岛 p 4 岛 蠡 一lo ll ol o0 ol 一l o 1 00 一l o l一1 l 0 一ll 由# 0 鼠f c = oo 得，网包含以下三个极小a 不变式： = 1 ，l ，l ，l ，0 ，o ) ；2 = 0 ，0 ，1 ，0 ，l ，0 ；6 = o ，1 ，0 ，l ，0 ，1 ) 。 与之霹痘靛支撑分弱最；陋l p b p z ，p 3 ，盈 ；隔掰，p 5 ；l i 南l t = p 2 ，p 4 ，p 6 。 由j # o 且c , j = o 得，网包含以下个极小n 不变式： 户 l ，l ，l ，1 ) ，其对应的支撑是：* f l ，t 2 ，“t 4 ) 。 弼巾骞一令严格羧，j 、信蠡：黔戳，函，强 。 因为j 孽= s 仁h u 5 u 6 _ t 3 u t 3 u 1 2 ，轴 = 坛如，t 4 ，f = v 胙s p = p 4 u p s u p 6 = “) u m ) u ，i ，3 ) 一 f i ，t 2 ，t 3 ，“) ，所以o c f t 故s 是一个信桥，因为它不包 含任何一举变式静支撵，也不包含援筒其它信栎，所以是一个严掊极小信标。 ( 2 ) 下嚣分耩扛乏模墅酶葫态特性 t 毒 瞄2 3 状态m p l t 4 图2 , 4 状淼尬 第二章p e t r i 网的基本概念 在秘始撂识m o = 4 ，0 ，0 ，0 ，l ，l 】下，m o ( p o w ( p ，t t ) 强m o ( 幽) 戳娜，t o ，掰醴 f l 是镬戆麴。当发射t l 瑟，产燕毅撂谈鼻磊3 ，l ，0 ，0 ，l ，0 】，记为矗岛强 鑫磊，鲤圈 2 t 3 所示。 在标识 矾= 【3 ，l ，0 ，0 ，l ，0 1 7 下，t 2 使能。发射1 2 餍，产生舄一新标识m 2 = 【3 ，0 ， i ，0 ，0 ，1 1 0 ，记为鼻f 蚴晒，如图2 4 衔示。 在携状态下，f l 和t 3 都侵能。若发射n 胃褥刘新标识 靠= 【2 ，i ，l ，0 ，0 ，0 】l 翔图2 。5 掰承。若发射t 3 樊| j 褥剿新轹谈硒= 【3 ，0 ，0 ，l ， ，甜，如阐2 6 所汞。 在状态下，没鸯变迁搜能，弼系统魁入疑锬。戴瓣，所蠢寒按标遣麴辫蹰 形成信瓠姆 出，p s , 艮 。在磊磊状态t ，趣偻能，发瓣t 4 霹圈到拐婊据谈磊是状态e t 4 翻2 , 5 捩态m 3 p 6p 1 鹜2 6 敬态m 4 综上所述，嘲从橼识 如开她的所有可达标识的集合詹( m 磊) 为： 插a 赫 2 3 小结 零章童簧奔绍了p e m 秘懿一些罄零定义秘戆痰，著对菜一p e t r i 鄹迸褥实褥套 辑，获翁对嚣覆耀到翡一整基本朝谖浚霞了落睽。 1 2 墓l ：p e t r i 疆麓柔缝囊滚系统嚣矮臻院綦萎突 第三章e s 3 p r 网模型 本文主要研究p e t r i 网的一个子类e s 3 p r 。并解决京的死锁预防问题。e s 3 p r 可以为一大类f m s 建模，代袋性很强。为了埘e s 3 p r 饔更好的理解，本章将首先 逶；璧一令实爨褒筏弱瑟e s 3 p r 两有个熹溪豹认识，然惹菇结合该实铡辩e s 3 豫矮 的凝本定义做一个简单的介绍。 3 。1e s 3 p r 鄹建摸实铡 图3 1 所示的f m s 由三个机器人( r i ，r 2 和) 、髓台机床( m l ，m 2 ，m 3 和 m 4 ) 、四种工具( h i ，h 2 ，h 3 和h 4 ) 、两个输入缓存库( i i 和1 2 ) 和两个输出缓存库( o i 翻0 2 ) 缀残。 强3 1 柔瞧裁造攀元 机器人r l 可以将输入缓稃库i l 中的零件装载到机床m l 或m 3 上，也可将机床 m 3 上如工好的零传卸载到输出缓存瘁0 2 枣。机器入r 2 珂以褥枧床m l 或机床m 3 上豹零律运送到税床m 2 上，也可将祝臻氛薹4 上靛零件遴送到祝床m 3 上。梳赣入 r 3 可以将机床m 2 上的零件卸载到输出缓襻库o - 中，也可将输入缀存库h 中的零 件装载到机床m 4 上。该单元肖两个加工进程p l 和p 2 ( 如图3 。2 所承) ，可生产两 类麓锌。在蕊烹：l 程p l 串，穰床酝l 热王王俘露嚣镬惩忑吴珏l ，撬疼m 3 期工王 件时需使用工具h l 和h 2 ，机床m 2 加工工件时需使用置具h ，和。在加工进稷 第三章e s 3 p r 卿楼型 p 2 中，捉臻m 4 擞工工传辩霭馊_ 霹；| 王其 3 翻h 4 ，枫床m 3 趣王王健聪爨使用王其 h l 和h 2 。 p t ：1 1 崇篇弋h 叫h 。p 0 1 h ：y r 2 i ： f m ，l 。立+ r 卜( 隧 l ， p 2 ：1 2 蕊k 瓶， 辩。滓k 酶，魄氆声0 0 2 蝴3 2 加l ：进橼p l 利p 2 每进程p l 羁p 2 对蔽憝p e t r i 瓣摸挺氧图3 3 ( 鑫) 靼3 。3 ( b ) f f i ：秀鼍。将稳鞫豹蜜源融 合后。可得剿该f m s 的p e t r i 网模型，如图3 4 所为专，此网模型属于e s 3 p r 网。 获巨串胃苏翥赘，嚣s 3 豫潮建辩s 3 p r 麓静透一步扩鼹，困魏应稻范番嚣广。 e s 3 p r 网包含多个状态机状态机之间共享一系列的资源，资源库所中的托肯数 表示此类资源的数露，黼且，个工作状态可能同时需簧多个不同类的资源，如 在她实例的进程p l 中，工序状态库联p ，代表规廉m 3 正农搬工忑 牛，此时鬟要用 到三类资源：m 3 ，h i 和h 2 。 r 1 r l 珏2 鲁 g a t i 3 寻 丑 塞3 t 1 4 r v p l 3 fl 亨t 1 3l 6 。1 2l 魏 闰3 3 ( a ) 进穰p l 的p e t r i 网模烈豳3 3 ( b ) 进襁p 2 的p e t r i 刚模型 o e ， 一 ：墓 域 晒 i 錾姻 塾p e t r i 网的柔性制造系统死锁预防研究 r 1 鞫3 4 与塑3 i 对瘟熬p e t r i 赠模型 3 2e s 3 p r 网的基本定义 以下将针对该宓例简单的解释一下e s 3 p r 网的一些基本定义c 2 0 3 0 。 【霓义3 。1 】1 8 3 令麓萃鞭黪翔工遴程s 2 p ( s i m p l es e q u e n t i a lp r o c e s s ) 是一令 p e t r i 网l ，_ ( a 扣o ，td ，其中： 1 ) 鼬辔r ，盛_ p ，m o ( p ”) l t v p e p ，硒国= o ； 2 i 是一个强连通的状态机，即w l | 叫= | f | = i ； 3 ) 的每一个回路包含p o 。 矿弥巍溺鬟霉鼹( 热工进程豹嚣始联结柬工序状态) ，p e p 称为工序状态痒掰。 以图3 3 ( b ) 为例，若不考虑资源， p o ) 和所有的变迁以及它们之间的遗接弧构成 酶子烈海s 2 p ，箕审芦 瑚，p l o 期l ，尹1 2 pn 3 tp 秘。 【定义3 2 】一个扩展的拥有资源的简单顺序加工进稷e s 2 p r ( e x t e n d e ds 2 p w i t hr e s o u r c e s 是一个p e t r i 两舯( c , - , e r ，毋，使褥： 1 ) 由x = p u 矿 u t 生成豹子网n x = ( p x , t x , 嘲是一个s 2 p ： 2 ) p r , o ( 秽 ) n p m ； 3 ) v r p a ，存在a 不交式磊健褥 r _ | 艄n 段，矿醐蹦，阶l 园| 尊基五= l ； 谯图3 3 ( b ) 中，p r = 脶，m 4 ，r t ，r 2 ，r 3 ，i - 1 , ，1 t 2 ，1 t 3 ，1 - 1 4 ，其中l m = m 3 + p t 2 ， 薅三章e s 3 p r 嬲模型 i ，= r t + p t 3 ，抽，= h l + p 1 2 0 【定义3 3 】令n = ( p u 矿 u p r ，t 是一个e s 2 p r 网，称为的许可初始 标识，当且仅当潢足以下条件：( 1 ) 蜗o ) l ；( 2 ) v p ，蜗国* o ；( 3 ) v r e p r ， m o ( o l 。 【定义3 】令2 兰 l 2 。囊 隽一骞鞭岿秘集，盈对v i e z ，n r = ( p i u p 。i u p r i ， 取黝是一个e s 2 p r 网。一个扩展的搠有资源的简单顺序加工进程系统e s 3 腿 ( s y s t e mo f e s 2 p r ) 燕由k ( k e l n 、 0 ) 个e s 2 p r 遴过共事资源簸台两成的瞀p e t r i 潮， 可表承成 悔o # l 协( a j j p o u 珞，e d ，其满足以下条件： 1 ) p = u k z 辫，其中胎m ，且对v i ，j e z ，当蚵时，p n 垮一巾； 2 ) i - u 斛 扩， ，艇对v f ，j e z ，当鳟眩，p o 棚母； 3 ) p w = w i e z p r f ，鼠对v i e z ，影e z 使得p 用r 、尸舟= p 。簪巾成立； 毒) 如嗡。z 霸，t ：o ，显对v 毒歹毒己当扫9