（管理科学与工程专业论文）基于petri网的产品开发过程建模及系统性能分析.pdf

摘要 摘要 企业为了在激烈的市场竞争环境下取得成功，必须缩短产品的开发周期， 同时还要保持产品的高质量。由于现代产品复杂度的提高和新产品开发模式的 应用，给产品开发过程管理带来了巨大的挑战。为了对产品开发过程进行分析、 改进和管理，一个能够准确地描述和分析产品开发活动和信息流动的产品开发 过程模型己成为成功实现产品开发的重要手段。而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 网；产品开发；工作流；可靠性；性能分析 a b s t r a e t a b s t r a c t i no r d e rt os u c c e e di nt h ei n c r e a s i n g l yf i e r c em a r k e tc o m p e t i t i o n , t o d a y s c o m p a n i e sh a v es h o r t e nt i m e - t o m a r k e to fp r o d u c t s ，w h i l et h e ya l s os h o u l dm a i n t a i n p r o d u c t s h i g hq u a l i 够m o r e o v e r , t h ei n c r e a s i n go ft h ep r o d u c t sc o m p l e x i t ya n dt h e a d o p t i o no ft h en e wp r o d u c td e v e l o p m e n tp a t t e r n sh a sb r o u g h tg r e a tc h a l l e n g e st o p r o d u c td e v e l o p m e n tm a n a g e m e n t ag o o dp r o d u c td e v e l o p m e n tp r o c e s sm o d e l w h i c hc a ne x a c t l yd e s c r i b ep r o d u c td e v e l o p m e n tp r o c e s s e sa n di n f o r m a t i o nf l o w si s b a d l yn e e d e df o rt h eb e t t e ru n d e r s t a n d i n g ，a n a l y s i s ，i m p r o v e m e n t ，a n dm a n a g e m e n t o fp r o d u c td e v e l o p m e n t t h u s ，w i t ht h ea d v a n t a g e so ff o r m a ls e m a n t i cd e f i n i t i o n , v i s u a l l yg r a p h i c a le x p r e s s i o n ，f n - mm a t h e m a t i c a lf o u n d a t i o na n dd e s c r i p t i o nb a s e do n s t a t e ，t h ep e t r in e ti sa p p l i e dt om o d e la n do p t i m i z et h ep r o d u c td e v e l o p m e n tp r o c e s s t h i sd i s s e r t a t i o nd e s c r i b e st h ep r o d u c td e v e l o p m e n tp r o c e s sb a s e do np e t r in e t a n dw o r k f l o wt h e o r i e s ，a n di ts e t su ph i e r a r c h i c a lm o d e lb a s e do nt h et h e o r yo f r e f i n e m e n t ，g i v i n gaf a t h e ra n df o u rs o np e t r in e tm o d e l s a n a l y z et h es t r u c t u r a l c o r r e c t n e s s ( r e l i a b i l i t y ) o ft h ep r o d u c td e v e l o p m e n tp r o c e s sm o d e l ，g i v i n gt h ew h o l e p r o c e s sw h i c ha n a l y z et h er e l i a b i l i t yo ft h em o d e l f o rt h ep e r f o r m a n c ee v a l u a t i o no f p r o d u c td e v e l o p m e n tp r o c e s ss y s t e m , i ta n a l y z e st h ep e r f o r m a n c ep a r a m e t e ro f t h e s y s t e mq u a n t i t a t i v e l y , s u c ha sm e a nw o r kt i m ea n dr e s o u r c eu t i l i z a t i o nr a t e ，b a s e do n g e n e r a l i z e ds t o c h a s t i cp e t r in e tt h e o r i e s p a r t i c u l a r l yi ta n a l y z e st h a tu n d e rt h e c o n d i t i o no fr e s o u r c e si sn o ta m p l e ，t h en e e do fe a c hr e s o u r c ea b i l i t y ，t h e nt h e e m u l a t i o nc o m p u t e dt h em i n i m a lr e s o u r c e sq u a n t i t yt h a te a c hr e s o u r c en e e d ，a n d m a k er e s o u r c e sc a nr e a s o n a b l ea l l o t m e n t k e yw o r d s ：p e t r in e t ；p r o d u c td e v e l o p m e n t ；w o r k f l o w ；r e l i a b i l i t y ；p e r f o r m a n c e a n a l y s i s 学位论文独创性声明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究丁 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，沦文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得南昌火学或其他教育机构的学位或证书而使用过的材料。与 我同工作的同志对本研究所做的任何贡献均己在论文r f l 作了明确 的说明并表示谢意。 学位论文作者签名( 手写) ：躇、波签字曰期：加田年肛月伽日 学位论文版权使用授权书 本学位论文作者完全了解直昌太堂有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复e i j i 4 二和磁 盘，允许论文被查阅和借阅。本人授权南昌大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编本学位论文。同时授权中国科学技术信息研究 所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：踌、淑 导师签名：叫卫移 f 签字日期：阳们年版月功日签字日期：刃年驴月d 2 日 第1 章绪论 第1 章绪论 1 1 论文的选题背景及意义 进入2 0 世纪末期，企业面临了前所未有的机遇和挑战：一方面科学技术飞 速发展，产品的结构、功能日益多样化，产品生命周期日益缩短，顾客对快速 响应的要求日益提高，使得企业之间的竞争日益激烈，给企业的生存带来了考 验；另一方面，近年来信息技术的日益成熟和广泛应用，使得很多与计算机技 术紧密关联的产品设计与制造的新思想、新概念、新方法和新工具不断涌现， 为企业新产品的研发提供了前所未有的机遇，产生了一系列新产品开发模式， 如并行工程、虚拟样机技术等。这些新产品开发模式都从不同角度和层次上对 产品开发方式做了相应的变革，同时也促成了新产品开发组织形式的诞生。而 新产品开发组织形式又给组织管理带来了一些问题。为了适应这些变化，企业 有必要对其将要进行的产品开发项目进行规划，实现产品开发中的协调与管理。 产品开发过程建模与系统性能分析就是在这种环境下产生的。 产品开发过程建模很早就有人提出，但是在传统的产品开发环境下，由于 涉及的开发人员相对比较容易组织等原因，一直没有得到充分的重视。随着现 代企业竞争的加剧以及新产品开发模式的应用，产品开发过程建模现己成为产 品开发项目管理和规划中必不可少的一部分。 在运用先进的产品开发模式以及适当的建模工具的基础上，对新产品开发 过程进行建模就是在产品开发之前对整个过程进行描述。首先建立物理模型， 然后建立数学模型，对所建立的数学模型进行性能分析，评估产品开发项目的 周期、人力资源利用率以及各资源的需求量等。通过过程建模和对模型的定量 评估，可以找出开发活动的瓶颈并针对性地采取改进措施，减少项目开发的风 险，并在有限的资源约束下缩短产品开发周期。这一系列工作为产品开发过程 的改造提供依据，同时也为企业的优化决策提供依据。 第1 章绪论 1 2 产品开发模式理论研究现状 1 2 1 传统的产品开发模式 传统产品的开发过程通常表现为以下几个职能部门( 如图1 1 所 示) ( f u n k e ，1 9 9 7 ) 。产品的开发通常开始于市场部，之后是产品设计部、工程部、 制造部和客户支持部。简单地说每个阶段为下个阶段提供成果。在这些职能部 门之间几乎没有什么沟通交流的渠道。没有交流的渠道，各部门之间自然会形 成隔阂。任何工程的改变都不得不纠正之前各个阶段所做出的不一致的决定。 随着竞争日趋激烈，以顾客为本，缩短产品开发周期的要求越来越高。这 种“跨墙式”o “”“1 方法被证明效率低下，在产品开发的所有阶段都需要所有职 能部门的参与，由此导致并行工程等一些新的产品开发模式的产生。 职能部门；运作顺序 lt e ：丘 图1 1 传统的开发过程 1 2 2 先进的产品开发模式 ( 1 ) 并行工程 并行工程是一种新的产品设计与开发的理念。是对产品及其相关过程( 包 括制造过程和支持过程) 进行并行、一体化设计的一种系统化的工作模式。这 种工作模式力图使开发者从一开始就考虑产品全寿命周期中影响设计的所有因 素，包括质量、成本、进度和用户需求嘲嘲。并行工程开发模式的目标是缩短产 品开发周期，提高产品质量，降低产品成本，它是对传统的产品开发模式( 串 行开发模式) 的一次变革。1 。另外，在并行工程中，设计开发任务的执行是由多 学科集成产品开发团队来完成的。 从并行工程的定义可以看出，采用并行工程技术进行产品开发具有以下特 点跚： 在产品的设计期间，并行的处理整个产品周期中的关系，体现t 4 , 组合 2 第1 章绪论 作、信任及共享的价值，因而消除了由串行过程引起的孤立、分散及“抛过墙” 综合症； 在产品的开发过程中，产品开发小组被划分为很多小组，通过并行规划， 这些小组将设计工作最大程度地集中起来作并行处理，因而缩短了产品开发周 期； 在设计一开始就考虑到影响产品质量的所有因素。通过产品的早期定 义，最大程度地避免设计错误，减少设计的更改和重复次数，提高质量，降低 成本，使产品开发过程接近一次成功。并行工程产品开发模式强调用户呼声， 对用户更加负责。销售人员与用户在产品设计阶段就参与，对产品设计的有关 要求在早期就已经提出并确定下来。 并行工程是对传统的开发模式的一次变革，这种变革不仅体现在技术方面， 还体现在组织和管理方面o ： 组织方面，组建多学科小组时要克服来自传统的按照功能划分部门的习 惯及狭义的局部利益等方面的阻力，而且还要使形成的多学科小组间便于合作， 并在此组织结构下获得优化的过程模型，使产品开发过程具有合理的信息传递 关系以及短的产品开发周期； 管理方面，具体体现在影响开发人员工作因素的数量明显增加、设计阶 段的冲突数量大大增加、决策及其冲突化解的复杂程度增加、解决冲突所采用 的工作方式有很大的变化； 技术方面，并行工程不仅包含和继承了许多c i m s 技术，而且还提出了 很多新的并行工程技术，如各种d f x 工具以及各种集成技术等。 ( 2 ) 虚拟样机技术 传统的设计模式要经过设计、样机试制、工业性试验、改进定型和批量生 产几个步骤。产品设计过程中早期的缺陷和失误往往需要反复多次的试验才能 够发现，这种方法即延长了新产品的研发周期又增加了新产品的研发成本。产 品结构越复杂，研发周期就越长，研发成本就越高，极大地制约了产品质量的 提升。近年来，由于市场竞争的激烈性，用户需求的个性化和多样化以及多种 标准规范的约束等对现代工程产品的研制和生产提出了更高的要求。虚拟样机 技术v p ( v i r t u a lp r o t o t y p i n g ) 就是在这种迫切需要的驱动下产生的。 虚拟样机是用来代替物理产品的计算机数字模型，它可以像真实的物理模 型一样，用来对所关心的产品的全寿命周期，如设计、制造、服务、循环利用 3 第1 章绪论 等，进行展示、分析和测试。这种构造和使用虚拟样机的技术就叫虚拟样机技 术嗍。 虚拟样机技术具有下述优点叫：使用虚拟样机技术与物理样机相比，减 少了设计费用；使用虚拟样机可以辅助物理样机进行设计验证和测试；虚 拟样机技术可以减少产品开发过程中所需的时间，可以使产品尽快上市；使 用虚拟样机技术可以在相同的时间内“试验”更多的设计方案，这是物理样机 无法比拟的；虚拟样机技术可以减少在产品开发后期的设计更改，进而使得 整个产品的开发周期最小化；虚拟样机技术与常规的仿真相比，它涉及的设 计领域广，考虑也比较周全，因而可以提高产品的质量；由于虚拟样机技术 支持并行设计，使得设计小组之间的沟通变得便捷。 ( 3 ) 反求工程 反求工程( r e v e r s e e n g i n e e r i n g ，r e ) ，也称逆向工程、反向工程“，是指用一 定的测量手段对实物或模型进行测量，根据测量数据通过三维几何建模方法重 构实物的c a d 模型的过程，是一个从样品生成产品数字化信息模型。并在此基础 上进行产品设计开发及生产的全过程。 传统的产品设计过程是一个从无到有的过程，即设计人员首先在大脑中形 成对该产品的总体构思，然后综合各方面的要素和因素，对产品的功能、性能、 结构、尺寸、形状和技术参数等借助计算机建立其三维数字化信息模型，最终有 可能将这个模型转入到制造流程中，指导生产过程，这样的产品设计过程称为 “正向设计”过程。而在整个产品的设计过程中，所建立的三维数字化信息模型 在后续的设计及制造环节中几乎没发挥作用，后期模型的制作还是依靠传统的 手工方法制作，造成前后工作脱节。 基于反求工程的产品设计从物质形态上来讲可以认为是一个“从有到无再 到有”的过程。简单地说，反求工程产品设计就是根据已经存在的产品模型，反 向推出产品设计数据( 包括设计图纸和数字模型) 的过程。反求工程主要应用于 新产品的造型设计中，以及产品的改型及更新换代的设计过程中，结合快速成型 技术，快速的制造出产品样品的实物模型或模具，供设计者进行性能测试、直观 评估和验证分析，完成产品的设计及制造。 4 第1 章绪论 1 3 产品开发过程建模方法研究 1 3 i 产品开发过程建模方法的选择 为了获得产品开发过程性能指标，如产品开发周期、所需的资源等，对产 品开发过程的分析建模是有必要的。很多公司为了在竞争市场上获得良好成果 被迫改变其产品开发过程。为了对其产品开发过程进行分析和优化，需要一种 结构化和统一的建模方法。 产品开发过程建模方法的选择需要从过程模型的表达方法、表达工具、计 算机实现和最终表现形式上进行全面研究，即怎样以图形化和动态的方式表示 设计过程，给设计参与者提供大量的信息，实现过程的有效管理，提高设计的 协同性。因此设计过程模型的建立需要考虑许多因素，建模方法应该不仅能够 表达设计过程中涉及到的诸多因素，能够静态地描述设计过程，而且也能够通 过建立的模型来定性和定量地分析设计过程。具体来说，在选择建模方法上需 要考虑以下几点： ( 1 ) 建模方法是否能够表示设计过程中大量的行为、现象、信息，即需要 表示产品开发过程中的反复性和设计迭代，以及任务之间的相互关系，如顺序、 并行，还有产品开发过程中涉及到的信息和资源等； ( 2 ) 建模方法是否具有直观的图形表达形式。使用图形表示的过程模型具 有直观的特点，易于理解； ( 3 ) 建模方法是否允许过程模型的层次化分解。由于产品开发过程的阶段 性和层次性，一个好的过程模型也应该具有层次性的特点，分别对应不同设计 层次的需要； ( 4 ) 建模方法是否能够动态地执行，即描述过程模型静态特性的同时，也 能捕捉其动态特性。产品开发过程模型在执行过程中，有很多不可预料的情况 发生，因而需要过程模型捕捉其动态性能； ( 5 ) 建模方法是否能够对过程模型进行分析，以检测其性能。不论是采用 数学理论推导方法还是计算机软件分析方法，一个良好的产品开发过程建模方 法，都应该可以对其所建立的模型的性能进行分析，获得其动态性能。 。 本文总结出五种比较通用的产品开发过程建模方法，分别是i d e f 系列方法、 活动网络图方法、设计结构矩阵方法、u m l 建模方法和p e t r i 网建模方法。 通过以上分析，上面介绍的几种常见的过程建模方法很多并不符合我们的 5 第1 章绪论 产品开发过程建模的要求，大多数过程建模方法，都是基于一种非正式的符号 表示，缺乏严密的数学推理，并且是静态的或是定性的，这样很难把它们作为 分析产品开发过程的一个建模工具。p e t r i 网建模方法则很好的满足了产品开发 过程建模的需要，本文把p e t r i 网作为主要建模方法，其理由主要基于以下几点 1 1 【1 2 1 ： 首先，p e t r i 网模型它是对建模对象系统的描述，这种描述可以是详细的描 述，也可以是一个简单的表示。在构造p e t r i 网模型之前，需要对系统进行仔细 深入的研究，一旦出现建模错误情况，可以利用p e t r i 网原理立即纠正过来，避 免花费很大的代价去实际中更正。 其次，所建立的p e t r i 网模型的性质和行为可以进行很好的分析，其分析手 段既可以借助于计算机的仿真模拟，也可以借助于更正式的严密数学推导方法。 最后，对模型进行描述的过程，以及分析模型行为( 静态和动态) 的过程都 可以使建模者对所建立的模型系统有更深入的理解，这比单纯的分析结果本身 要有效得多。 1 3 2 国内外p e t r i 网应用的研究现状 p e t r i 网方法是近年来过程建模研究和应用比较广泛的一种方法，因为p e m 网可以扩展成多种形式，因而可以实现对产品开发过程任务间关系的确切表示。 同时，p e t r i 网方法支持定量化分析和层次化分解。p e t r i 网方法最初在工程领域 的应用是研究机械制造过程建模1 4 1 ”】。a a l s t 等人将p e 仃i 网方法引入到工作流过 程建模中1 司【切，并对工作流网的性质【3 】【4 5 1 ，以及工作流的应用f 4 6 l 进行了深入的研 究。虽然产品开发过程模型和商业工作流模型有很大的区别【”，但是产品开发 过程建模也可以借鉴相对成熟的工作流技术的一些方法。其中采用p e t r i 网方法 是研究工作流技术的一种重要方法，s a l i m i f a r d 对其进行了很好的综述【1s j 。j m m e n 等人对有色p e t r i 网进行了深入研究，把有色p e t r i 网的定义、分析技术系统化， 并对p c t r i 网的应用进行了总结。 在产品开发过程建模方面，祖旭等结合s i m u l i n k 工具对产品的动态性能进 行了仿真，取得了良好的结果0 9 l 。此外，跨组织的工作流睇o j 和供应链工作流【2 1 】 也是工作流研究的一个重要课题。范玉顺对工作流技术的时间和结构性能、工 作流仿真建模等也进行了深入的研究 2 2 】。 尽管研究者对产品开发过程进行了一系列的研究，在实际的产品开发项目 6 第1 章绪论 管理、规划、协调和优化中也取得了重要作用。但是，正如前面所述，产品开 发过程是一个复杂多变的过程，因而还有一些问题需要继续研究： ( 1 ) 产品开发过程模型的可靠性分析 现代产品开发过程模型是对产品开发过程的静态的描述，但是产品开发过 程是一个动态多变的复杂的过程，因而产品开发过程模型在描述产品开发过程 的静态特性的同时，也应该可以描述其动态的执行，捕捉产品开发过程的动态 特性。模型的建立应该能够验证过程的可靠性( 正确性) 并预知各种可能发生 的情况，进而对产品开发过程进行有效管理和控制。 ( 2 ) 产品开发过程模型的性能分析 如何在最短的时间内开发出满足用户需要的产品是产品开发的根本目的。 产品开发过程模型应该可以对产品开发过程中涉及的时间、资源利用率等因素 进行模拟计算，能够通过建立的模型来定性和定量地分析系统性能参数，并对 参数分析的基础上，找出模型的瓶颈，加以改进使之达到缩短产品开发周期和 提高资源利用率的目的。 系统资源的能力需求是产品开发过程建模的另一个重要内容，因为在产品 开发过程中，合理有效地分配有限的资源是加快产品开发速度，提高产品开发 效率的有效途径。因此，分析产品开发过程模型的最少资源需求量是一值得研 究的问题。本文采用系统工作流方法对产品开发过程中的资源分配问题进行了 深入的研究。 1 4 本文的主要研究内容 本文的各章具体内容和框架结构安排如下： 第一章介绍了本文的选题背景及意义，并对产品开发模式和产品开发过程 建模方法的相关内容进行了综述。 第二章主要介绍了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 第1 章绪论 第四章在广义随机p e t r i 网理论的基础上，对产品开发过程系统的性能参 数，如平均服务时间、资源利用率，进行了定量分析。并提出了相应缩短产品 开发周期和提高资源利用率的措施。最后，在假设资源不充足的情况下，对产 品开发过程系统的资源最少需求量进行了模拟计算，使得资源分配合理。 第五章总结本文研究成果并提出下一步需要研究的内容。 论文的框架结构安排如图1 2 所示： 山上0 随机p e t r i 网p e t r i 网工作流网l 山l山 i t j 产品开发流程i t 顶层p c t r i 网模型四个子网模型i 山山 t 模型可靠性分析 i + 平均服务时间 ，人力资源利用率i j ，上 j ， 找出瓶颈因素并加以改进 0 i各资源类的能力需求 l 图1 2 论文的框架结构 8 第2 章p e t r i 网理论介绍 第2 章p e t r i 网理论介绍 1 9 6 2 年德国的c a p e t r i 博士在研究自动机通信时，提出了一套形式化的建 模方法，在当时引起了学术界的广泛关注，因此用他的名字命名为p e l r i 网 2 3 1 。 p e t r i 网是一种系统建模与分析工具，以并发论、网逻辑和网拓扑为主要内容， 它同时具有充分的模拟能力和丰富的分析方法。一方面，作为一种图形工具， p e t r i 网除了具有类似流程图等的可视描述功能外，还可以通过标识的流动模拟 系统的动态行为；另一方面，作为一种数学工具，p e t r i 网可以建立关联矩阵、 状态方程和s 尼不变量等来描述系统的结构特征。 经过五十多年的发展，p e t r i 网理论已经被广泛应用于许多领域，如计算机 网络的性能分析、分布式计算机系统的分析和控制以及在软件工程、分布式数 据库、操作系统、并行程序的设计与验证、人工神经网络、知识表示中的应用 等。本文采用p e t r i 网和工作流网作为产品开发过程建模与分析的工具。 2 1p e t r i 网理论 任何系统都是由两类元素组成的：表示状态的元素和表示状态变化的元素。 在p e t r i 网中用库所表示前者，用变迁表示后者。库所的作用是决定变迁能否发 生，变迁的作用是改变状态。两者之间的这种依赖关系用有向弧表示出来就是 一个p e t r i 网。 2 1 1p e t r i 网的基本概念 定义2 1 哪删( p e t r i 网) ：p e t r i 网是一个四元组= ( s ，t ；f , m o ) ，其中 ( 1 ) s = “，s 2 ，) 是库所的有限集合； ( 2 ) t = t l , t 2 ，) 是变迁的有限集合； ( 3 ) s u 丁m ，s n t = m ： ( 4 ) f ( ( s x t ) u ( s x t ) ) 表示库所和变迁之间的流关系； ( 5 ) d o m ( f ) u c o d ( f 1 = s w t ( 不存在孤立元素) ； d o m ( f ) = x 1 3 y ：( x ，y ) f )c o d ( f ) = x 1 3 y ：o ，x ) ， ( 6 ) 映射 靠：p 一 0 ，1 ，2 ， 网的初始标识。 有向网n = ( s ，t ：f ) 是p e t r i 网的基网，不包含初始标识。一个p e t r i 网也可 0 第2 章p e t r i 网理论介绍 以表示为( n ，m o ) 。 p e t r i 网是一种有向图，由两种类型的节点构成，一种是库所节点s ，用圆圈 来表示，另一种是变迁节点t ，用方框来表示，节点之间用有向弧来连接。p e t r i 网的状态用标识在库所中的分布表示。 定义2 2 】肼之7 】( 前置集和后置集) ：设网n = ( s ，t ；f ) ，对x s u r ，记 曩= y i y s u r ( y ，石) f ) x = y f y s u t ( x ，y ) ，) 称呵为元素x 的前置集，r 为x 的后置集， x k 9 r 为x 的外延。 作为一种建模工具，p e t r i 网除了具有上述的静态结构外，还可通过变迁的 使能和引发来反映系统的动态行为。库所中标识的存在会引起相应变迁的引发， 而变迁的引发又会使库所中的标识数目发生变化，从而改变整个p e t r i 网的状态。 定义2 3 】晔讲1 ( 变迁的使能与引发) ：设：( s ，t ；f , m o ) 是- - 个p e t r i 网，称变 迁t t 在标识下是使能的，当且仅当对v s t ，都有m o ( s ) l ，记作m o l t 。 在 厶下使能的变迁t 可以引发，引发后得到的后继标识为m ，则 rm o c s ) - - 1 若s e t - t m ( s ) = _ m o ( s ) + l 若s e t 。- t l m o ( s ) 否则 记作m o t m 。 2 1 2p e t r i 网的性质 【定义2 4 】【撕7 】( 可达性) ：设= ( s ，t ；f ，m o ) 是一个p e t r i 网，如果存在t t ， 使得 甜f m ，则称m 为从 靠直接可达的。如果存在变迁序列，如，和标 识序列m ，鸠，心，使得【f l m 【p m 2 地一陬 帆，则称尥从可 达的。从 靠可达的一切标识的集合记为r i m o ) ，规定m o r ( m o ) 。 r ( m o ) 给出了系统运行过程中可能出现的全部状态的集合。 【定义2 5 】 2 4 - 2 7 1 ( 有界性) ：设z = ( s ，t ；f , m o ) 是- - + p e t r i 网，若存在正整数b ， 使得对任意的 如r ( m o ) ，都有m ( s ) b ，则称该库所s 是有界的( b o u n d e d ) 。 若对v ses 都是有界的，则称该p e t r i 网为有界p e t r i 网。特别的，b = i 时，称库 所s 是安全的( s a f e ) 。 p e t r i 网的有界性反映了被模拟系统运行过程中对有关资源的容量要求。 定义2 6 。”( 活性) ：设= ( s ，t ；f , m o ) 是一个p e t r i 网，t t ，若对任意 1 0 第2 章p e t r i 网理论介绍 的 厶r ( m o ) - 1 m t ，则称变迁t 为活的( 1 i v e ) 。如果对v t t 都是活的，则 称该为活的p e t r i 网。 一个活的p e t r i 网无论选择怎样的变迁引发序列，都可以保证无死锁操作。 定义2 7 “。3 ( 强连通性) ：一个网n = ( s ，t ；f ) 称为是强连通的( s t r o n g l y c o n n e c t e d ) ，当且仅当其中的任意两个结点( 库所或变迁) x ，y s u t ，存在一条 从x 到y 的有向路c ，即存在序列= x ，n 2 ，, o0 9 n k = y ，有( 啊，n j + 1 ) f 0 f k - 1 ) 。 2 1 3p e t r i 网的分析方法 给定一个p e t r i 网= ( s ，t ；f ，m o ) ，s ，t ，f ，m o 。这些参数决定了此网的静态特性。 而p e t r i 网在连续运行过程中，会产生两种序列：状态演化序列和变迁发生序列。 对状态序列进行分析，主要有可达标识图或可覆盖树方法；对变迁序列进行分 析，主要有状态方程方法、不变量方法、p e t r i 网语言方法。 可达标识图或可覆盖树： 对于有界p e t r i 网，其可达标识集r ( m o ) 是一个有限集，因此可以将r ( m o ) 作 为顶点集，以标识之间的直接可达关系为弧集构成一个有向图，这种有向图就 称为p e t r i 网的可达标识图。通过一个p e t r i 网的可达标识图可以分析这个网系 统的状态变化和变迁在状态演化过程中的作用情况，从而得知网系统的有关性 质。 定义2 8 3 叫伽( 可达标识图) ：设= ( s ，t ；f , m o ) 是一个有界p e t r i 网，的 可达标识图定义为一个三元组r g ( e ) ( r ( m o ) ，e ，p ) ，其中 e = u m | ，m | 、m | ，m | r ( m o ) 且3 t k t 奄m i t k m 3 p ：e - - t ，p ( m ，m ，) = 当且仅当j j i t k m j 。 对于无界p e t r i 网，由于r ( m o ) 是一个无限集，不可能画出可达标识图。为 了用有限的形式表达一个具有无限个状态的系统的运行情况，需要引入一个表 示无界量的符号国，m 具有这样的性质：1 ) 对于任意正整数n ：国 玎c o 刀= ； 2 ) 缈c o 。当库所j 。中的标识数在p e t r i 网的运行中趋向于无限增长时，就把标 识向量中的第j 个分量改为c o ，以此覆盖所有这类标识。这样，就可以通过一个 有限树来反映这个p e t r i 网的运行情况，称这种有限树为p e t r i 网的可覆盖树。 关联矩阵与状态方程： 由于p e t r i 网的一个标识可以表示成一个m 维非负整数向量，p e t r i 网的结构 可以用一个矩阵来表示，这样就可以引入线性代数的方法对p e t r i 网的性质进行 第2 章p e t r i 网理论介绍 分析。 定义2 9 嘲删( 关联矩阵) ：设= ( s ，t ；f , m o ) 是一个p e t r i 网， s = 俩，是，) ，t = “，乞，厶) ，则p e t r i 网的结构( s ，t f ) 可以用一个n 行m 列矩阵彳= 【】表示。其中：吻= 瞄一a , 一j 厂1 若( ，s ，) fr 1 若o ，t ) f = _ 4 i ： 。 l o 否则【9 否则 f 1 ，2 ，栉 ，_ ， 1 2 ，研， 称a 为p e t r i 网的关联矩阵。 定理2 1 ：设= ( s ，t ；f , m o ) 是一个p e t r i 网，蚓= m ，i t i = n ，a 为的关联矩 阵，若m r ( m o ) ，则存在n 维非负整数向量x 使得m = 如+ z 。 上式称为p e t r i 网的状态方程，它给出了在p e t r i 网中，标识m 从初始标识 m o 可达的一个必要条件。如果m 是从m o 可达的，则使得m o a m 的任一变迁 序列盯t ，都满足x = 0 ，即x 中的第i 个分量等于r 在盯中出现的次数。 状态方程可用来分析p e t r i 网中不依赖于初始标识，而仅和网结构有关的 特性，如结构有界性、结构公平性和可重复性等。 不变量： 定义2 10 3 。”1 ( t - 不变量) ：设气s ，t ；f , m o ) 是一个p e t r i 网，i s l - m ，i t | = n ， a 为的关联矩阵，如果存在非平凡的n 维非负整数向量x 满足a 7 x = 0 ，则称 x 为p e t r i 网的一个t - 不变量。 p e t r i 网的t 一不变量反映了使状态回归的可能变迁序列。从初始标识m o 开 始，经过一系列变迁后，网的标识恢复到初始标识m o ，t 一不变量的各分量的值 决定了各个变迁的发生次数。利用t 一不变量可以研究周期性、循环性等性质。 p e t r i 网语言： 对p e t r i 网系统进行分析的另一种方法就是考察网系统中一切可能发生的 变迁序列以及这些序列构成的集合的性质。如果我们把一个p e t r i 网的变迁集 合看作一个字母表( 即把每一个变迁看作是一个字母) ，或者定义从变迁集合到 字母表上的一个映射，那么该p e t r i 网上所有可能发生的变迁序列或各序列映 射到字母表的集合就是一个语言。 定义2 1 1 嘣。2 7 1 ( p e t r i 网语言) ：对一个p e t r i 网= ( s ，t ；f , m o ) ，存在一个 对变迁的标注函数盯：r 专，使得三= 盯( ) i t 且垆 则称l 为p - 1 2 第2 章p e t r i 网理论介绍 型p e t r i 网语言。 2 2 随机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 网中引入时间参数的方法是：在每个变迁的使能与引发之间联 系一个随机的延时时间，这种类型的p e t r i 网就叫做随机p e t r i 网( s t o c h a s t i c p e t r in e t , s p n ) 。在随机p e t r i 网中，变迁引发延时随机变量又分为离散和连续 两种情形，对这两种随机变量可定义多种分布函数。为了保证随机过程是马尔 可夫过程或可嵌入马尔可夫过程，通常要求相关离散时间的随机变量为几何分 布，而相关连续时间随机变量为指数分布。 2 2 1 随机p e t r i 网的定义 把变迁与随机的指数分布引发延时相联系起来的思想是由m o l l y 、f l o r i n 和 n a t k i n 等人独立提出来的。给p e t r i 网的每个变迁相关联一个引发速率，得到的 模型就是随机p e t r i 网。 在连续时间随机p e t r i 网中，一个变迁从使能到引发需要延时，即一个变迁 t 从变成使能的时刻到它引发时刻之间被看成是一个连续随机变量工( 取正实数 值) ，且服从于一个分布函数只( x ) = p “x 。 在m o l l y 提出的连续时间s p n 中，该分布函数定义成一个指数分布函数： v t t ：f = 1 一e 一舢 其中实参数元 0 是变迁t 的平均引发速率，变量工0 。可证明啪1 ： ( 1 ) 两个变迁在同一时刻引发的概率为零。 ( 2 ) s p n 的可达图同构于一个齐次马尔可夫链( m a r k o vc h a i n , m c ) ，因而可 以用马尔可夫随机过程求解。 定义2 1 2 ( 随机p e t r i 网) 协1 ：连续时间s p n = ( s ，t ；f , m o ， ) 其中( s ，t ；l ：, m o ) 是一个p e t r i 网系统，a = ( ，五，以) 是变迁平均引发速率集合。丑是变迁t 的平均引发速率，表示在使能的情况下单位时间内平均引发次数。 1 3 第2 章p e 啊网理论介绍 2 2 2s p n 模型的性能分析 s p n 应用在系统模型的性能分析中分为三步： ( 1 ) 给出系统的s p n 模型； ( 2 ) 构造出该s p n 所同构的m c ： 同构m c 的获得比较简单：求出s p n 的可达图，将每条弧上标注的引发变迁t 换成其平均引发速率见，即可得m c 。 ( 3 ) 基于m c 的稳定状态概率进行系统性能分析。 s p n 是一个暂态系统，当时间趋于无穷时，它会达到一种动态平衡状态，因 此s p n 中的每一个状态m 有一个稳定概率p 【m f 】。设m c 中n 个状态的稳定概率 是一个行向量x = ( x o ，五，矗一。) ，则根据马尔可夫过程可建立下列线性方程： r 翘2 0 一一i l x x , = 1 其中q 吼】是一个转移速率矩阵。i c j m ，若从状态m 到状态膨，有一 条弧相连，则吼等于弧上标注的速率，否则吼= 0 ；i = j 时，g f ，一( 从状态m 输 出的各条弧上标注的速率之和) 。 解此线性方程组，即可得每个可达标识的稳定概率研m 】- t ( o i , - - 1 ) 。 在求得稳定概率的基础上，可进一步分析以下性能指标： ( 1 ) 在每个状态m 中驻留的时间 在每个状态m r ( ) 中的驻留时间是以一名为参数的一个指数分布随机 变量，平均为f ( m ) = ( 屹) = ( 乃) 一，其中h 是在标识m 下可引发的所有变迁 的集合。 ( 2 ) 令m 【 肘，下一个状态是肘，在m 状态的等待时间是一个指数分 布的随机变量，其平均值为：r ( mi m ，) = l r = 1 五( f 力。 ( 3 ) 标识概率密度函数 在稳定状态下，每个库所中所包含的标识数量的概率。对v s s ，令 p m ( s ) = k 】表示库所s 中包含k 个标识的概率，则该概率密度函数 研m ( s ) = 纠= p 【鸠】，其中鸠o ) = 七。 ( 4 ) 在库所中的平均标识数 在稳定状态下，库所s s 在任一可达标识中平均所含的标识数： 1 4 第2 章p e t r i 网理论介绍 ”( j ) = ，+ 研m ( s ) = 刀。 j 库所中的平均标识数是一个非常有用的性能参数，利用它可以做许多系统 性能的评估。例如，在系统的模型中，设置某库所表示某种设备的忙闲状态， 就可利用库所中所含的平均标识数来评估该设备的利用率等性能指标。 ( 5 ) 变迁的利用率 v t t 的利用率u ( t ) 等于使t 使能的所有标识的稳定概率之和，即 【，( ，) = 研m 】，其中e 是使t 使能的所有可达标识的集合。 村f ( 6 ) 变迁的标识流速 v t t 的标识流速是指单位时间内流入变迁t 的后置库所s 的平均标识数 r ( t ，s ) r ( t ，j ) = u ( f ) + 五，其中五是t 的平均引发速率。 2 2 3 广义随机p e t r i 网 然而，在实际的系统模型中，有些变迁只是