（机械电子工程专业论文）基于petri网结构分析的从属信标存在性研究.pdf

摘要 本文致力于研究p e t r i 网的一个子类- l s 3 p r ( l i n e a rs 3 p r ) 网的结构特 性，分析在何种结构下从属信标必然存在。 信标是网的结构特性，作为信标的子集严格极小信标( s t r i am i n i m a l s i p h o n , 简称s m s ) 更是能反映出网结构的活性，资源的不合理分配必然会导 致s m s 的出现。由各个顺序进程通过共享资源连接起来的s a p r 网系统可以 为一大类柔性制造系统( f l e x i b i l em a n u f a c t o r ys y s t e m , f m s ) 建模，由于其良 好的特性引起了人们的广泛兴趣。在其子类l s 3 p r 网中，资源的环形等待 是死锁出现的充要条件。 把由资源节点及之间的变迁组成的强连通子网抽象出来，并称之为资源 有向图。资源的循环等待在有向图中表现为圆圈的出现，称之为资源回路。 经研究发现，在l s 3 p r 网中s m s 与资源回路是一一对应的关系。 在s a p r ( s y s t e mo f s i m p l es e q u e n t i a lp r o c e s s e sw i t hr e s o u r c e ) 网中，正是 由于补集的存在导致了在网的进化过程中，s m s 被清空。依照s m s 的正 特征向量矩阵的特性，s m s 被分成基本信标、强从属和弱从属信标。任一 个从属信标的补集均可以被一组基本信标的补集线性表示，且组合关系完全 等同于该从属信标特征n 向量与该组基本信标特征弘向量之间的组合关系。 回路矩阵是一个资源有向图全部资源回路的代数描述，并且它与补集及t - 特征向量矩阵相互等价。因此可以方便地、直观地利用资源回路间关系来描 述必然存在丛属信标的一个网结构所需具备的条件。 经过分析大量存在弱从属信标的网结构及其资源有向图，总结并证明了 必然存在弱从属信标的资源有向图特性。通过资源有向图就能确定弱从属信 标的存在性，这为判断网的性质提供了一种简便快捷的方式。 关键词：资源回路l - s 3 p r 信标资源有向图p e t r i 网 a b s t r a c t t h i st h e s i si sd e v o t e dt ot h ec h a r a c t e ro fl i l l e 盯s 5 p r ( l - s p r ) n e t , as u b n e to f p e t r in e t s ，a n da n a l y z e st h en e c e s s i t yo f t h ee x i s t e n c eo f d e p e n d e n ts i p h o n s s i p h o ni so n ec h a r a c t e r i s t i co f an e t ，a si t ss u b c l a s s ，s t r i c tm i n i m a ls i p h o n ( s m s ) c a nr e p r e s e n ti t sl i v e n e s sm o r e i ti sj u s tt h eu n r e a s o n a b l ei e s o u l l 汜a l l o c a t i o nt h a t l e a d st oad e a d l o c k t h es y s t e mo fs i m p l es e q u e n t i a lp r o c e s s e s 弼t l lr e s o u r c e ( s 3 p r ) c a nm o d e lf o rab i gc l a s so ff l e x i b l em a n u f a c t o r ys y s t e m ( f m s ) ，a r o u s e p e o p l ea b r o a da t t e n t i o nd u et oi t sf a v o r a b l ec h a r a c t e r i s t i c i ni t ss u b c l a s s ，l - s 3 p r , t h ec i r c u l a r w a i tt u r n st ob es u f f i c i e n ta n dn e c e s s a r yc o n d i t i o no f d e a d l o c k t h es t r o n g l yc o n n e c t e ds u b n e tw h i c hi sc o m p o s e do fl e 翻) u r c en o d e sa n dt h e i r t r a n s i t i o n sw e r ea b s t r a c t e da n dc a l l e da sr e s o u r c ed i r e c t e dg r a p h t h ec k c u l a rw a i t o fr e s o a r c ee x p r e s s e si t s e l fb yt h eo c c u r r e n c eo fc i r c l ei nr e s o u r c ed i r e c t e dg r a p h ， n a m e da sr e s o u r c ec i r c u i t a f t e rs t u d y , t h ea u t h o rd i s c o v e r st h a ts m s sc o r r e s p o n dt o r e s o u r c ec i r c l e so n eb yo n ei na nl - s 3 p rn e t i nas 3 p rn e t , i ti se x a c t l yt h ee x i s t e n c eo fc o m p l e m e n t a r ys e tt h a ti n d u c e st h e s m st ob ee m p t i e dd u r i n gan e t se v o l u t i o n t h es m s sw e r ed i v i d e di n t o e l e m e n t a r y , s t r o n g l ya n dw e a k l yd e p e n d e n ts i p h o i l sa c c o r d i n gt h e i rm a t r i xc h a r a c t e r o ft - c h a r a c t e r i s t i cv e c t o r e v e r yc o m p l e m e n t a r ys e to fad e p e n d e n ts i p h o nw o u l db e l i n e a r l ye x p r e s s e db yt h ec o m p l e m e n t a r ys e t so fi t se l e m e n t a r ys i p h o i l s ，a n dt h e c o m b i n e dr e l a t i o nc o u l db ee q u a t e de n t i r e l yw i t l lt h a tb e t w e e nt - c h a r a c t e r i s t i c v e c t o ro fd e p e n d e n ta n di t se l e m e n t a r ys i p h o n s c i r c l em a t r i xi st h ea l g e b r a i c d e s c r i p t i o n o fa l lt h er e s o u r c ec i r c l e si nad i r e c t e dg r a p h , a n de q u i v a l e n c e r e c i p r o c a l l yt ot h a to n eo fc o m p l e m e n t a r ys e ta n dt - c h a r a c t e r i s t i cv e c t o r a n dt h e n , t h er e l a t i o n sb e t w e e nr e s o u r c ec i r c l e sc a nb eu s e dt od e s c r i b et h er e q u i r e ds t r u c t u r e c o n d i t i o ne x p e d i e n t l ya n di n t u i t i v e l yw h e nad e p e n d e n ts i p h o ni n e v i t a b l ye x i s t s b ya n a l y z i n gp l e n t yo fn e ts t r u c t u r e sw h i c he x i s td e p e n d e n ts i p h o na n dt h e i r r e s o u r c ed i r e c t e dg r a p h ，t h ec h a r a c t e r i s t i co fd i r e c t e dg r a p ht h a ti n e v i t a b l ee x i s t s d e p e n d e n ts i p h o nw a ss u m m a r i z e da n dp r o v e d t h ee x i s t e n c eo fd e p e n d e n ts i p h o n c o u l db ee n s u r e dt h r o u g hr e s o u r c ed i r e c t e dg r a p h ，t h i ss u p p l yac o n c i s ea n dq u i c k m e t h o dt o j u d g et h ep r o p e r t yo f an e t k e y w o r d ：r e s o u r c ec i r c l e l - s 3 p r s i p h o n s r e s o u r e ed i r e c t e dg r a p h p e t r in e t s 独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： ) 虿l 姆! 恤 日期j 翌日上兰互 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。本人保证 毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本人签名：阂嗣，彩够 导师签名 日期：跏 7 ，蟛 第一章绪论 1 1 研究背景与意义 面对全球技术、经济、市场变革的机遇与挑战，技术、经济将成为世界各国竞 争的焦点和社会发展的主要动力对制造业来说，竞争的核心将是新产品和新的 制造技术的竞争。从2 0 世纪7 0 年代开始，p e t r i 网以其能够模拟系统的并发和冲 突行为以及反映系统动态特性而受到了广泛关注。 p e t r i 网的概念最早是在1 9 6 2 年c a r l a d a mp e t r i 的博士论文中提出来的。作为 一种控制系统的设计手段，制造系统或者更一般地说工厂自动化是p e t r i 网应用的 一个最早领域，也是较为成功的一个领域。早在1 9 7 2 年，就有人研究p e t r i 网应用 于生产方案的分析。在工厂里材料( 部件) 被加工处理，然后这些部件被装配， 相同的部件经常被批处理。 在较早的生产线中，产品部件由一个传送装置驱动，工人们同步操作，每人完 成自己的规定任务。这样的制造系统仅生产一类产品。在任务车 a - g o bs h o p ) 的生 产方式中，对于每一个产品定义一个生产路i 刍( p r o d u c t i o nr o u t e ) 。路由描述了一个 机器操作序列，序列并不由机器的物理位置所限定，而是与工序相对应。这样的 系统可以生产多种产品，它的操作可以是异步的，有一定的灵活性，但效率不高【”。 柔性制造系统( f l e x i b l em a n u f a c t u r es y s t e m ，f m s ) 吸取生产线的高效率和任务 车间的柔性来满足高效率低成本的要求。一个f m s 包括：一组灵活的机器，一个 自动化的传送系统和一个复杂的决策系统，以决定在每一时刻每一台机器必须做 什么。柔性的机器有执行多种操作的能力，它们有自动工具存取系统和制造程序 加载能力。自动传送系统要求能够将部件传送到下一个操作执行的机器位置，不 管机器的物理位置在哪里。决策系统允许新的产品和路有的引进，容忍机器失效 和优化机器的利用率。一个f m s 由制造单元构成，每一单元包括一些灵活的机器、 一些局部的工具、部件的存储设置及一些传输设备在单元和全局传送系统之间传 递部件和工具。 在f m s 1 0 】【l l 】【16 】【】7 】【1 8 l 中，各种工件按照一定的节拍，在离散时间点上进入系统， 系统对它们进行并行加工处理，各加工进程共享一定数量的资源，如数控机床、 工业机器人、夹具、小车等。各种工件有自己的特殊加工路径，即资源需求序列 在加工过程中，各种工件的并行处理竞争有限的资源，从而可能导致系统的运行 陷入死锁之中。构建良好的p e t r i 网模型，是对f m s 进行建模设计、控制、确认、 仿真及性能分析的第一步。在这种情况下，如何快速判断系统的活性，如何从网 2 基于p e t r i 网结构分析的从属信标存在性研究 模型结构和配置的角度，在设计和调整阶段避免死锁，以及如何对存在问题的网 模型进行控制，都是需要深入研究的问题。 在一个制造系统中，计算机可用于许多功能的实现【1 9 1 。计算机集成制造 ( c o m p u t e ri n t e g r a t e dm a n u f a c t u r e ，c i m ) 意味着所有这些功能都完全集成起来。这样 的集成需要两个设置：一个局部网络支持通信，一个全局技术数据库存储技术数 据。必须被集成的三个主要功能是：计算机辅助工程( c o m p u t e ra i d e de n g i n e e r i n g ， c a e ) ，计算机辅助设计( c o m p u t e ra i d e dd e s i g n ，c a d ) 和计算机辅助制造( c o m p u t e r a i d e dm a n u f a c t u r e ，c a m ) 。 区分c i m 和f m s 是重要的，c i m 系统是高度自动化的系统，它同工厂自动化 类似，但不意味着系统是柔性的。另一方面，f m s 不必是完全自动化的。各种控 制能力可以存在，它们的集成可由管理人员执行或者决策制作过程可能是自动的， 但局部操作需由熟练工人手工完成。非常明显，一个熟练的工人比任何自动化机 器更加有柔性【1 9 1 。 p e t r i 网在f m s 系统模型中应用有一个重要的优点，它可以从设计的第一步到 系统的实现提供统一的模型工具。p e t r i 网模型提供： ( 1 ) 图形的、准确的形式描述，这可以使设计者、拥有者和用户之间进行系统 行为的深入对话： ( 2 ) 怠好定义的理论，它可进行模型性质( 活性、公平、有界等) 的验证； ( 3 ) 性能评价的理论和方法； ( 4 ) 系统实现技术，包括实时控制软件的代码产生技术。 p e t r i 网是可应用到很多系统和领域的图形和数学模型工具。p e t r i 网是信息处 理系统描述和模型的有力工具之一，它的主要特征包括：并行、不确定性、异步 性和分布描述能力和分析能力。作为图形工具，p e t r i 网除了具有类似流程图、框 图和网图的可视描述功能外，它还可以通过标识( t o k e n ，有时也称为拓肯) 的流 动模拟系统的动态行为，所以可以说，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 网系统模型的框架上完成各项任务。在这一点上，其它图形或数学工具则 不具备如此的功能。系统性能评价方法【1 9 1 ，尤其是排队论分析方法的发展和所遇 第一章绪论 3 到的问题，包括并行系统的资源共享描述和非乘积解的问题，给p e t r i 网应用领域 的拓展和发展带来了勃勃生机。从8 0 年代初随机p e t r i 网提出以来，性能评价已成 为p e l r i 网最成功的应用领域之一。 从1 9 8 5 年起，相关p e t r i 网和性能模型的国际研讨会也开始召开。在随机p e t r i 网简短的发展历史中，它的应用范围已经超出了计算机科学，成为研究离散事件 动态系统的一种有力工具。很有前途的应用领域包括柔性制造与工业制造系统、 离散事件系统、计算机网络、分布式软件系统、分布式数据库系统、并行和并发 计算系统、多处理机系统、容错与故障诊断系统、办公自动化系统和决策模型等。 1 9 7 0 至1 9 7 5 年，m i t 的计算结构研究小组积极参与p e t r i 网相关的研究。1 9 7 5 年7 月在m i t 举行了第一次p e t r i 网和相关方法的研讨会。1 9 8 1 年p c t c r s o n 出版了 第一本p e t r i 网方面的书，1 9 8 5 年出版了第二本p e t r i 网专著，到现在己出版了包 括高级网在内的许多p e t r i 网专著。从1 9 8 0 年召开第一次p c 仃i 网理论和应用的国 际研讨会以来，每年一次的国际研讨会连续不断。p e t r i 网理论和应用的研究成果 大部分集中在会议论文集中。从1 9 8 5 年起，关于p e t r i 网和性能模型的国际研讨会 也开始召开，这个研讨会每两年召开一次。近年来，p e t r i 网的论文已大量出现在 各种学术年会和期刊上。 p e t r i 网的理论也在不断地充实和完善。p e t r i 网研究的系统模型行为特性包括： 状态的可达性( r e a c h a b i l i t y ) 、库所的有界性( b o u n d e d n e s s ) 、变迁的活性( 1 i v e n e s s ) 、 初始状态的可逆性( r e v e r s i b i l i t y ) 、标识之间的可达( r e a c h a b i l i t y ) 、变迁之间的坚挺 ( p e r s i s t e n c e ) 、事件之间的同步距离( s y n c h r o n i cd i s t a n c e ) 和公平性( f a i r n e s s ) 等。p e t r i 网模型的主要分析方法依赖于：可达树、关联矩阵和状态方程、不变式( i n v a r i a n t s ) 和分析化简规则。p e t r i 网的抽象、描述能力也不断地向纵向和横向发展。 p e t r i 网作为一种数学方法，在离散事件系统建模、分析、性能评价和控制设计 中得到了广泛的应用。柔性制造系统作为一种典型的离散事件系统一直是p e t r i 网 的重要应用领域。在柔性制造系统中，不同类型的原料在离散的时间点进入系统 进行加工，它们共享诸如机床、机器人、夹具等有限的资源。每种原料按照特定 的生产流程来使用系统中的资源。所有的生产流程并发执行，这样便会引起共享 资源的竞争。资源竞争往往会产生死锁，此时两个或多个工序便会分别等待其它 工序释放资源。死锁通常出现在一个系统的几个并行进行的复杂加工进程的最终 状态，我们一般很难预先知道系统在什么情况下出现死锁。所以提出一种有效的 柔性制造系统控制策略，使系统不再发生死锁十分必要。在处理各种不同的柔性 制造系统时，人们很关心如何有效处理死锁1 2 ”。 j e z p e l e t a 等人提出了s 3 p r 网，并阐明可以通过限制资源分配系统来防止死锁 的发生，从p e t r i 网结构的角度研究死锁，开创了一种新的控制策略。通过给s 3 p r 网中的每个严格极小信标( s m s ，s t r i c tm i n i m a ls i o h o n ) 添加一个控制器就可以使整 基于p e t d 网结构分析的从属信标存在性研究 个网变活，而无须计算该网所有的信标。不幸的是，s m s 的数量在最坏的情况下 呈指数级增长( 与网结构的维数) 。z w l i 拓展了这种策略，提出了基本信标理 论。许多控制策略和方法，均是从网结构的角度( 信标，s m s ，资源回路等) 提 出新的解决办法的【2 1 】1 1 2 7 1 1 3 0 】【3 嘎 从资源分配的角度结合图论的理论研究p e 砸网的结构特性，并从中发现结构 特性与网的活性、可控性等的关系，这是一种直观的新的视1 2 2 2 3 2 5 1 1 2 6 1 2 8 1 1 2 9 。本 文正是基于这样的思路，通过研究网的s m s 与资源回路的关系，讨论了当弱丛属 信标必然存在时的一个p e t r i 网模型所必需的结构特性。 在l - s 3 p r 1 】资源的循环等待是引起死锁的充分必要条件，当死锁产生时可通过 添加控制器使网变活。【2 】【8 】首先提出基本信标，将p e t r i 网中的可被清空信标，也 即将s m s 分为基本信标和从属信标，并证明了仅对基本信标添加控制库所，通过 调整基本信标的控制深度就可以保证从属信标的可控性，大大简化了控制器的设 计。当一个网系统存在从属信标时，基本信标的选择并不唯一，不同的选择策略 会导致不同从属信标的种类和数量。在同样的网结构下，产生弱从属信标越少， 其受控网具有更多的可达状态数。 4 】从资源回路的角度考虑，给出了适用于s 3 p r 3 网结构的一种基本信标快速求取算法无需计算整个网结构的信标，就可确定 其基本信标。【9 】提出一种基本信标的选取方法，该方法能保证网结构具有最多的 强从属信标，对网结构添加控制库所后的受控网，其状态数达到最大。我们尽量 避免弱从属信标的出现，以使网结构受到限制最小，可达状态数最多，在f m s 表 现为高效率，正是人们所期盼的。 在某些l - s 3 p r 网结构中，无论怎么选取基本信标都会存在弱从属信标，也就 是说从属信标的出现部不依赖于基本信标的选取。本文致力于这方面的研究，发 现了这样的结构，并用一组约束条件把其资源有向图直观地描述出来。l s 3 p r 网 对应的资源有向图只要满足这组约束条件就会存在弱从属结构，这为建模者提供 了一个非常直观的判断依据。 1 2 本文完成的主要工作 本文从结构的角度研究p e t r i 网的一个子类l s 3 p r 网的结构特性，分析并 总结了在何种结构下从属信标尤其是弱从属信标的必然存在性。 信标是网的结构特性，作为信标的子集严格极小信标( s t r i c tm i n i m a ls i p h o n ，简 称s m s ) 更是能反映出网结构的活性，资源的不合理分配必然会导致s m s 的出现。 由于s m s 没有任何p 不变式的支撑，其标识是不守恒的，并且会不断地减少，在 网的运行过程中可以被清空。正是s m s 的存在使网模型出现死锁，并最终导致了 第一章绪论 网系统无法再继续运行。 各个顺序进程通过共享资源连接起来的s 3 p r 网系统可以为一大类柔性制造系 统( f m s ) 建模，由于其良好的特性引起了人们的广泛兴趣。在f m s 中，进程拥有 已分配到的资源，并且在申请到用于改变其状态的新资源之前不释放。进程使用 资源次序的不合理，造成了资源的循环等待。在共享公共资源的并行系统中，死 锁发生需要满足四个必要条件。f m s 本身的特性保证了前三个的成立性，即资源 互斥、请求与保持和不剥夺条件均成立。这样在s 3 p r 及其子类l s 弧中，资源 的循环等待便成了死锁存在唯一的必要条件。 本文重点研究的l s 3 p r ，还有另外一个重要特质资源的循环等待也是存 在死锁的充分条件，所以在l s 3 p r 中资源的环形等待就成了死锁出现的充要条件。 把由资源节点及之间的变迁组成的强连通子网抽象出来，并称之为资源有向 图。资源的循环等待在有向图中表现为圆圈的出现，称之为资源回路。在一个网 中它可能不止出现一次，那么相应的资源有向图中会存在多个资源回路。经研究 发现，在l - s 3 p r 网中，s m s 与资源回路是一一对应的关系。任意给出一个资源回 路，便能推导出唯一的s m s 。从网模型抽象出来的资源有向图隶属于图论的范畴， 是网结构资源分配情况的具体表现。验证网结构的是否存在循环等待，便相当于 在其对应的资源有向图中证实是否出现了资源回路。由于图论现有的运算不足以 描述资源有向图间的关系，一种多集和运算被提出并恰当运用于描述了有向图特 性。 在s 3 p r 网中，信标与它的补集构成一个p - 不变式。正是由于补集的存在导致 了在网的进化过程中，s m s 被清空。依照s m s 的正特征向量矩阵的特性，把s m s 分成基本信标，强从属和弱从属信标，并且只对基本信标添加控制库所就可以保 证网系统的活性。任一个从属信标的补集可以被一组基本信标的补集线性表示， 且组合关系完全等同于该从属信标特征弘特征向量与该组基本信标特征工向量之 间的组合关系。在一个网结构中，补集矩阵与正特征向量矩阵完全等价。由于弱 从属信标的复杂性和代表性，它成了本文的研究重点。 回路矩阵是一个资源有向图全部资源回路的代数描述，由资源回路与s m s 的 对应关系，很容易得出回路矩阵与补集矩阵等价的结论。 作者发现了回路矩阵与f 特征向量矩阵之间的等价关系。因此可以方便地直观 地利用资源回路间关系描述，当一个网结构必然存在弱丛属信标时所需具备的结 构条件。 经过分析并研究了大量存在弱从属信标的网结构及其资源有向图，总结并证明 了必然存在弱从属信标的资源有向图特性。通过资源有向图就能确定弱从属信标 的存在性，这为判断网的性质提供了一种简便快捷的方式。 由于时间仓促，加上作者认识水平有限，文中还有很多方面有所欠缺，敬请批 6 基于p e t r i 网结构分析的从属信标存在性研究 评指正。 第二章p e t r i 网的基本概念及数学基础知识 本章首先给出了一些矩阵与向量的一些基本知识【1 2 1 1 2 0 1 ，为后面章节的讨论和 理解奠定了基础：重点讨论p e t r i 网基本概念的形式定义1 2 6 1 1 7 ，以及后面所要用到 的一些定理和推论。这些基本概念在整个p e t r i 网的学习过程中都用到，是正确理 解p e t r i 网的基础。 2 1 数学基础知识 【定义2 1 】置y 是两个集合，当x 是】，的一个子集时，记为x c _ y ，包括石 等于y o 当x 是y 的一个子集，当x 不等于y 时，记为x c y ox y 表示不属于y 但属于z 元素的集合。 【定义2 2 】由m x n 个数a - j ( i = 1 ，2 ，m ；j = 1 ，2 ，n ) 排成的m 行n 列数 表 a = a 1 i口1 2 a 2 10 2 2 口m 1a m 2 q 。 口2 月 口m 称为m 行n 列矩阵，简称m x n 矩阵，记为 a m n 或a = ( a 1 1 h 。n 在多数情况下简记为 a 或a = a , j 【定义2 3 】设a 为m x n 矩阵，任取a 的r 行和r 列，位于这些行与列相 交处所构成的r 阶行列式，称为矩阵a 的r 阶子式。 【定义2 4 】设a 为m x n 矩阵，如果在a 中至少存在一个r 阶子式不为零， 而所有大于r 阶的子式全为零，则称矩阵a 的阶为r ，记为r a n k ( a ) - - - r 。 【定义2 5 】设a 为m x n 矩阵，若r a n k ( a ) = m i n ( m ，n ) 则称a 为满秩矩阵； 若r a n k ( a ) 玎协，f ) ； 3 ) 若g o 成立，则t 发射后，产生另一新标识凹，记为脚， ，有 肘7 ( p ) = 肘( p ) 一形( p , t ) m ( p ) + w ( p , t ) 肘( p ) 一w ( p , t ) + ( t , p ) 肘( p ) p m p t l t p f n 广 其它 4 ) 网从标识m o 开始的所有可达标识的集合记为r ( ，m o ) 或m o d 。它是一 个最小集，即m o e r ( n ，m o ) ，m e r ( ，m o ) a m 【f m m 罔，肘j ) ； 5 ) 当t l ，f 2 ，岛丁时，俨t i t 2 岛称为一个出现序列，当且仅当存在标识m o ， ，鸠满足m o 【t 1 ) 心) ； 6 1 对于网和标识m o ，( i v ，m o ) 称为一个网系统； 7 ) 网n = 护，nf ，叻的关联矩阵定义为以p 和丁为序标的矩阵m ：p x 丁与z ， z 是整数的集合，且 i o 基于p e t r i 网结构分析的丛属信标存在性研究 【】( b f ) = 一矽( 口f ) r e ( t , p ) 一r e ( p j f ) + ( p ) o p 山 p f 。r p 。t l i 。 其它 【定义2 1 4 1 如果= 妒，lf ，r r ) 是普通网，且v f l l = l 门= 1 ，则 称是状态机( s t a t em a c h i n e ) 。 【定义2 1 5 】如果一个p e t f i 网系统c ，m o ) 的任意一个节点和其它节点中的 任意一个之间总存在一条连接路径，则称该网是强连通的。 【定义2 1 6 1 如果一个p e t f i 网系统( m o ) 既是一个状态机又是强连通的， 则称其为强连通的状态机。 【定义2 1 7 1 如果；( p ，乃f ，叨是普通网，并且有v p ，i i = ip i _ 1 ， 则称是标识图“n a r k e dg r a p h ) 。 【定义2 1 8 网= 妒，乃只助称为纯的，当且仅当，3 ( x ，力( p x d u ( t x p ) ： o ，力f 以功e f 。 非纯网可以在保持动态性质不变的情况下化为纯网，下面要讨论的网都是纯 网。 【定义2 1 9 1 令n = 妒，乃nw ) 是一个p e t r i 网，节点x e p u t 的前置集 定义为? 垆 y p u t l ( 弘功毋。其后置集定义为，= 抄p u t i o ，力毋。节点的 集合h _ c p ut 的前置集( 后置集) 定义为w = u ，。n x ( h 。= u ；。x 3 。 2 2 2p e t r i 网的活性及不变式 【定义2 2 0 l 令= 妒，lf ，聊是一个网，m o 是的一个标识，有 1 ) 一个变迁t 在标识m o 下是活的，当且仅当v j l f r r ( ，m o ) ，3 m e r ( ，m o ) ： m i t ) 成立： 2 ) ( ，g o ) 是死锁的，当且仅当1 3 ，置m oi ，) 成立； 3 ) ( ，m o ) 是无死锁( 弱活) 的，当且仅当v m r ( n ，m o ) ，3 t t ：m 【f ) 成立； 4 ) ( i v ，g o ) 是活的，当且仅当v t t ：t 在标识m o 下是活的； 5 ) ( ，m o ) 是有界的，当且仅当3 k i m 0 ，v m er ( n ，m o ) ，v p e p ：肘) 鱼； 6 ) ( ，m o ) 是结构有界的，当且仅当对于任意的有限的初始标识，它都是有界 的： 值得说明的是，对于资源有限的实际系统而言，它的p e t r i 网模型一般都是结 构有界的。所有元素均为0 0 ) 的列向量记为0 0 ) 。 【定义2 2 l 】令n = 妒，乃f ，聊是一个网。 1 ) 以p 为序标的列向量 ，= p - - z 称为的p 向量； 2 ) 以r 为序标的列向量咿：t - - z 称为的t - 向量： 第二章p e t r i 网的基本概念及数学基础知识 3 ) 称p - 向量j 是一个p 不变式( 库所不变式) 当且仅当j o 且1 t i n = 0 t 。 0 = p e p l j ( p 净o ) 称为j 的支撑； 4 ) 称一个p - 不变式是极小的当且仅当它的支撑中不包含任何其它p - 不变式的 支撑，且其元素互质； 5 ) 称互向量_ r 是一个孓不变式( 变迁不变式) 当且仅当j - , e 0 且i n j - - 0 。 m f f 丁| 以僻o ) 称为_ ，的支撑； 6 ) 称是被p - 不变式jf r - 不变式j ) 覆盖的当且仅当v p e p ：i ( p ) o ( v t e t ： 以f 净o ) 。 本文中的p 不变式，如果没有特别声明，则都是极小p - 不变式。被p 不变式覆 盖的的网也称为保守的网。 【定义2 2 2 】令( ， 而) 是一个网系统，= ( p ，t ，f ，矽) ，有 1 ) 称非空集合踺? 是一个信标( s i p h o n ) ，当且仅当苫s 成立； 2 ) 称非空集合s 耋p 是一个陷阱( t r a p ) ，当且仅当苫蓼成立； 3 ) 称一个信标( 陷阱) 是极小的，当且仅当不存在其它信标( 陷阱) 是它的真子集； 4 ) 称p e p 是被标识肘标记的，当且仅当旭咖o ，称一个集合s _ c e 是被标识 肘标记的，当且仅当s 中至少有一个元素被m 标记，s a f f o 标识数 载驴写。p m ( 力； 5 ) 不包含任何p 一不变式支撑的信标称为严格信标，一个严格信标有可能被清 空： 6 ) 一个既是极小又是严格的信标，称为严格极小信标( s t r i c tm i n i m a ls i p h o n ， s m s ) 。 2 2 3p e t r i 网的一些基本性质 【性质2 3 】网系统( ，m o ) ，i 是= 妒，乃f ，聊的一个p 不变式，v m e r ( n , m 心：i t m = 1 1 m o 。 【性质2 4 】网系统( ，m o ) ，j 是= 妒，lf ，聊的一个正不变式，1 ，i 中 所有的变迁发射一次，可能会使网系统回到初始标识。 【性质z5 】网系统( ，m o ) ，n = p ，l 凡) ，_ s c _ e 是一个信标，若3 m e r ( n , 捣) ：坝垆o ，则s 以后永远不会被标记，称为被清空。 【性质2 6 】网系统( m o ) ，= ( p ，t ，f ，缈) ，s 耋? 是一个陷阱，若3 m e r ( n , m o ) ，m ( s ) 0 ，则s 以后总是被标记。 【性质2 7 】网= ( p ，兀，聊的p - 不变式j 的支撑i l 川l 既是一个信标又 是一个陷阱。 【性质2 8 1 ( ，g o ) 是一个网系统，其中- c p ，t 只叻，i 是一个尸不变 式，_ s c _ e 是的一个信标，那么此信标s 是在m o 下被p 不变式j 控制的，当且仅当 1 2 基于p e t r i 网结构分析的丛属信标存在性研究 i 。m o o 且对于所有的p e p 峪，j ( 力翊成立，或等同地，j1 m o o 且扫纠 j ( p 瑚) 量吼如果s 是一个在m o 下被p 一不变式j r 控制的信标，则s 不可能被清空， 也就是说，v m r ( n , m o ) ：s 在标识m o 下是被标记的。 【性质2 9 1 ( ，m o ) 是一个普通网系统， 辟( p ，l d ，若在膨下是死( 锁) 的，则所有未被标记的库所形成一个信标；如果网中没有信标可能被清空，则 称( ，m o ) 是无死锁的( d e a d l o c k f r e e ) 。 【性质2 1 0 1 对于普通网系统( ，肘) ，_ ( p ，lf ) ，死锁的必要条件是所有 的极小信标都被清空。 该性质是一般死锁分析方法的基础。需要说明的是，本中主要讨论普通有界 网。除非特别说明，下文提到的网模型是普通有界网。 2 3 自动制造系统的p e t r i 网模型 制造系统p e t r i 网模型中的库所可分为三类，假定- ，t ，) 是一个制造系统 的网模型，p 是一个库所， 而是的初始标识。 p 称为o p e r a t i o n - p l a c e ，当且仅当肘“力= o 。p 称为r e s o u r c e - p l a c e ，当且仅当 隅( 力是一个正的常数( 整数) 。p 称为i d l e - p l a c e ，当且仅当m o ( 力是一个变量。 o p e r a t i o n - p l a c e ，r e s o u r c e - p l a c e 和i d l e - p l a c e 与初始标识相关且具有明显的物理含 义。 自动制造系统中o p e r a t i o n - p l a c e 又称为操作库所，用于建模一个任务包含的加 工工序。r e s o u r c e - p l a c e 又称为资源库所，用于建模机床，机器人，物料传输系统 等。i d l e - p l a c e 又称为闲置库所，用于建模加工原料，夹具和托盘等。一个p e t r i 网 中的o p e r a t i o n - p l a c e ，r e s o u r c e - p l a c e 和i d l e - p l a c e 的集合分别记为j p ，靠，凡。例 如，图2 2 中p = p 2 ，p 3 ，p 4 ，p 5 ，p 6 ，p 7 ，p s ，p g ) ，玮= 0 ，e 0 是闲置库所集合， b ) p s = u ，j i 路，心n 脚，并且i j ，n 是加工库所集合， c ) p r = r l ，r 2 ，n ) ，n 0 ，p r 是资源库所集合： 2 ) t = u 净l 。r ，r n ，中，并且i j ，丁是变迁库所集合； 3 ) 对任意的i l ，2 ，k ) 由 助1 ) up s ur 产生的子网1 是一个强连通状态 机，因此每个环都包含了 助。) 和并且对任意的p c ，f ，i 矿i _ l ； 4 ) 对任意的i 1 ，2 ，k ) ，v p e 风。，。n 聊”h e r 并且l - t , n f 1 ； 5 ) 是强连通的。 每一个子网都被定义为一个线性简单加工进程( l i n e a rs i m p l es e q u e n t i a l p r o c e s s ，l - s 2 p ) ，各个子网通过共享资源构成整个l s 3 p r 网。通过不允许加工库所 p e 风存在分支，即i ，l = 1 ，保证资源集合的使用是线性和简单的，故称其为“线性 基于p e t r i 网结构分析的丛属信标存在性研究 ( l i n e a r ) ”s 3 p r 网模型。 图2 2 是个有趣的例子，它属于s 3 p r 子类，因i p 9 1 = 2 1 故不属于l s 3 p r 网模 型。 【定义3 7 】靠是= ( p d u 尽u 尸岛ld 的资源集合，对某个给定的p p 岛 n 忙 啊，则p 使用了资源知。对某个给定的r e p r ，肿，n b 称为资源，的持 有者，记坝r i ) u h ( r 2 ) u u h ( r m ) 为t 3 ，e s r h ( r ) ， n ，r 2 ，r m _ c p r 1 1 。 【性质3 1 】资源持有者与资源的并集，即n ( o u r 是个p 不变式的支撑【3 1 。 a )b ) c )