系统建模与仿真第三章课件.ppt

系统建模与仿真,第三章 离散事件系统建模,管理科学与工程学院付 赟,2023/3/25,系统建模与仿真,2,3.1 离散事件系统,离散事件系统的性质与连续系统完全不同，这类系统的状态只在离散的时间点上发生变化，而且这些离散的时间点是不确定的。例1：理发店就是一个典型的离散事件系统的例子。,2,系统建模与仿真,2023/3/25,2023/3/25,系统建模与仿真,3,3.1 离散事件系统,对于离散事件系统来说，系统的内部状态变化是随机的，同一个内部状态可以向多种状态转变，因此很难用函数形式来描述系统内部状态的变化，通常所关心的是系统内部状态变化的统计规律。系统的内部状态只在离散的随机时间点上发生变化，且状态在一段时间内保持不变。因此在建立离散事件系统模型时，只需考虑系统内部状态发生变化的时间点以及产生这些状态变化的原因，而不用描述系统内部状态发生变化的过程。,3,系统建模与仿真,2023/3/25,2023/3/25,系统建模与仿真,4,1、实体1）定义：实体(Entity)是指一个系统边界内部的客观对象，离散事件系统是由实体组成的。2）分类：临时实体 先进入系统并经过相应的环节后再离开系统，且在系统中的数量经常变化的实体，又称为主动实体、活动实体。永久实体 经常处于系统之内，其数量保持稳定的实体，又称为被动实体。,3.1.1 离散事件系统要素,4,系统建模与仿真,2023/3/25,2023/3/25,系统建模与仿真,5,3.1.1 离散事件系统要素,系统的工作过程实质上就是临时实体流动和接受加工、处理的过程。如：排队的顾客，待加工的工件等永久实体只要系统处于活动状态，它就一定存在。如：商店的营业员，加工设备等临时实体按一定规律不断到达，在永久实体作用下通过系统，最后离开系统。系统状态的变化主要是由实体的状态变化而产生的。,5,系统建模与仿真,2023/3/25,2023/3/25,系统建模与仿真,6,2、事件1）定义 事件(Event)是引起系统状态发生变化的行为。离散事件系统可以看做是由事件驱动的，它是在某一时间点的瞬间行为，如：待加工工件、顾客等的“到达”或“离开”等。事件不仅用来协调两个实体之间的同步活动，还用于各实体之间的信息传递。,3.1.1 离散事件系统要素,6,系统建模与仿真,2023/3/25,2023/3/25,系统建模与仿真,7,3.1.1 离散事件系统要素,2）分类时间事件和状态事件时间事件：依照系统的作业规则在预订时间发生的事件。状态事件：当系统状态符合某种条件下发生的事件。基本事件和二次事件基本事件：其发生可以事先加以预测的事件。二次事件：发生与否则取决于其他事件。如：顾客到达和接受服务,7,系统建模与仿真,2023/3/25,2023/3/25,系统建模与仿真,8,3.1.1 离散事件系统要素,3、活动 活动(Active)是实体在两个事件之间保持某一状态的持续过程。如：顾客接受服务的过程，工件被加工的过程 活动因某一事件的发生而开始，因下一事件的发生而结束，因此它标志着实体状态迁移的一个片段。如：在“顾客到达”与“服务开始”两个事件之间存在一个“排队等候”活动；“服务开始”与“服务结束”之间存在“顾客接受服务”活动。,8,系统建模与仿真,2023/3/25,2023/3/25,系统建模与仿真,9,3.1.1 离散事件系统要素,4、进程 进程(Process)是由与某类实体相关的事件和若干活动组成的，它描述了这些事件和活动间的相互逻辑关系和时序关系。如：“顾客到达系统排队开始接受服务服务结束”的过程就构成了一个进程。进程是事件与活动的组合，它可以更加完整地描述实体状态的迁移过程。,9,系统建模与仿真,2023/3/25,3.1.1 离散事件系统要素,2023/3/25,系统建模与仿真,10,理发店例子中进程的含义,10,系统建模与仿真,2023/3/25,2023/3/25,系统建模与仿真,11,3.1.1 离散事件系统要素,5、属性 属性(Attribute)是实体特征的描述，是实体所拥有的全部特征的一个子集，用特征参数变量表示。在仿真建模中，只需要使用与研究目的相关的一部分就可以了。,11,系统建模与仿真,2023/3/25,2023/3/25,系统建模与仿真,12,3.1.1 离散事件系统要素,6、状态 状态(State)是指在某时间点上对系统的所有实体属性和活动的描述。当一个系统的所有实体处于状态协调并定义状态的属性时，则认为系统处于特定状态。如：在随机服务系统模型中，“顾客”有“等待服务”和“接受服务”等状态，“服务员”有“忙”和“闲”等状态。活动总是与一个或几个实体的状态相对应，状态可作为动态属性进行描述。,12,系统建模与仿真,2023/3/25,2023/3/25,系统建模与仿真,13,3.1.1 离散事件系统要素,13,系统建模与仿真,2023/3/25,2023/3/25,系统建模与仿真,14,3.1.1 离散事件系统要素,7、仿真时钟 仿真时钟用于表示仿真时间的变化及作为仿真过程的时序控制，它是系统运行时间在仿真过程中的表示。仿真时钟推进的方式：固定步长时间推进机制下次事件时间推进机制 仿真时钟推进的时间间隔称为仿真步长，离散事件系统仿真时钟的推进步长是随机的，取决于系统的当前状态和事件发生的条件。,14,系统建模与仿真,2023/3/25,2023/3/25,系统建模与仿真,15,3.1.1 离散事件系统要素,8、系统环境 系统环境(System Environment)是系统周围的对象及过程(实体和活动)。发生于系统内部的活动称为内生活动，发生于系统环境中并对系统产生影响的活动称为外生活动，将活动划分为内生活动和外生活动就确定了系统的边界。,15,系统建模与仿真,2023/3/25,3.1.1 离散事件系统要素,确定系统的状态变量是很重要的。由于进行仿真研究的系统状态变量并不总是固定唯一的，它应当根据系统仿真研究的目的而确定。描述系统状态变化的流程到达并进入系统中实体的类型和数目使系统状态发生变化的事件类型事件发生时间的分布规律等,2023/3/25,系统建模与仿真,16,16,系统建模与仿真,2023/3/25,2023/3/25,系统建模与仿真,17,3.1.1 离散事件系统要素,离散系统实例,17,系统建模与仿真,2023/3/25,2023/3/25,系统建模与仿真,18,3.1.2 离散事件系统建模方法,建模是仿真的前提，是计算机仿真的关键技术内容之一；模型不正确，仿真的结果也失去意义由于随机事件系统的模型很难用常规的微分方程、差分方程来描述；随着系统科学和管理科学的发展机及其在各领域中应用的不断深入，逐步形成了一些与连续系统不同的建模方法主流方法：流图和网络图,18,系统建模与仿真,2023/3/25,3.1.2 离散事件系统建模方法,1、实体流图法与计算机程序流程图类似可以描述实体产生、流动、消亡及其被永久实体加工、处理的过程和逻辑关系实体流图模型易于转换为面向事件的仿真模型,2023/3/25,系统建模与仿真,19,19,系统建模与仿真,2023/3/25,3.1.2 离散事件系统建模方法,2、活动周期图法针对实体的行为模式进行建模可以直观地表示出某类实体生命周期中的活动和状况具有规范化的特点对不同实体之间协同关系的描述清晰、明确易于转换为面向活动的仿真模型,2023/3/25,系统建模与仿真,20,20,系统建模与仿真,2023/3/25,3.1.2 离散事件系统建模方法,3、Petri网法适于建立加工系统等多种离散事件系统的模型对网系统的特性进行较严密的数学分析处理并发、冲突、死锁等现象,2023/3/25,系统建模与仿真,21,21,系统建模与仿真,2023/3/25,2023/3/25,系统建模与仿真,22,3.2 实体流图法,系统要对临时实体产生作用，就必须有永久实体的活动，也就是必须有永久实体。临时实体和永久实体协同完成了某项活动，永久实体作为活动的资源而被占用。理发店的服务员，交通路口的红绿灯等都是永久实体的例子。,22,系统建模与仿真,2023/3/25,3.2.1 实体流图法概述,实体流图法(Entity Flow Chart，EFC)采用与计算机程序流程图相类似的图示符号和原理，建立表示临时实体产生、在系统中流动、接受永久实体“服务”，以及消失等过程的流程图。借助实体流程图，可以表示事件状态变化及实体间相互作用的逻辑关系。在离散事件系统中实体流图法应用比较普遍，原因如下：1）计算机程序框图的思想和方法已广为人们所接受；2）实体流图法简单，且对离散事件系统的描述比较全面。,23,系统建模与仿真,2023/3/25,3.2.2 实体流图法的建模思路,对建模者的两点要求：1）对实际系统的工作过程有深刻的理解和认识2）将事件、状态变化、活动和队列等概念贯穿于建模过程中常用的图示符号：菱形框（判断）；矩形框（事件、状态、活动）；圆角矩形框（开始和结束）；箭头（逻辑关系）,24,系统建模与仿真,2023/3/25,3.2.2 实体流图法的建模思路,建模的一般步骤如下：1）明确组成系统的各个实体及其属性2）分析各种实体的状态和活动，及其相互间的影响。3）考察那些导致活动的开始或结束的事情，或者是可以作为活动开始或结束的标志的事件，以确定引起实体状态变化的事件，并将条件事件合并。4）分析各种事件发生时实体状态是如何变化的。5）在一定的服务流程下，分析与队列实体有关系的特殊操作(如换队等)。,25,系统建模与仿真,2023/3/25,3.2.2 实体流图法的建模思路,6）根据以上分析，以临时实体的流动为主线，用约定的图示符号画出被仿真系统的实体流图。7）确定模型参数的取值、参变量的计算方法及属性描述变量的取值方法。属性描述变量(例如顾客到达时间、服务时间等)既可以取一组固定值，也可以由某一公式计算得到，还可以是一个随机变量。如果属性描述变量是随机变量，就应该给出其分布函数。8）确定队列的排队规则。当有多个队列存在时，还应给出其服务规则，例如队列的优先权、换队规则等。,26,系统建模与仿真,2023/3/25,3.2.3 实体流图法的实例分析,例1：理发店服务系统 单服务台、单队列服务系统有一个小理发店只有一个理发员，顾客来到理发店后，如果有其他顾客正在理发就坐在一旁等候。理发员按先来先理的原则为每一位顾客服务，而且只要有顾客就不停歇。建模目的是在假定顾客到达时间间隔和理发花费的时间服从一定的概率分布时，考察理发员的忙闲情况。,2023/3/25,系统建模与仿真,27,27,系统建模与仿真,2023/3/25,3.2.3 实体流图法的实例分析,（1）辨识系统实体三个实体：理发员是永久实体，顾客是临时实体，顾客队列是一类特殊实体（2）分析实体的状态和活动类实体的组成理发员的活动有“理发”和“休息”，对应“忙”和“闲”两种状态顾客与理发员协同完成理发活动，有“等待服务”和“接受服务”两种状态顾客队列的状态由队列长度来标识三类实体的活动及状态之间存在逻辑上的关系,2023/3/25,系统建模与仿真,28,28,系统建模与仿真,2023/3/25,3.2.3 实体流图法的实例分析,（3）分析实体状态的变化情况某一顾客到达时，如果理发员处于“忙”状态，则该顾客进入“等待服务”状态；否则进入“接受服务”状态理发员完成对某一顾客的服务时，如果队列处于“非零”状态，则立即开始服务活动；否则进入“闲”状态处于排队等待中的顾客，如果理发员完成了对前一顾客的服务，则进入“接受服务”状态；否则保持“等待服务”状态,2023/3/25,系统建模与仿真,29,29,系统建模与仿真,2023/3/25,3.2.3 实体流图法的实例分析,（4）分析引起状态变化的事件“顾客到达”或“顾客结束排队”导致“服务”活动的开始；而“顾客理完离去”导致“服务”活动的结束；这三个瞬时行为均可以作为事件看待。“顾客结束排队”是以理发员状态是“闲”为条件的；而队列状态是“非零”时理发员状态为“闲”是以事件“顾客理完离去”为条件的；以上两个条件事件顺序、互为因果。将“顾客结束排队”事件并入“顾客理完离去”事件，不予单独考虑，即合并条件事件。“顾客到达”将使理发员由“闲”变为“忙”，或使“队列长度”增加1。“顾客理完离去”将使理发员由“忙”变为“闲”。“顾客结束排队”将使“队列长度”减少1，并使理发员由“闲”变为“忙”。,2023/3/25,系统建模与仿真,30,30,系统建模与仿真,2023/3/25,3.2.3 实体流图法的实例分析,（5）分析队列实体的操作该问题只有一个队列，而且顾客不会因为排队人数太多而离去，因此队列规则简单，没有换队等特殊的队列操作。（6）画出系统实体流程图基于实体、活动和事件的分析从实体进入系统开始，按照事件和活动相互交替的原则，按顺序画出实体在系统中的流动过程。对条件事件，可在事件框前加入条件判断,2023/3/25,系统建模与仿真,31,31,系统建模与仿真,2023/3/25,3.2.3 实体流图法的实例分析,2023/3/25,系统建模与仿真,32,单线框：事件双线框：活动,理发员为忙、理发员为闲：设置系统标志的特殊操作，可以不画,32,系统建模与仿真,2023/3/25,3.2.3 实体流图法的实例分析,（7）确定模型参变量顾客的到达时间（随机变量）理发员为一个顾客理发所需的服务时间（随机变量）（8）给出排队规则队列的排队规则是先到先服务（FIFO）说明：实体流图是为描述实体流动和相互间逻辑关系而绘制的，与计算机程序框图不同,2023/3/25,系统建模与仿真,33,33,系统建模与仿真,2023/3/25,3.2.3 实体流图法的实例分析,例2：售票窗口服务系统 两类顾客竞争资源电影院雇用一名售票员同时负责电影票的销售和对电话问询者的咨询服务。窗口服务比电话服务优先级高。问询者打来的电话由电话系统存储后按先来先服务的规则一一予以答复。建模的目的是研究售票员的忙闲率。,2023/3/25,系统建模与仿真,34,34,系统建模与仿真,2023/3/25,3.2.3 实体流图法的实例分析,（1）辨识系统实体售票员：永久实体；购票者和电话问询者：临时实体；购票队列和问询队列：特殊实体。,2023/3/25,系统建模与仿真,35,35,系统建模与仿真,2023/3/25,3.2.3 实体流图法的实例分析,（2）分析实体状态和活动类实体组成售票员有“空闲”、“售票”和“接电话”3个活动，对应的是“闲”和“忙”两种状态购票者有“排队”和“购票”2个活动，对应的是“等待”和“购票”两种状态问询者有“排队”和“问询”2个活动，对应的是“等待”和“问询”两种状态顾客队列的状态以队列长度标识4类实体的活动及状态存在逻辑上的联系,36,系统建模与仿真,2023/3/25,3.2.3 实体流图法的实例分析,（3）分析实体状态变化的情况购票者或者问询者到达时，如果售票员处于“忙”状态，则该顾客进入“等待”状态；否则，进入“购票”或“问询”状态处于排队等待中的顾客，如果售票员完成了对前一顾客的服务，则进入“购票”或“问询”状态；否则，继续保持“等待”状态,37,系统建模与仿真,2023/3/25,3.2.3 实体流图法的实例分析,（4）分析引起状态变化的事件“购票者到达”、“问询者到达”、“购票者结束排队”或者“问询者结束排队”导致售票员“服务”活动的开始“购票者买票后离去”或“问询者咨询后离去”导致售票员“服务”活动结束,38,系统建模与仿真,2023/3/25,3.2.3 实体流图法的实例分析,（5）分析队列实体的操作该问题有两个队列，但两个队列中的顾客不会互换队列（6）画出系统实体流程图以临时实体为主线，画出实体流程,39,系统建模与仿真,2023/3/25,3.2.3 实体流图法的实例分析,40,系统建模与仿真,2023/3/25,3.2.3 实体流图法的实例分析,（7）确定模型参变量购票者到达时间电话问询者到达时间售票服务时间电话服务时间（8）给出排队规则排队规则：FIFO服务规则：购票者和问询者分别排队，优先进行购票活动,41,系统建模与仿真,2023/3/25,3.2.3 实体流图法的实例分析,两个与服务规则有关的判断和特殊操作当“电话问询者”和“窗口购票者”同时到达，且售票员处于“闲”的状态，后者接受服务，前者加入电话队列当服务完毕，且购票队列和电话队列均不为空时，先进行购票服务由于本例中有两类临时实体同时流动,因此可能出现资源冲突,对此类问题的描述,活动周期图有其独到之处.,42,系统建模与仿真,2023/3/25,3.2.4 模型的人工运行,建立实体流程图模型后，选取有代表性的例子将流程图全部走一遍，即所谓人工运行。人工运行模型要求遍历流程图的各个分支和实体的各种可能状态，在时间逐步变化的动态条件下，分析事件的发生及状态的变化过程，以检查模型的组成和逻辑关系是否正确。,2023/3/25,系统建模与仿真,43,3.2.4 模型的人工运行,例1中，假定：（1）系统的初始状态包括永久实体“理发员”的状态及特殊实体“队列”的状态初始时刻是仿真开始的时刻，理发员为“闲”，队列长度为0（2）模型参数及变量的取值第i个顾客与第i-1个顾客到达的时间间隔Ai理发员为第i个顾客的理发时间Si两个都是随机变量，可根据其分布函数来产生,2023/3/25,44,系统建模与仿真,3.2.4 模型的人工运行,模型需按照一定的规则运行，本模型的人工运行规则如下：规则1确定当前时间模型人工运行开始时，取当前时间TIME=t0（初始仿真时刻）人工运行开始后，当前时间逐步向前推移，且递取下一最早发生事件的发生时刻如果当前时间有顾客到达事件发生，转规则2若有顾客离去事件发生，则转规则3,2023/3/25,45,系统建模与仿真,3.2.4 模型的人工运行,规则2顾客到达事件处理假定在时刻TIME有顾客i到达，如果理发员“忙”，则入队列等待，队列长度加1否则，置理发员为“忙”状态，顾客开始理发，且在di=TIME+Si时刻理毕离去规则3顾客离去事件处理假定在时刻TIME有顾客i离去，如果此时队列长度为0，置理发员为“闲”状态否则，队列中排在队首的一名顾客开始理发，队列长度减1，顾客在di=TIME+Si时刻理毕离去,2023/3/25,46,系统建模与仿真,3.2.4 模型的人工运行,令A1=15，A2=32，A3=24，A4=40，令S1=43，S2=36，S3=34，S4=28，（1）在TIME=t0时刻，无任何事件发生下一最早发生的事件为“顾客1到达”，发生时刻为a1=TIME+A1=15（2）在TIME=15时刻，顾客1到达按规则2，理发员开始为顾客1理发，状态由“闲”变“忙”顾客1离去时刻d1=TIME+S1=15+43=58下一最早发生的事件为“顾客2到达”，顾客2到达的时刻为a2=a1+A2=15+32=4758,2023/3/25,47,系统建模与仿真,3.2.4 模型的人工运行,（3）在TIME=47时刻，顾客2到达因理发员“忙”，顾客2排队等待，队列长度变成1下一最早发生的事件为“顾客1离去”，离去时刻 d1=58a3=71（4）在TIME=58时刻，顾客1离去按规则3，队列长度为1，理发员为顾客2理发，队列长度变为0顾客2离去时刻d2=TIME+S2=58+36=94下一最早发生的事件为“顾客3到达”，到达的时刻为a3=a2+A3=47+24=71,2023/3/25,48,系统建模与仿真,3.2.4 模型的人工运行,（5）在TIME=71时刻，顾客3到达，,2023/3/25,49,系统建模与仿真,3.3 活动周期图法,实体流图法中，实体的行为模式在有限的几种情况之间周而复始地变化，表现出一定的生命周期形式如：理发员在“忙”和“闲”之间不断变化；顾客在“到达”、“等待”、“理发”和“离去”之间变化活动周期图法（Activity Cycle Diagram，ACD）正是基于这样的思想而逐步形成的一种离散事件建模方法,2023/3/25,50,系统建模与仿真,3.3.1 活动周期图概述,以直观的方式显示了实体的状态变化历程和各实体之间的交互作用关系，便于理解和分析。充分反映各类实体的行为模式，并将系统的状态变化以“个体”状态变化的集合方式表示出来，因此可以更好地表达众多实体的并发活动和实体之间的协同关系。但是，它只描述了系统的稳态，而没有表示系统的瞬态，即活动的开始和结束事件。,2023/3/25,51,系统建模与仿真,活动周期图建模方法将实体的状态分为静寂(Dead)和激活(Active)两种。,(a)静寂状态(b)激活状态,激活状态通常是实体的活动，模型中活动的忙期可采用随机采样等方法事先加以确定。静寂状态通常表示无活动发生，是实体等待参加某一活动时的状态，其持续时间在模型中无法事先确定，取决于有关活动的发生时刻和忙期。,3.3.2 活动周期图建模,2023/3/25,52,系统建模与仿真,3.3.2 活动周期图建模,活动周期图法建模过程（1）辨识组成系统的实体及属性辨识永久实体及临时实体，队列不作为实体考虑（2）分别画出个实体的活动周期图以实际过程为依据，队列作为排队等待状态来处理交替原则：静寂状态和激活状态必须交替出现闭合原则：临时实体的ACD表示一个或单位实体从产生到消失的循环过程；永久实体的ACD表示一个或几个实体被占用和释放的循环往复过程,2023/3/25,53,系统建模与仿真,3.3.2 活动周期图建模,2023/3/25,54,系统建模与仿真,3.3.2 活动周期图建模,（3）将各实体的ACD连接成系统ACD以各实体之间的协同活动为纽带进行连接（4）增添必要的虚拟实体ACD中，当一个活动的所有前置静寂状态均取非零值时，该活动才有可能发生，可以增添某些必要的虚拟实体，并假定它们与另外的实体协同完成某项活动为实体活动的发生加上某种附加条件，从而实现“隔时发生”的建模效果,2023/3/25,55,系统建模与仿真,3.3.2 活动周期图建模,（5）标明活动发生的约束条件和占用资源的数量活动是否可以发生的判断条件永久实体在参加一次协同活动时被占用和活动完成时释放的数量（6）给出模型参数的取值、参变量的计算方法及属性描述变量的取值方法，并给出排队规则和服务规则,2023/3/25,56,系统建模与仿真,3.3.2 活动周期图法建模举例,例3：机床加工系统的活动周期图法建模 操作工有休息饮茶的权利考虑一个简单的加工车间。车间内有数台自动机床，由一名工人负责看管。工人的任务是：如果机床的刀具完好，则为机床安装工件，然后按下运行按钮；如果机床的刀具损坏，则先要重装刀具，然后执行任务。只有当机床完成一次自动加工工序，并停止运行后，工人才能执行上述两项任务。假定每台机床均可加工各种工件，并且不会发生工件短缺的现象。建模的目的是为了研究工人的忙闲率。,2023/3/25,57,系统建模与仿真,3.3.2 活动周期图法建模举例,建模考虑的两类实体：机床、工人（1）工人活动：安装工件(RESET)，安装刀具(RETOOL)，其他活动(AWAY)三种活动均为激活状态否则，处于静寂状态“等待”，该状态取决于激活状态,2023/3/25,系统建模与仿真,58,3.3.2 活动周期图法建模举例,（2）机床三种激活状态：安装刀具，安装工件，加工(RUWNING)引入“预备”、“停机”两种静寂状态：满足交替原则的要求,2023/3/25,系统建模与仿真,59,3.3.2 活动周期图法建模举例,工人只要不从事“安装刀具”和“安装工件”的工作，就可从事“其他活动”。即，“等待”是“其他活动”的唯一前置条件。问题：限定工人每隔2h才能休息10min，如何在活动周期图中表示？办法：引入虚拟实体工人休息的权力,2023/3/25,系统建模与仿真,60,3.3.2 活动周期图法建模举例,权力实体协同工人实体完成“饮茶”活动，其生命周期中要完成“计时”（RECORD）这一活动。为了满足交替原则，增添“有权”(YES)和“无权”(NO)两种状态。权力实体的引入满足了每隔一段时间方可进入某一活动的建模需要,2023/3/25,系统建模与仿真,61,3.3.2 活动周期图法建模举例,2023/3/25,系统建模与仿真,62,3.3.2 活动周期图法建模举例,模型参数：“机床数量”模型参变量：“累计加工的工件数”判断当机床处于“停机”状态且工人处于“等待”状态时，机床是否需要重换刀具，从而决定是进入“安装刀具”还是“安装工件”属性变量：“加工时间”、“安装刀具时间”和“安装工件时间”、“饮茶时间”和“轮休时间”,2023/3/25,系统建模与仿真,63,3.3.2 活动周期图法建模举例,服务规则当工人处于“等待”状态时，是先饮茶休息，还是先工作（假定机床处于“停机”状态且权力处于“有权”状态），其选择取决于模型参数的值活动周期图中允许进行分支处理，这时分支状态需要有一个判断变量，根据判断变量的取值情况，可以确定实体的走向。,2023/3/25,系统建模与仿真,64,3.3.2 活动周期图法建模举例,例4：货物运转系统大型货车从工厂拉货到转运站，将货卸在固定的仓位。运来的货物经分拣后放在另外的专用仓位，由小货车运往客户。运转站内有两个卸货仓位，4个装货仓位，每个仓位前均只能停放一辆货车。货物由10名工人负责装卸，装卸一车货物需要2名工人。运送货物的大小货车首先从公路上拐进运转站门口的一个停车场，然后经过一条通道驶往各自的仓位。为了便于办理手续，通道被分为两半，左边出车，右边进车，而且进出通道只能容两辆小货车同时行进。大车的优先级高于小车，出车的优先级高于进车。仓位有空闲时才放货车进入通道。,2023/3/25,系统建模与仿真,65,3.3.2 活动周期图法建模举例,建模目的是研究在一定的货物吞吐量下设几个卸货仓位比较合适。不考虑货物数量的影响。实体：大货车、小货车、卸货仓位、装货仓位、工人、进站通道和出站通道7个实体：2个临时实体和5个永久实体,2023/3/25,系统建模与仿真,66,3.3.2 活动周期图法建模举例,（1）大货车由系统“外部”逐个“到达”，经停车场“排队”后，“驶入”卸货仓位“等候”工人“卸货”，“卸空”后“驶离”转运站。激活状态：“到达”、“驶入”、“卸货”和“驶离”协同活动：“外部”、“等候”、“排队”和“卸空”“驶入”活动发生的条件之一：至少有一个卸货仓位空闲（空闲卸仓个数UNBAY0）（2）小货车与大货车类似,2023/3/25,系统建模与仿真,67,2023/3/25,68,系统建模与仿真,2023/3/25,系统建模与仿真,69,3.3.2 活动周期图法建模举例,（3）装、卸仓位（4）装、卸工人（5）进、出通道,2023/3/25,70,系统建模与仿真,2023/3/25,71,系统建模与仿真,2023/3/25,系统建模与仿真,72,3.3.2 活动周期图法建模举例,模型参数：装卸工人的数量，装卸仓位的数量参变量：当前卸货仓位的数量UNBAY，装货仓位的数量BAY，工人的可用数量LABOUR，进、出通道数ROADIN和ROADOUT属性变量：各个活动的忙期，随机变量排队规则：FIFO服务规则：大小货车各排一队，装卸工、进出通道优先为大货车服务，优先安排货车离开货场,2023/3/25,系统建模与仿真,73,3.3.3 模型的人工运行,首先确定系统的初始状态按下列原则运行模型：规则1活动的发生与执行（1）活动的所有前置状态中均有实体停留，且各类永久实体的数量超过或等于相应资源占用量；（2）活动发生的约束条件已经满足。依次检查每一活动，以判断此活动是否可以开始，即此活动所要求的足够的实体集合是否已经存在于所有有关的前置队列中。如果含有，则将这个实体集合的标志移入此活动的矩形内，且计算出此活动的终止时间，并将此时间写在该活动的矩形内。当所有活动都检查完后，转向规则2。,2023/3/25,系统建模与仿真,74,3.3.3 模型的人工运行,规则2确定当前时间检查所有活动的终止时间，选其最小值，并设置时钟值为此选择值，然后转向规则3。规则3活动的完成从所有已发生的活动中，检出终止时间等于当前时间的临时实体，删掉为其标注的终止时间；然后将相应临时实体的标记移至其相关的后续状态中。参与活动的各永久实体的资源量相应增加，将参与活动的永久实体的后续状态作标记，转规则1,2023/3/25,系统建模与仿真,75,3.4 实体流图和活动周期图的比较,第一：EFC以临时实体在系统中的流动过程为主线，永久实体浓缩于表示状态和事件的图示符合中，队列作为一种特殊实体。ACD基于各类临时和永久实体的行为模式，有独特的图示标识，队列成为实体生命周期的一种状态。第二：EFC是带有小循环的树形流程图ACD中，各类实体是环形的循环图，整个系统由多个环套在一起,2023/3/25,系统建模与仿真,76,3.4 实体流图和活动周期图的比较,第三：EFC中，事件有显式的表达ACD中，事件蕴含在活动中，没有显式表达第四：EFC中，状态判断框的作用非常重要ACD中，将需作判断的状态用“空闲”、“等待”等静寂状态表示，对实体是否处于该状态的判断也无需标注在图中，而是作为模型运行时的一般规则,3.5 Petri网建模方法,改变活动周期图建模方法：取消临时实体ACD中的“源”状态，即不再考虑临时实体的生命周期循环将活动看作是“开始事件+状态+结束事件”，则，建模元素就变成“事件”和“状态”，后者包括ACD中的激活状态和静寂状态不强调实体模型之间的独立性用集合论的语言描述后，可以建立规范的Petri网方法,2023/3/25,系统建模与仿真,77,3.5.1 Petri网的基本概念,Petri网是由节点和有向弧组成的一种有向图它有两类节点：库所，即状态元素，它表示一个场所，而且在该场所存放了一定的资源，用“”表示；变迁，它指资源的消耗、使用以及对应状态元素的变化，用“”表示。另外，资源指的是与系统状态发生变化有关的因素。,2023/3/25,系统建模与仿真,78,3.5.1 Petri网的基本概念,2023/3/25,系统建模与仿真,79,Petri网定义：三元组N=(S,T;F)称为Petri网的充要条件是：,3.5.1 Petri网的基本概念,S：库所集；T：变迁集F：由一个S元素和一个T元素组成的有序偶的集合，称为N的流关系dom（F）：F所含序偶的第一个元素的集合cod（F）：第二个元素的集合N不能有孤立元素，即S,T,F均不能为空集,3.5.2 网系统,网是系统静态结构的基本描述容量、标识和权重,3.5.2 网系统,例5：有一条工业生产线，它要完成两项工业操作，这两项操作用t1和t2表示。第一个变迁t1将传入生产线的半成品s1和部件s2用两个螺丝钉s3固定在一起，变成半成品s4。第二个变迁t2再将s4和部件s5用3个螺丝钉s3固定在一起，得到新的半成品s6。完成操作t1和t2时都要用到工具s7。假定由于存放空间的限制，部件s2和部件s5最多不能超过100件，停放在生产线上的半成品s4最多不能超过5件，螺丝钉s3存放最多不能超过1000件。,3.5.2 网系统,3.5.2 网系统,（1）容量K(s)标识库所s中允许存放令牌的最大数量，其值标在表示库所的圆圈旁，不标明时容量为（2）权W(x,y)表示变迁发生时消耗和产出的令牌数量，其值标在弧（x，y）上；不标明时表示权为1（3）令牌表示原料、部件、产品、人员、工具、设备、数据和信息等组成系统的“资源”，标识M(s)的值用令牌数表示,3.5.2 网系统,2023/3/25,系统建模与仿真,85,3.5.3 Petri网的变迁原则,当变迁不断发生时，网系统的状态也不断发生变化，这一过程称网系统的执行。,2023/3/25,系统建模与仿真,86,3.5.3 Petri网的变迁原则,1）一个变迁被授权发生，当且仅当该变迁的每一个输入库所中的令牌数大于或等于输入弧的权值，并且该变迁的输出库所中已有的令牌数与输出孤权值之和小于输出库所的容量；简单地说就是“前面够用，后面够放”。2）变迁发生(点火)的充要条件是该变迁是授权的。3）变迁发生时，从该变迁的输入库所中移出与输入弧权值相等的令牌数，输出库所中产生与输出弧权值相等的令牌数。,2023/3/25,系统建模与仿真,87,3.5.3 Petri网的变迁原则,3.5.3 Petri网的变迁原则,3.5.4 Petri网的行为性质,Petri网的模型只给出系统的静态结构及特征，系统的动态行为是在Petri网的运行过程中体现出来的，主要由它的一些性质来描述。状态标识为一个向量，代表网中相应序号库所中所含令牌的数量，它反映了令牌在网中的分布情况。,定义(可达性)对于Petri网N,若存在tT 使得MtM，则称M是从M 直接可达的。若存在变迁序列=t1，t2，tk和标识序列=M1，M2，Mk 使得Mt1 M1 t2 M2Mk-1tkMk,则称Mk是从M 可达的，记作MoM。所有由M 可达的标识集合记为R(N,M)。可达性用于验证系统能否达到某种状态。,3.5.4 Petri网的行为性质,给定一个Petri网(N，M0)，一定可以建立起表达其可达集R(N，M0)的一个树状结构的图形，称之为Petri网(N，M0)，的可达树。可达树具有如下一些属性：（1）可达树在图形结构上呈倒立状树形；（2）从树根出发，按照由树根节点激发出的“使能变迁节点”个数来生长出相同个数的支线，并将使能变迁标注在对应的支线旁，各个支线末端为相应使能变迁发生后达到的新状态标识即新令牌分布，由此形成一批新的分支点，以这些分支点为起点，按相同原则，依次伸展；,3.5.4 Petri网的行为性质,（3）有限可达集对应于有限可达树，而无限可达集用有限可达树来表示。具体引入以下附加规定：a、分支的终止支点。伸展出的一个新节点在先前的支点或其它分支点出现过，该分支点终止延伸；b、引入无限参量。可达树构造过程中，如果某个支点M比由树根M0到M的一条分支上的一个“中途”支点M*要大，即支点M和M*的每个位置节点的令牌数均有M(pj)M*(pj),则对支点M中满足“”关系的位置节点采用无限参量来替代令牌数。,3.5.4 Petri网的行为性质,3.5.4 Petri网的行为性质,定义(有界性)如果对于sS 及任意M R(N，M0),都有M(S)K,则称网是K有界的,特别地，当K=1 时称此网是安全的。有界性保证了系统的缓冲区不会溢出,工件在某个操作阶段不会堆积。有界性判别：一个Petri网(N，M0)为有界的,即其可达集R(N，M0)为有限，当且仅当Petri网的可达树中不出现无限参量。安全性判别：一个Petri网(N，M0)是安全的,当且仅当Petri网的可达树的所有支点的位置标识中，只包含0和1两类元。,3.5.4 Petri网的行为性质,3.5.4 Petri网的行为性质,定义(死锁)对给定初始标识即初始令牌分布M0的一个Petri网R(N，M0)，称其一个变迁节点t为死锁，如果对由初始令牌分布M0可达的任一令牌分布MR(N，M0)下，此节点变迁t都是不使能即不具发射权的。在工程系统如柔性生产系统等的设计中，务必要从结构上尽可能避免死锁的存在，以保证系统的信息和物料的运行过程不致瘫痪。,3.5.4 Petri网的行为性质,定义(活性)对tT 和M R(N，M 0)，如果存在MR(N,M),使得M t,则称 t 是活的。所有的 tT 都是活的,则称网N 是活的。活性保证了系统不会出现死锁,生产可以正常连续进行。在活性 Petri 网中,无论怎样选取点火序列,都保证不会出现死锁。,死锁的判别：一个Petri网(N，M0)的一个变迁t是死锁的，当且仅当此变迁节点t不出现在Petri网的可达树的任一分支上。,3.5.4 Petri网的行为性质,M0=(1,1,1,0,0,0,0,0,0,0),t1、t2 冲突，让t1发生,M0=(1,0,0,1,0,0,0,0,0,0),t3发生,M0=(1,0,0,0,0,1,0,