离散事件建模与仿真

192第7章离散事件系统建模与仿真离散事件系统指的是一组实体为了达到某些目的，以某些规则相互作用、关联而集合在一起。与连续事件系统不同，离散事件系统所包含的事件在时间上和空间上都是离散的。离散事件系统在生产和生活中是很常见的，例如一个超市就是一个离散事件系统，它由顾客和收银员组成。在离散事件系统中，各事件以某种顺序或在某种条件下发生，并且大都是随机性的，所以，其模型很难用某种规范的形式，一般采用流程图或者网络图的形式来定义实体在系统中的活动。这类系统在建模时，只要考虑系统内部状态发生变化的时间点和发生这些变化的原因，而不用描述系统内部状态发生变化的过程。本章将介绍几种常见的离散事件系统和离散事件系统建模方法。7.1离散事件系统模型离散事件系统是指系统的状态仅在离散的时间点上发生变化的系统，而且这些离散时间点一般是不确定的。这类系统中引起状态变化的原因是事件，通常状态变化与事件发生是一一对应的。事件的发生没有持续性，可以看作在一个时间点上瞬间完成，事件发生的时间点是离散的，因而这类系统称为离散事件系统。首先看一个典型的离散系统的例子。例7.1超市服务系统某理发店只有一名理发师。在正常的工作时间内，如果理发店没有顾客，则理发师空闲；如果有顾客，则为顾客理发。如果顾客到达理发店时，理发师正在为其他顾客服务，则新来的顾客在一旁排队等候。显然，每个顾客到达理发店的时间是随机的，而理发师为每个顾客服务的时间也是随机的，进而队列中每个顾客的等候时间也是随机的。下面，结合例7.1介绍一下在离散事件系统仿真中所用到的一些基本概念。(1)实体实体是指有可区别性且独立存在的某种事物。在系统中，构成系统的各种成分称为实体，用系统论的术语，它是系统边界内的对象。在离散事件系统中，实体可分为两大类：临时实体和永久实体。临时实体指的是只在系统中存在一段时间的实体，这类实体由系统外部到达系统，在系统仿真过程中的某一时刻出现，最终在仿真结束前从系统中消失。例7.1中，顾客是临时实体，他们按一定的规律到达，经过理发师服务（可能要排队等待一段时间），最终离开系统。那些虽然达到，但未进入理发店的顾客则不能称为该系统的临时实体。永久实193体指的是永久驻留在系统中的实体，只要系统处于活动状态，这些实体就存在。例7.1中，理发师是永久实体，只要系统处于活动状态，这些实体就存在。可以这样说，永久实体是系统处于活动的必要条件。临时实体按一定规律出现在仿真系统中，引起永久实体状态的变化，又在永久实体作用下离开系统，如此整个系统呈现出动态变化的过程。(2)事件事件是引起系统状态发生变化的行为，它是在某一时间点上的瞬间行为。从某种意义上说，离散事件系统可以看作是由时间驱动的。例7.1中，可以定义顾客到达为一类事件。因为由于顾客的到达，系统的状态——理发师的“状态”可能从闲变到忙，或者另一系统状态——排队的顾客人数发生变化（队列人数加1）。一个顾客接受服务完毕后离开理发店系统也可以定义为一类事件——顾客离开，此事件可能使理发师的“状态”从忙变为闲。(3)属性实体的状态由它的属性的集合来描述，属性用来反映实体的某些性质。例如理发店服务系统中，顾客是一个实体，性别、身高、年龄、到达事件、离开事件等是他的属性。对一个客观实体，其属性很多，我们在仿真建模中，只需要使用与研究目的相关的一部分就可以了。顾客的性别、身高和年龄与理发店服务关系不大，则在理发店服务系统中不必作为顾客的一个属性，而到达事件、服务事件和离开事件是研究理发店服务效率的重要依据，是理发店服务系统仿真中顾客的属性。(4)状态在某一确定时刻，系统的状态是系统中所有实体的属性的集合。(5)活动实体在两个时间之间保持某一状态的持续过程称为活动。离散事件系统中的活动，通常表示两个相邻事件之间所经历的过程。活动因某一事件的发生而开始，因下一事件的发生而结束，活动的开始与结束都是由事件引起的，因此它标志着实体状态迁移的一个片段。在理发店服务系统中，在“顾客到达”与“服务开始”这两个事件之间存在着一个“排队等候”活动，而在“服务开始”与“服务结束”事件之间存在着一个“理发服务”的活动。从另一个角度来看，排队等候活动的开始和结束，都标志着顾客队列状态发生变化；而理发服务活动的开始和结束，都标志着理发师状态的变化。194(6)进程进程由和某类实体相关的若干事件及若干活动组成，它用于描述一个临时实体从进入系统到离开系统所经历的完整过程，包括期间发生的若干事件和若干项活动，以及这些事件和活动之间的逻辑和时序关系。例7.1中，一个顾客到达理发店系统→排队→理发师为之服务→服务完毕后离开理发店系统的过程，可视为一个进程。事件、活动和进程三者之间的关系可用图7-1描述。排队活动服务活动顾客服务进程顾客到达事件服务开始事件服务结束事件图7-1事件、活动和进程三者关系示意图(7)仿真时钟仿真时钟用于表示仿真时间的变化，作为仿真过程的时序控制。它是系统运行时间在仿真过程中的表示，而不是计算机执行仿真过程的时间长度。仿真时钟推进的时间间隔称为仿真步长。将连续模型进行离散化后而成为仿真模型时，仿真时间的变化由仿真步长确定，可以是定步长，也可以是变步长。而在离散事件系统仿真中，在任何两个相邻发生的事件之间，系统的状态不会发生变化，因此仿真时钟可以跳过这段时间，从上一事件发生时刻直接推进到下一时间发生的时刻。仿真时钟的推进方式基本上有两种：固定步长时间推进机制和下次事件时间推进机制。由事件发生的随机性可见，离散事件系统仿真时钟的推进步长是随机的，它取决于系统的当前状态和事件发生的条件。(8)统计计数器离散事件系统的状态随着事件的不断发生也呈现出动态变化过程，但仿真的主要目的不是要得到这些状态是如何变化的。因为这种变化是随机的，某一仿真运行得到的状态变化过程只不过是随机过程的一次取样，因而如果进行另一次独立的仿真运行所得到的状态变化过程可能全是另外一种情况，它们只有在统计意义下才有参考价值。7.2Petri网建模Petri网是由德国学者CarlAdamPetri（卡尔·A·佩特里）发明的，它是研究信息系统及其相互关系的数学模型。CarlAdamPetri于1962年在他的博士论文“Kommunikationmit195Automaten”（用自动机通信）中提出了一种用于描述事件和条件关系的网络，这就是最初的Petri网。Petri网是一种用简单图形表示的组合模型，具有直观、易懂和易用的优点，它能较好的描述系统的结构，表示系统中的并行、同步、冲突和因果依赖等关系，并以网图的形式，简洁、直观的模拟离散事件系统，分析系统的动态性质，易于在所构造的模型基础上直接实现控制系统。此外，Petri网还有严格而准确定义的数学对象，可以借助数学工具，得到Petri网的分析方法和技术，并用于有限状态机、数据流计算、通讯协议、同步控制、生产系统、形式语言和多处理器系统的建模中，成为离散事件系统的主要建模工具。经过40多年的发展，Petri网理论日益完善，它在机械设计与制造（如柔性制造系统），计算机科学技术（如操作系统、并行编译、网络协议、人工智能等），自动化科学技术（如离散事件动态系统、混杂系统等），以及其他许多科学技术领域都得到了广泛的应用。由于Petri网能表达并发的事件，研究领域趋向认为Petri网是所有流程定义语言之母。7.2.1Petri网的基本概念1.基本术语(1)资源资源指的是与系统状态发生变化有关的因素。例如原料、零部件、产品（产品或半产品）、工具、设备、数据以及信息等。(2)状态元素资源按照在系统中的作用分类，每一类放在一起，则这一类抽象为一个相应的状态元素。(3)库所状态元素就称为库所。它表示一个场所，并且在该场所存放了一定的资源。(4)变迁变迁指的是资源的消耗、使用以及对应状态元素的变化。(5)条件如果一个库所只有两种状态：有标记和无标记，则该库所称为条件。(6)事件涉及条件的变迁称为事件。(7)容量库存所能够存储资源的最大数量称为库所的容量。1962.Petri网的数学结构定义7.1满足下列条件的三元组FTPN;,，称作一个Petri网：1）PT2）PT3）FPTTP4）TPFcodFdom)(其中FyxTPyTPxFdom,:)(FxyTPyTPxFcod,:)(可以看出，P和T是两个不相交的集合（一般情况下可假定它们为有限集），它们是Petri网N的基本元素集。P的元素称为P-元或库所(Place)，也称为位置，T的元素称为T-元或变迁(Transition)，F是Petri网N的流关系(FlowRelation)。用图形来表示一个Petri网时，把一个P-元画成一个小圆圈（“○”），一个T-元画成一个小矩形（“□”）。对TPyx,，若Fyx,，则从x到y画一条有向边。有向边只存在于“○”和“□”之间，任意两个“○”之间或任意两个“□”之间都没有有向边相连接。并且一个Petri网中没有孤立结点。定义7.2设FTPN;,为一个Petri网。对于TPx，记FxyTPyyx,FxyTPyyx,称x为x的前集或输入集，x为x的后集或输出集。xx为元素x的外延。显然，一个库所的外延是变迁集T的一个子集，一个变迁的外延是库所集P的一个子集。对TPx，x的外延xx都不可能是空集（否则x就是一个孤立结点）。例7.2图7-2为一个简单的Petri网FTPN;,的图形表示，其中：库所集12345,,,,Pppppp变迁集123,,Tttt197流关系111213223233244335,,,,,,,,,,,,,,,,,FpttptpptptpttppttpP1t1P2P3t2P4t3P5图7-2一个简单的Petri网示例定义7.3设FTPN;,为一个Petri网。1)若K为从P到N的映射，NPK：，其中,3,2,1N，则K称为N上的容量函数。pK，表示P的容量为无穷；2)映射,2,1,0:PM称为Petri网N的一个标识(Marking)。二元组(N，M)(也即四元组(MFTP,;,))称为一个标识网(MarkedNet)；注意：用图形来表示一个标识网（MFTP,;,）时，对Pp，若kpM，则在表示库所p的“○”内加上k个小黑点（当数值k很大时，也可以直接写上数字k），并说库所p中有k个标识（Token）或标记。3)映射NFW:称为Petri网N的权函数，它对各弧线赋权，用tpW,或ptW,表示由p指向t或由t指向p的有向弧的权重。弧线都用其权重来标注，如果弧线的权重等于1，则标注可以省略。例7.3图7-3为一个具有W的Petri网图。其中：2,,,166512ptWptWptW4,33ptW3,54ptW5466654331,,,,,tpWtpWtpWtpWtpW1981,,,214322ptWptWtpWP1P3P2t2P4t3243P522P6t4t5t6t1图7-3一个具有W的Petri网图3.变迁条件和规则定义7.4一个网系统(NetSystem)是一个标识网MFTP,;,，并具有下面的变迁发生规则(TransitionFiringRule):1)对于变迁Tt，如果1:pMtpPp则说变迁t在标识M下有发生权（Enabled），记为tM。2)若tM，则在标识M下，变迁t可以发生（Fire），从标识M发生变迁t得到一个新的标识M（记为MtM），对Pp其他若若,,1,1pMttppMttppMpM定义7.5六元组MWKFTP,,,;,称为一个库所∕变迁系统(Place/TransitionSy