PETRI网建模理论基础.ppt

5.Petri网建模理论基础n n19621962年德国学者年德国学者Carl Carl A.PetriA.Petri在其博士论在其博士论 文中提出的描述事件和条件关系的网络文中提出的描述事件和条件关系的网络n n用简单图形较好的表示并发、同步、因果用简单图形较好的表示并发、同步、因果 等关系以等关系以网图网图的方式简洁、直观的模拟的方式简洁、直观的模拟 离散事件系统离散事件系统n n目前已得到广泛应用目前已得到广泛应用, ,有限状态机、通信协有限状态机、通信协 议、同步控制、生产系统、形式语言、多议、同步控制、生产系统、形式语言、多 处理器系统等建模中处理器系统等建模中petri网的应用领域n(1)通讯协议的验证通讯协议的验证是Petri网应用最为成功的领域之 一最初应用在70年代初期，由于 Petri网以形式 语言作为基础，可形式化地 对通信协议进行正确 性验证n(2)计算机通讯网络性能评价及多媒体应用随着计算机网络技术和信息技术的发展，对网络 进行性能分析的需要，不仅出现于企业内部的生 产控制的局域总线网，而且出现于光纤局域网或 ATM网中n(3)软件工程由于产品开发中的竞争和革新需要，导致产品开 发者面临巨大压力.在软件工程中Petri网主要用于 软件系统的建模和分析，比较成熟的是加色Petri 网，可以用于大型软件系统的设计、说明、仿真 、确认和实现，在软件开发生命周期的各个阶段 ，Petri网都可以得到很好的应用。

n(4)知识处理Petri网可用于Al中的知识表达和推理的形式化模 型的建立，可以表达各个活动之间的各种关系， 如顺序关系、与关系、或关系等，并可在模型基 础上通过已知的初始状态和初始条件进行逻辑推 理n(5)FMS的建模、分析和控制柔性制造系统(FMS)对于现代制造业具有重 要作用，Petri网由于其自身优点，在制造 系统中应用广泛，如带缓冲区的简单生产 线、机床加工中心、自动生产线、柔性制 造系统和及时加工系统n(6)系统可靠性分析系统的可靠性不仅包括硬件的可靠性、也 包括软件可靠性.利用随机Petri网对系统进 行可靠性分析，对软件复用、软件可靠性 分析5.1 基本概念n n资源：与系统状态变化有关的因素，资源：与系统状态变化有关的因素， 如原料、产品、工具、设备等如原料、产品、工具、设备等n n状态元素：资源归类后的抽象状态元素：资源归类后的抽象n n库所：一个场所，存放状态元素库所：一个场所，存放状态元素n n变迁：资源状态变化变迁：资源状态变化n n事件：引起条件的变迁称为事件事件：引起条件的变迁称为事件n n容量：库所的最大资源数量容量：库所的最大资源数量resourcestateplace ,“S”transition eventCapability，“K”Petri网数学定义n一个Petri网是一个三元组nP={p1，p2，…，pm}为库所（place）的集合；n nT={tT={t1 1，，t t2 2，，……，，t tn n} }为为变迁（变迁（transitiontransition））的集合的集合；nF =（P×T）∪（T×P）为输入函数和输出函数集，称 为流关系。

§ §三元组三元组N=N=（（P P，，T T；；F F）构成网（）构成网（netnet）的充分必要）的充分必要 条件：条件： ① ① P∩T=фP∩T=ф，，规规规规定了定了库库库库所和所和变变变变迁是两迁是两 类类类类不同的元素不同的元素；；② ② P∪T≠фP∪T≠ф，，表示网中至少有一个元表示网中至少有一个元 素素；；③ ③ F=F=（（P×TP×T））∪∪(T×P)(T×P)，，建立了从建立了从库库库库 所到所到变变变变迁迁、、从从变变变变迁到迁到库库库库所的所的单单单单方向方向联联联联 系，并且系，并且规规规规定同定同类类类类元素之元素之间间间间不能直接不能直接 联联联联系系；；一个简单的Petri网Petri Petri 网描述系统的最基本概念是网描述系统的最基本概念是库所库所和和变迁变迁§ § 变迁的发生受到变迁的发生受到系统状态的控制系统状态的控制，即变迁发生的前，即变迁发生的前 置条件必须满足；置条件必须满足；§ § 变迁发生后，某些前置条件不再满足，而某些后置变迁发生后，某些前置条件不再满足，而某些后置 条件则得到满足条件则得到满足§ § 库所库所表示系统的状态。

