（机械电子工程专业论文）一类柔性制造系统的死锁研究与分析.pdf

摘要 近年来，p e t r i 网在f m s 的建模、分析和控制过程中得到了广泛的应用。本文 对p e t r i 网模型的死锁控制问题进行了较为深入的研究。首先，论文对于几种常见 的死锁控制算法进行了较全面的介绍，同时论述了基本信标理论及其在死锁控制 中的应用，在此基础上，我们针对一种p e t r i 网子类一e s 3 p r 网提出了一种基于基 本信标理论的新的死锁迭代控制算法，该算法通过多步迭代分别给网系统添加普 通控制库所和加权控制库所，从而控制所有的基本信标。同时在一定条件下，使 得所有从属信标得到控制，从而得到活的控制网系统。与其它算法相比，论文中 所提出的预防方法可以得到对网系统行为限制较小的控制网。另外，论文还提供 了- - e e 基于m i p 的死锁优化算法。该算法通过移动控制库所的输出弧位置，减小 控制库所对网系统的行为限制。最后，通过实例验证了提出的死锁控制策略以及 优化算法的优越性。 关键词：p e t r i 网柔性制造系统死锁预防基本信标e s 3 p r a b s t r a c t r e c e n t l yp e t r in e t sh a v eb e e nw i d e l yu s e di nt h em o d e l i n g ，a n a l y s i sa n dc o n t r o lo f f l e x i b l e m a n u f a c t u r i n gs y s t e m s ( f m s ) t h i s t h e s i s i n v e s t i g a t e s s o m ed e a d l o c k p r e v e n t i o np r o b l e m si np e t r in e t s ，f i r s t l nw ep r e s e n ts o m ep o p u l a ra l g o r i t h m s ，a tt h e s a m et i m ew ed i s c u s st h et h e o r yo fe l e m e n t a r ys i p h o n sa n dt h e i ra p p l i c a t i o n si nt h e d e a d l o c kp r e v e n t i o n s ，o nt h eb a s i so ft h et h e o r yo f e l e m e n t a r ys i p h o n s ，w ep r e s e n ta n e wi t e r a t i v ea l g o r i t h mf o rac l a s so fp e t r in e t sc a l l e de s p r ( e x t e n d e df r o ms p r ) ，b y a d d i n gt w ok i n d so fc o n t r o lp l a c e sc a l l e do r d i n a r yc o n t r o lp l a c e sa n dw e i g h e dc o n t r o l p l a c e st ot h ee l e m e n t a r ys i p h o n s i nt h i sw a y , w ec a np r e v e n ta l le l e m e n t a r ys i p h o n s f r o mb e i n gu n m a r k e da n du n d e rs o m eg i v e nc o n d i t i o n sw ec a l lm a k ea l lt h es t r i c t m i n i m a lc o n t r o l l e da n dg e tal i v en e ts u p e r v i s o r c o m p a r i n gw i t ho t h e rp o l i c i e s ，w e i n t r o d u c et h ei d e ao ft h ee l e m e n t a r ys i p h o n sa n da ni t e r a t i v ec o n t r o lp o l i c y a sar e s u l t w ed on o th a v et og e n e r a t et h er e a c h a b i l i t yg r a p hf o ran e ts y s t e m t h eb e h a v i o ro ft h e n e tw ef i n a l l yc o n t r o l l e di sf a rl e s sr e s t r i c t e d i na d d i t i o n ，w eg i v ea no p t i m a la l g o r i t h m b a s e do nt h em i x e d i n t e g e rp r o g r a m m i n gt e c h n i q u e s i tr e d u c e st h er e s t r i c t i o n so ft h e c o n t r o lp l a c e st ot h en e ts y s t e mb ym o v i n gt h ep o s i t i o no ft h eo u t p u ta r c so fc o n t r o l p l a c e s ，f i n a l l y w eg i v eaf l e x i b l e m a n u f a c t u r i n ge x a m p l et o v a l i d a t et h ed e a d l o c k p r e v e n t i o np o l i c y a n dd e m o n s t r a t et h e a d v a n t a g e o fo u ro p t i m a ld e a d l o c kc o n t r o l a l g o r i t h m k e yw o r d s ：p e t r in e t s f m sd 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 y - s i p h o n r s 3 p r 独创性( 或创瓤性) 声明 y 6 9 5 5 65 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：夏洫试 同期乙墨：2 ：丛 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。本人保证 毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 导师签h 期工z ， 。：一 第一章绪论 第一章绪论 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 ) 的首创者是美国的 m a a l r o s e 公司。它于1 9 6 3 年制造了世界上第一条加工多种柴油机工件的数控自 动线。2 0 世纪7 0 年代末，由于国际市场竞争目趋激烈，要求生产者缩短生产周期、 降低生产成本，f m s 引起了比较普遍的重视。2 0 世2 8 0 年代，f m s 从探索阶段走 向了实用化和商品化阶段，成为机械制造技术进步的重要标志。 在我国有关标准中，f m s 被定义为：柔性制造系统是由数控加工设备、物流贮 运装罱和计算机控制系统组成的自动化制造系统。它包括多个柔性制造单元，能 根据制造任务或生产环境的变换迅速进行调整，适用于多品种、中小批量生产。 随着科学技术的发展和多品种、d q t g 量自动化生产的需要，柔性制造系统己越来 越受到人们的重视。f m s 涉及的领域包括机床、电子技术、液压传动、机器人技 术、控制技术、计算机技术及系统工程等，它是一种集多种高新技术于一体的现 代化制造系统，是c i m s 系统不可缺少的重要的制造单元。 从本质上柬酷f m s 是一种典型的离散事件动态系统( d e d s ) ，符合离散事件系 统的许多特征，有其固有的很多复杂特性比如说加工路径柔性、机器资源共享、 缓冲资源有限、操作并行、对特定资源的争夺导致的冲突、工序之间的优先级别 以及潜在的死锁情况等等。我们用传统方法分析起来比较困难，因为对于很多系 统特性，传统方法如数学规划等，根本没法精确的表示出来。 p e t r i 网是1 9 6 2 年德国的c a p e t r i 博士在其博士论文“c o m m u n i c a t i o n a u t o m a t a t i o n ”中首先提出的。它是系统建模的工具，用来研究信息系统及其相互 关系( 特别是涉及并发处理的系统) ，这一过程表示如下： 表绕 评井宪誊 i 、分析结 同横砸 圈t 1 利用p e t r i 同嫫投实际襄娆示意稠 p e t r i 网具有可用图形表示的组合模型，具有直观、易懂和易用的优点，对描 述和分析并发现象有其独到的优越之处。而且p e t r i 网是严格定义的数学对象，借 助数学丌发的p e t r i 网分析方法和技术既可用于静念的结构分析，又可用于动态的 行为分析。与传统的系统建模、分析和控制方法相比，p e t r i 网非常适合于异步并 ! 型燮燮塑咝堂墅堕坌堑 ，一 发系统的建模。 7 0 年代以后，p e t r i 网不仅在理论研究上得到迅速发展，而且其应用领域也不 断拓宽。下面简要叙述p e t r i 网在以下三个领域中的应用情况。 1 通讯协议的验证 通讯协议验证是p e t r i 网应用最为成功的领域之一。由于p e t r i 网以形式语言作为 基础，可以形式化地对通讯协议进行正确性验证。最初应用大致在7 0 年代初期， 女h m e d i n 等人【1 的“计算机系统和通讯系统的可恢复性”。到8 0 年代，p e t r i 网及其各 种扩展模型已广泛应用于协议工程的各个方面。 2 知识推理和神经元网络中的应用 w o e i - t z yj o n g 等人 2 】提出了一种基于模糊p e t r i 网的知识表达和推理的形式化 模型，并给出了一种检查时序知识一致性的方法。a k o n a r 3 】利用模糊p e t r i 网来 表达专家系统中的一种不确定的逻辑推理连接，一旦给出了初始条件，就可以通 过模糊推理计算出各个推理结果的可信度，最后通过选取得到合理的推理结果。 yz h o u 【4 】4 提出了一种基于人工神经元网络的模糊p e t r i 网系统n h f ，通过这个 n h f 模型，讨论了基于神经元网络中的反向传播算法的几种权值训练算法，包括 酊向推理算法、后向推理算法和知识学习算法等。 3 f m s 的建模、分析和控制 p e t r i 网由于其自身优点，在制造系统中应用广泛，包括带缓冲区的简单生产线、 机床加工中心、自动生产线、自动装配线、柔性制造系统以及即时加工系统。对 于此类问题的研究，已取得大量成果，其中比较有代表性的是m c z h o u 等【5 6 】提 出的混合建模方法。 本文的研究目的就是对柔性制造系统( f m s ) 的p e t r in e t 模型进行分析和控制。 1 2 国内外的研究状况 p e t r i 网在f m s 中的应用，近几十年来国内外的学者做了很多的研究工作。根据 研究目的和方法的不同，研究工作分成了一些不同的方向： l ，对于建模方法的研究 这方面的研究主要有：j e z p e l e l a 8 等提出的s 3 p r 网，m d j e n g 等【7 提出的 r c n 网，z h o u 等【6 】提出的一类共享资源系统。此类方法的共同特征是：针对某 类特殊问题提出一种满足某些约束条件的子网，通过较严格的数学证明来保证用 这类子网构建起来的系统模型能具有某些我们所希望的性质，比如说无死锁、安 全、有界、可逆等等。 2 对于调度方法的研究 利用p e t r i 来对f m s 进行调度也是研究的一个重点，通过p e t r i 网直接生成调度 第一章绪论 方案。其中较有影响的有l e e 和ed i c e s a r e 的工作，他们把p e t r i 网和a + 算法相结合， 利用启发函数来控制对p e t r i 网状态空间的搜索范围，从而能在可接收的时间内生成 较小系统的调度方案。后续工作从两个方面进行：一是开发出更有效率的启发函数。 另一个方面就是对算法本身进行改进，如h h x i o n 提出的将最好一优先的启发式 算法和受控回溯策略结合起来的混合搜索算法。 3 对于仿真方法的研究 由于f m s 系统所固有的复杂性，以及p e t r i 网模型能通过直接运行来分析系统性 能这一特性，丌发基于各种p n 的计算机仿真软件也成了一个研究的重要方向。使 用一个合适的专用仿真软件，能极大的提高我们的效率。人们开发出来了各种各 样的工具，从简单的t p n 仿真工具，到稍复杂的o s p n 仿真工具，直到各种功能强 大的c p n 仿真工具平台。如t c p n 等等。 4 对于模型控制方法的研究 近年来对f m s 模型的分析与控制主要集中在死锁问题的研究上，常见的处 理柔性制造系统中死锁问题的方法大致可归为以下几类：死锁避免方法；死锁校 正方法；死锁预防方法。 死锁避免方法是通过控制对资源的申请使系统避免产生死锁，其思想是如果 许可一个资源的请求会导致死锁，那么就不能允许该申请有效。对网模型而言，这 种方法实际上是有意地控制某些可使能的变迁发射，以避免p e t r i 网系统陷入死锁。 这种限制资源分配的策略也具有一定的保守性。最著名的死锁避免算法是银行家 算法。 n v i s w a n a d h a m 等 9 】是通过向前搜索网系统的可达标识图来避免死锁的。 当给定一个网系统的当前标识后，算法就会确定所有规定搜索长度内的标识状态： 通过判断这些标识是否是死锁标识，就可以找到那些发射后会导致系统死锁的变 迁。在网系统运行的时候，只要不使能这类变迁就可以避免系统产生死锁。这种 方法可以使系统有限度地避免死锁，但确定搜索步数有很大困难：而且还必须提 供系统出现死锁时的修复策略。 z b a n a s z a k 等【1 0 】提供了一种针对柔性制造系统的死锁避免算法，称为 d d a 算法。这种方法通过运用以下两个策略来避免系统死锁。其一是使p e t r i 网系 统中的某个库所集合中的托肯数不能超过该库所集合未占用的资源中的托肯总 数；其二是当该库所集合中的库所同时申请多个资源并且这些资源都可以申请到 时，它只能占用一个资源。d d a 算法在每一工步开始申请共享资源时，通过有意 的不使能某些变迁，来保证以上两条策略的实施。 f s ，h s i e n 等【l1 】的死锁避免算法是建立在最小资源需求的概念的基础之 上，即使得系统中占用共享资源最少的工序优先发射。这种算法具有多项式复杂 度，并且放松了对系统的约束，因而比【8 中的方法具有更广泛的应用。 ! 兰壁堂堂堕塑型堕堕塑 一 f l o 1 1 d d 的方法比较类似。它们都是从死锁结构的概念出发，明确了死锁产 生的条件，即当系统的死锁结构中占用的资源等于资源的总数时，系统就会陷入 死锁状态：并在此基础上形成了自身的死锁避免算法。 由于需要考虑大型的柔性制造系统，j p a r k 1 2 在p e t r i 网模型的基础上针对资 源分配系统开发了一种专门的新颖的建模和分析方法。它用整数规划的方法来避 免系统死锁。但是由于它考虑了资源分配系统中的大部分情况，从而使得网模型 不再只是适用于一般网，这就大大限制了它的应用。 第二种是死锁校f 方法。这种方法并不刻意去追求系统的无死锁性或活性， 而是一旦检测到系统发生了死锁，通过自动或人工的方法解锁。这种方法往往会达 到较高的生产率和资源利用率，但控制工程师必须对可能发生死锁的生产环节有 充分的认识，在设计单机( 如机器人，机床) 控制器时，需要设计相应的控制程序以 便解锁时应用。此外，可能还需要一些附加的设备供解锁时使用，其结果又是要加 大投入。 m c z h o u 等人【1 3 1 【1 5 】的目标是设计一个系统，浚系统所对应的p e t r i 网模 型本身就是无死锁的或者是活的。这种方法从逻辑上保证了系统中不会出现死锁， 因而不必再去控制系统运行过程中对资源的申请。 1 5 是通过限制进入系统工件的 数量( 对于网系统而言，就是控制网系统的初始标识) ，使系统的p e t r i 网模型是活 的，从而在原则上保证系统不会陷入死锁。这种方法从确保系统不存在任何死锁的 角度出发，相应地静态调配资源( 设置初始标识) ，从而提高资源的利用率。应该指 出，这种方法尽管保证了系统的全局活性，但具有较大的保守性，从而降低了系 统的生产率和资源的利用率。 近年来出现的死锁预防方法大都采用在目标p e t r i 网模型中增加新的控制库所 的方法。通过增加控制库所限制网系统的行为，从而保证网系统是无死锁的。 e z p e l e t a 等人【8 】应用p e t r i 网结构理论为柔性制造系统设计了控制器，最终得到无死 锁的网系统。他们定义了一类普通保守网的子类一s 3 p r 网，即含有资源的简单加工 进程系统，他们要求目标p e t r i 网为s 3 p r 网。并且为每个严格极小信标( 简记为s m s ， 个s m s 就是一个能被清空的极小信标) 添加一个监控库所来强制保证网的活性。 该方法简单有效，然而，由于添加了过多的监督器和弧，使得p e t r i 网控制器比原先 先建立的p e t r i 网模型复杂很多。同时，系统的行为也受到了极大的限制。 如果在一个p e t r i 网中没有s m s 被清空，则该p e t r i 网是无死锁的。同时它也 是一些p e t r i 网子类( 如自由选择网和非对称自由选择网) 活的充分条件。论文将引 用从属信标和基本信标的概念 1 6 1 。在一定的条件下，使得一个p e t r i 网中所有的 基本信标不被清空，则其从属信标也不会被清空，即所有的s m s 都不会被清空。 这意味着如果要使一个p e t r i 网没有信标被清空时，并不需要对所有的s m s 都添加 控制。因此，基于基本信标，可以得到一个较为简单的p e t r i 网控制模型，这个模 第一章绪论 型中包含较少的添加库所和有向弧，达到简化控制器设计的目的。 基于p e t r i 网研究系统的死锁问题取得了不少成果 7 】 8 】 1 7 】 1 8 】【1 9 ，但是仍 然有许多问题需要进一步研究和解决。此外许多控制方法和策略对系统的行为施 加了过多的限制，降低了系统的性能。 本篇论文致力于死锁预防方法的研究，通过分析p e t r i 网的结构特性，添n - 定的控制从而保证系统的p e t r i 网模型是无死锁的。 1 3 本文完成的主要工作 本文系统地论述了现有的死锁预防策略，通过对网结构的分析，提出了一种 针对e s 3 p r 网的死锁预防策略和一种优化策略。 第五章中，我们在前人研究工作的基础上针对e s 3 p r 网模型提出了一种基于 基本信标的迭代控制方法。该方法是通过多步迭代法给初始网模型添加两类控制 库所，普通控制库所o c 和加权控制库所w c 。首先判断基本信标中所有操作库所 的补集合中元素的n 。值，即从信标中偷取的标记数。对于n 。值为1 的基本信标， 采用普通控制，普通控制库所的添加对网系统的行为限制较小，但是会产生新的 可被清空的信标；对于n 。值大于1 的基本信标，采用普通控制会产生较多新的可 被清空信标，所以我们采用控制较严格的加权控制库所，即输出弧添加在网模型 的入口，由j e z p e l e t a 等人 8 的研究结果知道该控制库所不会产生新的可被清空 信标，但是很明显对网系统的行为限制较大。如此反复进行迭代控制，直至最后 一个基本信标( 基本信标的不唯一性使得我们可以选择一个加权控制库所作为结 束，它的添加不产生新的可被清空信标，同时基本信标数量有限保证了我们的迭 代过程是有限的而且是逐渐收敛的) 。这样通过有限步迭代我们可以控制迭代过程 中所产生的新的可被清空的基本信标，同时，在满足一定条件的情况下，保持从 属信标受控，从而使得所有的严格极小信标得到控制。这样不仅可以保证网系统 的活性，而且可以得到对网系统行为限制较少的控制库所。与传统死锁预防算法 相比较，这种方法的优点是对网系统添加的控制库所对网系统的行为限制减少，同 时具有较多的可达状态，并保证最终的网系统是活的。 第六章中，我们在基本信标理论和混合整数规划的基础上，提出并验证了一 种死锁控制优化算法。该方法是在e z p e l e t a 方法和基本信标理论相结合的控制方 法基础上，保持控制库所数量和标识数不变，向下移动控制库所的输出弧，因为 距离相对的输入弧越近，对网系统的限制越小。所以我们可以先假设输出弧移动 有效，然后用混合整数规划法来判断移动后网系统的活性，即判断g ( m ) = i p t 是否 成立，如是则移动有效，该输出弧的移动不影响网的活性，但减少了对网系统的 限制，控制库所得到了优化：如否，即输出弧的移动会影响网的活性，还原输出 6 弧的这次移动。这样重复移动每个控制库所，即可优化所有添加的控制库所，得 到一个优化后的可达状态数较多的网系统。 总之，论文主要研究了柔性制造系统p e t f i 网的死锁预防策略，得到了定的 成果。相信这些工作对p e t r i 网理论的进一步应用和发展都是十分有益的。限于时 间、条件和个人的认识，文中很多方面定有所欠缺，恳请指正。 第二章p e t r i 网的基本概念 一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 】库所变迁网( 简称尸丁网) 是一个四元组，n = ( 尸，t ，f ，聊，其 中p 代表库所的集合，7 1 代表变迁的集合，并且p 和7 1 是有限非空和不相交的集 合；f c ( p x t ) u ( t ) p ) 称为有向弧集；：f 寸肌 o ) 称为f 中弧上的权i n = o ，l ， 2 ， 。 称n = ( j p ，t ，f ，为普通网( o r d i n a r yn e t ) ，当且仅当v 店f ，玎切= l ，普通 网可以记做n = ( j p ，t ，同。v p e p ，v t e t ，如果0 t ) e f ，且w ( p ，f ) = 1 ，则称 为普通州丁网( p t o r d i n a r yn e t ) 。一个普通网肯定是一个普通p r 网。当驴p ，) e f , w q ) t 时，称n = ( p ，t ，f ，哟为一般n l ( g e n e r a ln e t ) 。 【定义2 2 】令n = ( 尸，t ，f ，是个p e t r i 网，节点x e p w t 的前置集定义 为 x = y e p u t l u ，x ) e f ) 。其后置集定义为x = 抄p u7 1 1 0 ，y ) e f ) 。节点的集合 h e p u t 的自u 置集( 后置集) 定义为h = 。、( 盯= 。雕) 。 【定义2 3 】如果n = ( 尸t ，f ，即是普通网，且vr t ，i t l = l t i = 1 ，则称是 状态机( s t a t em a c h i n e ) 。 【定义2 4 】如果n = ( j d ，t ，f ，是普通网，并且有v p e p ，i p l = l o i = 1 ，则称 是标识n ( m a r k e dg r a p h ) 。 【定义2 5 1 0 n 果一个p e t r i 网系统( a 南) 的任意一个节点和其它节点中的任意 一个之问总存在一条连接路径则称该网是强连通的。 【定义2 6 】如果一个p e t r i 网系统( ， 而) 既是一个状态机又是强连通的，则称 其为强连通的状态机。 【定义2 7 】网n = ( p ，t ，f ，称为纯的，当且仅当一3 ( x ，y ) e ( p x t ) w ( t x p ) ： ，力， o ，x ) e f 。 非纯网可以在保持动态性质不变的情况下化为纯网。下面要讨论的网都是纯 网。 【定义2 8 】令n = ( 尸，t ，f ，聊是一个网。 1 1 的标识是映射始p 寸w ； 2 ) 一个变迁，7 1 在m 下称为使能的，记为 虹，) 当且仅当v p e ，：m p 皿阡劬，f ) 1 3 ) 若m ，) 成立，则t 发射后，产生另一新标识 ，记为m ，) m ，有 m 7 ( p ) = m ( p ) 一r v ( p , t ) m ( p ) + w ( p ，f ) m ( p ) 一( p ，f ) + w ( t , p ) m ( p ) p t i t p f r p f n f 。 其它 4 1 网_ v 从标识开始的所有可达标识的集合记为r ( n ，m o ) 或 而【) 。它是一个 最，j 、集，即r ( n ，m o ) ，a ，r ( n ，m o ) x m 【f ) a ，= a ，r ( n ，a 南) ； 5 ) 当mt 2 ，丁时，俨t t t 2 岛称为出现序列，当且仅当存在标识，蚴， 坛满足m o 【t o h ) 螈； 6 ) 对于网和标识m o ，( n ，m o ) 称为一个网系统； 7 ) 网n = ( 尸，t ，f ，聊的关联矩阵定义为以p 和丁为序标的矩阵 朋：尸7 一z ，z 是整数的集合，且 【】( 口t ) = 一w ( p ，t ) i v ( t , p ) 一w ( p ，) + w ( t p ) o p e t i t 。 p t l r p e t i t 其它 2 1 2p e t r i 网的活性及不变式 【定义2 9 】令n = ( p ，t ，f ，聊是一个网。 而是的一个标识 1 ) 一个变迁r 在标【 a 靠下是活的，当且仅当v m r ( n ，m o ) ，j m r ( n ， 而) ：m 【，) 成立； 2 ) ( n ，m o ) 是死锁的，当且仅当一3 t t ：m o 【f ) 成立； 3 ) ( ， 毛) 是无死锁( 弱活) 的，当且仅当v m r ( n ，m o ) ，3 t t ：m 【f 成立： 4 ) ( n ，m o ) 是活的。当且仅当v f 叠f 在标识硒下是活的； 5 ) ( n ，m o ) 是有界的，当且仅当j 女刷 0 ) ，vm r ( n ，m o ) ，v p e p ：旭p ) ； 6 ) ( n ，m o ) 是结构有界的，当且仅当对于任意的有限的初始标识，它都是有界的； 值得说明的是，对于资源有限的实际系统而言，它的p e t r i 网模型一般都是结 构有界的。所有元素均为0 ( 1 ) 的列向量记为o ( 1 ) 。 【定义2 1 0 】令n = ( p ，t ，f ，阶是个网。 1 ) 以尸为序标的列向量p ：p - - ) z 称为的尸垧量。 2 ) 以，为序标的列向量1 , 9 1n z 称为的n 向量。 3 ) 称p 一向量，是一个p 一不变式( 库所不变式) 当且仅当i 0 且， 】= 0 1 。 i i 1 = 扣p f j p ) 0 称为，的支撑。 4 ) 称一个p 不变式是极小的当且仅当它的支撑中不包含任何其它p 不变式的支 撑。本文中的p 不变式，如果没有特别声明，则都是极小p 一不变式。 第二章p e t r i 网的基本概念 9 5 1 称r 向量，是一个f 不变式( 变迁不变式) 当且仅当j o 且 m j = o 。 1 1 4 1 = t 砒f ) o ) 称为l ，的支撑。 6 ) 称是被p 不变式“孓不变式d 覆盖的当且仅当v p e p ：i ( p ) c o ( v t e t ：j ( t ) o ) 。 被p 一不变式覆盖的的网也称为是保守的。 【定义2 1 l 】( ， 磊) 是一个网系统，_ = ( p ，t ，f ，阶。 1 ) 称一个非空集合s o p 是一个信标( s i p h o n ) ，当且仅当苫c f 成立： 2 ) 称一个非空集合s c p 是一个陷阱( t r a p ) ，当且仅当留三r 成立： 3 ) 称一个信标( 陷阱) 是极小的，当且仅当不存在其它信标( 陷阱) 是它的真子集； 4 ) 称p e p 是被标识m 标记的，当且仅当 ，p ) o 。称一个集合s _ p 是被标识们 标记的，当且仅当s 中至少有个元素被m 标记。s 中的托肯数m 研= l 。p m ( p ) ； 5 ) 不包含任何p 不变式支撑的信标称为严格信标。一个严格信标有可能被清空； 6 ) 一个既是极小又是严格的信标，称为，“格极小信标( s m s ) 。 2 1 + 3p e t r i 网的一些基本性质 【性质2 1 】网系统( ml i f o ) ，i 是= ( p ，t ，f ，的一一个p 不变式，v m e r ( n , 腼) ：1 1 m = i 。m o 。 【性质2 2 1 网系统( ，m o ) ，t ，是n = ( j d ，t ，f ，叻的一个卜不变式，0 川中所 有的变迁发射一次，可能会使网系统回到初始标识。 【性质2 3 】网系统( ，m o ) ，n = ( p ，t ，f ，聊s c _ p 是一个信标，若3 m e r ( n ，m o ) ： 心曲= o ，则s 以后永远不会被标记，称为被清空。 【性质2 4 】网系统( m o ) ，n = ( p ，t ，f ，s c _ p 是一个陷阱，若9 m e r c ，) ， m 0 ，则s 以后总是被标记。 【性质2 5 】网n = ( j 1 ) ，t ，f ，聊的户不变式，的支撑i 川既是一个信标又是 一个陷阱。 【性质2 6 】( ，m o ) 是一个网系统，其中| = ( p ，丁e 聊，i 是一个p 不变式，延p 是v 的一个信标，那么此信标s 是在下被p - 不变式控制的，当且仅当，朋p o 且对于所有的p e p y s ，始) o 且p j p l ) 0 ) 至s 。如果s 是一个在 如下被p 不变式，控制的信标，则s 不可能被清空，也就是说v m e r ( n , 霸) ：s 在标识a 磊下是被标记的。 【性质2 7 1 ( n ，m o ) 是一个普通网系统， 仨( 尸，t 毋，若j v 在时下是死( 锁) 的， 则所有未被标汜的库所形成一个信标：如果网中没有信标可能被清空，则称( ， 如) 是无死锁的( d e a d l o c k f r e e ) 。 【性质2 8 】对于普通网系统( ， 力，a k ( 尸，l 刃，死锁的必要条件是所有的极 小信标都被清空； 该性质是一般死锁分析方法的基础。需要说明的是，本中主要讨论普通有界 网。除非特别说明，下文提到的网模型是普通有界网。 2 2 举例 以图2 1 为例说明p e t r i 网的有关概念和性质。 ，l 图2 i 一个p e t r i 网实例 1 0 图2 1 中的p e t r i 网2 ( j d ，r ，r ，其中p = p t ，p 2 ，p 3 ，p 4 ，p 5 ，p 6 ，p 7 ，p 8 ，p 9 ，p io ， p i i ，p 1 2 ，p 1 3 ，p 1 4 ，p l s ，t = t t ，t 2 ，t 3 ，t 4 ，t 5 ，t 6 ，1 7 ，t 8 ，t 9 ，t j 0 ，t i i 。v f e f ，缈= l ，所以它是 一个普通网，记做= 驴，ln 。 网有7 个极小p - 不变式，它们的支撑分别是：i i = p i p 2 ，p 3 ，p s , p 6 ，p 7 ) ； | | j 2 | 户妇，p s ，p 9 ，p m ；2 锄，p l s ；i i x 4 1 1 2 p 7 ，p l l ；i l l s l l = p 3 ，9 9 ，p 1 2 ；p 溉，p 5 ， p 1 3 ；忻i 户t 邯，p 8 ，p m ； n n o e g 3 个严格极小信标：s 1 4 ，) 6 ，p 1 3 ，p 1 4 ) ，= 扣5 ，伽，p 1 2 ，p 1 3 ) ，墨= p 6 ，内， p 1 2 ，p 1 3 ，p 1 4 。以s l 为例，驾1 2 u p 。舶2 p 4 k j * p 6 k , 7 1 3 u o l 4 = t g u t 4 k g t 4 ，t l o u f 如， t g 。 t 4 ，1 5 ，t 9 ，t t o ，s i 2 s i p 2 p 4 。u p 6 。t - 3 p 3 。唧1 4 。= t 3 ，t 4 ，t 5 ，t 8 ，t 9 ，t l0 ，所以s l s l ， 故s t 是一个信标，而且它不包含任何j p 不变式的支撑，也不包含任何其它信标， 所以是一个严格极小信标。同样和& 也是严格极小信标。网的初始标识m o ：7 ， 0 ，0 ，0 ，0 ，0 ，0 ，0 ，0 ，5 ，1 ，2 ，1 ，2 ，1 。网的关联矩阵n i 为： 第二章p e t r i 网的基本概念 p l p 2 p 3 p 4 p 5 p 6 p 7 【n 】_ p 8 p 9 p 1 0 p l i p 1 2 p 13 p h p l5 2 3 自动制造系统的p e t r i 网模型 建立f m s 的p e t r i 网模型的步骤如下： 1 ) 根据状态和事件的定义，确定f m s 的状态集合j d 和事件集合l 并确定加工设备 和装卸站的状态、事件。 2 ) 确定f m s 的状态和事件之间的关系。 3 ) 根据建立p e t f i 网模型的基本规则，将状态和事件分别与库所和变迁对应，确定 库所和变迁之间的关系，从而得n v m s 的p e t r i 网图。 4 ) 根掘实际系统的状况，确定p e t r i 网图的初始状态，即初始状念下各库所中的托 肯数。 制造系统p e t r i 网模型中的库所可分为三类：假定= 僻z 一是一个制造系统 的网模型，p 是一个库所，肘j 是的初始标识。p 称为操作库所，当且仅当m o 例= 0 ： p 称为资源库所；当且仅当m o ( p ) 是一个正整数，p 称为闲置库所，当且仅当m o ) 是一个变量，操作库所、资源库所和闲置库所与初始标识相关且具有明显的物理 含义。自动制造系统中，操作库所用于建模一个任务包含的加工工序，资源库所用 于建模机床，机器人，物料传输系统等，闲置库所用于建模加工进程的开始和结束 工序状态 一般地，s 是自动制造系统p e t r i 网模型( m o ) 的一个信标，我们有( 5 皿2 。 下面用例子来说明如何建立p e t r i 网模型。考虑一个柔性制造单元，包括3 台 0 o 0 o 0 o o o10o o o o o 0 o o o o o ，o o o ，o o 0 o o l 0 0 0 o 0 o o o o o o o o 0 o o o ，0 o o o 0 o o o 0 0 o o o o o o o o o 0 o o o o o o 0 o o o o 一 o o 0 o 0 o o 0 o o o 0 ，0 o o 0 0 o 0 o o 0 o o ，o 0 o oo，o 0 o o 0 o一0 0 o o 0 0 o o o 0 o o o o 0 o o 0 o o o o 0 0 o o o 0 0 机床( m 1 ，m 2 ，m 3 ) ，2 台上下料机器人( r 1 ，r 2 ) ，两个输入缓存库1 1 ，1 2 和三个 输出缓存库0 1 ，0 1 2 ，0 3 ，该单元可生产三种零件类p l ，p 2 ，p 3 ，它们的工艺流 程如下： p 1 ：1 1 _ r 1 斗m 3 - 0 1 ： p 2 ：1 1 _ r i m 1 - - r 2 - - ) m 2 寸0 2 ： p 3 ：1 2 寸m 2 寸r 2jm 1 _ 0 3 ： 该单元的p e t r i 网模型如图2 1 所示。 明。 2 4 小结 本章主要对p e t r i 网的基本概念及性质进行了叙述，并结合例子对它们进行了说 第三章e s l p r 网模型及常见控制方法 第三章e s 3 p r 网模型及常见控制方法 e s 3 p r 一即拥有资源的扩展简单加工进程系统，该网模型的特点：某些操作库 所可能与多个资源发生联系，且某些资源在每个支路中的持有者集合可能大于1 。 e s 3 p r 网也是p e t r i 网的子类，包含常见的s 3 p r 网，所以可以模拟更为复杂的f m s 模型，研究与分析该类网的死锁控制对p e t r i 网的研究与发展有很重要的意义。从前 适用于s 3 p r 网的几种经典算法女h e z p e l e t a 法，p 不变式法等同样适用于e s 3 p r 网， 本章将介绍这两种经典的死锁预防算法：e z p e l e t a 死锁预防算法和基于p 不变式的 死锁迭代算法，两种算法均以控制严格极小信标不被清空为基础，最后将基本信 标的理论分别引入这两种算法来简化控制策略。 本章主要有四部分：第1 节介绍y e s 3 p r 网的概念；第2 节介绍了目前几种经典 的信标控制方法；第3 节对本章进行了概括总结。 3 1 类f m s 的p e t r i 网模型- - e s 3 p r 简介 f m s 通常是由多个加工中心和一个物料运输系统组成。一个f m s 要求能够完 成不同种类的零件加工，每个零件按照事先制订的加工工艺以一定的顺序使用 f m s 中的资源。所谓资源，是指f m s 中的机床、机器人、卡盘、储存箱等。每种 零件的加工顺序称为加工进程，在f m s 中允许存在不同的加工进程，这些加工进 程可以并行操作，因此存在资源竞争，导致冲突发生，从而可能产生死锁。死锁， 简单地说，就是系统中的一些加工进程总是不可能完成的。在f m s 领域，死锁状 态的出现是出于资源分配不合理，资源得不到释放而引起的，这意味着一系列的 资源处于循环等待之中。 如果用p e t r i 网来模拟加工进程，其中库所表示加工进程中的工序状态和系统 中的资源，资源库所中的标志数表示可供使用的浚资源的个数或加工能力：用变 迁表示工序状态之间的转换。 本文所讨论的e s 3 p r 是p e t r i 网的子类，包括常用的s 3 p r 网模型，同时也是 r c n 网的一部分，它可以为一大类f m s 建模。 【定义3 1 】【6 】一个简单加工进程( 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 网n = ( p t o ) ，rd ，是的初始标识，p o 称为闲置库所( 力口工进程的丌始和结 束工序状态) ，p p 称为工序状态库所。( ，m o ) i 茜足以下条件：( 1 ) p 巾，p o 硅户， m o ( p ”) 1 ，v p c p ，i o p ) = 0 ；( 2 ) n 是一个强连通的状态机，即v ，li t l = l t l = l ：( 3 ) 的每一个回路包含p o 。 【定义3 2 1 6 】一个拥有资源的简单加工进程( s 2 pw i t hr e s o u r c e s ) s 2 p r 是一 兰型鳖丝塑塑堕丝 个网 ，- ( p u 矿 u p r ，ld ，m 0 是n 的初始标识。( ，) 满足以下条件：( i ) 令 p o = p o ，由x = p w p o u r 生成的予网产( 尸舳t x , f x ) 是- - + 产p ，其中p x = p u p 。) ，