（机械电子工程专业论文）一类petri网的信标求取方法及应用研究.pdf

摘要 利用p e t r i 网对柔性巷4 造系统进行设计一直是p e t r i 网研究的重要方向。基于 信标理论的死锁预防策略的前提要得到网中严格极小信标。在面对大规模系统时 计算严格极小信标是十分费时的，而且对所有的严格极小信标进行控制会使网结 构变得非常复杂。 为了解决这些问题，本文针对p e 踊网的一个子类提出一种利用网的结构特点 得到严格极小信标的方法。由于充分利用了网的特性，使该方法获得严格极小信 标的时间大大减少。在得到严格极小信标后，从中提取基本信标。对基本信标添 加控制库所和控制弧后，使其被不变式控制。而从属信标的可控性由与之相关的 基本信标的可控性来保证，最终得到活的p e t r i 网控制器。 这种新的信标寻找方法与基本信标理论相结合形成新的p e i r i 网死锁预防策 略。该策略在计算严格极小信标时节省大量时间，而且由于只控制了基本信标， 使控制器的设计更为简化。因此利用这种新的死锁预防策略可以在较短的时间里 得到一个优化的p e t r i 网模型。 关键词：p e t ri 网信标柔性制造系统死锁预防 a b s t r a c t u s i n gp e 埘n e t st od c s i g nan e x i b l em n u f a c t u r i n gs y s t e mi s 锄i m p o n a l l t t a s ki n t h es t u d yo fp e t r in e t s g c t t i n ga us 岫c ln l i n i m a ls i p h 0 s ( s m s ) i st h cp r e m i s eo f d e 棚o c kp r e v e n t i 叽s t r a t e 舀e sb a s c do ns j p h o nt l i e o f y h o w e v e ri ti sv e r yt i m e - 咖s u m i n gw h e nt l l e 面z eo f t h es y s t e mj sh f g e a d d i n ga 嘞m 切p l a c ef o re a c hs t r i c l m i n i m a ls i p h o nw i l la l s om a k et l i en e tm o m p l e x ho r d e rt os o l v et h e s ep m b l e m s ，at c c h n i q u et of i n da l ls m si nas u b c l a s so fp e t r i n e ti sd c v c l o p e di nt i l i st h e s i s s i n o ct h cn e wm e t h o dm a l 【e su s eo ft h es t n l c t u r eo ft h e n e t ，瑚【u c ht i i i l ei ss a v c d a f i e rg c t t i n ga l lo ft h cs m s ，t h ee l e m e n t a r ys i p h o n sc a nb e o b t a i n e d t h ee l e m c n t a r ys i p h o n sc a nb ei i i v a d a n t - c o n t r o l l c db ya d d i n gc o n t r 0 1p i a c e s a i l da r c s ，a i l dt h c n t m l l a b i l i t yo fad c p e n d e ms i p h o nm a yb ee n s u r e db yt h a to fi l s r e l a t e de l e m c n t a r ys i p h o 璐f i n a l l y ，al i v e n e 髓- c n f o r c i n gs u p e i s o rc a nb ep r o d u c t e d o 锄1 b i l l i n gt h en d v e ls i p h o n l u t i o nm e t h o dw i t he l e i n e n t a r ys i p h o n sb a s e d t h e o f y ，an e wd e a d l o c kp r e v e n tp o i i c yi sd e v e l o p c d o ) m p a r e dw i t ho t h e rd c a d l o c k p r e v e m j 彻s t r a t e 沓c s ，i tc 纽m a k el l l es t 硼咖r eo ft l l es u p e r 订s o rs i n l p l e r a no p t i m a l c o n t f o l l e rc a i ib cg c n e f a t c dw i m1 c s s m p u 纽t i 蛐a lo o s tu s i n g n e wp o l j c y 1 畸w o r d s ：p e t dn e ts i p h o n 耵e 】d b km a 蛐h 咖一n gs y s t e m d e a d i o c k p r e v e n n o n 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：球哥江日期细2 莎 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。本人保证 毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本人签名：夕象干彩一、 导师签名 日期铆占2 巧 第一章绪论 第一章绪论 1 1 研究背景与意义 p e t r i 网最早是由c a r l a d 锄p c l f i 在1 9 6 2 年提出，他的博士论文k o m m u n i k a t i 彻 m i ta u t o m a t e n 阐述了一台计算机中的两个异步分支间的通讯理论基础，并特别注 意到事件问因果关系的描述。他的论文是p e t f i 网理论发展的基础。 p e t r i 的论述引起了a w h o l l 和其他在a d r ( 应用数据研究) 公司信息系统 理论课题组人们的注意。许多关于p e t r i 网的早期理论、记号和表示法都是由他们 导出或拟定的。 经过四十余年的发展，p e t r i 网理论取得了长足的进步。p e t r i 网的一些优良品 质使其成为一个很好的系统分析工具，在许多动态离散系统的设计中发挥重要作 用。在这类应用中一般先设计出系统，然后构造出相应的p c 仃i 网模型并对其进行 分析。在分析中所遇到的问题都可能是系统设计中的缺陷，必须修改设计以克服 这些缺陷。对修改后的系统重新建模分析，如此循环直到没有问题。利用p e t r i 网 建模分析实际问题的过程如下图所示： 校正 图1 1 利用p c 晡网进行系统设计的过程 柔性制造系统作为一类典型的离散事件系统一直是p e t f i 网应用的重要领域， 下面首先介绍柔性制造系统。 柔性制造系统( f m s - f l c x i b l cm a n 憾l c t u d n gs y s t c m ) 是由数控加工设备、物 料运输存储装置、计算机控制系统等组成的自动化制造系统。 柔性可以表述为两个方面：第一方面是系统适应外部环境变化的能力，可用 系统满足新产品要求的程度来衡量；第二方面是系统适应内部变化的能力，可用 在有干扰( 如机器出现故障) 情况下，这时系统的生产率与无干扰情况下的生产 率期望值之比来衡量柔性。 一般情况下，只有品种单一、批量大、设备专用、工艺稳定、效率高的生产， 才能形成规模经济效益；反之，多品种、小批量生产，设备的专用性低，在加工 形式相似的情况下，频繁调整工夹具，工艺稳定难度增大，生产效率势必受到影 2 一类p e 喇网的信标求取方法及应用研究 响。为了同时提高制造工业的柔性和生产效率，使之在保证产品质量的前提下缩 短产品生产周期，降低产品成本，最终使中小批量生产能与大批量生产抗衡，柔 性自动化系统便应运而生。 自2 0 世纪8 0 年代以来，在工业化国家中，柔性制造系统( f m s ) 作为迈向 工厂自动化的第一步，已获得了实际的应用。 柔性制造系统的优点：设备利用率高。一组机床编入柔性制造系统后，产量 比这组机床分散单机作业时的产量提高数倍；生产能力相对稳定；运行灵活；产 品应变能力强；减少在制品；节约生产投入。 柔性制造系统的构成： 自动加工系统：是柔性制造系统的加工单元，例如加工中心。 物流系统：物流系统指由多种运输装置构成，完成工什、刀且_ 等的供给弓f 送的系统。如传送带、轨道、转盘以及机械于等。它足柔性制造系统的重要组成 部分。 软件系统( 信息系统) ：软件系统指保证柔性制造系统用电子计算机进行有效管 理所必不可少的组成部分。包括设计、规划、生产控翎和系统监督等软件。 我们看到柔性制造系统包含了许多数量有限的资源如传送机器人、夹具、机 床等。这些资源如果分配不当就可能使系统进入死锁停机状态。正是由于柔性制 造系统构成的复杂性，使得f m s 的系统设计具有很大的挑战性。一个好的设计既 要完成生产控制功能，同时尽量合理配景资源使系统尽可能少的发生死锁。因此 如何得到一个更好的控制策略使柔性制造系统能尽可能的免于死锬是当前f m s 系 统设计的一个热点问题。 我们知道产生死锁有四个必要条件： 1 ) 互斥条件：任务对其要求的资源进行排它性控制。 2 ) 请求保持条件：在获得部分资源后又请求新的资源，而新的资源已被占用。 3 ) 不可剥夺条件：任务已获得的资源在未使用完之前不能被剥夺，只能在使 用完时由自己释放。 4 ) 环路条件：发生死锁时任务资源有向图中必构成环路。其中每个任务占有 下一个任务申请的一个或多个资源，如下图所示( 其中只表示资源，p 表示 任务。任务指向的资源表示任务申请的资源，资源指向任务表示任务占有 的资源1 。 图1 2 形成死锁的环路条件 对于一个系统，不论初始设计多么巧妙总是不能绝对保证不会发生死锁。那 第一章绪论 3 么一旦发现系统存在死锁，如何应对就是很重要的问题。对于死锁的处理，主要 存在四种策略： 1 ) 鸵鸟策略：一种不理睬的策略。死锁发生也不会影响系统主要功能的实现。这 是一种简单应对死锁的方法，主要用在一些即使发生死锁也不会有很大损失的 场合。 2 ) 死锁预防策略：破坏死锁的四个必要条件之一。 3 ) 死锁避免策略：精心的分配资源，动态的回避死锁。 4 ) 死锁的检测与校正：一旦发生死锁，系统不但能检测出来而且能够解除。 死锁预防是采用某种策略，限制并发任务对资源的请求，使系统在任何时刻 都不满足死锁的必要条件。预防死锁的两种策略： ( 1 ) 预先静态分配法：破坏不可剥夺条件，预先分配所需资源，屎征不等f 0 资源。该方法的问题是降低了对资源的利用率，降低任务的并发程度， 有时可能无法预知所需资源。 ( 2 ) 资源有序分配法：破坏环路条件，把资源分类按顺序排列，保证不形成 环路。该方法存在的问题是减少了系统的可达状态数。 死锁避免并不是要严格控制死锁产生的条件而是通过设计周密的算法来合理 的分配系统资源使系统在任何状态下都不会发生死锁。下面介绍有名的银行家算 法。 银行家算法：该算法对任务发出的每一个系统可以满足的资源请求命令加以 检铡，如果发现分配资源后，系统可能进入不安全状态，则不予分配；若分配后 系统仍然处于安全状态，则分配资源。 与死锁预防策略相比，死锁避免提高了资源的利用率，但增加了系统开销。 其中不安全状态是指有可能导致系统死锁的状态。 死锁检测与校正是解决死锁闯题的另一种方法。这种方法对系统的资源分配 不加限制，通过定时检测系统状态，若发生死锁即设法解除的策略来控制系统死 锁。这种方法允许系统发生死锁。死锁解除通常采用资源剥夺和撤销任务的方法 来完成。 由于柔性制造系统设计的复杂性，对其建模具有一定的难度。而近年来借助 网络来研究多任务并发系统取得了很大进展，其中利用p _ e 仃i 网来研究系统更是形 成了一种热潮。经过人们不懈的努力，科用p c t r i 网建模柔性制造系统取得了许多 重要的研究成果。在f m s 设计时所必需要考虑的死锁阎题都得到了较好的解决。 不论是死锁预防，死锁避免，死锁校正都有相应的p c t f i 网设计方法。下面针对死 锁预防简要介绍其中的主要理论。 死锁预防方法 7 9 1 4 2 3 2 4 ：这种方法要求设计出一个系统，该系统 对应的p e t r i 网模型本身就是无死锁的或者是活的。这种方法从根本上保证了系统 4 一类p e 证网的信标求取方法及应用研究 中不会出现死锁，因而不必再去控制系统运行过程中对资源的申请。m c z h 叫 等人 9 通过限制进入系统工件的数量( 对于网系统而言，就是控制网系统的初始 标识) ，使系统的p e 打i 网模型是活的，从而在理论上保证系统不会陷入死锁。这种 方法从确保系统不存在任何死锁的角度出发，相应地静态调配系统资源( 设置初始 标识) 。但是也应该看到，这种方法尽管保证了系统的活性，却在设计时具有较大 的保守性，从而降低了系统的生产率和资源的利用率。 目前出现的死锁预防方法大都采用在目标p e 仃i 网模型中增加新的控制库所的 方法 3 2 1 2 2 2 5 。通过增加控制库所限制网系统的行为，从而保证网系统是 无死锁的。如果在一个p e t r i 网中没有严格极小信标( 筒记为s m s ，一个s m s 就是 一个能被清空的极小信标) 被清空，则该p e t r i 网是无死锁的。同时它也是一些p e t r i 网了类( 如e i l i 选择网和怍刑称自由选择网) 活的充分条r f ：。 这_ _ 亘过控制严洛趿小信标米实现死锁预防方澍艮重要的少就足要求 系统中的所有严格极小信标。而计算信标又有许多不同的方法，目前比较常用的 是p e t r i 网分析工具i n t e g r a 把dn c ta m a l y z c r ( 玳砧。它是一款集成的分析软件，利 用不同的菜单选项实现对p e t r i 网性能的分析。眦的第一个版本出现于1 9 9 2 年是 由p e t e lh s t a f k c 教授开发，目前最新的版本为发布于2 0 0 3 年的2 2 版。由于其 简单易用逐渐成为p e t r i 网分析的主要工具，利用它可以得到网中的严格极小信标。 然而随着网规模的增大，网中信标的数量急剧增长，此时利用斟a 计算信标会花 费大量的时间，使系统设计的时间变得无法控制。 e r b 0 e r 和t m 删n a 在文献【3 9 】中提出利用符号矩阵求取信标的方法。该方 法利用库所和变迁的输入、输出关系建立符号关联矩阵，利用符号矩阵的运算得 到极小信标。这种方法考虑到了p e 啊网中库所与变迁的输入、输出关系使计算量 得到一定程度的降低。 m s i l v a 等人1 4 0 】 良出的方法基于用逻辑公式描述信标特性，用这种方法构建 逻辑等式，逻辑等式的变量代表一个库所是否属于某一个信标。这种方法经过改 进也具有较好的计算效果。 尽管人们从不同的角度出发，得到许多寻找信标的方法。但是如何能更加快速 有效的得到信标仍然是值得关注的问题，而找到一种更有效的信标计算方法在 刑s 的死锁预防中也具有非常重要的意义。 在得到严格极小信标后，下一步的工作就是对严格极小信标添加控制库所。如 果对每一个严格极小信标都添加控制，那么在网规模较大时，由于所需要控制的 严格极小信标数目非常惊人，使控制器的设计变得很复杂甚至在实际中由于成本 问题而不可实现。为了实现无死锁的中大规模网，1 1 7 】提出了基本信标的概念。基 本信标是严格极小信标的子集，基本信标理论将网中严格极小信标分为基本信标 和从属信标两部分。基本信标的数目总是小于或等于网中月咖( 吼l 功，因此基本信 第一章绪论 标的增长是随网的规模线性增长。在满足一定的条件下只要对网中的基本信标施 加控制即可控制所有的严格极小信标，从而实现整个网受控。 上面介绍了p e 仃i 网死锁预防策略的一些理论。下面再对死锁避免和死锁校正 做简要介绍。 死锁避免方法是通过控制对资源的申请使系统避免产生死锁，其思想是如果 许可一个资源的请求会导致死锁，那么就不能允许该申请有效。对网模型而言， 这种方法实际上是有意地控制某些可使能变迁的发射，以避免p e t “网系统陷入死 锁。这种限制资源分配的策略也具有一定的保守性。 死锁检测与校正方法 4 。这种方法的前提是允许系统发生死锁。在设计时不 会严格的要求系统活性，但是必须有发生死锁后的解锁方法。这种方法会使系统 达到较高的生产效率。旦足山丁允诈系统发生死锁，就限制了孩力法 ：许多重要 领域的应用。而且在设计j ；l ! 锁力法时要求设计人员对可能发尘死戮舱r t f j 克0 的认识，这也增加了系统设计的难度。 目前出现的死锁控制的几种策略在不同的场合都有应用，在死锁预防领域也 有许多方法可以利用。但是如何能够得到一个优化的死锁控制方法仍然是当前 p e t r j 网研究的热点问题。 1 2 本文完成的主要工作 本文主要对基于p c t r i 网的柔性制造系统的死锁预防问题展开了深入研究，专 注于p e t f j 网的一个子类s 3 p r 网的分析。根据s 3 p r 网的结构特点找到了一种从网 的结构获得严格极小信标的方法。由严格极小信标又可以得到网中的基本信标， 最后通过控制基本信标实现对f m s 的死锁预防。 为了实现死锁预防，s 3 p r 网中资源的分配仍然是我们关注的重点。为了更好 的分析资源使用状况，在s 3 p r 中引入资源回路的概念。根据资源回路可以得到 s 3 p r 网的严格极小信标。根据文献f 1 7 】可以将严格极小信标分为基本信标和从属 信标，对每一个基本信标添加控制库所和控制弧使其变为不变式可控。当所有的 基本信标全部受控后，从属信标的受控性由与之相关的基本信标保证，这样就可 以得到一个无死锁的p e t r i 网模型。本文的主要工作体现在下面几个方面： 证明了资源回路和极小信标之间的关系； 验证了组合的资源回路与极小信标的关系； 证明了可组合的极小信标组合后构成极小信标； 探讨了s 3 p r 网中基本信标的构成； 对几种求取信标的方法做出对比，探讨了各个方法的优缺点； 举例实现了f m s 的死锁预防控制。 6 一类p e t i i 网的信标求取方法及应用研究 总之本文深入研究了p e t r i 网的死锁预防策略，提出了求取信标的新方法并结 合基本信标理论对柔性制造系统实现了优化设计。文中对该方法所用到的相关定 理进行了证明，对该策略的优点进行了阐明。相信这些工作对从事相关领域的研 究具有一定的启发作用。由于时间有限以及个人的水平局限，文中难免一些不足 之处，敬请批评指正。 第二章p e m 网的基本概念 7 第二章p e t r j 网的基本概念 本章将介绍p 嘶网的基本概念【2 】【1 7 】【1 8 】，以及在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 】库所变迁网( 简称州r 网) 是一个四元组，= ( p tf ，叻，其中p 代表库所的集合，r 代表变迁的集合，并且尸和丁是有限非空和小相交的集合； f c ( p x 2 ) u ( z ，称为有向弧集；晰，一枞 o ，称为f 中弧上的权，州= 0 ，l ，2 ，。 称 r - ( p ，lf 叨为普通i 碉( o r d i l 坷r yn c t ) ，当且仅当v 蓐f ，h 奶= 1 ，普通网可 以记作= p ，t 叼。当| ，= 幼d g 驿狮 1 时，称 k ( p t 只叼为一般网幢e n e r a l n c t ) 。 【定义2 。2 】令= ( p ，l 只聊是一个网。 1 ) 的标识是映射 舡p t w ； 2 ) 个变迁延r 在m 下称为使能的，记为m 【f ) ，当且仅当，：m p 净讳弛0 ； 3 ) 若成立，则f 发射后，产生另一新标识m ，记为m 磅彬，有 j i f ( p ) 一 m ( p ) 一( b f ) 肘( p ) + 形( b f ) 埘( p ) 一形( p ，f ) + 缈( 细) 肘( p ) p m 。 p f i f p f n f 。 其它 4 ) 网从标识朋i 开始的所有可达标识的集合记为碰，蚴或肘o ) 。它是一个最 小集，即脑后r ( ，朋曲，旌r ( ，蛳) m 盼硝辛硝r ( 劬； 5 ) 当“，幻，岛z 时，啦n 如如称为发射序列，当且仅当存在标识肘i ， ，m 。 满足胁p ，) ； 6 ) 对于网和标识埘也( 肘j ) 称为一个网系统： 7 ) 网- ( p 瓦f 聊的关联矩阵定义为以p 和z 为序标豹矩阵【川：a ! - z ，z 是整 数的集合，且 8 一类p e t r i 网的信标求取方法及应用研究 【j 】( 另f ) = 一( p ，f ) ( 印) 一形( p ，f ) + ( p ) 0 p g t t p 门。t p e m 其它 【定义2 3 】令= ( 尸，tf ，聊是一个p e t r i 网，节点工p u 丁的前置集定义为 、= ) ，p u 丁lo ，工) f ) 。其后置集定义为并。= ， p u f l 瓴y ) 目。节点的集合王，p u r 的前置集( 后置集) 定义为? 而k u 朗? x ( 盯= l k 斛) 。 【定义2 4 】如果= ( p ，t ，聊是普通网，且v 炬li f i = = 1 ，则称是状 态机( s t a t em a c h i l l e ) 。 【定义2 5 】如果= ( p ，瓦f ，聊是普通网，并且有v p p ，瞄i _ p 。卜1 ，则称 足际谚! 罔( m a r k c dg m p h ) 。 【定义2 6 】如果个p e t f i 网系统( m 埘o ) 的旺意 个仉l 肼”亡节点“意 一个之问总存在一条连接路径，则称该网足强连通的。 【定义2 7 】如果一个p c t r i 网系统( 朋曲既是一个状态机又是强连通的，则称 其为强连通的状态机。 【定义2 8 】网= ( p ，l 只聊称为纯的，当且仅当一j0 ，) ，) ( p x d u ( 孤p ) ：0 ， 力f o ，z ) f 。 非纯网可以在保持动态性质不变的情况下转化为纯网。下面要讨论的网都是 纯网。 2 1 2p e t r i 网的活性及不变式 【定义2 9 】令= ( p ，tf 叻是一个网， 而是的一个标识 1 ) 一个变迁f 在标识胁下是活的，当且仅当v m r ( 锄，j m 鞫m 蚴使得 m 【力成立； 2 ) ( ，肘o ) 是死锁的，当且仅当，丑岖置肘i 【f ) 成立； 3 ) ( 如) 是无死锁的，当且仅当v j 盯r ( ，蚴，3 炬毋删成立； 4 ) ( ，慨) 是活的，当且仅当孔f 在标识肘i 下是活的； 5 ) ( ，) 是有界的，当且仅当 o ，协翻印( 蚴，坳p ：l 砌坶； 6 ) ( 胁) 是结构有界的，当且仅当对于任意的有限初始标识，它都是有界的。 值得说明的是，对于资源有限的实际系统而言，它的p e t r i 网模型一般都是结 构有界的。所有元素均为0 ( 1 ) 的列向量记为o ( 1 ) 。 【定义2 1 0 】令= ( p ，正只聊是一个网。 1 1 以p 为序标的列向量v ：p z 称为的p - 向量，z 是整数的集合。 2 ) 以丁为序标的列向量w ：z 兮z 称为的 向量。 3 ) 称p 向量j 是一个p - 不变式( 库所不变式) ，当且仅当如o 且，：m = 0 7 。 第二章p e t r i 嗣的基本概念 9 j 埘f = p 尸p 一o 称为j 的支撑。 4 1 称一个p - 不变式是极小的，当且仅当它的支撑中不包含任何其它p - 不变式的支 撑。如果没有特别声明，在本文中的p - 不变式都是极小p 不变式。 5 ) 称b 向量，是一个 不变式( 变迁不变式) ，当且仅当i ，- o 且嗍o = o 。i 堋l = f z 识f ) - o ) 称为，的支撑。 6 ) 称是被p - 不变式j 【l 不变式j ) 覆盖的，当且仅当坳尸：j ) 0 ( v f o ) 一0 ) 。 被p _ 不变式覆盖的的网也称为是保守的网。 【定义2 n 】( ，圳是一个网系统，( p lf ，聊。 1 ) 称一个非空集合s p 是一个信标( s i p h o n ) ，当且仅当苫s 成立； 2 ) 称一个非空集合s e p 是一个陷阱c t f a p ) ，当且仅当s j s 成立； 3 ) 称一个信标( 陷阱) 是极小的，当且仅当不存在其它信标( 陷阱) 足它的真了f i ； 4 ) 称p p 是被标识m 标记的，当且仅当m ) o 。称个集合s p 足坡h 、u 1 1 ， 标记的，当且仅当s 中至少有一个元素被m 标记。s 中的托肯数蛳9 = p 肘p ) ： 5 ) 不包含任何p - 不变式支撑的信标称为严格信标。一个严格信标有可能被清空； 6 ) 一个既是极小又是严格的信标，称为严格极小信标( s m s ) 。 2 1 _ 3p e 枉i 网的一些基本性质 【性质2 1 】网系统( ，胁) ，j 是= c 尸lf ，哟的一个p - 不变式，睚三r ( ，肘o ) ： 亡m i l l m 卟 【性质2 2 】髓系统( ，o ) ，是_ ( p lf ，聊的一个l 不变式，0j | l 中所有 的变迁发射一次，可能会使网系统回到初始标识。 【性质2 3 】网系统( 肘j ) ，= ( p ，l ，叨，难p 是一个信标，若| i i f 嚣( ，) ： 埘研_ o ，则s 以后永远不会被标记，称为被清空。 【性质2 4 】网系统( ，胁) ，- ( p ，l 只聊，5 留是一个陷阱，若埘酿( ，) ， l f 0 ，则s 以后总是被标记。 【性质2 5 】网- ( p ，lf 叻的p - 不变式j 的支撑j 既是一个信标又是一个 陷阱。 【性质2 6 】( ，蚴是一个网系统，其中商( p ，f ，聊，j 是一个p 不变式， s 口是的一个信标，那么此信标s 是在 f 0 下被弘不变式j 控制的，当且仅当 ， o 且对于所有的p 邓，j p ) = 0 成立，或等同地。， o 且 p e 砷酗) o ) 口。 如果s 是一个在肘i 下被只不变式j 控制的信标，则s 不可能被清空。也就是说， m 猷( ，胁) ：s 在标识肘i 下是被标记的。 【性质2 7 】( ，朋i ) 是一个普通网系统，= 以正d ，若在m 下是死( 锁) 的， 则所有未被标记的库所形成一个信标；如果网中没有信标可能被清空，则称， 1 0 一类p e 打i 网的信标求取方法及应用研究 ) 是无死锁的( d e a d l o c k f r c e ) 。 【性质2 8 】对于普通网系统( ，m 曲，= ( p td ，死锁的必要条件是所有的 极小信标都被清空。 该性质是一般死锁分析方法的基础。需要说明的是，本中主要讨论普通有界 网。除非特别说明，下文提到的网模型是普通有界网。 2 2p e t r i 网实例分析 在介绍了p e 啊网的基本概念和性质后，下面以图2 1 口为例来进行说明。 图2 1 口中的p e t d 网 f 职lf 聊，其中p = p l ，p 2 ，p 3 ，p 4 ，p 5 ，p 6 ，刃，p 8 ，p 9 ) ， ，_ f 1 ，如，“，f 5 ，f 6 。w i 三尹，矾f ) = 1 ，所以它是一个普通网，记作= ( 尸，r ，d 。 p 1 = f 6 ，_ 2 = f 1 ，p 3 = 如 ，p 4 = f 3 ) ，_ 5 = “) ，_ 6 = f 5 ，_ 7 = “ ，_ 8 = 幻，f 5 ， _ p 9 = f 2 ，坫，p 1 = f l ，p 2 = 屯) ，p 3 = f 3 ， p 4 = “ ，p 5 = f 5 ) ，p 6 = f 6 ，p 7 = 如 ，p 8 = f 2 ， “，p 9 = f 1 ，如 t 1 = 伽l ，p 9 ) ，。f 2 = 印，p 8 。= 仞3 ，p 7 ，“= 舳p 8 ，f 5 ： p 5 ，内 ，- f 6 = 邯) f 1 = p 2 ，f 2 = p 3 ，p 9 ) ，f 3 = p 4 肌) ，“= p 5 ，p 7 ) ，如= 协肌 珞= 如l ，p 9 ) 。 网有4 个极小p 不变式： ，1 = 1 ，1 ，1 ，1 ，l ，1 ，0 ，o ，o ，j 2 = 0 ，1 ，0 ，o ，0 ，1 ，0 。o 1 ， 局= o ，o ，l ，o ，1 ，0 ，0 ，1 ，0 ，j 4 = o ，o ，0 ，1 ，o ，0 ，1 ，0 ，o ) a 它们的支撑分别是： 岍0 = 伽l ，p 2 ，p 3 ，p 4 ，p 5 ，p 6 ，l 崛i i 船p 6 ，p 9 ，l 肌| l = 鼢d ，内 ，陋l 净 队p 7 。 p 图2 1 口一个p c t f i 网实例图2 。1 6 发射后的阿状态 第二章p e m 网的基本概念 1 1 网中有7 个极小信标：s 1 = p 6 ，p 7 ，p 8 ，p 9 ) ，& = 船，p 6 ，内，p 9 ) ，岛= p 2 ，p 6 ，p 9 ) ， & = 仞5 ，刃，p 8 ，& = 妇4 ，p 7 ) ，风= 伽3 ，p 5 ，p 8 ) ，岛= 仞l ，p 2 ，d ，肌，p 5 ，p 6 ) 。 以s l 为例，s l = l z p 舒1 p = _ 6 u p 7 u 0 恒u _ 9 = 如) u “ u 如，f 5 ) u 屯，f 6 ) = f 2 ，如，“，b f 6 ，s l 。= l ? p 6 乱p ；尹6 。l ，5 酊l 驷8 u p 9 = f 6 u f 3 u 恕，“) u f 1 ，f 5 = f 1 ，f 2 ，f 3 ，“，f s ，如 ，所 以0 1 c 5 1 。，故s l 是一个信标。 我们看到岛包含p 不变式厶的支撑，岛包含p - 不变式厶的支撑，& 包含厶 的支撑，岛包含 的支撑，因此这些都不是严格极小信标。网中的严格极小信标 为s 1 ，& ，函。 网的初始标识觚= 【5 ，o ，o ，o ，0 ，o 1 ，1 ，1 】，在状态慨下，n 可以触发。f 1 触发 后进入状态尬= 【4 ，1 ，o ，o ，o ，o ，1 ，1 ，o 】，记作肘j 【“ 地，如图2 1 6 所示。经过分析 我们知道该网共有1 1 个：状态，下面的图，十】表示了它们之间的l = f e 父系，川”姨忠 _ ；2 可以触发变迁f l 或“，触发f j 焉进入 如? 佚态系统将最终遗、je 曩_ 】并。o 态慨和鸠时如果触发变迁f ，系统也会进入潜在死锁状态眠和死锁状态m ，。 在进行p e 砸网设计时一定要阻止这些可能将系统带入死锁状态变迁的发射。 0 圈2 2 状态转化关系 由图中可以发现肘i = 【2 ，1 ，1 ，1 ，0 0 ，0 ，o ，o 】和胁= 【3 ，1 ，o ，o ，l ，o 1 ，o ，0 】没有后 续状态，系统进入这两个状态后没有变迁可以触发，系统于是进入死锁。眠和坼 中未被标识的库所构成信标伽5 ，p 6 ，p 7 ，p 8 ，p 9 ) 和 p 3 p 4 ，p 6 ，p 8 ，p 9 ，由于它们分别包 含s 1 和& ，因此它们不是极小信标。 网的关联矩阵【明为： 一类p e t r i 网的信标求取方法及应用研究 p l p 2 1 ) 3 p 4 n 】= p 5 p 6 p ? 1 ) 8 p 9 t lt 2t 3 t 4b 乜 - 100ool 1- 1oooo o1- looo ool- loo oool- 1o ooof ：ill oo- ll o o 011- 1lo 1lool1 2 3p c t r i 网中库所的分类 对p c t r i 网的库所进行分类主要是为了更好的对柔性制造系统建模。为了利用 p e t f i 网对柔性制造系统建模，需要分析柔性制造系统的基本要素。 一般情况下在一个制造系统中，原料总是从原料存储区出发经过物料运输系统 进入下一个生产环节。为了尽置提高生产效率，原料存储区最好能多储备一些原 料。但是过多的原料又会占用大量资金，为此根据不同的生产节拍，在原料区存 放的原料数不同，是一个变量。在p e 啊网中用闲置库所( 赴f f e 巾缸c c ) 来建模此类 对象。它可以定义为：p 称为闲置库所，当且仅当 f 和) 是一个变量。 生产系统中的机床、机器人、物料传输系统等在多个生产进程中可能共享的设 备在p e t “网中用资源库所( ，蝴愆卯肠) 来建模。由于系统设计完成后这些设 备的数目将不会发生改变，因此在p c t r i 网中称p 称为资源库所，当且仅当娲p ) 是一个正的常整数。 对于生产过程中的加工工序在p e 砸网中用操作库所( 删f f o 州咖) 来建模， p 称为操作库所，当且仅当m 妇) = 0 。 这样柔性制造系统中的基本元素，在p e t r i 网中都有相应的模型与之对应。这 样也将p e t r i 网中的库所分为了三类：闲置库所、操作库所和资源库所。它们的集 第二章p c m 网的基本概念 合分别用p ，尸，靠来表示。图2 1 口中p 三 融，p 3 ，p 4 ，p 5 ，p 6 ) ，斥= p 7 ，p 8 ，p 9 ) ，尸l l = 伽1 ) 。 在自动制造系统中，一个工序至少需要一个资源参与。从p e t d 网角度来看， d 即阳砌n p 缸钾和与之对应的r 啪h r 钾j 咖c e 构成一个尸- 不变式。同样，一个加工 原料要经过若干工序成为产品，所以脚肠俚和其对应的掣e m f f o n 巾如c e 也构成 一个p - 不变式。 一般地，s 是自动制造系统p c t r i 网模型肘0 的一个信标，我们有 f 0 2 。 以上对柔性制造系统和p e t r i 网的元素对应关系做简单介绍。应用p e t r i 网对柔 性制造系统建模，在下一章介绍s 3 p r 网时再举例做详细说明。 明。 2 4 小结 本章主要对p e t r i 删的基本概念及性质进行了叙述，并结合州“、九三m 进仃j 随 1 4 一类p e 哺网的信标求取方法及应用研究 第三章柔性制造系统的p e 仃i 网模型 根据应用的领域不同，为了研究方便，人们又根据p e 仃i 网的结构特点将其分 为很多子类。其中s 3 p r 网因其良好的系统模拟能力在对柔性制造系统的建模中得 到了广泛的应用。在本章第一节将首先介绍一个比s 3 p r 更大的p e 砸网子类资源 控制合并网，然后介绍s 3 p r 网的定义及柔性制造系统的建模过程。在第三节对本 章进行总结。 3 1 资源控制合并网 资源控制合并网( r c n m e r g e d1 1 e t s ) 7 】足 个比s 3 p r 了炎更人的【，h _ j 了炎， 也就是说s 3 p r 网包含在资源控制合并网中。资源控制合并网的些性质对于我们 设计s 3 p r 网的活性控制器很有用处。 【定义3 1 】一个资源控制网( r c n ) 是一个强连通的状态机( p ，瓦e 肘讲其中 存在一个且只有一个资源库所肼p ，使得m ) 一o ，而其余的库所称为操作库所。 【定义3 2 】一个变迁子网g = ( 匕，l ，f 4 ，肘砧是p e t r i 网g 的一个子网，它使 得任何p i 的输入和输出变迁都在集合死中。 【定义3 3 】通过公共变迁和公共变迁子网，把n 个资源控制网 g i g = ( b ，瓦， 磁o ) ，器1 ，2 ，咒) 合并起来得到一个p e t r i 弼g 音五e ，其中p = p l u u 最，r = 乃u u 瓦，圩l u u r ，若p 只，则瞄妇) 。很明显，在综合网模型g 中任意两个资源控制网的公共元素形成一个变迁予网。在下文，这样一个网模型 我们称为资源控制合并网。 一个资源控制合并网是状态机可分解的，每一个资源控制网都是一个状态机。 j e n g 等人【7 】都认为资源控制合并网是结构有界的。下面是关于资源控制网合并的 四个约束条件： 条件1 ：对于每一个公共变迁，最多存在一个输入库所是操作库所； 条件2 ：公共变迁子网不应该包含资源库所； 条件3 ：从综合模型g 中移去资源库所而得到的p e 岫网g 是一个无环图； 条件4 ：对于任何公共变迁，最多存在一个输出库所是操作库所。 下面的定理是【7 】的重要结论，从中我们可以很容易看出s 3 p r 网是一个资源控 制合并网。 【定理3 1 】假设约束条件1 3 成立，若当且仅当g 中没有信标可以被清空且 每个变迁至少发射一次，那么一个资源控制合并网g 是活的和可逆的，也就是说 每个变迁是潜在可发射的( p o t e n t i a l l yf r i a b l e ) 。 第三章柔性制造系统的p e 订i 网模型 【定理3 2 】假设约束条件1 - 4 成立，那么g 的任何变迁都是潜在可发射的。 【定理3 3 】假设约束条件1 4 成立，若当且仅当g 中没有信标可以被清空， 那么一个资源控制合并网g 是活的和可逆的。 【定理3 4 】假设约束条件1 - 4 成立，若g “( 岣= i p i ，那么一个资源控制合并 网( p ，le 蛳) 是活的和可逆的。 定理3 2 一般用来检验添加了控制器后，一个s 3 p r 网模型的活性是否成立。 3 2n i s 的p c t i ! i 网模型一s 3 p r 柔性制造系统一般是由多个如工设备和物料运送系统组成。由于在一个系统 中完成多种产品的加工，因此在f m s 中存在多个生产进程。零件按不同的生产要 求进入不同的生产进程。这些进程相互独立，在生产过程中对系统资源的需求睫 这些进程相互联系使系统成为一个有机的整体。然而由于系统中的资源自限，虫 机床，机器人等在f m s 中都是共享设备。而且由于系统中进程的并发性，如果不 能合理的安排资源使用顺序就有可能导致系统死锁。一量系统发生死锁，生产将 陷入停顿。 如果用p e 圩i 网来模拟加工进程，可以利用上一章中对p c 哦网痒所的划分用三 种库所分别对柔性黼造系统中不同元素建模。其中操律库所表示加工进程中的工 序，资源库所表示系统中的资源，资源库所中的托肯数表示可供使用该资源的个 数或加工能力，闲置库所表示系统中的原料托盘等。用变迁表示工序状态之间的 转换。 由文献【3 】提出的s 3 p r 网作为p c t r i 网的重要子类，可以为一大类f m s 建模。 下面的讨论将围绕s 3 p r 网进行。 【定义3 4 】f 3 卜个简单加工进程( s j m p l es e q u e n t i a lp f o c c s s ) s 2 p 是一个p e t r j 网小陪( p u 矿) ，t 靠 霸是的初始标识，矿称为闲置库所( 加工进程的开始和结束 工序状态) ，p p 称为工序状态库所。( ，埘磅满足以下条箨：( 1 ) 丹籼p 她脑舻0 ) 之1 ， 坳p ，m 妇) 胡：f 芍是一个强连通的状态机，即悯i f i 母1 = 1 ；( 3 ) 的每一个 回路包含。 【定义3 s l 设：妃ld 是一个网，设x 留u r ，那么盹- = ( p 赫了k 黝是盖 生成的子网，其中致= p n 矗艮= 吖，f x = f n ( 私。 【定义3 石l 习一冷据有资源的翁单加工进程( s 夸潮陋豫踟 c e s ) s 2 p r 是一个 网= ( p u p o ) u 际，。t d ， 而是的初始标识。