表示系统的状态 § § 变迁变迁表示资源的消耗、使用及使系统状态产生的变表示资源的消耗、使用及使系统状态产生的变 化§ § 图形化表示：图形化表示：以圆圈表示为库所以圆圈表示为库所以粗实线表示变迁以粗实线表示变迁以联结库所与变迁之间的以联结库所与变迁之间的有向弧有向弧表示输入输出函数表示输入输出函数用令牌（用令牌（tokentoken））表示库所中拥有的资源数量表示库所中拥有的资源数量————黑点或数字表示黑点或数字表示库所变迁§ 库所中令牌分布决定变迁的使能（enabled）和激发（fire），变迁的激发又将改变令牌的分布§ 以变迁激发导致令牌在库所间的流动，Petri网可以用于模拟系统的动态运行过程，反映系统的动态特性§网N=（P，T；F）构成了描述系统静态结构框架，但还不能描 述系统静态结构的全貌§ 网论尊重资源有限的事实实际上，变迁发生所需的资源是有限的，库所容量也应是有限的§ 完整的网系统应指明资源的初始分布，规定变迁的活动原则 ，确定库所容量和变迁与资源数量之间的关系实例1：工业生产线的Petri网模型n有一工业生产线，要完成两项操作，分别为 变迁t1和t2表示，变迁t1 将进入生产线的半成 品s1s2用两个部件s3固定在一起，后形成中间 件s4。

然后第2个变迁t2 将s4 和s5用3个部件s3 固定在一起形成中间件s6完成t1和t2 都需要 用到工具s7n假设受空间限制s2 s5最多不能超过100件， s4最多不能超过5件，s3最多不能超过1000件 Petri网模型实例实例2 2：： 基于基于PetriPetri网的柔性制造系统网的柔性制造系统 （（FMSFMS））建模举例建模举例§ 板材加工FMS主要由以下三部分组成：① 数控加工设备，包括：数控冲床、数控剪板机和数 控折弯机等及其上下料辅助装置；② 自动化物料运储装置，如立体仓库、堆垛机及上下 料小车等；③ 计算机控制及管理系统§ 与金属切削FMS相比，板材FMS具有以下特点：① 零件的种类、批量及复杂程度存在较大差异；② 板料和零件的出入库等操作以托盘为单位，加工过程则以托盘上的单张板料或零件为单位；③ 作业计划制定涉及零件混合排样问题，零件种类、排样方法及调度策略等对机床的换模形式、换模时间以及FMS效率具有重要影响；④ 板材零件的加工工序较为简单和固定从板料到零件需要只经过冲压、剪切和折弯等三道工序，有些零件则只需冲压和剪切等两道工序 具有冲压、剪切和折弯单元的板材加工具有冲压、剪切和折弯单元的板材加工FMSFMS物理配置图物理配置图Petri网（Petri net）§ 从系统建模角度，将板材加工FMS中的活动分为三类：① 以冲压和剪切为特征的冲剪操作；② 冲剪后零件的折弯操作；③ 板料以及冲剪后零件的出入库操作。

