（机械电子工程专业论文）petri网的信标最大可控性及其应用研究.pdf

摘要 论文研究了p e 雠网的一种特殊子类g s v s t e m 在柔性制造系统中的死锁问题， 提出了基于信标最大可控性的死锁预防策略即参数化的监督控制器设计策略及其 改进后的参数化监督控制器设计策略。 参数化的监督控制器设计策略是首先对系统p e t r i 网模型中的基本信标实施控 制，然后通过线性规划求取所有从属信标满足可控性的条件，即基本信标的控制 深度变量。和现有方法相比，该策略只需加入少量的控制库所，且可避免不必要 的迭代过程。该策略能保证含有并发执行装配过程的一类柔性制造系统g s v s t e m 的无阻塞性，即在控制下，受控系统从任意可达状态都可以到达理想状态。 改进后的参数化监督控制器设计策略是对参数化监督控制器设计策略进行了 改进，不是将控制库所输出弧直接提前到空闲库所的后置变迁，而是将控制库所 的输出弧撤回至使得新的受控系统中不产生新的严格极小信标的变迁为止，从而 改善了网系统的动态性能，从控制效果上来看也是一种较好的方法。 这两种死锁预防策略适用于大型和中型复杂的资源分配系统，最后，通过了 一个g s v s t e m 例子来验证这两种策略的应用。 关键词：柔性制造系统p e t r i 网死锁预防基本信标无阻塞 a b s t r a c t t h i st h e s i si n v c s t i g a t e sd e a d l o c kp r o b l e m sf o ras p e c i a ld 弱so fp e t r in e t s ，w h i c hi s c a l l e dg s y s t e m st h a tc 趾w e l lm o d e ln c x i b l em a n u f a c t u 血gs y s t e m s ( f m s ) 1 w o d j 堙e r c n td e a d l o c kp f c v e n t i o np o l i d e st h a ta r eb a s e do nm a x - 伽l 仃o l l e dp m p e r t yo f s i p h o n s a r cd c v e l o p c d o i sp 盯a m e t e r i z e ds u p c i s o rc o n t m ld c s i 弘p o l i c yb 勰e do n a n dm eo t h c ri sa ni m p r o v e dp a r a m e t e r i z e ds u p e r v i s o rc o n t r o ld e s i g np o l i c y n e 矗r s ts u p e r v i s o rd e s i g np o l i c yp u r p o s e saw a ym a k i n gc v e r ys t r i c tm i n i m a l s i p h o nm 趿一c o n t m l l e db ya d d i l l gac o n t r 0 1p l a c et oe v c r ye l e m c n t a r ys i p h o n t h e n t r o l l a b i l i t yo fd c p e n d e n ts i p h o n si se n s u r e db yp m p e r l ys e l e c t i i i gt h ec 0 t r 0 1d e p t h v a r i a b l e so fe l e m e m 盯ys i p h o n s ，w h i c hc a nb eo b t a i n e db yl i n e a rp r o g m m m i n g t e c h n i q u e s c 0 m p 砌w i t ht h ee x i s t i n gp o l i c i e s ，t h ea d v a i i t a g eo fo u r si st h a tam u c h s m a l l e rn u m b e ro fm o n i t o r sa r ea d d e da n du 皿e c e s s a f yi t e 珀t j v ep f o c e s s e sa r ea v 0 i d e d ar e l e v a i l tp m p e r t yo ft h es y s t e mb c h a v i o ri st ob cn o n _ b 1 0 c k i n g ，i e ，如ma n y r e a c h a b l es t a t e ，ad e s j r a b l es t a t ec a i ib ca l w a y sr e a c h e du n d e rs u p e n ，i s i o n a l li m p m v e dp a r 锄e t e r i z e ds u p e r v i s o rc o n t m ld e s i g np o l i c ya i m sa ti m p r 0 v i n gt l l e p a r 锄e t e r i z e ds u p c r v i s o rc o n t m ld e s i 印p o l i c y w h e r et h eo u t p u ta r c so ft h ca d d i t i o n a l m o n i t o r sa r en o td i c t l ym o v e dt ot h cp o s t p o s i t i o nt m s i t i o 璐o fi d l e p l a c e s i t w i t h d r a w st h eo u t p u ta r c st ot h et r a i l s i t i o n s 眦mt h ec o n 仃0 l l e ds y s t e md o e sn o tg e n e r a t e n e we m p t i a b l em i i m a ls i p h o n s c o n s e q u e n t l y ，d y n 棚i cb e h “i o ri si l n p f o v e d ni sa l s o a ne d i c c i t v ep 0 1 i c y 胁c o n t r o lp c o 瑚肌c ep o i n to fv i e w t 钾od e a d l o c kp r e v e m i o np o l i c i e sa r ea d e q u a t et ol a f g c r 粕dm e d i 姗n c ts y s t e m s f i n a l l y ，t l l ea p p l i c a t i o no ft l l et w oa p p r o a c h e si si l l u s t r a t e db yag s y s t e me x 帅p l e k e y w o r d s ：f m s ； p e 纳 n e t ；d e a d k kp n v 吼t i o n 翻e m 蛆t a r ys i p h o n ； n 蛳- b l 傀k i 雌 创新性声明 y8 5 8 7 8 i 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人躲垫坐日期立生蟛 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。本人保证 毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。“呆密的论文 在解密后遵守此规定1 本人签名 导师签名 日期迸! 望：! 差 第一章绪论 第一章绪论 1 1 研究背景与意义 随着经济的不断发展，产品多样化的需求增加，产品更新换代速度加快，传统 的制造业己远远不能满足时代发展的需要，另一方面，计算机技术、信息技术在 制造业中得到了广泛的应用，同时其它学科的知识也应用到制造业中，它们与传 统制造技术相结合形成了先进制造技术( a m t = a d v a n c c dm 趾u f a c t u f i n g 1 k l i l l o l o g y ) ，先进制造技术已经不是传统意义上的机械制造技术，它是集机械、 电子、光学、计算机科学、材料科学、生物科学、管理学最新成就为一体的新兴 技术。近年来，工业发达国家和一些新兴工业化国家把发展先进制造技术作为一 项极其重要的发展战略或政策。把它列为国家中长期发展的重大关键技术，将其 看作是经济增长的根本动力之一。2 1 世纪科学技术曰新月异，先进制造技术也将 继续不断改进、改造、完善和发展，并以智能化( h l t e l l i g c c e ) 、网络化( i i l t e m e t ) 、 集成化( i n t e g r a t i o n ) 、柔性化( f 1 懿i b i l i l y ) 、知识化( k n o 西l e d g e ) 和创新( h l i t o v a t i o n ) 为特征的信息化( i n f o m l a i i o n ) 为主要发展方向。从总的发展趋势来说，主要有以下 几种形式：柔性制造系统( f m s ，h e x j b l em a n u f a c t l l r i n g s y s t e m ) 、计算机集成制造系 统( c l m s ， c o m p u t c ri i l t e 掣a t e d s y s t 锄) 、智能制造系统( 订s ，i n t e n i g e n t m 锄u f a c t u r i n gs y s t c m ) 、生物制造系统( b m s ，b i o n i c m a i l u f a c t i l r i n 亩、敏捷制造系统 ( a m s ，a 西l em 柚u f a c t u 血gs y s t e m ) 、虚拟制造系统( v m s ，n u a lm a n u f a c l u 血g s y s t e m ) 、纳米制造系统、创新制造系统等。然而经济全球化日趋成熟，企业分工 日益精细。竞争激烈的市场需要产品更新换代加快，大大缩短了产品的生产周期， 要求产品更具特色、更具个性化，但是却大大降低了产品的批量性。这就要求企 业能够快速小批量的来生产产品，而适应这一要求的柔性制造系统( f m s f l e x i b i e m a n u f a c t u r es y s t e m s ) 系统就应运而生了。柔性制造系统是一个具有同时处理多种 零件能力的计算机控制的生产系统。它的特点是：可以同时完成不同零件、不同工 序的制造任务；各制造设备之间是通过物料的自动输送、自动加工，大大缩短了 占9 5 的无机器加工时间；整个物流系统由计算机集成控制和集中监视，能在不停 机调整的情况下以最短时间向另一种零件转换。这些特点表明f m s 具有更大的柔 性，进一步提高了设备利用率，缩短了生产周期，降低了制造成本。f m s 的出现 改变了传统生产方式，生产设备在时间上和空间上是兼容的，即加工对象不断改变 时，只改变生产信息，而原生产设备不变( 时间柔性) ；且同一种制造系统可同时 2 p 细嚼的褂福秽：可控陆砭射朔叛畹 制造不同的加工对象( 空间柔性) 。这些正是多品种、中小批量生产所要求的生产 方式。然而，集计算机辅助设计( o 姬) 技术、机电一体化技术、模糊控制技术、模 糊数学、人工智能、专家系统技术和人工神经网络( a n n ) 技术于一体的f m s 为了 适应市场的需要变得日益复杂，从单一进程的串行系统到多个进程的并行系统， 从基于单机环境下的操作到网络并行环境下的机群操作等等。而具备并发、异步、 离散、并行、时变和随机特征的复杂f m s 给设计者带来了更为严峻的挑战。死锁 是f m s 设计者们不可回避的问题。如何采用科学的数学、图形模型来动态地描述 实际的f m s ，实现优化无死锁的高生产效率的f m s 是工程设计者们所面临的主要 课题。 通常，f m s 由一系列的工作站和柔性的传输系统所组成，工件通过运输系统 得到加载、传输和卸载并在工作站加工。不同类型的毛坯离散地进入系统，利用有 限的资源( 如机床、机器人、夹具、运载小车、传送带等) 按照既定的加工进程( 由 一系列工序组成) 进行加工。工件也可以根据当前系统实时状态灵活地选择加工进 程，这样就造成众多的不同加工进程并行共存于f m s 中，从而来竞争有限的共享 资源。如果有限的共享资源不能得到合理的分配，必然会产生各个进程忙于抢占 系统资源，同时每一个进程都不能满足自身的资源申请，从而造成部分进程不能 进行或者使所有进程都停止不前，即系统陷入了局部死锁或者全局死锁状态，严 重地影响了系统的动态性能，降低了系统的生产效率。因此设计人员需要建立系 统的抽象模型，研究死锁发生的机理，进而防止系统死锁的发生，也即提出有效 的控制死锁发生的策略。国内外的专家学者在这一方面进行了广泛深入的研究， 如串行处理的串演系统( 如经典自动机模型，n 演算模型，p o s t 一系统模型等) 、并行 处理系统的系统( p e t r i 网、c s p 、c c s 等) 。本文以p e t r i 网模型来动态地模拟f m s ， 提出了两种基于信标最大可控性的死锁预防策略。 1 2p e t r i 网的研究和应用现状 p e t r i 网是1 9 6 2 年由德国人c 盯l a d 锄p e t r i 先生在他的博士论文用自动机通 信中首次提出的网状结构的信息流模型。这一工作引起了美国和欧洲一些科学 家的重视，之后的4 0 年里，p e t f i 网的应用范围也扩展到通信以外的许多领域。p e m 网是一种系统的数学和图形的描述与分析工具。对于具有并发、异步、分布、并 行、不确定性和随机性的信息处理系统，都可以利用这种工具构造出要开发的p e t r i 网模型，然后对其进行分析，即可得到有关系统结构和动态行为方面的信息，根 据这些信息就可以对要开发的系统进行评价和改进，因此具有很好的工程应用前 景。目前，p e t r i 网最为成功的应用领域当属系统性能的评估与通信网络协议的分 析。p e t r i 网作为一种图形工具，象软件设计中的结构图、流程图一样，直观、形 第一章绪论 3 象，而且在这些网中，可以使用标记( t o k e n ) 来模拟系统的动态行为和并发活动。作 为一种数学工具，p c t r i 网可以建立状态方程、代数方程以及系统行为的其他数学 模型。数学方法的好处就是系统的数学方程一旦建立，就便于计算和验证，所以 对于p c t t i 网，实际工作者和理论工作者都可以根据需要加以利用。同时，p e t r i 网 为他们之间的沟通和交流提供了一个强有力的桥梁，即实际工作者可以从理论工 作者那里学到如何使他们的建模更加条理化，而理论工作者可以从实际工作者那 里学到如何使他们的建模更加实用化。随着实际系统提出更高的模拟要求，从事 p e t r i 网理论研究的专家们不断的扩充其模型，具有代表性的p e 一网模型有：时间 时延p e t r i 网( 豇m c 门晤m c dp c 砸n c t ) 1 1 】；高级p e t r i 网( h i g i i 1 e v e lp c t r in c t ) l z j ；随机 p c 打i 网( s t o c h 鹤t i cp e t r in c t ) 抑止弧p c n i 网模型( i nh i b i t o ra r c sp e t r in e t m o d e l ) 鸭对象p e t i i 网( o b j c c tp c t r in e t ) f 5 】；受控p e t r i 网( c o n t m l k dp e t r in e t ) i 州等。 在p e m 网模型的基础上，其分析技术也取得了长足的发展，具有代表性的技术包 括：代数分析技术川，图形分析技术1 8 】和归纳分析技术f 9 】o 目前，p c t r i 网建模已经广泛应用于许多领域，包括分布式软件系统、分布式 数据库系统【1 0 】、并发并行程序、柔性制造工业控制系统、离散事件系统、多处理 机存储系统、数据流计算系统、容错系统、可编程逻辑和v l s i 阵列、异步电路和 结构、编译器和操作系统、办公信息系统、形式语言、逻辑程序、网络设计与规 划、神经网络、数字滤波器、决策模型、化学系统和法律系统等。这些系统的共 同特点都是具有并发、异步、分布、并行、不确定性和随机成份，具有这些成份 的系统都可以使用p e t r i 网进行描述和分析。 1 3 蹦s 系统的死锁研究现状 系统的死锁一直是困扰f m s 系统设计者的一个棘手的问题。这问题对于复杂 的并行f m s 而言，尤为突出。许多专家学者在这一方面做了大量的研究工作。 通常死锁可以分为全局死锁和局部死锁诱种，前者影响系统所有的状态，后 者仅影响系统部分的状态。死锁使系统的全部( 或者部分) 的加工进程不能顺利完 成，甚至造成新的加工进程不能开始。并行f m s 系统共享有限的资源，资源的不 合理分配就可能造成上述死锁的出现，降低系统的生产效率。 从目前的文献来看，很多学者对f m s 中的死锁问题以及死锁产生的充分必要 条件作了深入的研究f 1 1 1 1 1 2 l 【1 3 1 。特别是c o 肋l a n 等人【1 1 1 给出了死锁发生的四个必要 条件： 互斥：资源只能分配给某个确定的任务或是空闲，资源不能同时被两个任 务占据。 非抢占：资源不可抢占，只能被占用它的任务自愿释放( 任务完成了相应 4 工序) 。 占用并等待：占据某些资源的任务请求另外的新资源，而这些资源为其它 任务占据。 循环等待：存在一组资源请求 p 1 ，如，p 。 ，其中p 1 等待p 2 占据的资源， p 2 等待p 3 占据的资源，p n 等待p l 占据的资源。 由此可见，只要保证其中的某个条件不成立，就可以消除死锁问题。通常专 家学者通过控制系统资源的分配来破坏不同进程间循环等待的条件，从而解决系 统中的死锁，相关的死锁解决策略也是基于这种思想。这些策略大致可分为以下 几类：死锁避免策略、死锁检测和恢复策略、死锁预防策略。 1 死锁避免 死锁避免策略通过不断地搜索系统的可达状态来取得死锁控制的目的。根据 该算法，系统每运行一步，即由控制系统判断系统选择可达图的何种分枝不会导 致死锁，并沿该分支继续运行下去，反之，则不选择该分支，从而达到死锁避免 的效果，【1 4 】【1 5 】【1 6 】中即采用了该算法。死锁避免算法的优点在于系统可以具有最大 许可的控制效果，也就是说除了危险节点及死锁节点外，受控系统保留了全部的 好的状态，在实际的并发系统中，这意味着系统运行效率得到了最大程度的保留。 但是，死锁避免算法也具有必须事先计算系统的可达状态图的缺点。而在p e t r i 网 系统中，系统的可达状态具有爆炸性的特点，也就是说，其可达状态数随着网规 模的增大呈现指数级的增长趋势。这使得即使在一些中等规模的网系统中，该算 法的实现都是极其不现实的。 2 死锁检测和恢复1 1 ” 这种方法并不刻意去追求系统的无死锁性或活性，而是一旦检测到系统发生 了死锁，通过自动或人工的方法解锁。这种方法往往会达到较高的生产率和资源 利用率，但控制工程师必须对可能发生死锁的生产环节有充分的认识，在设计单 机( 如机器人，机床) 控制器时，需要设计相应的控制程序以便解锁时应用。此外， 可能还需要一些附加的设备供解锁时使用，其结果又需要加大投入量。 3 死锁预防 死锁预防策略【1 8 - 2 1 1 是基于信标理论的一种死锁控制思想。这种方法从逻辑上 保证了系统中不会出现死锁，因而不必再去控制系统运行过程中对资源的申请。 该策略要向f m s 系统添加强制约束或者通过离线的机构控制资源的分配从而保证 系统的所有进程得以顺利进行。我们希望系统的静态的控制策略一旦建立就可以 保证系统不会出现我们不希望出现的死锁状态。死锁是由于系统中的信标被清空 而引起的，根据该思想，只要控制该系统中的所有的严格极小信标使之不被清空， 该网系统就不会出现死锁。 基于p e i r i 网系统的死锁问题研究取得了不少成果【2 砬引，但是仍然有许多问题 第一章绪论 需要进一步研究和解决。此外，许多控制方法和策略对系统的行为旌加了过多的 约束，降低了系统的性能。近年来出现的死锁预防方法大都采用在目标p e t r i 网模 型增加控制库所限制网系统的行为，来保证网系统是无死锁的。州中e z p c l c t a 提 出了针埘普通网的子类舟r 的死锁预防策略，把死锁和严格极小信标( 简记为 s m s l 一一对应起来，通过对每一个s m s 添加监控器来保证网系统的活性。该算法 具有不需要计算系统的可达状态的优点，但是其缺点也是十分明显的，首先，通 过添加控制库所，虽然危险的尤其是死锁节点会被去除，但同时一部分好的节点 也会被去除，从而使得目标网系统的运行效率受到影响。其次，由于在网系统中， s m s 的个数也是与网规模的大小成指数关系递增的，所以对于大型网系统而言， 我们需要添加大量的监督器和连接弧，从而使得控制器的设计变得复杂，甚至难 以实现。论文致力予死锁预防方法的研究，通过分析p e t i i 网的结构特性，完成了 基于基本信标的f m s 中的死锁预防策略的基础性理论研究，运用代数的方法保证 系统的p e t r i 网模型是无死锁的。 1 4 本文完成的主要工作 本文主要致力于p c t f i 网的一般网系统死锁预防策略的研究。其中主要引入了 两大理论：基本信标理论和信标最大可控性理论，在这两种理论的基础上开发的 死锁预防策略可以有效的预防死锁发生，提高f m s 系统的动态性能。文中我们主 要针对p e t r i 网一个特殊的子类g s v s t 锄进行建模分析。国外学者已经对该特殊 p e t r i 网子类【2 0 】硎做了较为详细的描述。g s y s t e m 网系统可以有效地模拟工序对多 个多类型的资源申请的完全顺序加工系统，这意味着该网系统是比普通网系统更 为复杂的一般网系统。 本文基于基本信标理论和信标最大可控性理论提出了两种预防死锁的策略。 这两种策略主要是对受控网系统设计监督控制器以及合理配置控制器中的初始标 识从而保证系统的最大可控性和最好的动态特性。依据g s y s l e m 系统的良好的结 构特性，理论证明我们最后可以获得活的和无阻塞性的g s v s t e m 网系统。 第一种控制策略是参数化的监督控制器设计策略。在该策略中引入了基本信 标理论【2 5 l 【2 6 】和信标最大可控性理论f 2 8 i 。以前采用的死锁预防策略多是对每一个严 格极小信标添加控制库所来保证系统的无死锁性，它仅适用于规模较小的网系统， 对于大型的网系统而言，由于严格极小信标的数量是随网的规模呈现指数递增， 这意味着所要添加的控制库所数量将随之呈现指数递增，这样会使得受控网系统 更加复杂化，且难以控制。因此，我们依据信标的特征t - 向量的线性相关性将严 格极小信标分为基本信标和从属信标，从而引入了基本信标理沦。该理论能大大 减少控制库所的设计数量，简化受控系统的复杂度。该理论的核心就是只需为所 6 有的基本信标添加控制库所，并且通过调节控制库所的初始标识来控制从属信标 的可控性，不需要对每一个严格极小信标添加控制库所就可以保证系统的无死锁 性。该策略将添加控制库所的初始标识用含有控制深度参数固的变量表达式来设 定，首先通过保证基本信标最大可控性来获得该变量的初始约束条件；随后检验 从属信标的最大可控性，获得从属信标最大可控后的控制深度变量的约束条件。 由于控制深度变量越小就意味着对系统的约束就越小，所以对该变量建立优化函 数来保证系统获得最优控制。变量优化过程可以直接避免从属信标最大可控性的 重复性验证，可以一次性获得满足系统最大可控性的控制库所中的初始标识，从 而优化了算法。最后，结合g s w t e m 网系统的良好的结构特性，就可以得到活的 且无阻塞的网系统。 第二种控制策略是改进后的参数化监督控制器设计策略。它主要是针对参数 化监督控制器设计策略进行了改进，从而促进了系统动态性能的改善。由于在参 数化死锁预防的策略中，将控制库所输出弧直接提前到空闲库所的后置变迁，这 样可能会对系统产生过度的约束，降低系统的动态性能。后续部分我们对参数化 的死锁预防策略做了进一步的改进，将控制库所的输出弧撤回至使得新的受控系 统中不产生新的严格极小信标的变迁为止，从而改善了网系统的动态性能。虽然 在一定程度上会增加算法的复杂性，但是从控制效果上来看还不失为一种好的方 法，它适用于规模适中的网系统。 总之，本文主要致力于p e 砸网的一般网系统死锁预防策略的研究，提出了两 种基于基本信标的信标最大可控的监督控制器设计方法，通过实例验证可以看出 取得了较好的控制效果，具有一定的工程应用前景。相信我的工作会对一般p e t r i 网死锁预防控制策略的研究起到进一步的丰富和促进作用。限于时间、条件和个 人的认识，文中会有一定的欠缺，恳请指正。 第二章p c i r i 网理论和系统建模分析 第二章p e t r i 网理论和系统建模分析 本章详细的介绍了p e 啊网的基本概念、性质以及系统的建模分析，为本文后 面几章的命题、定理做了准备。详细的例子以及证明可以参考【7 】1 2 5 】【2 6 】【2 9 】。 2 1p e t r i 网理论 2 1 1p e l r i 网的基本定义 【定义2 1 】库所变迁网( 简称p 厂r 网) 是一个四元组，表为n = ( p ，t f ，w ) ， 其中p 代表库所的集合，用圆圈表示：t 代表变迁的集合，用长方框表示；p 和t 是有限集合，并且p ，g ，t g ，p n t 夸彩；f ( p d u ( t x p ) 称为有向弧集；w ：卜聃 0 称为f 中弧上的权，m = o ，1 ，2 ，) 。 当且仅当v f f ，w 回= 1 ，称n = ，t ，f ，w ) 为普通网( o r d j n a r yn e t ) ，可以记作 n = ( p ，t ，f ) 。v p p ，v t t ，如果0 ，t ) f ，且w o ，t ) = 1 ，则称n 为普通p 厂r 网( 肌 o r d i n 矗yn e t s ) 。一个普通网肯定是一个普通p 厂r 网。了f = t ) f ，w l 时，称n = ( p ， t ，f ，w ) 为一般网( g c f a ln e t s ) 。 【定义2 2 】令n = ( p ，t ，f w ) 是一个网，n 的标识是映射m ：p i n ，m 表 示库所p 中的托肯数，托肯用实心圆点或数字表示；给定s p u t ，则m ( s ) = p s m ；称( n ，m o ) 为网系统或标识网，其中m o 为网n 的初始标识。 【定义2 3 】设n = ( p ，t ，f ，w ) 是一个p e t r i 网，节点x p u t 的前置集定义为 x = y 巾u t l ( y ，x ) f ) 。其后置集定义为x = y p u t i ( x ，y ) f ) 。将该定义进一步 推广为节点的集合，即h d ，u t 的前置集( 后置集) 定义为h = u ：h + x ( h = u 妇j x 。) 。 【定义2 4 】设n = t ，e w ) 是一个p e 耐网，v p p ，令m 积p - m a x 唧 w ( p ，t ) ) ， m i n p - m i “t p w q ，t ) ) ，m a x p = m a x 睁p 、h t ，p ) ) ，m i l l p = m i n 妊p w t ) ) 。如果网是 无阻塞当且仅当v p ep ，g 且m i n p 2 m i n p 。如果网是强无阻塞当且仅当v p p p 。_ 黟并且m i n p m 缸p 。 【定义2 5 】如果n = ( p ，t ，f ，w ) 是普通网，且v t t j | i l = 1 1 | = 1 ，则称n 是状 态机( s t a t em a c h j n e ) 。 【定义2 6 】如果n = 口，t ，f ，w ) 是普通网，并且有v p p ，= | p | = 1 ，则称n 是标识图( i n a r k e dg r a p h ) 。 【定义2 7 】如果一个p e l r i 网( n ，m o ) 的任意一个节点和其它节点中的任意一 个之间总存在一条连接路径，则称该网是强连通的。 【定义2 8 】如果一个p e t r i 网( n ，m 0 ) 既是一个状态机又是强连通的，则称其 为强连通的状态机。 【定义2 9 】网n = ( p ，t ，f w ) 称为纯的，当且仅当一j ( x ，y ) ( p d u 口p ) ：( x ， y ) f ( y x ) f 。 【定义2 1 0 】设n = ( p ，t ，f ，w ，m o ) 是一个五元组系统。 1 悄的标识是映射m ：p 一矾； 2 ) 一个变迁t t 在m 下是使能的，记为m 【t ) ，当且仅当v p 。t ：m 七w o ，t ) ； 3 ) 若m 【t ) 成立，则t 发射后，产生另一新标识m ，记为m 【t ) m 。，有 f ( p ) 一 m ( p ) 一w ( p ，t ) m ( p ) + ，( p ，t ) m ( p ) 一w ( p ，t ) + w ( t ，p ) m ( p ) 一t t p t t t n t 其它 4 ) 网n 从标识m o 开始的所有可达标识的集合记为r ( n ，m o ) 或m o 【) 。它是一个最小 集，即m 雁r ，m 0 ) ，m r 科，m 0 ) m 【t ) m j m 。甄n m 0 ) 5 ) 当t bt 2 ，t n t 时，庐t l t 2 t n 称为出现序列，当且仅当存在标识m 0 m 1 ，m 。 满足m o 【t 1 ) 【t n ) m 。； 6 ) 对于网n 和标识m o ，( n ，m o ) 称为一个网系统； 7 ) 网n = ( p ，t ，f ，w ) 的关联矩阵定义为以p 和t 为序标的矩阵【n 】：p t _ - z ，z 是整数 的集合，且 【n 】( p ，t ) t w ( p ，t ) w ( t ，p ) 一w ( p ，t ) + w ( t ，p ) 0 一t t p t t p t t 。 其它 8 ) 输入关联矩阵【n 】。= a i j ) ，输出关联矩阵【n 】+ = a i i + ) ，关联矩阵f n 】= 【n 】+ 【n 】。， n 】j ( 【n l ，【n l + ) 是矩阵【n 】( 【n l ，【n 1 j + ) 的第j 列，其中8 q = w p i ，b ) ，a i j + = ，p i ) 2 1 2p e 砸网的活性及不变式 【定义2 1 1 】设n = ( p t f ，w ) 是一个网，m o 是n 的一个标识。 1 ) 一个变迁t 在标识m o 下是活的，当且仅当v m r ( n m 0 ) ，j m d r ，m 0 ) ：m 。i t ) 成 立： 2 n ，m o ) 具备死锁性，当且仅当，j 日：m o 【t ) 成立； 3 ) ( n ，m 0 ) 具备无死锁( 弱活) 性，当且仅当v m r ( n ，m o ) ，j t m m 【t ) 成立； 4 ) 系统在m o 下具备准活性，当且仅当在m o 状态下v t e t ，j m 【m o t 。 5 ) ( n ，m o ) 具备活性，当且仅当v t r t 在标识m o 下是活的，也即是v t m v m 【m o 第二章p e “i 网理论和系统建模分析 j m 【m ，m 。【t 。 6 ) ( n ，m 0 ) 具备有界性，当且仅当j k i 玳 0 ) ，v m r 吖，m 0 ) ，v p p ：m ( p ) 呔； 7 ) ( n ，m o ) 具备结构有界性，v m o ，心，m o ) 是有界的； 8 ) ( n ，m o ) 具备结构活性，当且仅当j m o ，( n ，m o ) 是活的。 9 ) 设m 。是“h o m e ”的，当且仅当v m 【m o ，m 。【m 。 1 0 ) ( n ，m o ) 具备可逆性，当且仅当m o 是“h o m e ”的。 值得说明的是，对于资源有限的实际系统而言，它的p e t r i 网模型一般都具备 结构有界性。 【定义2 1 2 】设n = ( p ，t ，f ，w ) 是一个网。 1 1 以p 为序标的列向量v ：p z 称为n 的p 向量。 2 ) 以t 为序标的列向量w ：t z 称为n 的t 向量。 3 ) 称p 向量i 是一个p 不变式( 库所不变式) 当且仅当i - o 且i t 【n 】- o t 。 i l i l l = p p l l ( p ) 0 ) 称为l 的支撑。令恻+ = p p l l ( p ) o ) ，i l l | l = p p 1 1 ( p ) o 。称一个集合s p 是被标识m 标 记的，当且仅当s 中至少有一个元素被m 标记。s 中的标识m ( s ) = ，p m ；s 是最大标识的，当且仅当v p s ，j m 0 ) m a x p - 。 5 ) 不包含任何p 不变式支撑的信标称为严格信标。一个严格信标有可能被清空。 6 ) 一个既极小又严格的信标，称为严格极小信标( s m s ) 。 2 1 3p e t r j 网的基本性质 【性质2 1 】网系统( n ，m 0 ) ，i 是n = ( p ，t f ，w ) 的一个p 不变式，v m r ( n ，m 0 ) ： i t m = i t - m o 。 【性质2 2 】网系统( n ，m 0 ) 1 1 和1 2 分别是该网系统的p 一的不变式，那么i = 1 1 。1 2 也是该网系统的p 不变式。 【性质2 3 】网系统，m 0 ) ，x 是n = ( p ，t f ，w ) 的一个t _ 不变式，i f x i f 中所有 的变迁发射一次，可能会使网系统回到初始标识。 【性质2 4 】网系统( n ，m o ) ，n ：( p ，t ，f ，w ) ，s c i 是一个信标，若j m r ( n ， m o ) ：m ( s ) = o ，则s 以后永远不会被标记，称为被清空。 【性质2 5 】网系统心，m 0 ) ，n = 婶，t f ，w ) ，s g ? 是一个陷阱，若j m r ，m o ) ， m ( s ) o ，则s 以后总是被标记。 【性质2 6 】网n = ( p ，t f ，w ) 的p 不变式l 的支撑| i i l | 既是一个信标又是一个 陷阱。 【性质2 7 】( n ，m o ) 是一个网系统，其中n = ( p ，t ，f ，w ) 。如果该网系统是无 死锁的并且状态m o 是“h o m e ”的，那么该网系统就是活的。 【性质2 8 】( n ，m o ) 是一个普通网系统，n = ( p ，t ，f ) ，若n 在m 下是死锁的， 则所有未被标记的库所形成一个信标；如果网n 中没有信标可能被清空，则称( n ， m 0 ) 是无死锁的( d e a d l o c k 骶e ) 。 上文采用p e t r i 网模拟f m s 系统的理论基础。通过分析p c t r i 网模型的结构特 性和系统的动态特性，寻求设计活的网系统的方案。本中主要讨论一般资源有界 网系统。 2 2p e t r i 网的系统建模 图2 1 。2 2 用一个我们常见的化学反应式2 h 2 + 0 2 = 2 h 2 0 演示了p c t r i 网的基本 运行规则，图3 1 表示在该时刻有两个h 2 和两个0 2 ，图3 2 表示t 发射后的系统状 态。对比图3 1 、3 2 可知两个h 2 和两个0 2 合成两个水分子h 2 0 。 图2 1 发射前 图2 2 发射后 第二章p e 埘网理论和系统建模分柝 下面以一个例子演示p c n j 网模型在柔性制造系统中的应用。 图2 3 用p e t t i 网描述了一个简单的柔性靠4 造系统。 图2 3 一个柔性制造系统 图2 3 所示的系统包含两个加工进程，分别为p 1 一p 2 - p 3 一p 4 ，p 1 1 一p 1 0 p 9 一p 8 ，三个 加工工具p 5 ，p 6 ，p 7 ，每次可以加工一个工件。它可以模拟两个独立的f m s 共享资 源后的系统，这个独立的f m s 系统由机床( m 1 ，m 2 ) 、三个机器人( r 1 ，r 2 ，r 3 ) 、输 入缓存库i 和输出缓存库o 组成，且机床m 每次只加工一个工件，机器人r 每次 只能夹持一个工件。机器人r 可以将输入缓存库i 中的零件装载到机床m 上，也 可以将机床m 上的零件卸载到输出缓存库o 中。其加工进程为：p 1 ：i r 1 一m 1 一 r 2 + m 2 r 3 ，o 。 2 3p e t r i 网系统模型分析 ( 1 ) 首先根据p e t r i 网的基本定义分析在图2 3 所示的p e t f i 网n = ( p ，t ，f ，w ) 的 结构特性： 该模型由1 1 个库所，8 个变迁构成，属于一个小型的p e 仃i 网，其中有2 个空 闲库所，3 个资源库所，其余为操作库所。其常见的结构特性和基本信息如下： p = p 1 ，p 2 ，p 3 ，p 4 ，p 5 ，p 6 ，p 7 ，p 8 ，p 9 ，p l o ，p 1 1 ) ，t 毫 t l ，t 2 ，1 3 ，t 4 ，t 5 ，t 6 ，7 ，8 ) ，v f f ， w ( d = 1 ，它是一个普通网。 初始标识m o = 【1o 0 0 1l1o 0 0 1 】t ，( n ，m o ) 为网系统或标识网。 根据前罱集和后置集的定义，可以得到该模型的节点分布，如表2 1 所示。 ! !型堕堕塑塑型坚燮 表2 1 模型的节点分布 库所变迁m 0 0 ) pp tt p l t l 1 t 4t lp l ，p 5p 2 p 2 t 2 o t lt 2p 2p 3 p 3 t 3 o t 2 t 3 p 3p 4 p 4 t 4 0 t 3 t 4 p 4p l ，p 7 p 5 1 5 1 t 2 ，t 5t l ，t 6 p 8p 5 ，p l l p 池 1 t 3 ，t 6t 2 ，t 7 p 5 ，p 9p 6 ，p 8 p 7 t 7 1 t 4 ，t 7 t 3 ，t 8p 6 ，p l op 7 ，p 9 p 畦t 8 o 6b p 7 ，p 1 1p l o p 9 ob t 6 p 1 0 ot 8 t 7 p 1 1 1 t 5 t 8 网n 的关联矩阵为 表2 2 关联矩阵 t 1t 2t 3l t 5t 6bt 8 p 1 10010o0 0 p 2 1 10 o 000o p 30 1100000 p 正00110000 h - l1o011oo p 6 01l0011o n0o 1 10 011 p 8 o000 11 0 0 p 9 o0o00 110 p l o 0 0o o 0011 p 1 loo 0o1001 由不变式的定义i - o 且i t c = o t 得，网模型n 包含以下五个极小p 不变式： i l = o ，1 ，o ，0 ，1 ，0 ，0 ，1 ，o ，0 ，o ) ； 1 2 = o ，0 ，1 ，0 ，o ，1 ，o ，o ，l ，0 ，o ) ； 1 3 = o ，o ，o ，1 ，o ，o ，l ，0 ，o ，1 ，o ) ； 1 4 = o ，o ，o ，0 ，o ，o ，o ，1 ，1 ，1 ，1 ) ； 第二章p e t i i 鼹理论和系统建模分析 1 3 1 5 = 1 ，1 ，1 ，1 ，0 ，o ，o ，0 ，o ，o ，o 与之对应的不变式支撑分别是：l l l l h = p 2 ，p 5 ，p 8 ；i 1 2 | 1 p 3 ，p 6 ，p 9 ；i l l 3 i i = p 4 ，p 7 ， p l o ；i i l 4 i i = p 8 ，p 9 ，p 伯，p 1 1 ；h i s l i = p l ，p 2 ，p 3 ，p 4 )