（控制理论与控制工程专业论文）柔性制造系统中基于petri网的死锁预防策略.pdf

摘要 柔性制造系统对有限资源的竞争会产生死锁现象。p e t r i 网作为一种分析工具， 可以有效地为柔性制造系统建模、分析并解决死锁问题。基于信标理论的死锁预 防策略是p e t r i 网死锁预防策略的研究方向之一，该策略为网模型中每一个严格极 小信标添加控制库所和连接弧。理论上网模型中的信标个数与网规模成指数关系， 网规模越大，信标的个数就会激增，从而导致添加了过多的控制库所和连接弧。 本文针对p e t r i 网的子类s 3 p r 网研究了其死锁预防问题，提出一种算法，该算法 不仅能够减少网系统中控制库所的个数并且能够使网系统得到更多的许可行为。 基于p e t r i 网和信标理论，严格极小信标可分成基本信标和从属信标。对基本 信标和从属信标采用不同的控制策略。对是否含有中心资源( c e n t e rr e s o u r c e ) 的从属 信标加以区分，不同从属信标采用不同的控制方法，使原网中的所有严格极小信 标均不会被清空，新产生的严格极小信标不会影响网系统的活性。最后利用隐式 库所特性对受控网系统进行化简。 本文所提算法能够得到结构更为简单，状态数更多的活的网系统。最后，我 们利用本死锁预防策略对f m s 实例进行分析和验证，显示出了该算法的优越性。 关键词：柔性制造系统( f m s ) p e t ri 网基本信标死锁预防 a b s t r a c t t h ec o m p e t i t i o nf o rl i m i t e dr e s o u r c e sl e a d st od e a d l o c k 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 ) a sat o o l jp e t r in e t sa r ea ne f f e c t i v ew a y t om o d e l ，a n a l y z e ，a n dc o n t r o l d e a d l o c k si nf m s o n et r e n do fd e a d l o c kp r e v e t i o np o l i c yi st h ed e a d l o c kp r e v e n t i o n m e t h o db a s e do ns i p h o nt h e o r y t h i sm e t h o da d d sc o n t r o lp l a c e sa n dr e l a t e da r c st o e v e r ys t r i c tm i n i m a ls i p h o n ( s m s ) h o w e v e rt h en u m b e ro fs i p h o n sg r o w si ng e n e r a l e x p o n e n t i a l l yw i t hr e s p e c tt ot h es i z eo ft h ep e t r in e t ，r e s u l t i n gi nt o om a n ya d d i t i o n a l p l a c e sa n da r c s 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 no fs p rn e t ，w h i c hi s o n es u b c l a s so fp e t r in e t s ap o l i c yi sd e v e l o p e d ，w h i c hc a nn o to n l yr e d u c et h en u m b e r o fc o n t r o lp l a c e sb u ta l s oc a ne n s u r et h a tt h en e ts y s t e mh o l dm o r ep e r m i s s i v eb e h a v i o r b a s e do np e t r in e t sa n ds i p h o nt h e o r y , s t r 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 o e l e m e n t a r ya n dd e p e n d e n ts i p h o n s d i f f e r e n tc o n t r o lp o l i c i e sw i l lb et a k e nt o w a r d e l e m e n t a r ya n dd e p e n d e n ts i p h o n s t h ed e p e n d e n ts i p h o n sw i l lb ed i v i d e db yw h e t h e r i t i n c l u d e sc e n t e rr e s o u r c eo rn o t ，a n dd i f f e r e n tc o n t r o lp o l i c i e sw i l lb ea d d e da l s os u c h t h a tt h es t r i c tm i n i m a ls i p h o n si nt h eo r i g i n a ln e tw i l lb es u f f i c i e n t l ym a r k e d f u r t h e r m o r e ，t h en e w l yg e n e r a t e dc o n t r o l i n d u c e ds t r i c tm i n i m a ls i p h o nw i l ln o ta f f e c t t h el i v e n e s so ft h en e t f i n a l l y , t h ec h a r a c t e r i s t i co fi m p l i c i tp l a c ew i l lb eu s e df o r s i m p l i y l i n gt h en e ts y s t e m t h en e wd e a d l o c kp r e v e n t i o np o l i c ye n a b l e st h es u p e r v i s o r ss t r u c t u r et ob e s i m p l e r , a n dm o r ep e r m i s s i v eb e h a v i o rc a nb eo b t m n e di nn e ts y s t e ma sw e l l i nt h e f i n a lp a r to ft h i sr e s e a r c h ，t h ea d v a n t a g e sa n ds u p e r i o r i t i e so ft h i sm e t h o dc a nb ep r o v e d t h r o u g hc o m p a r i n gw i t ho t h e rk i n d so fd e a d l o c kp r e v e n t i o nm e t h o d si nf m s k e yw o r d s ：f l e x i b l e s i p h o n m a n u f a c t u r i n gs y s t e m ( f m s ) p e t r in e t s e l e m e n t a r y d e a d l o c kp r e v e n t i o n 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：杰趁日期幽! 墨，星 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名：至跹 导师签名：乏查查丞蝰)日期型：! ：壁 p 第一章绪论 第一章绪论 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 s ) 就应运而生了。 套完整的柔性制造系统是由统一的信息控制系统、物料储运系统和一组数 字控制加工设备组成，能适应加工对象变换的自动化机械制造系统，如图1 1 所示。 其中，信息控制系统负责f m s 的实时控制和在线监督，信息由多级分布式计算机 进行处理和控制。f m s 的工艺基础是成组技术，它按照成组的加工对象确定工艺 过程，选择相适应的数控加工设备和工件、工具等物料的储运系统，并由计算机 进行控制，故能自动调整并实现一定范围内多种工件的成批高效生产( 即具有“柔 性”) ，并能及时地改变产品以满足市场需求。 图1 1f m s 实倒 2 柔性制造系统中基于p e t r i 网的死锁预防策略 柔性制造系统的诞生标志着传统的机械制造行业进入了一个发展变革的新时 代，从一开始就显示出来强大的生命力。它克服了刚性自动化只适用于大量生产 的局限性，表现出了对多品种，小批量生产方式的适应性。 在f m s 中【4 】【7 】【8 】【9 】【2 0 】【2 4 1 ，各种工件按照一定的节拍，在离散时间点上进入系统， 系统对它们进行并行加工处理，各加工进程共享一定数量的资源，如机床、机器 人、夹具、托盘等。各种工件有自己的特殊加工路径，即资源需求序列，在加工 过程中，各种工件的并行处理竞争着有限的资源，从而可能会导致系统运行和控 制的许多问题，其中最为突出的问题是f m s 的死锁问题【3 】。f m s 的死锁是制约系统 控制和调度实现的关键因素，因此避免f m s 死锁的研究是f m s 目前研究的热点 之一。 对于一个实际f m s 系统人们很难事先准确地描述系统的运行状况。可行的方 法是对整个系统进行建模，模拟其运行状况，从而分析出被模拟系统在结构和动 态行为等方面的重要信息。p e t r i 网就是这样一个很好的建模、分析工具。 p e t r in e t ，也称为p e t r i 网，是由德国人c a p e t r i 于1 9 6 2 年在他的博士论文 中首次提出的。它【5 】【6 】是一种适用于多种系统的图形化、数学化建模工具，为描述 和研究具有并行、异步、分布式和随机性等特征的信息j h t 系统提供了强有力的 手段。p e t r i 网以其能够模拟系统的并发和冲突行为以及能反映出系统的动态特性 而倍受青睐。f m s 作为一种典型的离散事件动态系统一直是p e t r i 网的重要应用领 域。p e t r i 网是描述和分析自动制造系统的一个有力工具，它可以很清楚地反映出 系统运行中变迁之间的顺序、并发、同步及死锁等现象。 基于p e t r i 网【5 】【lo 】人们研究了很多方法来处理柔性制造系统中的死锁问题。这 些方法大致可归为三类：死锁避免方法；死锁检测与校正方法；死锁预防方法。 第一种，死锁避免方法【2 】【l l 】【1 2 】【1 3 】【1 4 】，死锁避免策略通过不断地搜索系统的可 达状态来取得死锁控制的目的。根据该算法，系统每运行一步，即由控制系统判 断系统选择可达图的何种分枝不会导致死锁，并沿该分支继续运行下去，反之， 则不选择该分支，从而达到死锁避免的效果。死锁避免算法的优点在于系统可以 具有最大许可的控制效果，也就是说除了危险节点及死锁节点外，受控系统保留 了全部的好的状态，在实际的并发系统中，这意味着系统运行效率得到了最大程 度的保留。但是，死锁避免算法也具有必须事先计算系统的可达状态图的缺点。 而在p e t r i 网系统中，系统的可达状态具有爆炸性的特点，也就是说，其可达状态 数随着网规模的增大呈现指数关系的增长趋势。这使得即使在一些中等规模的网 系统中，该算法的实现都是极其不现实的。 v i s w a n a d h a m 等人【2 】提出的方法是通过向前搜索网系统的可达标识图来避免 死锁的。当给定一个网系统的当前标识后，算法就会确定所有规定搜索长度内的 标识状态；通过判断这些标识是否是死锁标识，就可以找到那些发射后会导致系 第一章绪论 3 统死锁的变迁。在网系统运行的时候，只要不使能这类变迁就可以避免系统产生 死锁。这种方法可以使系统有限度地避免死锁，但确定搜索步数有很大困难，而 且还必须提供系统出现死锁时的修复策略。 第二种，死锁检测与校正方法【l 5 】【l6 1 。这种方法并不刻意去追求系统的无死锁 性或活性，而是一旦检测到系统发生了死锁，通过自动或人工的方法解锁。这种 方法往往会达到较高的生产率和资源利用率，但控制工程师必须对可能发生死锁 的生产环节有充分的认识，在设计单机( 如机器人、机床) 控制器时，需要设计相应 的控制程序以便解锁时应用。此外，可能还需要一些附加的设备供解锁时使用，其 结果又是要加大投入。 第三种，死锁预防算法【1 1 】【2 5 】【2 6 】【2 7 】【2 8 】【2 9 】。该方法要向f m s 系统添加强制约束 或者通过离线的机构控制资源的分配从而保证系统的所有进程得以i l i o n 进行。这 种方法从逻辑上保证了系统中不会出现死锁，因而不必再去控制系统运行过程中 对资源的申请。m c z h o u 等人【2 8 】通过限制进入系统工件的数量( 对于网系统而言， 就是控制网系统的初始标识) ，使系统的p e t r i 网模型是活的，从而在原则上保证系 统不会陷入死锁。这种方法从确保系统不存在任何死锁的角度出发，相应地静态 调配资源( 设置初始标识) ，从而提高资源的利用率。应该指出，这种方法尽管保证 了系统的全局活性，但具有较大的保守性，从而降低了系统的生产率和资源的利 用率。 目前出现的死锁预防方法大都采用在目标p e t r i 网模型中增加新的控制库所的 方法【7 】【1 7 】【1 8 】【19 1 。通过增加控制库所限制网系统的行为，从而保证网系统是无死锁 的。如果在一个p e t r i 网中没有严格极小信标( s m s ) 被清空，则该p e t r i 网是无死锁 的。同时它也是一些p e t r i 网子类( 如自由选择网和非对称自由选择网) 活的充分条 件。e z p e l e t a 等人【j 7 】以p e t r i 网结构理论问基础，提出了一种柔性制造系控制器设计 方法，最终得到无死锁的受控网系统。他们定义了一类普通保守网的予类s 3 p r ， 即含有资源的简单加工进程系统，他们要求目标p e t r i 网为s 3 p r 网，通过为每个 严格极小信标添加一个监控库所来限制网系统的某些行为从而保证网系统的活 性。该方法简单且有效，然而，网系统中的可被清空的s m s 数目会随网系统规模 激增，因此需要给网系统添加大量的监督控制库所和连接弧，使得p e t r i 网控制器 比原先建立的p e t r i 网模型复杂很多，许可行为也会受到很大的限制。 论文通过分析p e t r i 网及s 3 p r 网的结构特性，重点分析对比e z p e l e t a 等死锁 预防算法，将引用基本信标和从属信标的概念，结论表明，在一定条件下，如果 一个p e t r i 网中所有的基本信标不会被清空，则其某些从属信标也不会被清空，进 一步可以保证所有严格极小信标( s m s ) 不会被清空。这就说明，一个网中如果 没有信标被清空时，并不需要对所有的s m s 都添加控制器。因此，基于基本信标 理论可以得到一个包含较少控制库所和有向弧的受控网模型，由此引出较为优化 4 柔性制造系统中基于p e t r i 网的死锁预防策略 的死锁预防算法。 1 2 本文完成的主要工作 本文主要针对柔性制造系统中基于p e t r i 网的死锁预防问题进行研究，阐述了 f m s 中的死锁问题及其基于p e t r i 网的建模。着重分析了p e t r i 网的一个子类，s 3 p r 网的定义，结构以及性质。重点介绍了e z p e l e t a 死锁预防算法和基于基本信标理 论的死锁预防算法。结合基本信标理论和中心资源概念提出了新的死锁预防策略， 根据p e t r i 网的基本理论和性质，应用反证法对新的预防策略加以证明。根据隐式 库所的特性，简化受控的p e t r i 网模型。最后应用本算法对f m s 实例进行了分析和 验证。与e z p e l e t a 死锁预防算法对比，特别是在更为复杂的网系统中，该预防策 略添加的控制库所更少，许可行为更多，达到了更好的控制效果。 限于时间、条件和个人的认识，本文不可避免地存在一些不足之处，敬请指正。 第二章p e t r i 网基本理论及建模 第二章p e t r i 网基本理论及建模 p e t r i 网理论是由c a p e t r i 博士于1 9 6 2 年提出的。作为一总数学方法，以其能 够模拟系统的并发和冲突行为一起反应系统动态特性而受到了广泛关注。本章介 绍了p e t r i 网的基本理论，术语，为后面章节提供理论依据【1 】【5 】【6 】【3 0 】【删。 2 1p e t r i 网基本定义及性质 本小节主要介绍p e t r i 网的基本定义和性质【7 】【2 3 】【3 3 】【4 0 l 。 2 1 1p e t r i 网的概念及基本定义 【定义2 1 】p e t r i 网( 或库所变迁网) 是一个四元组，可表示为- ( 尸正只叻， 其中： 1 ) 尸代表库所的集合，库所用圆圈表示； 2 ) r 代表变迁的集合，变迁用长方框表示，且p 和f 是有限非空和不相交的集合； 3 ) f c _ ( p x 乃u ( a 尸) 称为有向弧集； 4 )形n 玳 o ) 称为f 中弧上的权，i n = 0 ，1 ，2 ) ； 当且仅当坼，w 0 0 = i ，称- ( 尸，正e 功为普通i n ( o r d i n a r yn e t ) ，记作- 正用。 【定义2 2 】令_ zer e ) 是一个p e t r i 网，节点石尸u r 的前置集定义为 沪 y e p w t l ，功毋，其后置集定义为x _ y e p w t i ，y ) 毋。可将该定义进一 步推广为节点集的前置集( 后置集) ：给定x _ c p u t , 则珏叱x 吖( x 文以x x ) 。 【定义2 3 】如果= ( 尸正只叨是普通网，并且有跏p ，l i _ 扩i = 1 ，则称n 是标识图( m a r k e dg r a p h ) 。 【定义2 4 】如果_ ( 尸，乃e 功是普 n i n ，且vt t ，i 。t l = l t l = l ，则称n 是状 态机( s t a t em a c h i n e ) 。 【定义2 5 1 如果一个p e t r i 网( m o ) 的任意一个节点和其它节点中的任意一 个之间总存在一条连接路径则称该网是强连通的。 【定义2 6 】如果一个p e t r i 网( mm o ) 既是一个状态机又是强连通的，则称其 为强连通的状态机。 【定义2 7 】称网= ( 只ler v ) 为纯网，当且仅当- 1 j o ，力( p x 乃u ( a d ： ， y ) e f t y ，x ) e f 。 非纯网可以在保持动态性质不变的情况下化为纯网，下面讨论的网都是纯网。 【定义2 8 1 网- ( 尸正只功的关联矩阵定义为以p 和r 为序标的矩阵c ： 尸n z ，z 是整数的集合，且 6 柔性制造系统中基于p e t r i 网的死锁预防策略 m 。降w m ， i 一( d f ) p 。t i t 。 p t l t p e f i t 其它 2 1 2p e t r i 网的活性及不变式 【定义2 9 】令_ ( p 正只功是一个网，m o 是的一个标识， 1 ) m o ) 是有界的，当且仅当3 k e i n o ，v m er m o ) ，v p p ：m p ) 致； 2 ) ( mm o ) 是结构有界的，当且仅当对于任意的有限的初始标识，它都是有界的； 值得说明的是，对于资源有限的实际系统而言，它的p e t r i 网模型一般都是结构有 界的。所有元素均为o ( 1 ) 的列向量记为0 ( 1 ) 。 【定义2 1 0 令- ( p ，正只叨是一个网系统，m o 是的一个标识，( ，m o ) 是可逆的，当且仅当v m e r ( n , m o ) ，3 0 使得m o ) m o 。 【定义2 1 1 】令- ( 只正e 聊是一个网系统，m o 是的一个标识， 1 ) 一个变迁t 在标识m o 下是活的，当且仅当v m e r ( n , m o ) ，jm r ( ，m o ) 使得 m 【成立； 2 ) ( mg o ) 是死锁的，当且仅当1 了f 弘m o t 成立； 3 ) ( ，m o ) 是无死锁( 弱活) 的，当且仅当v m er ( mm o ) ，3 t t ：m d 成立； 4 )似m o ) 是活的，当且仅当v t t ：t 在标识下是活的； 【定义2 1 2 1 令= ( 只z 只聊是一个网系统， 1 ) 以尸为序标的列向量v ：尸斗z 称为的p - 向量，z 是整数的集合。 2 ) 以丁为序标的列向量w ：n z 称为的互向量。 【定义2 1 3 1 令，和，分别为网= ( 尸，l 只叨的尸向量和r 向量， 1 ) 称p 向量i 是一个尸不变式，当且仅当0 且r , c = 0 7 。i 旧| - 妇尸l 地) o ) 称为 ，的支撑。 2 ) 称丁向量，是一个r 不变式，当且仅当j 0 且c o j = o 。i i d l l = t e t i d ( t ) 0 称为j 的支撑。 3 ) 称一个p 不变式( t 不变式) 是极小的，当且仅当它的支撑中不包含任何其它 尸- 不变式( t 不变式) 的支撑。 4 ) 称是被p 不变式及丁不变式力覆盖的，当且仅当v p e p ：i ( p ) 0 ( v t e t ：j ( d o ) 。 本文中的p 不变式，如果没有特别声明，则都是极小p 不变式。 【性质2 1 】网系统( m o ) ，是= ( p ，z 只聊的一个p 不变式，v m e r ( n , ) ： 亡m = 亡m o o 【性质2 2 1 网系统( m o ) ，j 是_ ( p ，瓦只聊的一个f 不变式，0 9 l i 中所有 的变迁发射一次，可能会使网系统回到初始标识。 第二章p e t r i 网基本理论及建模 7 2 1 3 信标和陷阱的定义和性质 1 ) 2 ) 3 ) 4 ) 5 ) 【定义2 1 4 1 m o ) 是一个网系统，- 正只叨， 称一个非空集合诞，是一个信标( s i p h o n ) ，当且仅当。延r 成立； 称一个非空集合s _ c p 是一个陷阱( t r a p ) ，当且仅当鼬，成立： 称一个信标( 陷阱) 是极小的，当且仅当不存在其它信标( 陷阱) 是它的真子集； 称p e p 是被标识m 标记的，当且仅当朋) o 。称一个集合s 堂是被标识m 标记的，当且仅当s 中至少有一个元素被m 标记。s 中的托肯数m 研= 岛m 弛) ； 不包含任何只不变式支撑的信标称为严格信标，一个严格信标有可能被清空； 一个既是极小又是严格的信标，称为严格极小信标( s m s ) 。 【性质2 3 】网系统m o ) ，_ ( p ，正e 叨，s _ c _ p 是一个信标，若3 m r ( n , ) ： 心研= o ，则s 以后永远不会被标记，称为被清空。 【性质2 4 】网系统( m o ) ，- 以正只叨，s _ _ c p 是一个陷阱，若j m r ( ，m o ) ， m 研 0 ，则s 以后总是被标记。 【性质2 5 】网- ( p ，ze 聊的p 不变式，的支撑8 川既是信标又是陷阱。 【性质2 6 1 m o ) 是一个网系统，其中胆( p ，正e 功，? 是一个p - 不变式， 诞? 是的一个信标，那么此信标s 是在下被p 不变式，控制的，当且仅当， 0 且对于所有的p 朋，坳) 郢成立，或等同地，l r m o 0 且仞尸i 坳) o ) 酉。如 果s 是一个在m o 下被尸不变式，控制的信标，则s 不可能被清空，也就是说， v m e r ( n , m o ) ：s 在标识m o 下是被标记的。 【性质2 7 】( mg o ) 是一个普通网系统，胙妒，正d ，若在m 下是死锁的， 则所有未被标记的库所形成一个信标。 【性质2 8 】( ，m o ) 是一个普通网系统，- ( p ，正曰，如果网中没有信标可 能被清空，则称( g o ) 是无死锁的( d e a d l o c k f r e e ) 。 2 2 p e t r i 网实例分析 以图2 1 为例说明p e t r i 网的有关概念和性质。 柔性制造系统中基于p e t r i 网的死锁预防策略 p ， 图2 1 一个p e t r i 网实例 p 1 5 图2 1 中的p e t r i 网_ 俨，t ，f ，叨，其中尸= 仞l ，p 2 ，p 3 ，肌，p 5 ，邸，刃，内，7 9 ，p l o ， p l l ，p 1 2 ，p 1 3 ，p 1 4 ，p 1 5 ) ，仁拍，龟，t 3 ，t 4 ，t 5 ，t 6 ，t 7 ，t 8 ，t 9 ，h o ，t 1 1 ) 。坼f ，呦= 1 ，所以它是 一个普通网，记做= ( p ，l 用。 网有7 个极小p - 不变式，它们的支撑分别是：l m i j = p 2 ，p 1 4 ；i i 2 i i = p 6 ，p 7 ) ； i i 厶l i - p l ，p 2 ，p 3 ，p 4 ，p 5 ，p 6 ；i 4 i i = p 5 ，p 8 ，p 1 3 ；l 晒i i = p 4 ，p 9 ，p 1 2 ；i 峨l l = p 3 ，p l o ，p l l ； i i 厶i i - p 8 ，p 9 ，p l o ，p 1 5 ) 。 网中有3 个严格极小信标：s l = p 5 ，p 9 ，p 1 2 ，p 1 3 ，s 2 肌，p l o ，p l l ，p i 2 ) ，s 3 p 5 ， p l o ，p l l ，p 1 2 ，p 1 3 ) 。以s l 为例，。s l = 坼$ i * p = * p 5 k - ) * p 9 k - ) * p 2 k ) * p 1 3 = t 4 k _ ) t 9 w t 4 ，t l o u t 5 ， 幻) = t 4 ，t 5 ，t 9 ，t l o ，s l 。= 乙_ s i p 。= p 5 。u p 9 。乙p 1 2 。l ) p 1 3 。= t 3 ，t 4 ，t 5 ，t s ，t 9 ，h o ) ，所以。s l c s l 。，故蜀是一个信标，而且它不包含任何p - 不变式的支撑，也不包含任何其它 信标，所以是一个严格极小信标。同样和岛也是严格极小信标。网的初始标识 m o = 3 ，0 ，0 ，0 ，0 ，0 ，1 ，0 ，0 ，0 ，2 ，1 ，2 ，1 ，3 】。网的关联矩阵 朋为： 第二章p e t r i 网基本理论及建模 9 p 1 p2 p 3 p4 p5 p6 p1 】= p8 p9 p 10 p i1 p l2 p 13 p i4 p i5 f lt 2t 3 1 oo 11o o 11 o ，ol ooo ooo ooo ooo oo o ooo o11 o o1 ooo 11o ooo 幻如 o 1 oo oo 1o 11 oo oo oo 0o oo oo 1 o 11 oo oo 2 3p e t r i 网模型的建立 t 9t 1 0t t l o0o ooo ooo ooo ooo ooo ooo 1oo 11o o11 o11 11o l oo ooo oo1 2 3 1p e t r i 网建模删 用p e t r i 网描述、建模的系统有一个共同的特征：系统的动态行为表现为资源 ( 物质资源和信息资源) 的流动。下面我们列举两个应用实例。 实例一，如图2 2 ，2 3 用一个常见的化学反应式2 h 2 + 0 2 = 2 h 2 0 演示了p e t r i 网 的基本运行规则，图2 2 表示在该时刻有两个h 2 和两个0 2 ，图2 2 表示t 发射后的 系统状态。对比2 2 ，2 3 可知两个h 2 和两个0 2 合成两个水分子h 2 0 。 h ， 图2 2 发射前 8 ，o o o o o o o 1 o o o o o o o 幻1 o o o o 1 l o 0 0 o 0 o o o _ 坫o 1 o o o 1 l 0 o o o o o 1 o i - 1 0 柔性制造系统中基于p e t r i 网的死锁预防策略 h 2 图2 3 发射后 实例二，对运动小车的建模 图2 4 中( b ) 是对一个运动小车系统( a ) 的p e t r i 网建模。小车处于导轨之中，开 始向左运动，抵达a 端后，改变运动方向，向右运动直至b 端，到达后再改变方 向向左运动，如此在导轨内来回往复运动。 a a 一个小车运动系统 b 向左运动 到达a 端 向右运动 到达b 端 b 对应的p e t r i 网模型 图2 4一个小车运动系统及相应p e t r i 网模型 2 3 2 柔性制造系统的p e t r i 网模型 图2 5 用p e t r i 网描述了一个简单的柔性制造系统，该系统包含两个进程，分 别为p l - p 2 - p 3 - p 4 ，p l i - p l o p 9 p 8 ，三个加工工具p 5 ，p 6 ，p 7 ，每次可以加工一个工件。以 p e t r i 网作为模型来描述柔性制造系统，可以直观的分析系统的结构与行为，是对 f m s 进行设计，建模，仿真及性能分析的有力工具。本文中的工作就是以f m s 的 p e t r i 网模型为对象展开研究的。 第二章p e t r i 网基本理论及建模 图2 5 一个柔性制造系统的p e t r i 网模型 2 4 本章小结 本章主要叙述了p e t r i 的基本定义及性质，为本文后面章节网系统活性判断， 死锁预防算法的提出提供了理论基础。另外，本章还介绍了p e t r i 网模型的建立， 为本文后面柔性制造系统p e r t i 网模型的建立做了基础准备。 第三章s 3 p r 网定义及网模型 1 3 第三章s 3 p r 网定义及网模型 s 3 p r 是e z p e l e t a 等人【7 】中提出p e t r i 网的子类，它可以为一大类f m s 建模， 代表性很强。基本信标【8 】是一种特殊的严格极小信标( s m s ) ，对于一个p e t r i 网，当 其全部基本信标不被清空时，其所有的s m s 有可能不被清空。一个p e t f i 网的基本 信标的数量比其s m s 的数量要少得多，尤其当p e t r i 网规模大而复杂时这一点变得 更加显著。因此能否通过控制s m s 中的一少部分而不是全部就可获得一个无死锁 的或者活的p e t r i 网，对死锁预防来说，显得特别重要。 本章有三部分，第一节介绍了s 3 p r 网的基本概念；第二节介绍了s 3 p r 对制 造系统的建模过程。第三节对本章进行了概括总结。 3 1s 3 p r 简介及基本概念 f m s 一般是由多个加工设备和物料运送系统组成。由于在一个系统中完成多 种产品的加工，因此在f m s 中存在多个生产进程。零件按不同的生产要求进入不 同的生产进程。这些进程相互独立，在生产过程中对系统资源的需求使这些进程 相互联系，使系统成为一个有机的整体。然而由于系统中的资源有限，如机床， 机器人等在f m s 中都是共享设备，而且由于系统中进程的并发性，如果不能合理 的安排资源使用顺序就有可能导致系统死锁。一旦系统发生死锁，生产将陷入停 顿。 如果用p e t r i 网来模拟加工进程，可以利用上一章中对p e t r i 网库所的划分用三 种库所分别对柔性制造系统中不同元素建模。其中操作库所表示加工进程中的工 序，资源库所表示系统中的资源，资源库所中的t o k e n 数表示可供使用该资源的个 数或加工能力，闲置库所表示系统中的原料托盘等。用变迁表示工序状态之间的 转换。 由文献提出的s a p r 是p e t r i 网的子类，它可以为一大类f m s 建模，具有相当 的代表性。 【定义3 1 】【7 】一个简单加工进程( 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 网 - 俨u 伽o ) ，ld ，是的初始标识，p o 称为闲置库所( 1 j n y - 进程的开始和结束工 序状态) ，p e p 称为工序状态库所。( ，m o ) 满足以下条件：( 1 ) 辟巾，p o 甚p ，m o ( p o ) - l ， v p 尸，p ) = o ；( 2 ) n 是一个强连通的状态机，艮1 v t et , i t l = l t o l = l ；( 3 ) n 的每一个 回路包含珈。 【定义3 2 】设_ 瓦刀是一个网，设x c _ p u t ，那么n x = ( p x , t x , f x ) 是x 生成的子网，其中尉= p n 只砑= 刀泷麟可1 n 。 【定义3 3 】【7 】- 个拥有资源的简单加工进程( s 2 pw i t hr e s o u r c e s ) s 2 p r 是一个 1 4 柔性制造系统中基- fp e t r i 网的死锁预防策略 网- ( p o w p r ，正d ，是的初始标识。( m o ) 满足以下条件：( 1 ) 令p o = to ) ， 由净rj p o w t 生成的子网n x = ( p x , t x , f x ) 是一个s 2 p ，其中p x = t u p o ) ，研= 乃 f x = f n ( p x x t x ) ( 2 ) r e p r 称为资源，p r 是资源的集合，p r * 0 ，( p u 伽) ) 飧= 巾； ( 3 ) v p e p ，v t e e p ，v t e p o ，3 r p e p r , t c t p r = t * n p r = r p ；( 4 ) v r e p r ，m o ( r ) l ，v r e p r ， m p = 厂r 、胯巾；v r ep r ，r n r = 巾；( 5 ) p o ) 厂、p r _ 锄) n p r - 巾；( 6 ) 对于一个给 定的r e p r ，h ( r ) = ( r ) n 尸称为资源r 的持有者集合。对于一个资源集合r = r l ，r 2 ， r m ，用u h ( 0 l r e r 或u r m - i ( r ) 表示h ( r 1 ) u h ( r 2 ) u u h ( r m ) 。 【定义3 4 】【7 】一个拥有资源的简单加工进程系统( s y s t 锄o fs 2 p r ) ，s 3 p r 是 k ( k i n 0 ) ) 个s 2 p r 通过共享资源复合而成的p e t r i 网，n = o i = l k n i = ( p u p 0 u p r ，瓦 d 。记n k = 1 ，2 ，k ) 。s 3 p r 网系统( ，m o ) 满足以下条件：( 1 ) 一个s 2 p r 也是一 个特殊的s 3 p r ；( 2 ) v i e n k ，v je n k i ) ，( p i u p o i ) n ( p j u p o j ) = o ，且存在 p r i c 、i p r j = p c i j q b ，死n 巧= 巾；( 3 ) p = u i - l k p i ，p o - - l ) i = i k p o i ，p r = u i - l 胍i ；i _ 1 k 死， f - - - u i = 1 k f i ；( 4 ) v i e n k ，跏p u p o i ，m o ( p ) = m o i ( p ) ，v i e n k ，v r e p r i p c i j ， m o ( r ) = m o i ( r ) ，v r e p c i j ，m o ( r ) - - m a x m o l ( r ) ，m o k ( o , ( 5 ) 符号n i 表示组成第i 个 s 2 p r 网n i 的s 2 p 。 【定义3 5 】设一个s 3 p r 网系统( ，m o ) ，其中- ( m o u p r ，瓦刃，s 是网 的一个信标。s r 表示信标s 中的资源，s r = s n p r ；s p 表示信标s 中的工序状态库 所，s p = - s c - x p 。明显地，辟s r t ) s p 。 【定义3 6 】设_ ( 啪u 豫，瓦乃是一个s 3 p r ，s 是网的一个严格信标， 即s 不包含任何p 不变式的支撑。那么i s c 、尸r i ，也就是说，s 中至少包含两个资 源。详细证明见【7 j 3 2s 3 p r 对f m s 建模实例 经过以上介绍我们对s 3 p r 网有了初步的了解，下面举例说明用s 3 p r 网对制 造系统的建模过程。 图3 1 制造系统实例 第三章s 3 p r 网定义及网模型 1 5 上面图中是一个简单的制造系统。系统中有三个机械手r l 水2 皿3 和两台机床 m i ，m z 。该系统包括三个进程尸l ：零件从备料台 进入，由r l 运送到尬加工完 成后由尺2 运送到卸料台d l ；尸2 ：零件从备料台尼进入，由恐运送到m z 加工完成 后由尺l 运送到卸料台0 2 ；1 3 ：零件从备料台厶进入，由尺3 运送到m 2 加工完成后 由月3 运送到卸料台仍；其中尺l 负责与 ，尬，m 2 ，0 2 相关的物流操作；r 2 负责与 d l ，尬，1 2 ，m 2 相关的物流操作。而尺3 负责0 3 ，m 2 ，1 3 的操作。其中机械手每次只能 装卸一个零件，机床每次加工一个零件。 我们利用进程角来说明建模的具体方法。 首先将进程局分解为3 个部分：第一步零件从备料台 进入，由足l 运送到 m l ；第二步m l 对零件进行加工；第三步尺2 将零件由尬运送到卸料台d l 。整个 尸l 过程可以表示如下图所示。 图3 2 进程1 的网模型 其中p 2 ，p 3 ，肌代表进程的三个阶段，pj l ，p 1 2 ，p 1 3 分别表示m ，r l 和飓的可用 状态，变迁t 表示零件所处状态的转变。资源库所中的初始t o k e n 数为1 表示车床 与机械手只能同时处理一个零件，初始状态下操作库所中没有t o k e n 表示开始时系 统中没有零件加工。而为了保证系统的最大生产能力，空闲库所中的t o k e n 数设定 为进程中操作库所数。 同样的方法可以得到另外两个进程的模型。 1 6 柔性制造系统中基于p e t r i 网的死锁预防策略 图3 3 进程2 的模型 1 6 图3 4 进程3 的模型 此时将三个进程按资源的共用关系连接起来，就构成了整个制造系统的网模 型。柔性制造系统的各个环节都在网模型中得到了体现。 图3 5 对f m s 建模得到的网系统 由上面的例子可以看出，利用s 3 p r 网对柔性制造系统建模可以很方便的得到 网模型。 3 3本章小结 本章主要介绍了s 3 p r 网的基本概念，通过一个简单的实例介绍了s 3 p r 对f m s 的建模过程。 第四章基本信标理