§ 采用Petri网建模的基本步骤：① 划分和定义系统内所有活动及其相互关系； ② 采用Petri网描述上述活动及其关系，得到系统Petri网模型板材加工FMS的Petri网模型其中，“▕ ”表示变迁，t1～t16为系统中的变迁“◯ ”表示普通库所，p0～p20为普通库所“◎ ”表示决策库所，pd0～pd7为决策库所 Petri网（Petri net）Petri网（Petri net）Petri网（Petri net）5.2 Petri网的行为特性：§ 与其它建模方法相比，Petri网的优点不仅表现在建模能力上 ，更主要表现在它所具有的分析能力上§ § PetriPetri网具有一些网具有一些专门专门专门专门 的分析手段，的分析手段，对对对对系系统统统统活性（活性（livenessliveness）） 及及死死锁锁锁锁（（deadlockdeadlock））进进进进行分析行分析，分析系统中的，分析系统中的顺序顺序、、并发并发及及冲冲 突突等复杂事件关系等复杂事件关系§ §采用采用可达树（可达树（reachability treereachability tree））理论分析系统的理论分析系统的有界性有界性（（boundnessboundness））与与安全性（安全性（safetysafety））等等 5.2.1 顺序关系5.2.2 并发关系5.2.3 可达性n是研究任何系统动态特性的基础,决定系 统能否到达一个指定的状态.(1)系统按照一定的流程运行，系统是否能 够实现一定的状态；或者不期望的状态 不出现。

比如：生产调度计划的验证（按照一定的生产调度计划进行生产， 一定的生产任务是否能够完成）可达性（2）要求到达一定的状态，如何确定系统 的运行轨迹（流程）比如：生产调度，如何安排作业顺序？死锁关系5.2.4 活性 n在系统中用于检测是否存在死锁一个系统 存在的一个潜在问题是死锁,为了避免死锁, 系统的Petri网模型必须具有活性. （1）互斥：同时争夺唯一资源 （2）占用且等待 （3）无抢占 （4）循环等待逻辑关系图：冲突（互斥）逻辑关系图：冲突（互斥）\ \冲撞关系冲撞关系§ 冲突的实质是竞争资源§ 冲突就是指这种两者都有发生权，但在同一时刻只能有一个发生的关系§ 冲突双方谁先发生由系统实际运行环境及状态决定，即谁有优先权是不确定的§冲突又称为选择（choice）或不确定（nondeterminism）， 是对系统性能影响最大的事件类型5.2.5 有界性 n是一个非常重要的特性,它保证系统在 运行过程中不会需要无限的资源.n有界性反映一个库所在系统运行过程中能 够获得的最大的令牌数,即所能获得的最大 资源数,它与系统的初始令牌有关. n在实际系统设计中,必须使网络中的每个库 所在任何状态下的令牌数小于库所的容量, 这样才能保证系统的正常运行。

5.2.6 安全性 （是否会溢出）n决定系统中正在执行的操作不会发出请 求.若Petri网为1有界,则称此Petri网是安 全的.这种网的每一个库所要么有一个令牌,要么没有令牌.安全性是有界性的一种特殊情况 .5.2.7 5.2.7 可逆性和回家状态（主宿状态可逆性和回家状态（主宿状态 ））在制造业系统和过程控制系统中存 在着一个重要的问题：错误复原，即系 统能否重新回到原来状态(保证系统的循 环特性)n n可逆可逆————系统可自生初始化系统可自生初始化n n主宿（回家）主宿（回家）————系统经过有限步骤，将系统经过有限步骤，将 回到期望状态回到期望状态5.2.8 守恒性 n在一个Petri网系统中,令牌被用来描述系 统资源,对这类Petri网,守恒性是一个重要 性质,要使代表资源的令牌在Petri网运行 中既不会增加也不会减少,最简单的方法 就是网中总令牌数保持恒定.Petri网性能分析：n覆盖树（Coverability tree）——可达图n不变量（Invariation）• 1、标识向量m• 初始标识m0=(1 1 0 0 0)T • 标识m1=(0 0 1 0 0) T • m2=(0 0 0 1 1) T覆盖树性能分析法覆盖树性能分析法覆盖的数学定义：分析步骤分析步骤 1、m0作为“树根”（可作上new记号） 2、对有new记号的标识m做以下事情，否则终止； 3、选择某一“new”标识m； （1）若m与树中间已有的其他标识m相同，则将其记 为“old”，转向其他“new”标识； （2）若在m下无变迁使能，则将m记为“dead end”； 4、对于m下有使能的所有变迁t，做以下事情： （1）激发t，产生标识m’； （2）若从树根至m’的路径上存在一标识。