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

摘要 本文主要研究柔性制造系统中的死锁问题，基于p e t r i 网中的一种子类s 4 r 网 给出了一种改进的死锁预防算法。p e t r i 网中，信标作为一种结构体，在网的分析 和死锁控制中起着相当重要的作用。然而，要计算所有的信标是很耗时的，甚至 是不可能的，特别是当网的规模非常大时。s 4 r 网可以建模复杂的、拥有多个并行 加工进程的资源分配系统，而且不同的工序可以申请不同类型的多个资源。在s 4 r 网中，死锁的产生归因于存在空的或未被充分标记的信标。目前的死锁预防控制 策略大都通过添加控制库所使这些空的或未被充分标记的信标最大可控，然而却 往往限制了网系统的许可行为，从而降低了系统的性能。 文中改进的死锁预防算法采用迭代的控制方法并不需要求解所有的严格极小 信标。在每一次迭代时通过求解整数非线性规划问题来计算出一个 n o n - m a x - m a r k e d 的信标，然后对该信标添加控制库所以保证其是m a x - c o n t r o l l e d ， 一直迭代直到不存在n o n m a x m a r k e d 的信标，最后所有的信标都是 m a x - c o n t r o l l e d 。该策略保证添加控制器后的网系统是活的并且具有更多的许可行 为。文中最后以具体的柔性制造系统实例验证了改进的死锁预防算法。 关键词：柔性制造系统p e t r i 网死锁信标 a b s t r a c t t t l i sm e s i sf o c u s e so nt h ep r o b l e mo fd 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 gs y s t e m s ( f m s ) b a s e do ns y s t e mo fs e q u e n t i a ls y s t e m sw i t hs h a r e dr e s o u r c e s ( s 4 r ) ，ac l a s so f p e t r in e t s a ni m p r o v e dd e a d l o c kp r e v e n t i o na l g o r i t h mi s p r o p o s e d a sas t r u c t u r a l o b i e c to fap e t r in e t ，s i p h o n sa r ev e r yi m p o r t a n ti na n a l y s i sa n d c o n t r o lo fd e a d l o c k si n p e t r in e t s h o w e v e r , i ti sq u i t et i m e c o n s u m i n go re v e ni m p o s s i b l e t oe n u m e r a t ea l l s i p h o n so fan e t ，e s p e c i a l l y , w h e nt h en e ti sv e r yl a r g e s 4 rc a nm o d e lc o m p l i c a t e d r e s o u r ea l l o c m i o ns y s t e m sw i t hm u l t i p l ec o n c u r r e n tp r o c e s s e s ，a n dd i f f e r e n tt y p e s0 l m u l t i p l er e s o u r c e sc a nb er e q u e s t e db yd i f f e r e n tp r o c e s s e s t h ee x i s t e n c eo fe m p t y s i p h o n so ri n s u f f i c i e n t l ym a r k e do n e si st h er e a s o nf o rd e a d l o c k si ns 4 r s o f a r ，m o s to f t h ed e a d l o c kp r e v e n t i o np o l i c i e sa r ea c h i e v e db ya d d i n g m o n i t o r sb a s e do nt h e m a x c o n t 】_ o l l a b i l 时o fs i p h o n st oe m p t ys i p h o n so ri n s u f f i c i e n t l ym a r k e do n e s h o w e v e r ， t h e s ea p p r o a c h e sa l w a y sl i m i tt h ep e r m i s s i v eb e h a v i o ro f n e ts y s t e m s t h u s ，t h es y s t e m p e r f o r m a n c ei sd e g r a d e d t h ei m p r o v e da l g o r i t h mp r o p o s e di nt h i st h e s i si sa ni t e r a t i v ea p p r o a c h ，i td o e sn o t n e e dt oc o m p u t ea l l s t r i c tm i n i m a ls i p h o n s ( s m s ) o fan e t a te a c hi t e r a t i o n ，a n o n m a x - m a r k e ds i p h o ni sc o m p u t e db ys o l v i n ga ni n t e g e rn o n 。l i n e a rp r o g r a m m i n g p r o b l e m t h e n ，am o n i t o rn e e d st ob ea d d e d t ot h es i p h o nt og u a r a n t e et h a tt h es i p h o ni s m a x ，c o n t r o l l e d t h ea l g o r i t h mt e r m i n a t e sw h e n t h e r ei sn on o n - m a x - m a r k e ds i p h o nm t 量l en e t a sar e s u l t ，a l lt h es i p h o n si nt h en e ta r em a x c o n t r o l l e d t h e nt h en e ti sl i v e a n di th 弱m o r ep e r m i s s i v eb e h a v i o r s e v e r a le x a m p l e so ff m s a r eu s e dt oi l l u s t r a t ei t k e y w o r d ：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 ) p e t r i n e td e a d l o c ks i p h o n 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名： 导师签名： 日期丝z21 圣：f 兰 日期坦竺主。生厂 第一章绪论 第一章绪论 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 定义为由计算机，数控机床和一个物料传输系统构成、能够高效地生 产中小批量产品的计算机控制系统1 3 j 。 图1 1 所示【2 】【3 j 的是一个典型f m s 的构成。硬件设备包括四台计算机数控加工中 心和一个用于在加工设备之间传输工件的自动引导小车( a g v - a u t o m a t e dg u i d e d v e h i c l e ) 。中心计算机通过局域网和各个单元控制器进行通信与协调。单元控制器 负责控制可编程序控制器( p c p r o g r a m m a b l ec o n t r o l l e r ) 或者个人计算机，每一台p c 机用于一个物理资源( 设备) 的控制。由于f m s 的控制系统一般很复杂，实际中往往 采用这种分层递阶的控制模式。数据库管理系统( d b m s d a t a b a s em a n a g e m e n t s y s t e m s ) 用于建立、使用和维护系统中的各种数据库，并对数据库进行统一的管理 和控制，以保证数据库的安全性和完整性。 在f m s 中，不同类型的原料在离散的时间点进入系统进行加工，它们共享诸 如机床、机器人、夹具等有限的资源。每种原料按照特定的生产流程来使用系统 中的资源。由于所有的生产流程并发执行，这样可能会引起对共享资源的竞争， 资源竞争便可能使系统处于死锁状态。死锁，简单地说，就是系统中的些加工 进程总是不可能完成的。在有些情况下，死锁造成整个或部分系统的停顿并不是 2 基于p e t r i 网的柔性制造系统死锁预防研究 单纯地降低生产率，而是可能造成重大经济损失甚至灾难性后果3 1 。为此，本文致 力于f m s 中死锁问题的研究。 图1 1 典型f m s 的构成 对死锁问题的系统研究，始于二十世纪下半叶，源于计算机操作系统中的资 源分配问题。上世纪八十年代以后，制造系统完成了从大批量、品种单一的生产 模式向以小批量、多品种以及具备适应市场快速变化能力为目标的现代自动f m s 的转变，自动制造系统中的死锁问题的研究也受到了广泛重视和关注。一般认为， 死锁产生的主要原因是：( 1 ) 系统资源不足；( 2 ) 进程允许推进的顺序不当；( 3 ) 资 源分配不当。c o f f m a n 等人给出了系统死锁的四个必要( 但非充分) 条件1 4 j ： 1 ) 相互抑s m j ( m u m a le x c l u s i o n ) ：一个资源每次只能被一个进程使用； 2 ) 持有并等待( h o l da n dw a i t ) ：持有资源的进程允许申请其它资源： 3 ) 非剥夺条件( n op r e e m p t i o n ) ：除非资源被释放，否则一个资源不允许被强 行剥夺； 4 ) 循环等待( c i r c u l a rw a i t ) ：若干进程形成了一个进程链，该进程链中的每一 个成员等待着它的下一个进程持有的资源。 上述前三个条件实际上是由系统和资源的物理特性决定的。也就是说，对于 第一章绪论 3 一个给定资源集合的系统，这三个条件要么成立要么不成立，它们不会随着时间 变化的。而第四个条件却可因对资源的请求、分配和释放随时间而变化。只要发 生死锁，这四个条件必然满足。反之，只要有一个条件不满足，系统就不会发生 死锁。 处理死锁的方法一般分为四种【3 l ：第一种是忽略死锁发生的可能性，即所谓的 鸵鸟算法( o s t r i c ha l g o r i t h m ) 。如果死锁发生的可能性非常小或者即使发生死锁，也 不会有严重的后果，而避免发生死锁的代价又很昂贵，这种情况下就可以忽略死 锁问题。第二种方法称为死锁的检测与恢复( d e a d l o c kd e t e c t i o na n dr e c o v e r y ) 。这种 方法允许死锁的发生，并不断检测死锁是否已经发生。一旦检测到死锁便采取相 应的措施，并以最小的代价恢复系统的运行。第三种方法死锁避免( d e a d l o c k a v o i d a n c e ) 是在系统的运行过程中，对进程发出的每一个系统能够满足的资源申请 进行动态检测，并根据检测结果决定是否分配资源。若分配后系统可能发生死锁， 则不予分配，否则予以分配。第四种方法死锁预防( d e a d l o c kp r e v e n t i o n ) 是使以上发 生死锁的四个必要条件之一不成立。破坏相互抑制的思想是使用假脱机代替相互 抑制，对于大多数资源来说这种方式并不可能。破坏持有并等待条件的做法是要 求每一个进程在开始运行时就请求其所需的所有资源，但这种做法过于保守。破 坏非剥夺性条件在一般情况下并不可行。破坏循环等待条件是通过离线地建立一 种相对固定的资源使用序列，并要求这些资源按照该序列被申请使用。死锁预防 策略是一种解决死锁比较有效也是应用较广的方法，本文采用这种方法来研究处 理f m s 中的死锁问题。 当今国际上研究死锁问题的主要数学方法有图论、形式语言和自动机理论以 及p e t r i 网。本文基于p e t r i 网理论来研究f m s 中的死锁问题。 p e t r i 网1 5 】【6 】是由德国科学家c a r la d a mp e t r i 于1 9 6 2 年在他的博士论文 “k o m m u n i k a t i o nm i ta u t o m a t e n ( 用自动机通信) 中首次提出的，用来描述计算机 系统事件之间的因果关系。它是一种适用于多种系统的图形化、数学化的建模工 具，为描述和研究具有并行、异步、分布式和随机性等特征的信息加工系统提供 了强有力的手段。与传统的系统建模、分析和控制方法相比，p e t r i 网作为一种图形 化和数学化的建模工具，能够提供一个集成的建模、分析和控制环境，为系统的 设计提供便利。早期p e t r i 网主要应用于计算机与信息处理领域，后来具有工程背景 的研究人员将p e t r i 网用在工程系统尤其是自动制造系统的研究。基于p e t r i 网理论处 理f m s 中的死锁的方法大致可分为四种，即忽略死锁、死锁检测与恢复、死锁避 免和死锁预防。在高度自动化的系统中，任由死锁发生是不可取的。死锁的检测 与恢复实际上是一种被动的方法。基于p e t r i 网的柔性制造系统死锁避免方法的基本 思想是，在系统的每一个状态( 标识) 下，使用一种在线的控制策略控制变迁的发射。 这种方法的目的是使得系统在众多可行的进化方案中选择一种系统不会陷入死锁 4 基丁p e t r i 网的柔性制造系统死锁预防研究 状态的方案。然而，这种处理方法需要在线决策，同时过于进取的策略往往不能 完全避免死锁，过于保守的策略会严重限制系统的许可行为。基于p e t r i 网理论的死 锁预防是一种静态方法，它使用一种离线计算的机制控制资源的请求，保证系统 不会发生死锁。一旦这种无死锁的控制机制建立起来，系统在这种机制下运行就 永远不会进入死锁状态。本文采用基于p e t r i 网理论的死锁预防策略来处理f m s 中的 死锁。 迄今所出现的死锁预防策略大都采用在目标p e t r i 网模型中添加新的控制库所 的方法【7 】【8 】，通过添加控制库所限制网系统的行为，从而保证网系统是无死锁的。 通常求取控制库所的分析方法可以归结为两种：基于网结构的死锁预防分析方法 1 8 1 1 ”f l o 1 1 1 1 】【1 2 】【1 3 j 和基于可达图的死锁预防分析方法1 1 4 】【1 5 】。基于可达图的死锁预防分 析方法中的代表是区域理论的应用。它通过添加控制库所限制一些变迁的发射使 危险状态和死锁状态分离，可以获得最佳的或最大许可行为的p e t r i 网控制器。利 用区域理论对网系统设计控制器的优点在于可以使系统获得最大许可行为，缺点 在于随着网规模的扩大，可达标识增多，会产生状态爆炸，从而造成求解的线性 规划问题规模增大，计算复杂度也急速增长。m u z a m 对区域法在p e t r i 网中的应 用进行了适当的改进【i 副，在对网模型利用区域法进行分析之前对网模型进行化简， 之后对化简后的网模型利用常规的区域理论进行求解，得到一个控制器，该控制 器对原网来说是具有最大许可的控制器。该方法在一定程度上简化了区域法应用 的计算复杂度，但对于整个区域法理论的应用来说仍然存在计算复杂度过大的问 题。 基于网结构的死锁预防分析方法主要是通过计算、分析目标p e t r i 网模型的极小 信标，为严格极小信标( s m s s t r i c tm i n i m a ls i p h o n ) 添加控制库所来保证待控网系统 是无死锁的。e z p e l e t a 等) k r 7 1 利用p e t r i 网结构理论为f m s 设计了控制器，最终得到 了无死锁的网系统。他们定义了一类普通保守网的子类s 3 p r ，即拥有资源的 简单加工进程系统。针对s 3 p r 网，通过为每个s m s 添加一个控制库所来限制网系 统的某些行为从而保证网系统的活性。该方法简单且有效，然而，网系统中s m s 的数目会随网系统规模的增大而激增，因此需要给网系统添加大量的控制库所和 连接弧，使得p e t r i 网控制器比原先建立的p e t r i 网模型复杂很多，许可行为也会受到 很大的限制。基本信标理论【l6 1 的出现使控制器设计更为简便，它将网中的严格极 小信标分为基本信标和从属信标两大类。只需保证p e t r i 网中所有的基本信标不被清 空，并满足一定的控制条件时，其从属信标也不会被清空，进而网中所有的s m s 都不会被清空。采用迭代的控制方法【1 7 1 1 1 8 1 虽然可以获得更多的行为特性，但是此 方法不适合复杂或大规模的网系统。这是因为网系统中信标的个数是随网规模成 指数递增的，每进行一次迭代，网系统中都会产生许多的信标，相应的就需要添 加许多的控制库所，最后使得迭代无法进行下去。本文的控制方法虽然采用的是 第一章绪论 迭代的控制方法，但是在每次迭代时添加控制库所后不会产生新的信标。由于求 解所有严格极小信标的固有复杂性，c h u 和x i e 提出了求解信标的混合整数规划 ( m i p m i x e di n t e g e rp r o g r a m m i n g ) 方法【1 9 j 。这种方法的思想是传统信标求解的数学 规划实现。对于一个给定的网系统，求解其最大空信标的算法是首先从网中移去 那些被标记的库所，然后移去那些没有输入库所的变迁和这些变迁的输出库所。 重复以上两步直到没有可再移去的库所和变迁。c h u 和x i e 用m i p 实现了这种算法。 当一个p e t r i 网中存在空信标时，m i p 的可行解对应于一个最大的空信标，否则m i p 的最优解等于网中库所的个数。尽管m i p 问题的求解在理论上是n p h a r d l 2 ，但数 值实验表明该方法比传统的遍历信标和状态的方法在计算上更为有效。由于死锁 控制往往关心的是极小信标，这就需要由最大空信标导出极小信标瞄j 1 2 。鉴于此， c h a o 提出了一种修改的m i p 方法【2 2 1 ，这种方法可以直接求出可被清空的极小信标， 但这种方法不适用于一般p e t r i 网。 p i r o d d i 等人【2 3 】从信标和死锁标识之间的关系出发，通过深入研究有选择地控 制可能引起死锁的信标，进而抑制所有死锁标识的可达性以达到行为优化或者次 优化的控制效果。该死锁预防策略采用迭代的控制方法，每一次迭代需要枚举所 有的极小信标、生成所有的支配标识和求解一个集合覆盖问题，所有以上三项任 务在最坏的情况下都是指数复杂性的，从而整个问题是指数复杂性的。而且在迭 代的过程中可能会产生权值大于一的弧，因此迭代过程中会产生一般网。当网转 化为一般网时，该策略中采用的是将一般网转化为p t - 普通网，对得到的p 正普通 网完成信标的迭代控制，最后通过逆变换还原成为一般网。这种变换意味着网的 规模会暂时扩大，进而降低了计算效率。对于一般p e t r i 网，死锁的产生归因于存 在空的或未被充分标记的信标，目前的控制方法大都使这些信标最大可控，但往 往限制了使网系统具有更多许可行为的性能。为此，本文针对一般p e t r i 网的子类 s 4 r 网进行深入研究以达到使网系统具有更多的许可行为，文中同样采用的是迭代 的控制方法，每一步迭代时并不需要求出所有的严格极小信标，而是通过求解数 学规划问题来导出一个n o n m a x m a r k e d 的信标，然后对该信标添加控制库所并保 证其是m a x c o n t r o l l e d ，这样一直迭代直到不存在n o n m a x m a r k e d 的信标，最后 得到活性的网系统，同时这种控制方法在添加控制库所后不会引人新的信标而且 具有更多的许行为和结构上相对简单的控制器。 综上所述，f m s 中的死锁问题是一个需要急待解决的问题，对它的研究具有 重要的意义。基于p e t r i 网来研究f m s 的死锁，虽然已经取得了丰硕的研究成果，但 许多控制策略并不完善，还需进一步深入研究并改进。因此，寻求一种更为有效 的控制方法对解决f m s 的死锁具有重要意义。 6 基于p e t r i 网的柔性制造系统死锁预防研究 1 2 本文完成的主要工作 本文基于p e t r i 网理论对f m s 中的死锁问题进行了深入研究，阐述了f m s 的 死锁问题，系统地介绍了p e t r i 网的一些基本理论、建模以及两个特殊子类w s 3 p r 网和s 4 r 网的概念、性质。本文工作主要包含以下几个方面的内容： 1 ) 论文着重介绍了文献【2 4 】的死锁预防策略，对其中的算法通过具体的f m s 的p e t r i 网模型实例进行了重复验证和分析研究了其中的不足之处。由于该 算法在每一步迭代时都要用到数学规划软件l i n g o t 2 5 1 来计算一次整数线性 规划问题以求出一个非最大标记的信标，而这个整数非线性规划问题约束 条件很多导致输入很耗时，为此编写程序实现了生成求解整数线性规划问 题的l i n g o 输入文件。 2 ) 给出了一种通过求解整数非线性规划问题来导出n o n m a x m a r k e d 信标的 方法，并对该整数非线性规划问题的正确性给予了验证说明；给出了求解 控制深度变量的方法使得所要添加控制库所的信标是m a x 一c o n t r o l l e d ，并 对其正确性进行了证明。 3 ) 针对文献 2 4 】的死锁预防算法的不足之处给出了一种改进的死锁预防算 法，对算法的收敛性和对添加控制库所后的网系统的活性给予了证明；该 算法达到了使网系统具有更多的许可行为并且得到的控制器在结构上相对 的简单。 4 ) 将该改进的算法应用到具体的f m s 实例中，验证了它的收敛性和得到的网 系统的活性。通过与以前的死锁预防算法相比较说明了改进的算法能达到 预期的控制效果。最后，分析了该算法所存在的一些不足之处。 总之，论文主要研究了f m s 中的死锁问题并基于p e t r i 网给出了一种改进的死 锁预防算法。限于时间、条件和个人的认识，文中很多方面可能会有所欠缺，恳 请批评指正。 第二章p e t r i 网的基本理论及分析技术 7 第二章p e t r i 网的基本理论及分析技术 本章【3 】【5 】【6 】【2 6 】【2 7 】将介绍p e t r i 网的一些基本概念、性质以及基于p e t r i 网的系统 模型分析技术，为后续章节的命题、定理等打下基础。 2 1p e t r i 网的基本理论 2 1 1p e t r i 网的基本定义 【定义2 1 】一个p e t r i 网( 结构) 是一个四元组妒，l 只叻，p 和玢别称为库所 ( p l a c e ) 和变迁( t r a n s i t i o n ) 的集合，p 和列e 空、有限且不相交。也就是说p 历，再叨， 尸n 辟历。f c ( p x t ) u ( t x p ) 称为流关系或有向弧的集合。渺妒d u ( 歌竹一州 ( 肛 o ，1 ，2 ) ) 是一个映射，该映射为每一条弧分配一个权值，l l p 若：f e f ，w q ) o ； 若f i t f ，职i 乃= 0 。称w 为p e t r i 网的权函数。 在p e t r i 网中，库所和变迁称为p e t r i 网的节点( n o d e ) 。用图形表示p e t r i 网时，库 所用圆圈表示，变迁用矩形或杠表示。库所和变迁之间用有向弧连接，同一类型 的节点之间不能用有向弧连接。 若坼f ，职，) = l ，则称_ 妒，le 叻为普通网( o r d i n a r yn e t ) ，可记作_ ，l d 。若v p ，t ) e f ，t r i p ，0 = 1 ，则称- 俨，le 叨为p 弘普通网( p t - o r d i n a r yn e t ) 。一 个普通网肯定是一个p n 普通网。若3 f = ( p ，t ) e f ，呦 1 ，则称= 俨，瓦e 叨为一 般网( g e n e r a l i z e dn e o 。 【定义2 2 】令= ( p ，le 叻是一个p e t r i 网，的标识是映射肱p 专州，m ( p ) 表示库所p 中的托肯数，托肯用实心圆点或数字表示；给定s _ c e ，则拟$ = d e 妙幼) ： 称( m o ) 为网系统或标识网，其中为网的初始标识。 【定义2 3 】令p e p 是p e t r i 网_ 俨，ze 叻的库所。称p 在标识m 下是被标 记的，当朋p ) 0 。称库所集合埏尸在m 下是被标记的，当d 中至少有一个库所 被标记。称心d ) = 岛o m ( p ) y 可库所子集d 在m 下的托肯数总和。 【定义2 4 】令_ ( p ，le 叻是一个p e t r i 网，节点x e p w t 的前置集定义为 x = y e p u t lf y ，功毋，其后置集定义为x = y e p u t io ，力毋。可将该定义进一 步推广为节点集的前置集( 后置集) ：给定x _ c e u t ，则僻v 膳r x 。= u _ x e x x ) 。 若x 是库所，其前置集中的元素称为其输入变迁，后置集中的元素称为其输出 变迁。若x 是变迁，其前置集中的元素称为其输入库所，后置集中的元素称为其输 出库所。 基于p e t r i 网的柔性制造系统死锁预防研究 【定义2 5 】若= ( 尸，兀只即是普通网，且v t e t ，i t l = l f l = l ，则称是状态机 ( s t a t em a c h i n e ) 。 【定义2 6 】若_ ( p ，ze 叨是普通网，并且有功e p ，l i = 眵i = 1 ，则称是 标识图( m a r k e dg r a p h ) 。 【定义2 7 】若一个p e t r i 网系统( mm o ) 的任意一个节点和其它节点中的任意一 个之间总是存在一条连接路径，则称该网是强连通的。 【定义2 8 】若一个p e t r i 网系统( mm o ) 既是一个状态机又是强连通的，则称其 为强连通的状态机。 【定义2 9 】若1 j o ，力e ( p x t ) u ( t x p ) ：o ，力卧，功f ，则称网_ ( 尸，瓦e 叨 为纯网。 非纯网可以在保持动态性质不变的情况下转化为纯网，本文中讨论的网都是 纯网。 【定义2 1 0 l 令_ 妒，正e 叻是一个纯网。的关联矩阵【m 是一个以p 劝序 标的整数矩阵，【加 ，) = 职，p ) 一w ( p ，0 。库所p 对应的行向量称为p 的关联向量， 记做m p ，) 。变迁，对应的列向量称为，的关联向量，记做 n i ( ，) 。 关联矩阵【m 可以进一步分为两部分 n = p o s t - p r e ，p o s t 称为后置关联矩阵( 也 称输出矩阵或函数) ，肌称为前置关联矩阵( 也称输入矩阵或函数) ，其中觑p ，0 = ，0 ，p o s t ( p ，力= 职，力。假定p e t r i 网有刀个库所和m 个变迁，肌妒，) = ( 脚l ，) ， w ( p 2 ，0 ，w ( 见，d ) 1 ，i n p ，乃2 ( m p ，1 ) ，m p ，f 2 ) ，m p ，f n l ) ) 。 【定义2 1 1 】令n = 妒，冗e 叨是一个p e t r i 网。若跏。，鲋p ) ，0 ，记为 m 0 ，则称，赃标识朋下是使能的( e n a b l e d ) 。使能的变迁可以发射。变迁，发射后， 网系统跃迁到另外一个状态，产生一个新的标识m ，使得即e p ，m 。p ) = 肘p ) 一w ( p ， d + 职，p ) 。在标识时下发射，到达标识m ，记为m t ) m 。若存在一个变迁的发射序 列萨，t 2 t 一和标识肘1 ，m 2 ，m 一，使得m1 t i m 2 t 2 ) m 1 ，n ) m 成立， 则称标识m 。是从可达的。若存在标识臌得 而【回 以则有方程胙 而+ m l 其 中【 7 】为关联矩阵，助发射序列矢量，其第f 个数值代表第，个变迁在序列砷出现 的次数，称该方程为状态方程。从m o 可达的所有标识的集合称为网系统( mm o ) 的 可达集，记为r ( ，g o ) 。 任何一个可达标识都满足状态方程，但满足状态方程的标识并不一定是可达 的。状态方程提供了朋从初始g o 可达的必要条件。也就是说，若肘是从m o 可达的， 必存在一个发射序列。使得胙 而+ 【m y 成立。若状态方程 仁+ mj ，是不可解的， 则蚴然是从m o 不可达的。 【定义2 1 2 1 令n f ( p ，正e 聊是一个网，m o 是的一个标识，( ，m o ) 是可逆 的，当v m e r ( n , m o ) ，了破得m 砷。 【定义2 1 3 1 令( ，m o ) 是一个网系统，- 俨，冗e 叻， 第二章p e t r i 网的基本理论及分析技术 9 1 ) 称变迁t e t 是活的，当v m e r ( n , m o ) ，3m e r ( n , 蚴使得m 。【f ) 成立； 2 ) ( ，m o ) 是死锁的，当jm r ( mm o ) 使得：- - , 3 t e t ：m 【f ) 成立； 3 ) ( ，g o ) 是无死锁( 弱活) 的，当v m e r ( n , m o ) ，3 t e t ：m r ) 成立； 4 ) ( ，m o ) 是活的，当v t e t ，r 是活的。 【定义2 1 4 1 令n f f i ( p ，le 叨是一个网，m o 是的初始标识， 1 ) ( ，m o ) 是有界的，当3 k e h h 0 ，v m e r ( n , m o ) ，v p e p ：拟p ) 敛： 2 ) ( m o ) 是结构有界的，当对于任意有限的初始标识，它都是有界的。 值得说明的是，对于资源有限的实际系统而言，它的p e t r i 网模型一般都是结 构有界的。 2 1 2p e t r i 网的结构特性 【定义2 1 5 1 令一( 尸，瓦e 聊是一个网， 1 ) 以尸为序标的列向量v ：尸专z 称为的只向量，z 是整数的集合。 2 ) 以丁为序标的列向量w ：m 称为的乃向量。 【定义2 1 6 1 令s 留是p e t r i 网= ( 尸，te 叨的库所子集，m 为关联矩阵， p - 向量砧称为s 的特征p 一向量，当跏s ，砧p ) = 1 ，否则砧( 功= o 。= 【m 1 砧称 为s 的特征正向量。 【定义2 1 7 令，和，分别为网= ( 尸，瓦只叨的p 向量和正向量， 1 ) 称p - 向量，是一个只不变式，当0 且，m = o r 。1 1 1 1 1 = p p i i ( p ) 0 ) 称为，的支 撑( s u p p o r t ) ，+ = 妇e p i ( p ) 0 ) 称为，的正支撑( p o s i t i v es u p p o r t ) ， i i l l l 一= 妇e p i i ( p ) 0 ，则vm e r ( n , 蚴，m 。( 固 o 。 上述两条性质说明，一旦信标在某个标识下被清空，该信标在这个标识的所 有后继标识下永远保持为空。一旦陷阱在某个标识下被标记，该陷阱在这个标识 的所有后继标识下永远被标记。显然，若信标包含一个初始标识下含有托肯的陷 阱，那么该信标永远都不会被清空。若信标s 在m 下被清空，那么任何属于f 的 变迁在m 下均不使能，且永远不会使能，即这些变迁是死的。因此，信标和网系 统的死锁密切相关。 【性质2 5 】网= ( 尸，兀e 叨的尸不变式，的支撑i l 川既是信标又是陷阱。 【性质2 6 】( ，m o ) 是一个网系统，其中_ 俨，瓦只叨，i 是一个p - 不变式， s _ c p 是的一个信标，那么此信标s 是在m o 下被p 不变式，控制的，当且仅当 i r m o 0 且对于所有的p 朋，坳) o 且仞e p l i ( p ) o c s 。 第二章p e t r i 网的基本理论及分析技术 如果s 是一个在下被尸不变式，控制的信标，则s 不可能被清空，也就是说， v m r ( n , m o ) ，s 在标识m 下是被标记的。 【性质2 7 】( mm o ) 是一个普通网系统，- ( p ，瓦d ，若在m 下是死锁的， 则所有未被标记的库所形成一个信标。 【性质2 8 】( ，m o ) 是一个普通网系统，_ ( p ，ld ，若网中没有信标可能 被清空，则称( m o ) 是无死锁的( d e a d l o c k - f r e e ) 。 2 1 4 多集 由于p e t r i 网中的标识、p 向量、正向量以及一般网中信标的补集等均以多集的 形式表示，为此本小节对多集的定义给予介绍。 【定义2 2 0 非空集御上的多集q 是映射q ：彳专删 o ) 。多集q 可用形式和 罗q ( 口) a 表示。 多集q 中，非负整数q ( 口) 称为元素口彳的系数，表示元素a 在q 中出现的次数。 若q ( 订) 0 ，则称a c a 属于q ，记为口q 。若q ( 旬= 0 ，则称口4 不属于q ，记为口萑q 。 令q l 和q 2 是定义在集御上的两个多集。多集的基本运算有并、交、加和减的 定义如下： 【定义2 2 1 】( 多集并) q lu q 2 2 。a m a x n i ( 口) ，q 2 ( 口) ) 口 【定义2 2 2 1 ( 多集交) q lr 、q 2 2 口。4 m i n f 2 i ) ，q 2 ( 口) ) 口 【定义2 2 3 1 ( 多集加) q l + q 2 2 州 q l ( 口) + q 2 ( 口) ) 口 【定义2 2 4 ( 多集减) q l q 2 2 。月( q l ( 口) 一( q in q 2 ) ( 口) ) 口 不包含任何元素的多集记为空集a 。若一个多集中任何元素的系数均为1 ，该 多集就是一个集合。 例如，q l = 口帕，q 2 = 2 计6 + c 是定义在集合彳= 口，b ，c ) 上的两个多集。我们有q l u q 2 = 2 口+ 6 + c ，q ln q 2 - 口+ 6 ，q l + q 2 = 3 a + 2 b + c ，q i q 2 2 a 。 2 2p e t r i 网模型的分析技术 上一节对p e t r i 网的一些基本概念、性质做了简要介绍，这一节简要介绍几种 具有代表性的p e t r i 网模型的分析技术： 1 代数分析技术： 代数分析技术主要以关联矩阵的形式对一个网系统的结构给予刻画，然后建 立状态可达的线性系统关系。它的优点是可以借助线性代数的有关结果来简洁地 展现p e t r i 网的一些性质，特别是结构性质。然而，其作用是有限的，难以很好地 刻画系统的动态特性。一般，它对可达性的刻画只是一个必要条件而非充分条件， 1 2 基tp e t r i 网的柔性制造系统死锁预防研究 只有针对无冲突的子类才是充要的。 2 图分析技术： 图分析技术是以一个有限的有向图( 树) 直接展现一个网系统的运行机制， 类似于一个状态机。它的优点体现在其能够反映出一个网系统的动态行为和一些 特征。对于一个有界p e t r i 网，它是一个准确刻画，且其对应一个有限状态机。然 而，对于无界p e t r i 网却只能部分反映。 3 归纳分析技术 归纳分析技术是针对p e t r i 网的状态复杂性而提出来的。一般来说，对于一个 规模不大的网系统，也有可能会出现状态爆炸的危险，从而给系统分析带来困难， 对此人们提出了化简和分解的思想。化简是将一个较复杂的p e t r i 网简化成一个比 较简单的p e t r i 网但保留一些性质不变的同态变换过程，这个过程减少了可达状态， 通过对简单网系统的分析来理解原网的性质；分解的思想就是“分而治之 ，是将 一个复杂的网系统分解成若干较为简单的网系统，分解过程也要保持一些性质不 变。这样，通过对简单的子网系统的分析便可了解复杂网系统的性质。 另外，p e t r i 网理论研究的另一个主流研究方向是建立在通用图论基础之上的 并发行为的特性研究。通用图论是从更为基础、更为抽象的网模型上研究系统的 特性，其中最重要的就是并发性。 2 3实例分析 本节以图2 1 为例说明p e t r i 网的有关概念和性质。 p 1 图2 1 一个p e t r i 网模型 图2 1 中的p e t r i 网_ ( 尸，乃e 叻，其中p = p l ，1 ) 2 ，p 3 ，1 ) 4 ，p 5 ，p 6 ，1 ) 7 ，p s ，p 9 ，p l o ， p lj ，弘 ，i ，t 2 ，t 3 ，t 4 ，t 5 ，t 6 ，t 7 ，t s ) 。驴( t s ，p g ) f ，呦= 3 1 ，所以该网是一个一般网， 第二章p e t r i 网的基本理论及分析技术 1 3 并且可知是一个纯网。 该网中有5 个极小尸不变式：h = p l + p 2 + p 3 + p 4 ，如= p s + p 6 + p 7 + p 8 ，五耽+ v s + p 9 ， 厶讹+ 劲3 印7 印l o ，如碘+ 劲6 + p l l 。极小p 一不变式的支撑如表2 1 所示。 表2 1 极小尸不变式的支撑 极小p 不变式支撑库所 p 1 ，p 2 ，p 3 ，p 4 厶p 5 ，p 6 ，p 7 ，p s 厶p 2 ，p 8 ，p 9 厶 p 2 ，p 3 ，p 7 ，p 1 0 毛p 4 ，p 6 ，p 1 1 网系统的关联矩阵m ，前置关联矩阵肌和后置关联矩阵p o s t 分别为： t it 2t 3t 4 | st 6t 1 | s 尸r e = a 仍 p 3 p 4 p 5 【】= 风 p 1 风 p 9 p l o p l i ，p o s t = 验证可知：m = p o s t - p r e 。 该网中有8 个极小信标，如表2 2 所示。 0 o 0 o 1 o 0 3 0 0 l c _ j 0 0 o o o o 一 1 一 l o i 0 0 0 0 0 1 o o 一 2 1 2 0 0 0 o l o 0 0 o 一 - l 0 o 一 0 o 0 0 0 o lil o