《Petri网原理与应用》读书笔记

《Petri网原理与应用》读书笔记1传统Petri网介绍CarlAdamPetri教授于1962年在博士论文《用自动机理论通信》中首次提出的一种自动机网状结构模型，拥有能恰当处理因果上的不存在依赖性的并行现象和表示不确定性的选择的能力，以及以系统模型用网状图形表示的方法。传统的Petri网是简单的过程模型，由两种节点：库所和变迁，有向弧，以及令牌等元素组成的。相关概念：（1）transitionenabled（变迁的就绪）：当且仅当transition的每一个输入place都至少有一个token的时候，变迁就绪，可以实施。（2）transitionfiring（变迁的实施）：变迁实施的时候它的每一个输入库所托肯减少一个，并使它的每一个输出库所的托肯增加一个。图1.1显示了Petri网的基本建模，其中圆圈表示place；矩形表示transition；存在于place中用的token用黑点表示。用简单图形较好的表示并发、同步、因果等关系。以网图的方式简洁、直观的模拟离散事件系统。目前已得到广泛应用,有限状态机、通信协议、同步控制、生产系统、形式语言、多处理器系统等建模中。通讯协议的验证是Petri网应用最为成功的领域之一最初应用在70年代初期，由于Petri网以形式语言作为基础，可形式化地对通信协议进行正确性验证。随着计算机网络技术和信息技术的发展，对网络进行性能分析的需要，不仅出现于企业内部的生产控制的局域总线网，而且出现于光纤局域网或ATM网中。图1.1Petri网基本模型由于产品开发中的竞争和革新需要，导致产品开发者面临巨大压力。在软件工程中Petri网主要用于软件系统的建模和分析，比较成熟的是加色Petri网，可以用于大型软件系统的设计、说明、仿真、确认和实现，在软件开发生命周期的各个阶段，Petri网都可以得到很好的应用。Petri网可用于Al中的知识表达和推理的形式化模型的建立，可以表达各个活动之间的各种关系，如顺序关系、与关系、或关系等，并可在模型基础上通过已知的初始状态和初始条件进行逻辑推理。柔性制造系统(FMS)对于现代制造业具有重要作用，Petri网由于其自身优点，在制造系统中应用广泛，如带缓冲区的简单生产线、机床加工中心、自动生产线、柔性制造系统和及时加工系统。系统的可靠性不仅包括硬件的可靠性、也包括软件可靠性.利用随机Petri网对系统进行可靠性分析，对软件复用、软件可靠性分析。Petri网描述系统的最基本概念是库所和变迁。库所表示系统的状态。变迁表示资源的消耗、使用及使系统状态产生的变化。变迁的发生受到系统状态的控制，即变迁发生的前置条件必须满足；变迁发生后，某些前置条件不再满足，而某些后置条件则得到满足。库所中令牌分布决定变迁的使能（enabled）和激发（fire），变迁的激发又将改变令牌的分布。以变迁激发导致令牌在库所间的流动，Petri网可以用于模拟系统的动态运行过程，反映系统的动态特性。网N=（P，T；F）构成了描述系统静态结构框架，但还不能描述系统静态结构的全貌。网论尊重资源有限的事实。实际上，变迁发生所需的资源是有限的，库所容量也应是有限的。完整的网系统应指明资源的初始分布，规定变迁的活动原则，确定库所容量和变迁与资源数量之间的关系。2扩展Petri网的研究2.1扩展的Petri网在以Petri网为工具对特定的系统进行建模分析时，不仅要遵守严格的语义还要兼顾图形语言。用Petri网建立的模型可能十分的复杂，因为在一个动态的网络图中很多活动都需要用一个库所、一个变迁以及连接它们的一条连接弧来表示。如果系统中处于动态过程的活动过多，利用Petri网对其建立模型会产生状态爆炸的现象。由于Petri网在设计之初并没有引入层次化的建模理念，这导致了利用Petri网建立的工作流模型很难重复利用，难以进行有效维护，理解起来非常困难。区别于传统的面向问题的方法的面向对象方法，使得计算机能以更加类似人类的思维方式解决问题，从而直观地描述客观世界，并拥有封装性、继承性、支持软件的复用以及易于扩充等优点。在Aalst提出的工作流网的基础上引入对象技术及细化变迁实现流程的分层建模，可以降低建模的复杂程度，提高模型的可读性和重用性。从系统建模角度，将板材加工FMS中的活动分为三类：①以冲压和剪切为特征的冲剪操作；②冲剪后零件的折弯操作；③板料以及冲剪后零件的出入库操作。采用Petri网建模的基本步骤：①划分和定义系统内所有活动及其相互关系；②采用Petri网描述上述活动及其关系，得到系统Petri网模型。2.2Petri网的行为特性与其它建模方法相比，Petri网的优点不仅表现在建模能力上，更主要表现在它所具有的分析能力上。Petri网具有一些专门的分析手段，对系统活性（liveness）及死锁（deadlock）进行分析，分析系统中的顺序、并发及冲突等复杂事件关系。采用可达树（reachabilitytree）理论分析系统的有界性（boundness）与安全性（safety）等。Petri网的可达性是研究任何系统动态特性的基础,决定系统能否到达一个指定的状态。(1)系统按照一定的流程运行，系统是否能够实现一定的状态；或者不期望的状态不出现。比如：生产调度计划的验证（按照一定的生产调度计划进行生产，一定的生产任务是否能够完成）（2）要求到达一定的状态，如何确定系统的运行轨迹（流程）。比如：生产调度，如何安排作业顺序？活性在系统中用于检测是否存在死锁。一个系统存在的一个潜在问题是死锁,为了避免死锁,系统的Petri网模型必须具有活性。（1）互斥：同时争夺唯一资源（2）占用且等待（3）无抢占（4）循环等待有界性是一个非常重要的特性，它保证系统在运行过程中不会需要无限的资源。有界性反映一个库所在系统运行过程中能够获得的最大的令牌数，即所能获得的最大资源数，它与系统的初始令牌有关。在实际系统设计中，必须使网络中的每个库所在任何状态下的令牌数小于库所的容量，这样才能保证系统的正常运行。2.3扩展Petri网的触发机制扩展的Petri网能够区别变迁的使能和变迁的实施两种不同状态。被使能的变迁如果要得以真正实施，必须满足一定的条件即具备相应的触发机制。使被使能的变迁真正实施的外部条件即为触发机制，它主要由以下4种类型：第一，自动触发：变迁被使能的同时触发，通常用于那些通过应用程序来自动执行、不需要与人进行交互的自动型活动。第二，人工触发：活动的执行通过执行者从工作流任务管理器提供的工作流任务表中选择工作项来进行触发。当执行者选中某一工作项时，此工作项开始执行，被转换为活动。第三，消息触发：由系统外部的消息(事件)来触发，如E-mail，EDI消息的到来。第四，时间触发：由控制时间的定时器来触发。3基于Petri网的工作流网研究作为一种良好的建模工具，如今Petri网已经被广泛地运用到很多方面。如数据分析、协议验证、工作流管理、工作流模式、并行程序设计、软件设计等。但是由于经典Petri网存在没有测试库所中零令牌的能力、模型容易变得很庞大、模型不能反映时间方面的内容、不支持构造大规模模型如自顶向下或自底向上等局限性，在实际运用中需要对其进行改进。为了解决这些问题Aalst等人对经典Petri网进行了扩展和改进，定义了工作流网(Workflownet，WF-net)模型及其有效性准则，采用了任务对应变迁、状态对应库所的策略，孤立地定义了单个案例的动态行为。当用WFN对工作流模型进行描述时，库所用的圆圈表示条件，有两方面的作用：确保任务按正确的次序执行；用来表示案例的状态。而变迁节点用的矩形表示工作流任务。库所到变迁或变迁到库所间的弧表示任务和工作流的逻辑关联形式。库所中包含的黑点(托肯)表示工作流执行的状态。只有每个输入库所至少有一个托肯，变迁才能够实施。工作流网模型中的任务包括顺序、并行、选择和循环四种路由结构。工作流执行的基本结构由这四种路由构成。这四种路由结构按照一定的方式组合可以合成工作流所有的执行结构。为方便四种路由结构的Petri网表示，引入与分叉、与合并、或分叉、或合并四种构造模块。与分叉和与合并的共同使用表示了一个并行执行过程，或分叉和或合并的共同使用表示了一个选择执行过程。4Petri网模型的化简规则化简技术也称归约技术或模型转换技术，它是以保证模型的基本特点为前提将过程模型化简到适当的程度，以方便对模型可能存在的各种冲突进行检测。对扩展Petri网内对象的化简，首先可以在验证合理性时将与工作流环境紧密相关的触发机制和工作流路由去掉。对于触发机制只是简单地忽略掉就可以了，而对于工作流路由的处理要复杂一些，需要把OR-split、OR-join、AND-split、AND-join这样的工作流元组件还原成经典Petri网中普通的库所和变迁，这样新生成的模型中不再有专门的控制变迁。5Petri网模型的正确性分析工作流过程定义结束后，需要对其进行正确性验证，只有在证明了所建工作流模型无死锁、无死任务，是合理的、安全的之后，对其进行性能分析、仿真优化才有意义。工作流的正确性对业务过程目标的正确完成有着重要的影响。工作流模型的正确性包括两方面的含义：结构上的正确性(即工作流模型是安全的、无死锁的)和语义上的正确性(即在完成业务目标上是与实际业务过程等价的)。对工作流模型的正确性分析主要指对工作流模型结构上的正确性进行分析。目前，在模型的正确性研究方面，主要有以下两种方法：可达图分析和化简。利用Petri网可达图分析技术分析结点较多的模型时，尤其是集成制造领域的模型，其过程会很复杂，验证所需的时间随节点个数呈指数增长会导致状态空间爆炸；而且可达图分析技术只能提供模型正确与否的结论，而无法具体地定位错误，不便辅助设计者修改模型。6Petri网的步语义问题Petri网的步语义（stepsemantics）是一种有效的建模方法，它与顺序语义（sequencesemantics）相比对实际行为的描述更为详尽，而与难以掌握的偏序技术相比更贴近实际，是顺序语义与偏序技术在实用性和表达能力上的折衷。PhilippeDarondeau等人针对步语义可能引起状态爆炸以及缺乏对行为协调有效支持两个缺点，引入了步触发策略，它限制了Petri网并发行为，因此改进了步语义的执行和建模特征。MatthiasJantzen等人比较了各种变迁触发方式，定义了Petri网中通过步、最大步、多步和最大多步语义生成的语言；通过允许在一个多步中多次使用变迁，得到一个语言体系，弥补了带标记Petri网步语义所定义的语言在若干方面的缺失。7Petri网的合成Petri网的合成自20世纪90年代起逐渐成为本领域内一个研究热点，它探讨如何从系统的一个行为规范描述生成一个行为等价Petri网模型。J.Carmona等人提出了一个从变迁系统生成有界Petri网的算法，这个算法基于一般域（generalregion）的理论将已有的Petri网合成算法由安全网扩展到有界网，根据这一扩展，合成算法的适用范围扩大到带有权弧的k-阶Petri网。而且这个合成算法使用基于BDD的符合化表示方法来表达状态空间，从而有效地生成最小域，与安全网的合成方法相比，生成的网模型更简单直观。通过研究有步触发策略的Petri网合成方法，给出一个公理，说明一个变迁系统在何种条件下能够由一个给定步进触发策略控制的Petri网的可达图来表示。J.M.E.M.vanderWerf等人给出了一种基于域理论的流程发掘算法，由系统的执行日志生成Petri网模型。域理论起源于硬件设计控制领域，用于由行为说明构造Petri网。由于域理论直接应用于流程发掘会导致生成的网模型中库所个数依赖于日志规模，作者通过引入整数线性规划思想，由库所来限制网的可能触发序列，解决了这个问题。在展示工具的论文中，也有一篇是关于Petri网合成的：RobinBergenthum等人展示了一个由场景合成Petri网的工具，它为基于Petri网的商业流程工具viptool加入了Petri网合成的新特性，改写了流程建模的起点，由用户设计