（机械电子工程专业论文）柔性制造系统无死锁petri网控制器的分解研究.pdf

摘要 本文致力于柔性制造系统( f m s ) 中死锁预防问题的研究。传统的死锁预防 策略要对每个可被清空的严格极小信( s m s ) 标添加一个控制库所从而使p e t r i 网 模型受控。s m s 的数量决定了该控制策略会导致一个结构异常复杂的死锁预防控 制器。基本信标概念的提出极大地避免了这种情况的发生。本文针对p e t r i 网的一 个子类一e s 3 p r 网提出了两种基于基本信标的死锁预防策略。在第一种策略中， 对基本信标添加的控制库所保证其被p 不变式控制且不会产生新的可被清空的信 标。通过调整某些基本信标的控制深度变量可使整个网系统最大可控，接着对控 制器的冗余控制库所进行检测，移除某些冗余控制库所，从而进一步简化控制器、 减少对网系统的限制。 为了能控制网系统，通常需要穷举所有的s m s 。而s m s 数量随着网络规模成 指数增长，所以要求出所有s m s 是非常耗时的，有时甚至是可望而不可及的。第 二种控制策略能同时避免穷举s m s 和控制器中从属信标的产生，同时将受控广义 网转换成普通网。进一步降低控制器的结构复杂性，为继续研究该受控网提供方 便，有很好的实际应用价值。 通过同一个f m s 制造系统实例的检验，这两种死锁预防策略都取得了良好的 控制效果，显示出了各自的优越性。 关键词：柔性制造系统p e t r i 网e s 3 p r 网死锁预防基本信标广义网普通网 a b s t r a c t 耽i st h e s i sd e a l sw “ht 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 j s a d v a m a g co ft h ee x i s t i n ga p p f o a c h e si st h a tt o om a n y m o n i t o i sa n da r c sh a v et ob ea d d e d ，l e a d 抽gt oam u c hm o r cs t r i l c t u m l l yc o m p i e xp e 们 n e ts u p c i s o rf o ra n 蹦s a ne f f e c t i v ec o n t f o lm e t t l o di sd e v e l o p e dt op r e v e n t d e a d l o c k sf m mo c c u h i n gi nad a s so fn e t s ，e s p r ，w h e i bd e a d l o c k sa r et i e dt o u n m a r k e ds i p h o n s s t f i c tm i n i m a ls i p h o n sa r ed i v i d e di n t oe l e m e n t a r ya n dd e p e n d e n t o n e s f b re a c he l 锄e n t a r ys i p h o n ，am o n i t o ri sa d d e dt oe s u r ci ts u f f i c i e n t l ym a r k e d w i t h o u t g e n e r a t i i l ge m p t i a b l e c o n t r o l i n d u c c ds i p h o n s t h ec o n t r o l l a b i l i t yo fa d e p c n d e ms i p h o ni se n s u r c db yc h a n g i n gt h ec o n 打o ld e p t hv a d a b l e so f “sr e l a t e d e i e m e n t a f ys i p h o n s ，w h i c hl e a d st oal i v e n e s s e n f o r c i n gs u p c r v i s o rf o rap l a n tm o d e l f u r t h e r m o r e ，b yc h e c h n g t h e r e d u n d a r l c y o ft h ea d d i t i o n a lm o n i t o f s ， s o m e c o n 仃0 1 r e d u n d a i i tm o i l i t o r sc a nb er e l n o v c d ，w h i c hl e a d st oam o r ep e m i s s i v ea n d s 毫兀l c t u f a l l ys j m p l en e ts u p e r v i s o l t h eo t h c rd c a d l o c kp r e v e n t i o np l o d y ，w h i c hc o m b i n e sm i p ( m i x e di n t e f g e f p m 掣a m m i n 曲w i t ht h ec o n c e p to fc l e m t a r ys i p h o n s ，i sp r c s e n t e d ，w h i c hc a na v o i d b o t he x p l i c i te n u m e r a t i o no fs i p h o n sa i l dt l l er e d u n d a i l c yo ft h em o n i t o r sf b rap l a n t m o d e l _ n i sp o l i c yc a l l1 e a dt 0am o r es t n l c t u r a i l ys i m p l en e ts u p e i s o lh o w e v e r t h e r e s u l t a ms u p e r v i s o ru s u a l l yb e c o m c sag c n e 豫l i z e dn e t 世e rc o n t r o l l i n gt h ee m p t i 曲l e s i p h o n si ne s 3 p rn e t s ，w h i c hi sd i f 珏c i l l t t o n d u c tf i l n h e r 明a l y s i s n e r e f o r e ，i ti s n e c e s s a f yt ot r 卸s f o 珊ag e n e r a l j z e dn e ts u p c i s o ri n t oa i lo m i n a r yo n ew i t b o u t c h 觚g i i l gi t sb e h a v i o rp r o p e n i e ss u c ha sl i v e n e s s a nf m se x a m p l ei su s e dt om u s t r a t et l l ea b o v e m c n t i o n e dc o n c e p t sa n d a p p r o a c h e s ， w h i c h s h o w st h es i 印i f i c 柚ta d v a n t a g e so v e r t h ep r e v i o u sm e t h o d s k e yw o r d s ：n l s p e t r i 眦te s 3 p rd e a 珊眦kp 托v 蛆t i o ne l e m e n t a r ys i p h o n g e n e n l i z e dn e to d i 雌r y 靴t 独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：害砌1 菱 日期2 。i 、2 2 ：) 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。本人保证 毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) j 本学位论文属于保密，在年解密后适用本授权书。 本人签名! 垒型走 导师签名 日期如2 ：至9上生年棼 l 丘二 第一章绪论 第一童绪论 1 1 研究背景及意义 竞争日益激烈的市场需要产品更新换代快、生产周期短，且更具特色化、个 性化。这就要求企业能够快速、灵活小批量地生产产品，因此适应这些需求的柔 性制造系统( f m s f i 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 ) 就应运而生了。作为计算机集成 制造系统( c l m s ) 的主要组成部分，它标志着传统的机械制造行业进入了一个发展 变革的新时代，这种变革克服了传统的刚性自动线只适用于大量生产的局限性，表 现出了对多品种、中小批量生产制造自动化的优良适应能力。 柔性制造系统是由统一的信息控制系统、物料储运系统和组数字控制加： 设备组成，能适应加工对象变换的自动化机械制造系统。f m s 的工艺基础是成组 技术，它按照成组的加工对象确定工艺过程，选择相适应的数控加工设备和工件、 工具等物料的储运系统，并由计算机进行控制，故能自动调整并实现一定范围内 多种工件的成批高效生产( 即具有“柔性”) ，并能及时地改变产品以满足市场需 求。 集计算机辅助设计( c a d ) 技术、机电一体化技术、模糊控制技术、模糊数学、 人工智能、专家系统技术和人工神经网络f a n n ) 技术于体的f m s 为了适应市场 的需要变得日益复杂，从单一的串行系统到多进程的并行系统，从基于单机环境 下的操作到网络并行环境下的机群操作等等。而具备并发、异步、离散、并行、 时变和随机特征的复杂f m s 给设计者带来了更为严峻的挑战。在柔性制造系统中， 各种工件在离散时间点上进入系统，系统对它们进行并行加工处理，各加工进程 ( 由一系列加工工序组成) 共享一定数量的资源，如机床、机器人、夹具、托盘 等。各种工件有自己的特殊加工路径，即资源需求序列，在加工过程中，各种工 件的并行处理流竞争着有限的资源，从而造成部分进程不能进行或者使所有进程 都停止不前，即系统陷入了局部死锁或者是全局死锁状态，严重地影响了系统的 动态性能，降低了系统的生产效率。因此，死锁问题 1 是f m s 系统设计者无法 回避的一个问题。f m s 的死锁是制约系统控制和调度实现的关键因素，因此解决 f m s 死锁问题的研究是目前f m s 研究的热点之一。 研究死锁问题的首要问题是要清楚死锁发生的充分必要条件，对于这一问题 很多学者都做了比较深入的研究 2 儿3 4 ，其中c o f f b l a n 等人 2 比较系统地给出 了死锁发生的四个必要条件： 互斥：资源只能分配给某个确定的任务或是空闲，资源不能同时被两个任 柔性制造系统无死锁p e t r i 网控制器的分解研究 务占据。 非抢占：资源不u ，抢占，只能被占用它的任务自愿释放( 任务完成了相应 工序) 。 占用并等待：占掘某些资源的任务请求另外的新资源，丽这些资源为其他 任务占据。 循环等待：存在一组资源请求 p l ，p 2 ，p n ) ，其中p 1 等待p 2 占据的资 源，p 2 等待p 3 占据的资源，p n 等待p l 占据的资源。 对于一个实际f m s 系统人们很难事先准确地描述系统的运行状况。可行的方 法是对整个系统进行建模，模拟其运行状况，从而分析出被模拟系统的在结构和 动态行为等方面的重要信息。p e t r i 网就是这样一个很好建模、分析工具。 近年来，p e t r i 网以其能够模拟系统的并发和冲突行为以及能反映出系统的动态 特性而倍受广泛关注。p e t r i 网理论是由德国的c a r l a d a mp e t r i 在1 9 6 2 年提出的，后 来由p e t e t s 咖加以阐述。它是一种适用于多种系统的图形化、数学化建模工具，为 描述和研究具有并行、异步、分布式和随机性等特征的信息加工系统提供了强有 力的工具。作为一种图形化工具，可以把p c t r i 网看作与数据流图相似的通讯辅助方 法；作为一种数学化工具，它可以建立状态方程、代数方程和其他描述系统行为 的数学模型。f m s 作为一种典型的离散事件动态系统一直是p e 埘网的重要应用领 域。p e t r i 网是描述和分析自动制造系统的一个有力工具，它可以很清楚地反映出系 统运行中变迁之间的顺序、并发、同步及死锁等现象。 基于p e t r i 网 5 6 人们研究了很多方法来处理柔性制造系统中的死锁问题。 这些方法大致可归为三类：死锁避免方法；死锁检测与校正方法；死锁预防方法。 第一种，死锁避免方法 7 儿8 9 1 0 1 1 。它是通过控制对资源的申请使系 统避免产生死锁，其思路是如果许可个资源的请求会导致死锁，那么就不能允 许该申请有效。对网模型而言，这种方法实际上是有意地控制某些可使能的变迁 发射，以免p e t f i 网系统陷入死锁。这种限制资源分配的策略具有一定的保守性。 v i s w a i l a d h a m 等人 7 提出的方法是通过向前搜索网系统的可达标识图来避免 死锁的。当给定一个网系统的当前标识后，算法就会确定所有规定搜索长度内的 标识状态；通过判断这些标识是否是死锁标识，就可以找到那些发射后会导致系 统死锁的变迁。在网系统运行的时候，只要不使能这类变迁就可以避免系统产生 死锁。这种方法可以使系统有限度地避免死锁，但确定搜索步数有很大困难，而 且还必须提供系统出现死锁时的修复策略。 b a n a s z a k 等人 8 提供了一种针对柔性制造系统的死锁避免算法，称为d d a 算法。这种方法通过执行以下两个策略来避免系统死锁。其一是使p e t r i 网系统中 的某个库所集合中的托肯数不能超过该库所集合未占用的资源中的托肯总数；其 二是当该库所集合中的库所同时申请多个资源并且这些资源都可以申请到时，它 第尊绪论 只能占用一个资源。d d a 算法在每。丁序”始申请共享资源时，通过有意的不使 能某些变迁，来保证以上两条策略的实旌。 h s i e h 等人 9 提出的死锁避免算法是建立在最小资源需求的概念的基础之 上，即使得系统中占用共享资源最少的1 二序优先发射。这种算法具有多项式复杂 度，并且放松了对系统的约束，因而比 8 中的方法具有更广泛的应用。 8 9 中的方法比较类似。它们都是从死锁结构的概念出发，明确了死锁产 生的条件，即当系统的死锁结构中占用的资源等于资源的总数时，系统就会陷入 死锁状态，并在此基础上形成了自身的死锁避免算法。 由于需要考虑大型的柔性制造系统，p a r k 1 1 在p e i r i 网模型的基础上针对资 源分配系统开发了一种专门的新颖的建模和分析方法。它用整数规划的方法来避 免系统死锁。但是由于它考虑了资源分配系统中的大部分情况，从而使得网模型 不再只是适用于一般网，这就大大限制了它的应用。 第二种，死锁检测与校正方法 】2 1 3 。这种方法并不刻意去追求系统的无 死锁性或活性。而是一旦检测到系统发生了死锁，通过自动或人工的方法解锁。 这种方法往往会达到较高的生产率和资源利用率，但控制工程师必须对可能发生 死锁的生产环节有充分的认识，在设计单机( 如机器人、机床) 控制器时，需要设计 相应的控囊4 程序以便解锁时应用。此外，可能还需要一些附加的设备供解锁时使用， 其结果又是要加大投入。 第三种，死锁预防方法 8 1 4 儿1 5 儿1 6 1 7 1 8 。这种方法的目标是设计一 个系统，该系统所对应的p c t r i 网模型本身就是无死锁的或者是活的。这种方法从 逻辑上保证了系统中不会出现死锁，因而不必再去控制系统运行过程中对资源的 申请。m c z l l o u 等人 1 7 通过限制进入系统工件的数量( 对于网系统而言，就是 控制网系统的初始标识1 ，使系统的p e t r i 网模型是活的，从而在原则上保证系统不 会陷入死锁。这种方法从确保系统不存在任何死锁的角度出发，相应地静态调配 资源( 设置初始标识) ，从而提高资源的利用率。应该指出，这种方法尽管保证了系 统的全局活性，但具有较大的保守性，从而降低了系统的生产率和资源的利用率。 目前出现的死锁预防方法大都采用在目标p c t f i 网模型中增加新的控制库所的 方法 1 9 2 0 2 1 2 2 。通过增加控制库所限制网系统的行为，从而保证网系统 是无死锁的。如果在一个p e t r i 网中没有严格极小信标( s m s ) 被清空，则该p e 耐 网是无死锁的。同时它也是一些p c l f j 删子类f 如自由选择网和非对称自由选择网 活的充分条件。e z p e k t a 等人 1 9 以p e t r i 网结构理论问基础，提出了一种柔性制 造系控制器设计方法，最终得到无死锁的受控网系统。该方法通过为每个严格极小 信标添加一个监控库所来限制网系统的某些行为从而保证网网系统的活性。该方 法简单且有效，然而，网系统中的可被清空的s 淞数目会随网系统规模激增，因此 需要给网系统添加大量的监督控制库所和连接弧，使得p e t r i 网控制器比原先建立 4 柔性制造系统无死锁p e t r j 网控制器的分解研究 的p e t r i 网模型复杂很多。同时，系统的行为也受到了极大的限制。传统的迭代法 2 0 2 2 2 3 虽然可以获得更多的行为特性，但同样需要控制太多s m s 而对稍具 规模的网系统束手无策。 近年来，在离散事件动态系统的监督控制中，区域法 2 4 儿2 5 成为一种重要的 方法。此方法最大的优点是通过添加控制库所使事件与危险状态和死状态分离， 可以获得最佳的和最大行为许可的p e t f j 网控制器。因为要产生可达图，同时要解 大量的不等式，所以其主要缺点在于计算量过大。 基本信标理论 2 6 的提出给死锁控制器设计带来了巨大变革，它将网中的严格 极小信标分为基本信标和从属信标两大类。一定的条件下，如果使得一个p e 仃i 网 中所有的基本信标不被清空，则其从属信标也不会被清空，进而网中所有的s m s 都不会被清空。而且在网系统中的基本信标个数却是非常有限的，这就意味着要 使一个p e t t i 网受控。只需要对少数几个可被清空的s m s 添加控制库所就可以了。 该方法大大简化了监控器的结构，在很大程度上减少少了对网系统的许可行为的 限制。因此，通过基本信标理论，能够设计出比较理想的p e 丽网控制模型。 综上所述，在柔性制造系统中，如何设计出一个结构简单、性能优越的死锁控 制器，是非常具有实际应用价值的。因此，对f m s 的死锁控制问题的研究是一项 非常必要的研究课题。基于p e t r i 网，虽然此问题已取得了不少研究成果，但目前 的解决方案仍需进一步地研究和完善。 1 2 本文完成的主要工作 本文对柔性制造系统中的死锁预防问题做了进一步的研究。文中提出了两种 有效的死锁预防策略，且得到了一些重要的结论。通过对f m s 单元应用实例的控 制来检验这两种控制策略的有效性。结果表明与现有的预防策略相比，这两种方 法都取得了较好的控制效果。本文工作主要包含以下几方面内容： 1 针对p e t i i 网的一个子类一e s 3 p r 网，在提出一种死锁预防策略的过程中做了 如下具体工作： 给出一种死锁预防控制策略，只需控制少数几个信标，便可使网最终受控。 论证了通过实施该算法后，得到的受控网的活性。 移除了控制器中的冗余控制库所，并论述了这样做的合理性。 2 在e s 3 p r 中受控网一般都是广义网，这样对受控网的进一步研究带来了困难， 因此在第六章中给出了一种算法，它能有效地将广义网转化成普通网，下面是 在提m 该策略时所做的一些具体工作： 给出了从最大可被清空信标中如何求取可被清空的s m s 算法，且证明了 从一个最大可被清空信标中一定能求出至少一个可被清空的s m s 。 第一章绪论 给出了结合m i p 和基本信标理论的一种控制器设计方法。 给出了将受控广义网转化为普通网的算法。 给出了这种算法并不改变网系统活性的证明。 总之，论文主要研究了柔性制造系统中的死锁预防问题，并取得了一定的成果。 其中通过控制策略一可以大大简化控制器的结构、增加网系统许可行为，适合解 决中小规模p e t r i 网死锁预防问题，控制策略二不用穷举网系统的所有s m s 就可以 得到结构简单的死锁预防控制器，且最后得到的网系统是普通网。最后，由于本 人时间、精力以知识所限，文中难免有一些纰漏，恳请指正。 6 柔性制造系统无死锁p e t r i 网控制器的分解研究 第二章p e t r i 网的基本知识 2 1p e t r i 网的基本定义和性质 本节主要介绍p e t r i 网最基础的定义及其性质 1 9 2 7 。 2 1 1p e t r i 网的结构及发射规则 【定义2 1 】p c t r i 网( 或库所变迁网) 是一个四元组，可表示为n = ( p ，t f ，w ) ， 其中： 1 ) p 代表库所的集合，库所用圆圈表示； 2 ) t 代表变迁的集合，变迁用长方框表示，且p 和t 是有限非空和不相交的集合； 3 ) f c 口1 ) u 口p ) 称为有向弧集； 4 ) w ：f 一小+ 称为f 中弧上的权，i n + = 1 ，2 ) ； 当且仅当v f f ，、h f ) = 1 ，称n p ，t ，f ，w ) 为普通网( o r d i n a r yn e t ) ，记作n = ( p ， t ，n 。 【定义2 2 】令n = ( p ，t ，f w ) 是一个p e t r i 网，节点x 曰，u t 的前置集定义为 + x = y p u t l ( y ，x ) 予) ，其后置集定义为x = y p u ti ( x ，y ) f 。可将该定义进一 步推广为节点集的前置集( 后置集) ：给定艇p u t ，则x = u 积x ( x 。= u 榴( x ) 。 【定义2 3 】如果n = ( p ，t ，f ，w ) 是普通网，并且有v l ，尹，= i p | = 1 ，则称n 是标识图( m a r k e d 黟a p h ) 。 【定义2 4 】如果n = ( p ，t ，f ，w ) 是普通网，且vt t ，| 1 i = l t i = 1 ，则称n 是状 态机( s t a t em a c h i n e ) 。 【定义2 5 】称网n = ( p ，t ，f ，w ) 为纯网，当且仅当一j ( x ，y ) ( p x l ) u ( t p ) ：( x ， y ) f ( y ，x ) f 。 非纯网可以在保持动态性质不变的情况下化为纯网，下面讨论的网都是纯网。 【定义2 6 】网n = ( p ，t ，f ，w ) 的关联矩阵定义为以p 和t 为序标的矩阵c ： p t z ，z 是整数的集合，且 小露吣p ， p m 。 p n 。 p 其它 【定义2 7 】令n = ( p ，t ，f ，w ) 是一个p e t r i 网， 1 1n 的标识是映射m ：p i n ，m 表示库所p 中的托肯数，托肯用实心圆点表 示； 第二章p e 埘网的基本知识 2 ) 给定s c 】p u t ，则m ( s ) = p sm ( p ) ； 3 ) 称( n ，m o ) 为网系统或标识网，其中m o 为9 【】9n 的初始标识。 【定义2 8 】令n = ( p ，t ，f ，w ) 是一个网系统， 1 ) 一个变迁t t 在m 下称为使能的，记为m 【1 ) ，当且仅当v p t ：m 净w ( p ，t ) 2 ) 若m f t ) 成立，则t 发射后，产生另一新标识m ，记为m 【| ) m ，有 m ( p ) = m ( p ) 一缈( b f ) m ( p ) + ( b f ) m ( p ) 一( b f ) + ( 印) m ( p ) p 啦 p f f p f n f 其它 3 ) 网n 从标识m o 开始的所有可达标识的集合记为r ，m o ) 或m o 【) 。它是个最 小集，即m 0 r ( n ，m o ) ，m r ( n ，m 0 ) m 【t ) r j m r ( n ，m o ) ； 4 ) 当且仅当存在标识m o ，m 1 ，m 。满足m o 【t 1 ) 【t 。) m 。，s = t l t 2 t 。为发射序 列； 5 ) 若存在标识m 使得m o i s ) m ，则m = m 0 + c y ，其中c 为关联矩阵，y 为发射 序列矢量，其第i 个数值代表第i 个变迁在序列s 中出现的次数。 2 1 2p e t r i 网的特性 【定义2 9 】令n = ( p ，t ，f ，w ) 是一个嗣，m o 是n 的一个标识， 1 ) ( n ，m o ) 是有界的，当且仅当j k 日n o ) ，v m r ( n ，m o ) ，v p p ：m s k ； 2 ) ( n ，m 0 ) 是结构有界的，当且仅当对于任意的有限的初始标识，它都是有界的； 值得说明的是，对于资源有限的实际系统丽言，它的p e t r i 网模型一般都是结构有 界的。所有元素均为0 ( 1 ) 的列向量记为o ( 1 ) 。 【定义2 1 0 】令n = ( p ，t ，f ，w ) 是一个网系统，i o 是n 的一个标识，( n ，n i o ) 是可逆的，当且仅当v m r ( n ，m o ) ，j s 使得m 【s ) m o 。 【定义2 1 1 】令n ；( p t ，f ，w ) 是一个网系统，m o 是n 的一个标识， 1 ) 一个变迁t 在标识m o 下是活的，当且仅当v m r 0 也m o ) ，jm r ( n ，m 0 ) 使 得m 【t ) 成立； 2 ) ( n ， b ) 是死锁的，当且仅当- 永蚤m o f t ) 成立： 3 ) ( n ，m o ) 是无死锁( 弱活) 的，当且仅当v m r ( n ，m 0 ) ，3 t t ：m 【哆成立； 4 ) ( n ，m o ) 是活的，当且仅当v l 蚤t 在标识m o 下是活的； 2 1 3 不变式的定义及其性质 【定义2 1 2 】令n = ( p ，lf w ) 是一个网系统， 1 1 以p 为序标的列向量v ：p z 称为n 的p - 向量，z 是整数的集合。 以t 为序标的列向量w ：t z 称为n 的t 向量。 柔性制造系统无死锁p e t r i 网控制器的分解研究 【定义2 1 3 】令i 和j 分别为网n = ( p ，t ，f ，w ) 的p 向量和t 向量， 1 ) 称p 向量i 是一个p 不变式，当且仅当i - o 且i c = 0 7 。 i l i l = p p l i ( p 瑚) 称为 i 的支撑。 2 ) 称t 向量j 是一个t 不变式，当且仅当j o 且c j = o 。删= t r l i ( t ) 0 ) 称为j 的支撑。 3 ) 称一个p 不变式( t 不变式) 是极小的，当且仅当它的支撑中不包含任何其它 p 一不变式( t 不变式) 的支撑。 4 ) 称n 是被p 不变式i ( t 不变式j ) 覆盖的，当且仅当v p p ：i ( p ) - 0 ( v t t ：j ( t ) 0 ) 。 本文中的p 不变式，如果没有特别声明，则都是极小p 不变式。 【性质2 1 】网系统，m 0 ) ，i 是n = ( p ，t ，f ，w ) 的一个p 不变式，v m r ( n ，m o ) ： 1 1 m = i t m o 。 【性质2 2 】网系统( n ，m o ) ，j 是n = ( p ，t f ，w ) 的一个t 不变式，”0 中所有 的变迁发射一次，可能会使网系统回到初始标识。 1 ) 2 ) 3 ) 钔 2 1 4 信标和陷阱的定义和性质 【定义2 1 4 】( n ，m o ) 是个网系统，n = ( p ，t ，f ，w ) ， 称一个非空集合s c p + 是一个信标( s i p h o n ) ，当且仅当s s 成立； 称一个非空集合s g p 是一个陷阱( t r a p ) ，当且仅当s s 成立； 称一个信标( 陷阱) 是极小的，当且仅当不存在其它信标( 陷阱) 是它的真子集； 称p p 是被标识m 标记的，当且仅当m ( p ) 0 。称一个集合s g ? 是被标识m 标记的，当且仅当s 中至少有一个元素被m 标记。s 中的托肯数m ( s ) = p p m ； 不包含任何p 一不变式支撑的信标称为严格信标，一个严格信标有可能被清空； 一个既是极小又是严格的信标，称为严格极小信标( s m s ) 。 【性质2 3 】网系统( n ，m o ) ，n = ( p ，t ，f ，w ) ，s ( ，是个信标，若j m r ( n m o ) ： m f s l = o ，则s 以后永远不会被标记，称为被清空。 【性质2 4 】网系统( n ，m o ) ，n = ( p ，t ，f ，w ) ，s g p 是一个陷阱，若j m r ( n ，m 0 ) ， m f s b o ，则s 以后总是被标记。 【性质2 s 】网n = ( p ，t ，f ，w ) 的p 不变式i 的支撑l l f 既是信标又是陷阱。 【性质2 6 】( n ，m o ) 是一个网系统，其中n = ( p ，t ，f ，w ) ，l 是一个p 一不变式， s p 是n 的一个信标，那么此信标s 是在m o 下被p 不变式i 控制的，当且仅当 1 7 m o o 且对于所有的p p s ，i ( p ) = o 成立，或等同地，i r m o o 且 p p l i ( p ) o ) s 。 如果s 是一个在m o 下被p 不变式l 控制的信标，则s 不可能被清空，也就是说， v m r ( n ，m o ) ：s 在标识m o 下是被标记的。 第二章p e t r i 网的基本知识 【性质2 7 】( n ，m o ) 是一个普通网系统，n = ( p ，t ，f ) ，若n 在m 下是死锁的， 则所有未被标记的库所形成一个信标。 【性质2 8 】，m o ) 是一个普通网系统，n = ( p ，t ，f ) ，如果网n 中没有信标可 能被清空，则称，m o ) 是无死锁的( d e a d l o c k - f r e e ) 。 2 2 小结 本章主要介绍了p e t r i 网的一些基本定义、性质及关于p e m 网的一些基本原理 对本文后面章节将要用到的一些基本知识进行了必要的说明。 1 0 柔性制造系统无死锁p e t r i 网控制器的分解研究 第三章e s 3 p r 网系统基本概念 本文主要研究p e 啊网的一个子类e s 3 p r ，并解决它的死锁预防问题。e s 3 p r 可以为一大类f m s 建模，代表性很强。为了对e s 3 p r 有更好的理解，本章第一节 首先介绍一个f m s 单元实例， 然后用p e 耐网对它进行建模得到一个e s 3 p r 网， 并进行一些必要的说明。在第二：节中结合第一节的f m s 单元实例对e s 3 p r 网的基 本定义、理论等