（机械电子工程专业论文）一类柔性制造系统死锁预防策略.pdf

摘要 论文应用基本信标研究死锁预防策略，通过对柔性制造系统( f m s ) 的p c t r i 网模型子类- - r c n 合并网的结构特性分析，将r c n 合并网中存在问题的信标区分 为基本信标和从属信标，提出基于基本信标的r c n 合并网的死锁预防方法。应用 这种控制策略可以更加有效的控制网系统，增强新网的活性。论文还针对由于信 标清空而产生死锁的一类p e t r i 网模型系统，提出了一种综合应用p e t r i 网基本信标 理论和区域理论处理死锁预防问题的常规设计方法，并编写程序实现了对可达图 的分析计算。该方法包括信标控制和区域法理论控制两个主要步骤。第一步的工 作主要是降低第二步的计算量，这比单独应用区域法理论的方法很大程度上减少 了计算量，提高了效率。 关键词：p e l r i 网死锁预防基本信标r c n 合并网区域理论 a b s t r a c t f o rac l a s so fp e t f in e t s ，r c n m e r g e dn e t s ，ad e a d l o c kp r e v e n t i o np o l i c y i s d e v e l o p e db yu s i n ge l e m e n t a r ys i p h o n s f i r s tt h ep r o b l e m a t i cs i p h o n s a r ed i s t i n g u i s h e d i na l lr c n m e r g e dn e tb ye l e m e n t a r ya n dd e p e n d e n to n e s t h e r e f o r e ，b yt h ed e a d l o c k p r e v e n t i o np o l i c y , al i v e n e s s e n f o r c i n g p e t r in e t s u p e r v i s o r c a l lb e p r o d u c e d f u r t h e r m o r e ，ac o m p a r i s o ns t u d yi sc o n d u c t e dw i t ht h ee x i s t i n gm e t h o d s ，w h i c hd e a l w i t ht h ed e a d l o c kp r o b l e m si nr c n - m e r g e dn e t s t h er e s u l t si n d i c a t et h a tt h i sm e t h o d i sm u c hb e t t e ri nt e r m so f p e r m i s s i v eb e h a v i o r t a r g e t t i n gac l a s so fs y s t e m sw h e r et h e d e a d l o c k si nt h e i rp e t dn e tm o d e l sr e s u l tf r o me m p t y s i p h o n s ，t h i st h e s i sa l s od e v e l o p s a f o r m a ld e s i g nm e t h o d o l o g yf o rt h ed e a d l o c kp r e v e n t i o np r o b l e m sb a s e do ne l e m e n t a r y s i p h o n so f p e t r in e t sa n dt h et h e o r yo f r e g i o n s ，a n dp r o g r a m m i n gf o rt h ea n a l y s i so f t h e r e a c h a b i l i t yg r a p h t h ea p p r o a c hp r o p o s e dc o n s i s t so f t w om a i ns t a g e s ：s i p h o nc o n t r o l a n dt h et h e o r yo fr e g i o n s t h ef i r s ts t a g ew o r ks i g n i f i c a n t l yl o w e r st h ec o m p u t a t i o n a l c o s ta tt h es e c o n ds t a g ec o m p a r e dw i t ht h ea p p r o a c hw h e r et h et h e o r yo f r e g i o n si s a l o n eu s e d k e y w o r d s ：p e t r in e t 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 ys i p h o n r c n - m e r g e d n e t s t h e o r y o f r e g i o n s 独创性( 或创新性) 声明 y6 9 5 5 7 0 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名i 差! ! 日期o f j d 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。本人保证 毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 本人签 导师签 r 期坚! ：! 同期碰：! ：兰2 一 第一章绪论 1 第一章绪论 1 1 研究背景与意义 1 9 6 2 年，德国人c a p e t r i 在他的博士论文“c o m m u n i c a t i o nw i t h a u t o m a t a ” 中首次提出“网状结构的信息流模型”，标志着p e t r i 网( p e t r in e t s ，p n ) 理论的 诞生。p e t r i 网是一种适合于系统描述和分析的数学模型。 p e t r i 网理论具有模拟性、客观性、流特性、描述性、分析性、基础性、异步 并发性的特点。模拟性是指从组织结构的角度，模拟系统的控制和管理，不涉及 系统实现所依赖的物理和化学原理：客观性是指精确描述事件( 变迁) 间的依赖 ( 顺序) 关系和不依赖( 并发) 关系。这种关系客观存在，与观察无关；流特性 是指适合描述已有规则的流动行为特征的系统，包括能量流、物质流和信息流； 描述性是指用统一的语言( 网) 描述系统结构和系统行为：分析性是指网系统具 有与应用环境无关的动态行为，是可以独立研究的对象。这样，可按特定方式进 行系统性质的分析和验证：基础性是指网系统在各个应用领域得到不同的解释， 是沟通不同领域的桥梁：异步并发性是指适合描述异步并发系统。如：不同子系 统事件间的并发、局部和全局目标间的冲突、资源限制、不同类型信息流的统一 描述、不同机器和不同用户间不同类型的接口。 上述特点使p e t r i 网广泛应用于许多领域，如分布式软件系统、并发并行程 序、离散事件系统、多处理机存储系统、数掘流计算系统、容错系统、可编程逻 辑和v l s i 阵列、异步电路与结构、编译器和操作系统、办公信息系统、逻辑程 序、局域网、神经网络、数字滤波器、决策模型、化学系统和法律系统等。这些 系统的共同特点都是具有并发、异步、分布、并行、不确定和随机成分。 p e t r i 网理论作为一利擞学理论。在离散事件系统( d i s c r e t ee v e n ts y s t e m s d e s ) 建模、分析、性能评价和控制设计中得到了广泛的应用。柔性制造系统作为一种 典型的离散事件系统一直是p e t r i 网的重要应用领域。 柔性制造系统是由数控加工设备、物料运储装罱和计算机控制系统等组成的 自动化制造系统。它包括多个柔性制造单元，能根据制造任务或生产环境的变化 迅速进行调整，以适宜于多品种、中小批量生产。它通过简单地改变软件的方法 能够制造出多种零件中的任何一种。f m s 以其灵活性成为现代企业非常重要的生 产方式，能满足日趋激烈的市场竞争及需求多样化对产品的要求。与传统的一台 机床只能加工种产品不同的是，f m s 中的机床除可以加工初始安排的任务外， 还有能力替换其他机床进行加工。在这种情况下的生产调度必须考虑到机床的通 2 类黎眺蛐系缈e 锁预防策略 用性，而f m s 可以用容许替换加工的生产调度取代传统的分离式加工计划和生产 调度。在f m s 中，不同类型的原料在离散的时间点进入系统，进行加工，它们共 享诸如机床、机器人、夹具等有限的资源。每种原料按照特定的生产流程来使用 系统中的资源。所有的生产流程并发执行，这样便会引起共享资源的竞争( 即死 锁) 。死锁通常出现在一个系统的几个并行进行的复杂加工进程的最终状态，我们 一般很难预先知道系统在什么情况下出现死锁。所以研究有效的柔性制造系统控 制策略，使系统不再发生死锁显得十分必要。本文主要研究柔性制造系统的死锁 问题。 基于p e t r i 网，人们研究了很多方法来处理自动制造系统中的死锁问题，大致 可归分为以下几类： 死锁预防方法 死锁避免方法 死锁校正方法 综合法 首先是死锁预防方法，如【2 】【4 】【7 】。死锁预防方法的目标是设计一个系统，该 系统所对应的p e t r i 网模型本身就是无死锁的或者是活的。这种方法从逻辑上保证 了系统中不会出现死锁，因而不必再去控制系统运行过程中对资源的申请。在 f m s 中，主要使用鼹种p e t r i 网分析技术处理死锁的预防：结构分析和可达图分 析。 前者中，可以捕获到系统p e t r i 网模型的行为特性诸如活性和有界性，和它的 结构之间的关系。然后。基于p e t r i 网理论的活性特征得到死锁预防控制策略 【2 0 】- 【2 2 】。在这种情况下，可以通过增加新的网元素，诸如带有初始标记的库所 和相关弧，放置到f m s 的初始p e t r i 网模型中，实现控制策略。其思想是，通过 新的网元素阻止一些变迁的发射，使系统不进入死锁状态。在文献 11 】中可以找 到这些技术的相关例予。这些技术引起的问题是为了得到活性，牺牲了系统原有 的一些好的状态标识，因此控制后的p e t r i 网模型不是最大许可的。也就是说，这 种解决办法不是最理想的。 后者是通过分析。f m s q 的p e t r i 网模型的可达图获得无死锁系统行为，研究从 p e t r i 网标识的可达图中剔除死锁状态的一种简单的预防死锁方法。应用这种方法 使得系统资源的使用最优化，同时阻止了死锁的产生。文献 2 6 【3 1 】研究了基于从 p e t r i 网标记的可达图中剔除死锁状态的一种简单的预防死锁方法。复杂而冗余的 计算严重影响了算法的效率。由于“状态爆炸问题”，在庞大的p e t r i 网中应用这 种方法，可达图规模成为另一个潜在的障碍。实际上，已经有一些我们比较熟悉 的技术来避免状态爆炸问题【2 6 】- 【2 8 】。另外还有一种著名的从复杂p e t r i 网模型中 提取特性的方法，它是利用化简的方法保持网的特性，如有界性、活性、可逆性 第一章绪论 等简化子网和结桩j 2 9 】。 其次是死锁避免方法【2 5 】。这种方法可分为两类；一类是通过控制对资源的 申请使系统避免产生死锁，其思路是如果许可一个资源的请求会导致死锁，那么 就不能允许该请求有效。对于网模型而言，这种方法实际上是有意识的控制某些 使能的变迁发射，避免p e t r i 网系统陷入死锁。这种限制资源分配的策略也具有一 定的保守性。 另一类死锁避免方法是通过改变p e t r i 网的结构，使系统不会产生死锁。做法 是为系统p e t r i 网模型中的每一个极小的信标增加一个所谓的控制库所，使得该信 标成为一个受控信标，然后保证网模型中的所有信标都不会被清空。这种做法的 缺点有两个：一是与第一类方法相比其资源分配策略具有较高的保守性；二是使 得p e t r i 网模型更加复杂( 增加了很多库所节点) 。 第三种是死锁校正方法，如 3 0 l 。它并不刻意去追求系统的无死锁性或活性， 而是一旦检测到系统发生了死锁，通过自动或人工的方法解锁。这种方法往往会 达到较高的生产率和资源利用率，但控制工程师必须对可能发生死锁的生产环节 有充分的认识，在设计单机( 如机器人、机床) 控制器时，需要设计相应的的控 制程序以便解锁时应用。此外，可能还需要一些附加的设备供解锁时使用，其结 果又是要加大投入。 综合法的思路是建立一些具有某种性质的p e t r i 网模型，使得在某类p e t r i 网 中，针对这些特殊的性质，可以采用特定的控制策略来消除死锁，如0 2 1 1 3 1 1 1 4 1 。 它的优点在于控制策略简单实用，但只能用在p e t r i 网的特定子类中。 目前基于网论的方法研究系统的死锁问题取得了不少成果，但是仍然有许多 问题需要进一步研究和解决，如i c 的生产系统与机械生产自动化系统有许多不同 之处。但目荫的研究成果一般都是针对机械生产的自动化系统有效的。此外许多 控制方法和策略对系统的行为施加了过多的限制，降低了系统的性能。 论文致力于死锁避免方法的研究，引用基本信标和冗余信标的概念，通过 分析p e t r i 网的结构特性和可达图，运用代数方法保证系统的p e t r i 网模型是无死 锁的。应用基于基本信标的方法，可以得到一个较为简单的p e t r i 网控制模型，这 个模型中包含较少的添加库所和有向弧，达到简化控制器设计的目的。 本文所提出基于p e t f i 网的控制理论力求把人们从复杂控制系统的设计，模 拟，性能评价，编程和最终调试的繁琐工作中解放出来，提高控制系统柔性，提 前发现前期的设计错误，缩短控制系统设计周期，从而提高生产效率。 1 2 本文的主要工作 论文系统地分析了现有的各类典型的死锁预防算法，应用基本信标理论，提 出了两种改进的的死锁预防算法，并针对性的解决了p e t r i 网领域内的一些基础性 问题： 针对一类p e m 网子类一r 烈合并网，提出了一种基于基本信标的死锁预 防算法。 将上述理论和算法应用于r c n 合并网实例，并进行了验证说明。 找到一种计算网系统死锁标识、坏标识、危险标识和活标识的可达图分析 的计算机实现算法，以及计算状态变迁分离实例的编程方法。 提出了一种新的死锁优化预防方法，它包括两个阶段：信标控制和区域理 论的应用。 将上述方法和理论应用于p c t r i 网子类，并进行了比较说明。 总之，全文结合p e t r i 网的基本信标理论和死锁避免算法，解决了p e tr i 网领 域里的一些基本问题，完善了p e l r i 网的理论体系，取得了一定的成果。限于时间、 条件和个人的认识，文中欠缺之处在所难免，恳清指正。 第二章p e l r i 网的基本理论 5 第二章p e t r i 网的基本理论 本章给出p e t r i 网的基本概念和性质 2 9 1 1 1 1 ，以及后面所要用至的一些定理和 推论。 2 1p e t r i 网的基本概念 2 1 1p e t r i 网的基本定义 【定义2 1 】库所变迁网( 简称p z 网) 是一个四元组，= ( p t 只即，其中： ( i ) p 代表库所的集合； ( 2 ) r 代表变迁的集合，并且p 和7 、是有限非空的不相交集合： ( 3 ) f c _ ( p x 幻u ( a p ) 称为有向孤集： ( 4 ) 胍n 肌 o ) 称为f 中弧上的权，= 0 ，1 ，2 ，) ； 当且仅当v f e f , 纾= l ，称n = ( ，正e 即为普通网( o r d i n a r yn e t ) ，可以记 作n = ( 尸，正d 。 当3 f = p ，f ) f 。t g q ) 1 时，称= ( p ，t 只f 约为一般网( g e n e r a ln e t ) 。 【定义2 , 2 】令| = ( 尸，l e 聊是一个网， ( 1 ) 的标识是映射mp - - t n ，蚴眵) 表示库所p 中的托肯数，托肯用实心圆点或 数字表示； ( 2 ) 给定避尸u l 则旭l s ) ；，。j 且l p ) ； 称( m m o ) 为网系统或标识网，其中为网的初始标识。 【定义2 3 1 令= ( p ，e 只聊是一个p e t f i 网，节点x e l ) u t 的前置集定义为 x - = y e p t j t l 抄，x ) e f ) 。其后置集定义为x = t y p u 7 1 10 ，y ) e f ) 。节点集合h e p u t 的前置集( 后置集) 定义为日= u 。，汉f = u 。) 。 【定义2 4 1 如果v = ( p ，l 只即是普通网，且v ，e 丁，i t l = l t i = 1 ，则称v 是状 态机( s t a t em a c h i n e ) 。 【定义2 5 】如果= ( p ，正e 是普通网，并且有寸s p ，l p b 。i = 1 ，则称 是标识图( m a r k e dg r a p h ) 。 【定义2 6 1 如果一个p e t r i 网系统( ，a 如) 的任意一个节点和其它节点中的任 意一个之间总存在一条连接路径，则称该网是强连通的。 【定义2 7 】如果一个p e t r i 网系统( m o ) 既是一个状态机又是强连通的，则 称其为强连通的状态机。 【定义2 8 】网= ( p ，z ：f j 叻称为纯的，当且仅当_ 1 0 ，力( p x u ( ，k 即：化 ，f ，( y ，功e f 。 6 类i 旨l 制造系目移e 锁预防策略 _ _ 一一 非纯网可以在保持动态性质不变的情况下化为纯网。下面要讨论的网都是纯 网。 【定义2 9 】令= ( p ，l 只是一个网， ( 1 ) 一个变迁m t 在m 下称为使能的，记为 砸d ，当且仅当，p 仨，：m ( p ) - - w ( p ，) 。 ( 2 ) 若m f ) 成立，则t 发射后，产生另新标识m ，记为聊 m ，有 p e t l t p t t t p ，n t 其它 ( 3 ) 网n 从标识 如开始的所有可达标识的集合记为r ( m o ) 或m o d 。它是一个 最小集，即e 尺( ，m o ) ，m er ( ) m 【，) m j m 尺( m o ) 。 ( 4 ) 当且仅当存在标识，m ，满足【t t ) 【) ：当r l ，t 2 ，r 时， 萨t t t 2 如称为出现序列。 ( 5 ) 对于网和标识m o ，( ，m o ) 称为一个网系统。 ( 6 ) 网| = ( p ，te 哟的关联矩阵定义为以j d 和7 为序标的矩阵m ：p t - ) z ， z 是整数的集合，且 【7 v 】( 且，) = 一( p , t ) ( t , p ) 一j 玖p , t ) + 缈( t p ) 0 p m p t l f p t i t 其它 2 1 2p e t r i 网的活性及不变式 【定义2 1 0 1 令n = 沪，l 只叻是一个网， 而是的一个标识 ( 1 ) 一个变迁t 在标识a 南下是活的，当且仅当v m r ( ， 如) ，了m r ( | ) ：m f ) 成立： ( 2 ) ( ， 而) 是死锁的，当且仅当、3 t t ： 而i t 成立； ( 3 ) ( a 劬是无死锁( 弱活) 的，当且仅当v 矩兄( ma 而) ，3 f 殳m d 成立t ( 4 ) ( ) 是活的，当且仅当v t e t ：，在标识下是活的。 【定义2 1 1 】令= ( 尸，正f 帅是一个网，是的一个标识 ( 1 ) ( 南) 是有界的，当且仅当j 艇z m 0 ) ，v a 托r c m o ) ，v p p ：m ( p ) o 。称一个集合踺p 是被标识m 标记的一当且仅当s 中至少有一个元素被吖标记。s 中的托肯数 m ( s ) = e p 。p m ( p ) 。 ( 3 ) 不包含任何严不变式支撑的信标称为严格信标。一个严格信标有可能被清空。 ( 4 ) 个既是极小又是严格的信标，称为严格极小信标( s m s ) 。 2 1 3p e t r i 网的一些基本性质 【性质2 1 】网系统( m o ) ，是= 妒，t e 叨的个p - 不变式，v m e r ( m o ) ： p 、洚 m 4 ， 【性质2 2 】网系统( ，l i f o ) ，j 是= ( p ，tf 的一个n 不变式，| | 中所有 的变迁发射次，可能会使网系统回到初始标识。 【性质2 3 】网系统【，m o ) ，= ( p ，瓦f 聊，s c p 是一个信标，若3 m e r ( n 。m o ) ： 麒s ) ：0 ，则s 以后永远不会被标记，称为被清空。 【性质2 4 1 网系统( ，m o ) ，= ( 只lf 叻，s c _ p 是一个陷阱，若3 m e ( n 、m o ) ， 坂s ) ，o ，则s 以后总是被标记。 【性质2 5 】网= ( p ，t 只聊的只不变式j 的支撑i l 川i 既是一个信标又是一个 陷阱。 【性质2 6 1 ( m o ) 是一个网系统，其中三lf 吩，j 是一个p 一不变式， s g p 是| v 的一个信标，那么此信标s 是在埘j 下被j p 一不变式，控制的，当且仅当 ，m o o 且对于所有的p a s ，蚴s 0 成立，或等同地，m o o 且p e p i i ( p ) o _ c s 。 如果s 是一个在m o 下被p 不变式，控制的信标，则s 不可能被清空，也就是 说，v m e r ( n , 釉：s 在标识下是被标记的。 【性质2 7 】( m o ) 是一个普通网系统，皇( 尸，t d ，若在m 下是死( 锁) 的， 则所有未被标记的库所形成一个信标：如果网中没有信标可能被清空，则称( m o ) 是无死锁的( d e a d l o c k - f r e e ) 。 【性质2 8 】对于普通网系统( ，蚴， 净( p ，t 刃，死锁的必要条件是所有的极 小信标部被清空。 该性质是一般死锁分析方法的基础。需要说明的是，本中主要讨论普通有界 网。除非特别说明，下文提到的网模型都是普通有界网。 2 2 p e t r i 网概念和性质的举例说明 下面以图2 1 为例说明p e t r i 网的有关概念和性质。 t 1 幽2 i 一个初始标识为 00 0 20 】。 p t 1 图2 , 2 图2 i 的p e t r i 网系统 的p e t r i 网模型 发射f j 后的状态 图2 l 中的p e t r i 网n = ( p ，只聊，其中j p = 扫l ，p 2 ，p 3 ，p 4 ，p 5 ) ，7 ，ht 2 ，t 3 ，t 4 ，。5 ， t 6 。昧f r v ( ) = l ，所以它是个普通网，记作a k ( p ，e n 。 初始标识m o = o 002o 】7 ，( m o ) 为网系统或标识网。 网元素的前置集和后置集如下： j 2 f 冬，6 ) ，轨2 f ，j ，t 3 ，锄= ( ，i ，4 ， ，4 = f f 2 ) ，5 = f r 2 ， p l 。= 1 ) ，p z = ( ，2 t s ，p 3 。= ( t 2 ，f 6 ) ，p 4 。= n ，“ ，p 5 。= ( f s 。r 6 ， 翌三空! ! ! ! ! 堕塑堇查型笙9 t l = p i ) ，。t2 = p 2 ，p 3 ) ，3 = 伽4 ，t 4 2 p 4 ，。t5 2 p 2 ，p s ，t6 2 p 3 ，p s ， ，1 = p 2 ，p 3 ) ，2 = 扣4 ，p 5 ) ，3 。= p 2 ) ，“= i p 3 ) ，f s 2 p i ) ，r 6 。 p 1 ) 网的关联矩阵啪为： p 1 p 2 【n 】_ p 3 p 4 p 5 t lt 2 - 10 l一1 11 0l 01 t 3t 4 o0 101o o1ol - 1 一loo o011 当，= 【2 11 1 1 】。时有，p 、】= d t ，所以j = 【2 1 1 1 1 】1 是一个p 不变式。网 只有1 个极小p - 不变式，它的支撑是：m i f p l ，见，内，p 4 ，p s ) ；当j 1 = 11 1 0l o 】。 和以= 1l 0101 】。时同时有= o 和【m , j 2 = o ，所以 和以是网结构中的变 迁不变式。 网中有3 个严格极小信标：s t = ( p i ，p 2 ，p 3 ，p 4 ，= 伽i ，p 3 ，p 4 ，p 5 ) ，岛= p 1 ， p 2 ，j ，4 ，邱) 。以蜀为例，。s l = l 如。s 1 p = l u 2 u ? m up 4 = ，5 ，t 6 u t ! ，t 3 u t , ，“) u f 2 ) = f i ，t 2 ，t 3 ，t 4 ，t 5 ，t 6 ) ，s t = e s i p * = p l 。u p 2 u p 3 l p 4 = ，i t 2 ，t 3 ，t 4 ，t 5 ，6 ) ，所以s ：_ s i 。， 故呙是一个信标，而且它不包含任何p 不变式的支撑，也不包含任何其它信标， 所以是一个严格极小信标。同样，和岛也是严格极小信标。 下面再来分析它的动念特性： 在图2 1 标识状态下有初始标识m o = 0002o 】t ，因为，3 和，4 的输入库所m 中有托肯，所以变迁t 3 和，4 是使能的：因为t i 、t 2 、，5 和t 6 的输入库所中都没有托 肯。所以其它变迁不是使能的。由予t 3 和“是使能的，它们当中的任一个都可以 发射。如果发射t 3 ，则从它的每一个输入库所中移走托肯，且托肯数等于输入弧 的权数；使它的每一个输出库所增加托肯，且托肯数等于输出弧的权数。即从m 中移走一个托肯，在p 2 中加入一个托肯，这样产生的新的标识就如图2 2 所示。 初始标识蜥状态下发射t j 可得到新的标识蚴= 0l 0l o 】。，在新的标识下 变迁是t 3 和，4 使能的，这时若继续发射t 3 ，可到达新的标识m 2 = 【0 200o 】t ，如 图2 3 所示。 在标识n 如下没有变迁是使能的，网系统陷入死锁。如果在标识m 下不发射 变迁t 3 而改为发射变迁，4 ，则可到达另一个新的标识a 磊= 01 l0o 7 ，如图2 4 所示。在标识m 3 下又有变迁是使能的，所以网系统可继续运行。 综上所述，网| v 从标识开始的所有可达标识的集合联，) ，如图2 5 所 示。 ! ! 二鲞型墅塑婴塑望堕箜些 t l p 圈2 3 图2 2 发射 质图2 4 图2 2 发射“后 图2 5 可选图 9 2 3 柔性制造系统的p e t r i 网建模 柔性制造系统中a - p l a c e 称为工序库所，用于建模一个任务包含的加工工序。 b - p l a c e 称为固定资源库所，用于建模机床，机器人，物料传输系统等。c - p l a c e 称为可变资源库所，用于建模加工原料。夹具和托盘等。一个p e t r i 网中的a - p l a c e 。 b - p l a c e 和c - p l a c e 的集合分别记为n ，p 品p c 。例如，图2 6 中n = ( p 2 ，p 3 ，p 4 ，p s ， p 6 ，p 7 ，协，d ，p b 5 ( p l l ，p 1 2 ，p t 3 ，p i 4 ，p i s ) ，p c = p l ，p r o 。 在柔性制造系统中，一个工序至少需要一个固定资源参与。从p e t r i 网角度来 看，a - p l a c e 和与之对应的b - p l a c e 构成个p 不变式。网样，一个加工原料要经 过若干工序成为产品，所以c - p l a c e 和其对应的a - p l a c e 也构成一个p 不变式。根 据a - p l a c ，b - p l a c e 和c - p l a c e 的定义，可以看到柔性制造系统的网模型被p 一不变 式覆盖，且这些不变式中肯定含有托肯。 一般地，s 是柔性制造系统p e t r i 网模型( ，m o ) 的一令信标，我们有m d s ) _ 2 。 下孺j 舄例子来说明如何建立p e t r i 网模型。考虑一个柔性制造单元，包括三台 机床( m i ，m 2 ，m j ) ，两台上下料机器人( r l ，r 2 ) 。两个输入缓存库( i j ，1 2 ) 和三个输出 第二章p e t r i 网的基本理论 缓存库( o f ，0 2 ，0 3 ) 该单元可生产三种零件类( j l ，j 2 ，j 3 ) 它们的工艺流程如下 j i ：i l _ r l 哼m 3 斗o l ； j 2 ：i l _ r 1 _ m i j r 2 寸m 2 甘0 2 ； j 3 ：1 2 - m 2 _ r 2 寸m i 哼0 3 ； 该单元的p e t r i 网模型如图2 6 所示。 t 1 p 图2 , 6p e t r i 同模型 p 1 0 2 4 本章小结 本章主要对p e t r i 网豹基本概念及性质进行了叙述，对后面用到的基本知识进 行了实例说明。 1 2 = 鲞! 蔓壁燮i 至! 墼丝雯堕篁堕 _ _ _ - _ _ _ _ 一一 第三章r c n 合并网模型及基本信标理论 r c n 合并网是p e t r i 网的子类 5 1 3 1 ，它可以为一大类f m s 建模，代表性很强。 每个资源控制网( r c n ) 被认为是基本的单位模块，整个系统模型是由这些模块通过 相互作用的普通变迁和普通变迁子网合并而成的。 基本信标 1 1 1 9 是一种特殊的严格极小信标( s m s ) ，对于一个p e t r i 网，当其全部 基本信标不被清空时，其所有的甄贿可能不被清空。一个p e t r i 网的基本信标的数 量比其s m s 的数量要少得多，尤其当p e t r i 网规模大而复杂时这一点变得更加显著。 本章引用的基本信标概念，提供了解决这个问题的一把钥匙。将基本信标的概念 引入p e t r i 网可以使得现有许多控制算法得到简化。可以设计出更简单( 具有少量的 控制库所和连接弧) 的监督控制器。 本章主要有五部分：第1 节介绍了r c n 合并网的定义和性质；第2 节介绍了p e t r i 网的基本信标理论，给出了基本信标和从属信标的概念：第3 节介绍了基于基本信 标的信标控制方法；第4 节提出了基于基本信标的死锁预防策略；第5 节对本章进 行了概括总结。 3 1r c n 合并网简介 f m s 通常是由多个加工中心和一个物料运输系统组成。一个f m s 要求能够 完成不同种类的零件加工，每个零件按照事先制订的加工工艺以定的顺序使用 f m s 中的资源。所谓资源，是指f m s 中的机床、机器人、卡盘、储存箱等。每 种零件的加工顺序称为加工进程在f m s 中允许存在不同的加工进程，这些加工 进程可以并行操作，因此存在资源竞争，导致冲突发生。从而可能产生死锁。死 锁，简单地说，就是系统中的一些加工进程总是不可能完成的。在f m s 领域，死 锁状态的出现是由于资源分配不合理。资源得不到释放而引起的，这意味着一系 列的资源处于循环等待之中。 如果用p e t r i 网来模拟加工进程，其中库所表示加工进程中的工序状态和系统 中的资源，资源库所中的标志数表示可供使用的该资源的个数或加工能力；用变 迁表示工序状态之间的转换。 我们首先简单介绍一下常用的由文献( 1 1 提出的p e t r i 网的子类s 3 p r 。 【定义3 1 】一个简单加工进程( 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 网 = ( 八jp o ，正d ，d 而是的初始标识，矿称为空闲库所( ) j 日工进程的开始和结束 工序状态) ，p p 称为工序状态库所。( v ， 南) 满足以下条件：( 1 ) ，o ，p o g 尸， 第三章r c n 合并网模型及基本信标理论 ，0 0 0 ) l ，e p ，m o ( p ) = 0 ：( 2 ) n 是一个强连通的状态机，即v ，t ，i 。t l = l t 卜1 ； ( 3 ) 的每一个回路包含p ”。 【定义3 2 1 一个拥有资源的简单加工进程( s 2 pw i t hr e s o u r c e s ) s 2 p r 是一个 网n = ( p u p o w p r ，ld 。m o 是的初始标识。( ， 而) 满足以下条件：( 1 ) 令 p o = 矿 ，1 9 x = l j 矿) u r 生成的子网n xc p 骼7 麓n ) 是一个s 2 p ，其中p x = p u 扩) ， 矗= 7 1 ，既= f n ( p x x t x ) ：( 2 ) r e p r 称为资源，n 是资源的集合，p t c c & b ( p u 扣o ) ) n p 旷( d ；( 3 ) v p e p ，v t e p - v g e p 。3 r p e p r - t c - t p l = g n p r 2 ( 咋l ；( 4 ) v r e p r ， m o ( r ) l ；v re p r ，r n p - - - r 协m ；v r e p r ，r t h r = 田；( 5 ) ( p o ) n p f p o ) n p r = ( d ； ( 6 ) 对于一个给定的r e p r ，俄r ) = ( “，) r 、p 称为资源，的持有者集合。对于一个资 源集合9 1 = r l ，n ，棚 用u h ( r ) r e g l 或u r 。9 i 脚表示坝r 1 ) u 川r 2 ) u u h ( r ，。) 。 【定义3 3 】一个拥有资源的简单加工进程系统( s y s t e mo fs 2 p r ) s 3 p r 是 ( r z m o ) ) 个s 2 p r 通过共享资源复合而成的p e t r i 网n = 0 h 尸( p u p o u p 如7 1 ，d 。 记m = 1 ，2 ，k ) 。s 3 p r 网系统( ，m o ) 满足阻下条件：( 1 ) 一个s 2 p r 也是一个特 殊的s j p r ：( 2 ) v i e m ，w 似 ，( 尸j u p u 0 n ( 卧卯勺= m ，且存在靠，n 尸旷p f 。( d ， 聊驴m ；( 3 ) p 刮卢l 镰，p o = u 卢l * p o t ，p n = u ，l ，t = l ) 。i k 乃f 钆州饥；( 4 ) v i e n , ， 砌p u n i ，p ) ；v i e 坼，v r e 玮 p c 口，m o ( r ) = m o ( r ) ；v r e p c o ，m o ( r ) ：m a x 如( 一， 而 ) 。( 5 ) 符号可表示组成第i 个s 2 p r 网m 的s 2 p 。 【定义3 4 1 设一个s 3 p r 网系统( ，m o ) ，其中 ，一( p u p o u ，en ，s 是网n 的一个信标。表示信标s 中的资源，s r = s n p r ；函表示信标s 中的工序状态库 蕊，s 矿s n p 。明显地，s ；s * j s p 。 【定理3 1 】设- ( p u p 。u p r ，瓦刃是一个s 3 p r ，踞网| v 的一个严格信标，即5 不包含任何尸一不变式的支撑。那么i s n p n l 1 ，也就是说，s 中至少包含两个资源。 证明：参见文献 1 1 】。 r c n 合并网是p e t f i 网的子类。每个资源控制i 网( r c n ) 被认为是基本的单位模 块t 整个系统模型是由这些模块通过相互作用的普通变迁和普通变迁子网合并而 成的【8 】【1 2 】。相关基础理论如下： 【定义3 5 】【5 r c n 是强连接状态机，g = ( 只正em o ) 其中存在难库所 p r e p 被称为资源库所，使得m o ( p r ) o ，剩余的库所被称为操作库所。 【定义3 6 】p e t r i 网g 的变迂子网g a = ( ，死，r ，坛o ) 是g 的子网使得对于 任何p e p 。的输入变迁和输出变迁是死中的变迁，换句话说变迁子网的库所是局 部的。 【定义3 7 1p e t r i 网g = ，l 只m o ) ，是通过普通变迁和普通变迁子网合并【1 个r c n s g jg s2 ( p s ，疋，足，坛0 ，s = l ，n 而形成的，其中：户= p fu u 只， t = t i u u l ，庐n u u r ，m o ( p ) = m s o ( p ) ，如果p e 只。显然，在合并模型g 中任何两个r c n 中的普通元素构成一个变迁予网。我们在下文中称r c n 合j j ： ! ! 二翌望矍璧堡夔塑! 塑堡堕垂堕 网。 举例说明，一个生产系统包含4 种类型的资源：工具集a 和b ，机床c 和d 。 其中两个机床共享工具。该系统可以同时生产两列z 类型的产品a 下圈显示了资源 a 、b 、c 和d 的r c n 模型及合并后生成的r c n 合并网。 ( a ) g a t 4 费 p ( b ) g b t 1 ( c ) g c t 4 ( d ) g d( e ) 台并阔 图3 1r c n 含并网合成模型 其中库所表示操作，它们的解释见表3 1 ，变迁可以解释为开始或者完成操作。 这些r c n 的初始标识分别记作n a n b ，n c 和n d 。 表3 1 库所的实际含义 p 1 c 中的机器可以使用 p 2 c 中的机器a 拿起类型一的原料和工具准备第一步操作 p 3 机器拿起b 中的工具，进行第二步操作，加工后分别将工具放回原处 p 4 d 中的机器可以使用 p 5 d 中的机器a 拿起类型一的原料和工具准备第一步操作 p 6 机器拿起a 中的工具，进行第二步操作，加工后分别将工具放回原处 p 7 a 中的机器可以使用 p 8 b 中的机器可以使用 在n 个r c n 合并时必须满足以下的约束条件： 【约束3 1 】对于每个普通变迁，至多存在一个是操作痒所的输入库所。 【约束3 , 2 1 普通变迁子网不应该包含资源库所，因此，这些子网中的库所应 笙三皇垦型盒茎旦竖型垦董查堕堡垄堡惦 该是初始没有被标识的。 下面的两个例子在合成时不满足上面两个约束条件，因此不能称为r c n 合 并网。 t l t 4 资 p 图3 2 不满足约求条件3 1 的r c n 合成网系统 d ( a ) r c n g a( b ) r c n g b( c ) r c n g c( d ) 台并后的阿系统 图3 3 不满足约柬条件3 2 的r c n 合成网系统 【定义3 8 1g = ( p ，瓦em o ) 是由合并n 个r c n sc = g 。lg s = ( 只，瓦，r ，坛力， s = i ，n ) 形成的网，满足约束条件3 i 和3 2 。循环结构定义为( 7 么d ) 使得 v ，e ，3 p , ( 0 ，p a ( ，) ，使得p r ( o 是资源库所，p o ( o 是操作库所，其中7 j 7 ， d 的功能是使d ：p c ，满足下面的条件： ( a ) 如果p 仨p j ，那么g j d ( p ) 。也就是说，d 映射到一个r c n 包含的一个库所。 ( b ) d ( p o ( t