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

《《系统建模与仿真系统建模与仿真》》第三章第三章 离散事件系统建模离散事件系统建模管理科学与工程学院管理科学与工程学院付付 赟赟2024/7/28《系统建模与仿真》23.1 离散事件系统n离散事件系统的性质与连续系统完全不同，这类系统的状态只在离散的时间点上发生变化，而且这些离散的时间点是不确定的n例1：理发店就是一个典型的离散事件系统的例子2《系统建模与仿真》2024/7/282024/7/28《系统建模与仿真》33.1 离散事件系统n对于离散事件系统来说，系统的内部状态变化是随机的，同一个内部状态可以向多种状态转变，因此很难用函数形式来描述系统内部状态的变化，通常所关心的是系统内部状态变化的统计规律n系统的内部状态只在离散的随机时间点上发生变化，且状态在一段时间内保持不变因此在建立离散事件系统模型时，只需考虑系统内部状态发生变化的时间点以及产生这些状态变化的原因，而不用描述系统内部状态发生变化的过程3《系统建模与仿真》2024/7/282024/7/28《系统建模与仿真》41、实体、实体1）定义：）定义： 实体实体(Entity)是指一个系统边界内部的客观对象，离散事件系统是由实体组成的。

2）分类：）分类： 临时实体临时实体 先进入系统并经过相应的环节后再离开系统，且在系统中的数量经常变化的实体，又称为主动实体、活动实体 永久实体永久实体 经常处于系统之内，其数量保持稳定的实体，又称为被动实体3.1.1 离散事件系统要素4《系统建模与仿真》2024/7/282024/7/28《系统建模与仿真》53.1.1 离散事件系统要素n系统的工作过程实质上就是临时实体流动和接受加工、处理的过程n如：排队的顾客，待加工的工件等n永久实体只要系统处于活动状态，它就一定存在n如：商店的营业员，加工设备等n临时实体按一定规律不断到达，在永久实体作用下通过系统，最后离开系统系统状态的变化主要是由实体的状态变化而产生的5《系统建模与仿真》2024/7/282024/7/28《系统建模与仿真》62、事件、事件1）定义）定义 事件事件(Event)是引起系统状态发生变化的行为 离散事件系统可以看做是由事件驱动事件驱动的，它是在某一时间点的瞬间行为，如：待加工工件、顾客等的“到达”或“离开”等 事件不仅用来协调两个实体之间的同步活动，还用于各实体之间的信息传递。

3.1.1 离散事件系统要素6《系统建模与仿真》2024/7/282024/7/28《系统建模与仿真》73.1.1 离散事件系统要素2）分类）分类n时间事件和状态事件时间事件和状态事件n时间事件：时间事件：依照系统的作业规则在预订时间发生的事件n状态事件状态事件：当系统状态符合某种条件下发生的事件n基本事件和二次事件基本事件和二次事件n基本事件：基本事件：其发生可以事先加以预测的事件n二次事件：二次事件：发生与否则取决于其他事件n如：顾客到达和接受服务7《系统建模与仿真》2024/7/282024/7/28《系统建模与仿真》83.1.1 离散事件系统要素3、活动、活动 活动活动(Active)是实体在两个事件之间保持某一状态的持续过程 如如：顾客接受服务的过程，工件被加工的过程 活动因某一事件的发生而开始，因下一事件的发生而结束，因此它标志着实体状态迁移的一个片段 如如：在“顾客到达”与“服务开始”两个事件之间存在一个“排队等候”活动；“服务开始”与“服务结束”之间存在“顾客接受服务”活动 8《系统建模与仿真》2024/7/282024/7/28《系统建模与仿真》93.1.1 离散事件系统要素 4、进程、进程 进程进程(Process)是由与某类实体相关的事件和若干活动组成的，它描述了这些事件和活动间的相互逻辑关系和时序关系。

如：“顾客到达系统—排队—开始接受服务—服务结束”的过程就构成了一个进程 进程是事件与活动的组合，它可以更加完整地描述实体状态的迁移过程9《系统建模与仿真》2024/7/283.1.1 离散事件系统要素2024/7/28《系统建模与仿真》10理发店例子中进程的含义理发店例子中进程的含义10《系统建模与仿真》2024/7/282024/7/28《系统建模与仿真》11 3.1.1 离散事件系统要素5、属性、属性 属性属性(Attribute)是实体特征的描述，是实体所拥有的全部特征的一个子集，用特征参数变量表示 在仿真建模中，只需要使用与研究目的相关的一部分就可以了11《系统建模与仿真》2024/7/282024/7/28《系统建模与仿真》123.1.1 离散事件系统要素6、状态、状态 状态状态(State)是指在某时间点上对系统的所有实体属性和活动的描述当一个系统的所有实体处于状态协调并定义状态的属性时，则认为系统处于特定状态 如：在随机服务系统模型中，“顾客”有“等待服务”和“接受服务”等状态，“服务员”有“忙”和“闲”等状态。

活动总是与一个或几个实体的状态相对应，状态可作为动态属性进行描述12《系统建模与仿真》2024/7/282024/7/28《系统建模与仿真》133.1.1 离散事件系统要素13《系统建模与仿真》2024/7/282024/7/28《系统建模与仿真》143.1.1 离散事件系统要素7、仿真时钟、仿真时钟 仿真时钟仿真时钟用于表示仿真时间的变化及作为仿真过程的时序控制，它是系统运行时间在仿真过程中的表示•仿真时钟推进的方式：仿真时钟推进的方式：•固定步长时间推进机制•下次事件时间推进机制 仿真时钟推进的时间间隔称为仿真步长，离散事件系统仿真时钟的推进步长是随机的，取决于系统的当前状态和事件发生的条件14《系统建模与仿真》2024/7/282024/7/28《系统建模与仿真》153.1.1 离散事件系统要素8、系统环境、系统环境 系统环境系统环境(System Environment)是系统周围的对象及过程(实体和活动)发生于系统内部的活动称为内生活动，发生于系统环境中并对系统产生影响的活动称为外生活动，将活动划分为内生活动和外生活动就确定了系统的边界。

15《系统建模与仿真》2024/7/283.1.1 离散事件系统要素n确定系统的状态变量系统的状态变量是很重要的n由于进行仿真研究的系统状态变量并不总是固定唯一的，它应当根据系统仿真研究的目的而确定n描述系统状态变化的流程系统状态变化的流程n到达并进入系统中实体的类型和数目n使系统状态发生变化的事件类型n事件发生时间的分布规律等2024/7/28《系统建模与仿真》1616《系统建模与仿真》2024/7/282024/7/28《系统建模与仿真》173.1.1 离散事件系统要素系统系统实体实体属性属性活动活动系统状态系统状态事件事件工业生产机器、零件 生产能力、故障加工要求加工时间、故障时间机器忙、机器闲加工开始、加工结束通信信号、信道 信号长度、传输终端传输信道发送忙、信道发送闲信号开始传输、信号传输结束仓储仓库、物品库房容量进货库存水平、欠付需求需求交通道路、交叉口车辆信号机车道数、车型、车速周期运动时间、信号时间系统总车数、红绿灯车辆到达、绿灯开始离散系统实例离散系统实例17《系统建模与仿真》2024/7/282024/7/28《系统建模与仿真》183.1.2 离散事件系统建模方法n建模是仿真的前提，是计算机仿真的关键技术内容之一；模型不正确，仿真的结果也失去意义n由于随机事件系统的模型很难用常规的微分方程、差分方程来描述；随着系统科学和管理科学的发展机及其在各领域中应用的不断深入，逐步形成了一些与连续系统不同的建模方法n主流方法：主流方法：流图流图和网络图网络图18《系统建模与仿真》2024/7/283.1.2 离散事件系统建模方法n1、实体流图法、实体流图法n与计算机程序流程图类似n可以描述实体产生、流动、消亡及其被永久实体加工、处理的过程和逻辑关系n实体流图模型易于转换为面向事件面向事件的仿真模型2024/7/28《系统建模与仿真》1919《系统建模与仿真》2024/7/283.1.2 离散事件系统建模方法n2、活动周期图法、活动周期图法n针对实体的行为模式进行建模n可以直观地表示出某类实体生命周期中的活动和状况n具有规范化的特点n对不同实体之间协同关系的描述清晰、明确n易于转换为面向活动面向活动的仿真模型2024/7/28《系统建模与仿真》2020《系统建模与仿真》2024/7/283.1.2 离散事件系统建模方法n3、、Petri网法网法n适于建立加工系统等多种离散事件系统的模型n对网系统的特性进行较严密的数学分析n处理并发、冲突、死锁等现象2024/7/28《系统建模与仿真》2121《系统建模与仿真》2024/7/282024/7/28《系统建模与仿真》223.2 实体流图法n系统要对临时实体产生作用，就必须有永久实体的活动，也就是必须有永久实体。

n临时实体和永久实体协同完成了某项活动，永久实体作为活动的资源而被占用n理发店的服务员，交通路口的红绿灯等都是永久实体的例子22《系统建模与仿真》2024/7/283.2.1 实体流图法概述 实体流图法实体流图法(Entity Flow Chart，，EFC)采用与计算机程序流程图相类似的图示符号和原理，建立表示临时实体产生、在系统中流动、接受永久实体“服务”，以及消失等过程的流程图 借助实体流程图，可以表示事件状态变化及实体间相互作用的逻辑关系 在离散事件系统中实体流图法应用比较普遍，原因如下：1）计算机程序框图的思想和方法已广为人们所接受；2）实体流图法简单，且对离散事件系统的描述比较全面23《系统建模与仿真》2024/7/283.2.2 实体流图法的建模思路n对建模者的两点要求：对建模者的两点要求：n1）对实际系统的工作过程有深刻的理解和认识n2）将事件、状态变化、活动和队列等概念贯穿于建模过程中n常用的图示符号：常用的图示符号：n菱形框（判断）；矩形框（事件、状态、活动）；圆角矩形框（开始和结束）；箭头（逻辑关系）24《系统建模与仿真》2024/7/283.2.2 实体流图法的建模思路n建模的一般步骤如下：建模的一般步骤如下：n1）明确组成系统的各个实体及其属性n2）分析各种实体的状态和活动，及其相互间的影响。

n3）考察那些导致活动的开始或结束的事情，或者是可以作为活动开始或结束的标志的事件，以确定引起实体状态变化的事件，并将条件事件合并n4）分析各种事件发生时实体状态是如何变化的n5）在一定的服务流程下，分析与队列实体有关系的特殊操作(如换队等)25《系统建模与仿真》2024/7/283.2.2 实体流图法的建模思路n6）根据以上分析，以临时实体的流动为主线，用约定的图示符号画出被仿真系统的实体流图n7）确定模型参数的取值、参变量的计算方法及属性描述变量的取值方法属性描述变量(例如顾客到达时间、服务时间等)既可以取一组固定值，也可以由某一公式计算得到，还可以是一个随机变量如果属性描述变量是随机变量，就应该给出其分布函数n8）确定队列的排队规则当有多个队列存在时，还应给出其服务规则，例如队列的优先权、换队规则等26《系统建模与仿真》2024/7/283.2.3 实体流图法的实例分析n例例1 ：理发店服务系统：理发店服务系统 ——单服务台、单队列服务系统单服务台、单队列服务系统n有一个小理发店只有一个理发员，顾客来到理发店后，如果有其他顾客正在理发就坐在一旁等候。

理发员按先来先理的原则为每一位顾客服务，而且只要有顾客就不停歇建模目的是在假定顾客到达时间间隔和理发花费的时间服从一定的概率分布时，考察理发员的忙闲情况2024/7/28《系统建模与仿真》2727《系统建模与仿真》2024/7/283.2.3 实体流图法的实例分析n（（1）辨识系统实体）辨识系统实体n三个实体：理发员是永久实体，顾客是临时实体，顾客队列是一类特殊实体n（（2）分析实体的状态和活动类实体的组成）分析实体的状态和活动类实体的组成n理发员的活动有“理发理发”和“休息休息”，对应“忙忙”和“闲闲”两种状态n顾客与理发员协同完成理发活动，有“等待服务等待服务”和“接受服务接受服务”两种状态n顾客队列的状态由队列长度队列长度来标识n三类实体的活动及状态之间存在逻辑上的关系2024/7/28《系统建模与仿真》2828《系统建模与仿真》2024/7/283.2.3 实体流图法的实例分析n（（3）分析实体状态的变化情况）分析实体状态的变化情况n某一顾客到达时，如果理发员处于“忙忙”状态，则该顾客进入“等待服务等待服务”状态；否则进入“接受服务接受服务”状态n理发员完成对某一顾客的服务时，如果队列处于“非零非零”状态，则立即开始服务活动；否则进入“闲闲”状态n处于排队等待中的顾客，如果理发员完成了对前一顾客的服务，则进入“接受服务接受服务”状态；否则保持“等待服等待服务务”状态2024/7/28《系统建模与仿真》2929《系统建模与仿真》2024/7/283.2.3 实体流图法的实例分析n（（4）分析引起状态变化的事件）分析引起状态变化的事件n“顾客到达顾客到达”或“顾客结束排队顾客结束排队”导致“服务服务”活动的开始；而“顾客理完离去顾客理完离去”导致“服务服务”活动的结束；这三个瞬时行为均可以作为事件看待。

n“顾客结束排队顾客结束排队”是以理发员状态是“闲闲”为条件的；而队列状态是“非零非零”时理发员状态为“闲闲”是以事件“顾客理完离去顾客理完离去”为条件的；以上两个条件事件顺序、互为因果n将“顾客结束排队顾客结束排队”事件并入“顾客理完离去顾客理完离去”事件，不予单独考虑，即合并条件事件n“顾客到达顾客到达”将使理发员由“闲闲”变为“忙忙”，或使“队列长度队列长度”增加1n“顾客理完离去顾客理完离去”将使理发员由“忙忙”变为“闲闲”n“顾客结束排队顾客结束排队”将使“队列长度队列长度”减少1，并使理发员由“闲闲”变为“忙忙”2024/7/28《系统建模与仿真》3030《系统建模与仿真》2024/7/283.2.3 实体流图法的实例分析n（（5）分析队列实体的操作）分析队列实体的操作n该问题只有一个队列，而且顾客不会因为排队人数太多而离去，因此队列规则简单，没有换队等特殊的队列操作n（（6）画出系统实体流程图）画出系统实体流程图n基于实体、活动和事件的分析n从实体进入系统开始，按照事件和活动相互交替的原则，按顺序画出实体在系统中的流动过程n对条件事件，可在事件框前加入条件判断2024/7/28《系统建模与仿真》3131《系统建模与仿真》2024/7/283.2.3 实体流图法的实例分析2024/7/28《系统建模与仿真》32单线框：事件单线框：事件双线框：活动双线框：活动理发员为忙、理发员理发员为忙、理发员为闲：为闲：设置系统标志的特殊设置系统标志的特殊操作，可以不画操作，可以不画32《系统建模与仿真》2024/7/283.2.3 实体流图法的实例分析n（（7）确定模型参变量）确定模型参变量n顾客的到达时间（随机变量）n理发员为一个顾客理发所需的服务时间（随机变量）n（（8）给出排队规则）给出排队规则n队列的排队规则是先到先服务（FIFO）n说明：实体流图是为描述实体流动和相互间逻辑关系而绘制的，与计算说明：实体流图是为描述实体流动和相互间逻辑关系而绘制的，与计算机程序框图不同机程序框图不同2024/7/28《系统建模与仿真》3333《系统建模与仿真》2024/7/283.2.3 实体流图法的实例分析n例例2：售票窗口服务系统：售票窗口服务系统 ——两类顾客竞争资源两类顾客竞争资源n电影院雇用一名售票员同时负责电影票的销售和对问询者的咨询服务。

窗口服务比服务优先级高问询者打来的由系统存储后按先来先服务的规则一一予以答复建模的目的是研究售票员的忙闲率2024/7/28《系统建模与仿真》3434《系统建模与仿真》2024/7/283.2.3 实体流图法的实例分析n（（1）辨识系统实体）辨识系统实体n售票员：永久实体；n购票者和问询者：临时实体；n购票队列和问询队列：特殊实体2024/7/28《系统建模与仿真》3535《系统建模与仿真》2024/7/283.2.3 实体流图法的实例分析n（（2）分析实体状态和活动类实体组成）分析实体状态和活动类实体组成n售票员有“空闲空闲”、“售票售票”和“接接”3个活动，对应的是“闲闲”和“忙忙”两种状态n购票者有“排队排队”和“购票购票”2个活动，对应的是“等待等待”和“购票购票”两种状态n问询者有“排队排队”和“问询问询”2个活动，对应的是“等待等待”和“问询问询”两种状态n顾客队列的状态以队列长度队列长度标识n4类实体的活动及状态存在逻辑上的联系36《系统建模与仿真》2024/7/283.2.3 实体流图法的实例分析n（（3）分析实体状态变化的情况）分析实体状态变化的情况n购票者或者问询者到达时，如果售票员处于“忙忙”状态，则该顾客进入“等待等待”状态；否则，进入“购票购票”或“问询问询”状态n处于排队等待中的顾客，如果售票员完成了对前一顾客的服务，则进入“购票购票”或“问询问询”状态；否则，继续保持“等待等待”状态37《系统建模与仿真》2024/7/283.2.3 实体流图法的实例分析n（（4）分析引起状态变化的事件）分析引起状态变化的事件n“购票者到达购票者到达”、“问询者到达问询者到达”、“购票者结购票者结束排队束排队”或者“问询者结束排队问询者结束排队”导致售票员“服务服务”活动的开始n“购票者买票后离去购票者买票后离去”或“问询者咨询后离去问询者咨询后离去”导致售票员“服务服务”活动结束38《系统建模与仿真》2024/7/283.2.3 实体流图法的实例分析n（（5）分析队列实体的操作）分析队列实体的操作n该问题有两个队列，但两个队列中的顾客不会互换队列n（（6）画出系统实体流程图）画出系统实体流程图n以临时实体为主线，画出实体流程39《系统建模与仿真》2024/7/283.2.3 实体流图法的实例分析40《系统建模与仿真》2024/7/283.2.3 实体流图法的实例分析n（（7）确定模型参变量）确定模型参变量n购票者到达时间n问询者到达时间n售票服务时间n服务时间n（（8）给出排队规则）给出排队规则n排队规则：FIFOn服务规则：购票者和问询者分别排队，优先进行购票活动41《系统建模与仿真》2024/7/283.2.3 实体流图法的实例分析n两个与服务规则有关的判断和特殊操作两个与服务规则有关的判断和特殊操作n当“问询者问询者”和“窗口购票者窗口购票者”同时到达，且售票员处于“闲闲”的状态，后者接受服务，前者加入队列n当服务完毕，且购票队列和队列均不为空时，先进行购票服务n由于本例中有两类临时实体同时流动由于本例中有两类临时实体同时流动,因此可能出现资源冲突因此可能出现资源冲突,对此类问对此类问题的描述题的描述,活动周期图有其独到之处活动周期图有其独到之处.42《系统建模与仿真》2024/7/283.2.4 模型的人工运行n建立实体流程图模型后，选取有代表性的例子将流程图全部走一遍，即所谓人工运行。

n人工运行模型要求遍历流程图的各个分支和实体的各种可能状态，在时间逐步变化的动态条件下，分析事件的发生及状态的变化过程，以检查模型的组成和逻辑关系是否正确2024/7/28《系统建模与仿真》433.2.4 模型的人工运行n例例1中，假定：中，假定：n（（1）系统的初始状态）系统的初始状态n包括永久实体“理发员理发员”的状态及特殊实体“队列队列”的状态n初始时刻是仿真开始的时刻，理发员为“闲闲”，队列长度为0n（（2）模型参数及变量的取值）模型参数及变量的取值n第i个顾客与第i-1个顾客到达的时间间隔Ain理发员为第i个顾客的理发时间Sin两个都是随机变量，可根据其分布函数来产生2024/7/2844《系统建模与仿真》3.2.4 模型的人工运行n模型需按照一定的规则运行，本模型的人工模型需按照一定的规则运行，本模型的人工运行规则如下：运行规则如下：n规则规则1——确定当前时间确定当前时间n模型人工运行开始时，取当前时间TIME=t0（初始仿真时刻）n人工运行开始后，当前时间逐步向前推移，且递取下一最早发生事件的发生时刻n如果当前时间有顾客到达事件发生 ，转规则2n若有顾客离去事件发生，则转规则32024/7/2845《系统建模与仿真》3.2.4 模型的人工运行n规则规则2——顾客到达事件处理顾客到达事件处理n假定在时刻TIME有顾客i到达，如果理发员“忙忙”，则入队列等待，队列长度加1n否则，置理发员为“忙忙”状态，顾客开始理发，且在di=TIME+Si时刻理毕离去n规则规则3——顾客离去事件处理顾客离去事件处理n假定在时刻TIME有顾客i离去，如果此时队列长度为0，置理发员为“闲闲”状态n否则，队列中排在队首的一名顾客开始理发，队列长度减1，顾客在di=TIME+Si时刻理毕离去2024/7/2846《系统建模与仿真》3.2.4 模型的人工运行n令A1=15，A2=32，A3=24，A4=40，…n令S1=43，S2=36，S3=34，S4=28，…n（（1）在）在TIME=t0时刻，无任何事件发生时刻，无任何事件发生n下一最早发生的事件为“顾客顾客1到达到达”，发生时刻为a1=TIME+A1=15n（（2）在）在TIME=15时刻，顾客时刻，顾客1到达到达n按规则2，理发员开始为顾客1理发，状态由“闲闲”变“忙忙”n顾客1离去时刻d1=TIME+S1=15+43=58n下一最早发生的事件为“顾客顾客2到达到达”，顾客2到达的时刻为a2=a1+A2=15+32=47<582024/7/2847《系统建模与仿真》3.2.4 模型的人工运行n（（3）在）在TIME=47时刻，顾客时刻，顾客2到达到达n因理发员“忙忙”，顾客2排队等待，队列长度变成1n下一最早发生的事件为“顾客顾客1离去离去”，离去时刻 d1=58

n充分反映各类实体的行为模式，并将系统的状态变化以“个体”状态变化的集合方式表示出来，因此可以更好地表达众多实体的并发活动和实体之间的协同关系n但是，它只描述了系统的稳态，而没有表示系统的瞬态，即活动的开始和结束事件2024/7/2851《系统建模与仿真》 活动周期图建模方法将实活动周期图建模方法将实体的状态分为静寂体的状态分为静寂(Dead)和激和激活活(Active)两种a) 静寂状态 (b) 激活状态 激活状态通常是实体的活动，模型中活动的忙期可激活状态通常是实体的活动，模型中活动的忙期可采用随机采样等方法事先加以确定采用随机采样等方法事先加以确定 静寂状态通常表示无活动发生，是实体等待参加某静寂状态通常表示无活动发生，是实体等待参加某一活动时的状态，其持续时间在模型中无法事先确定，一活动时的状态，其持续时间在模型中无法事先确定，取决于有关活动的发生时刻和忙期取决于有关活动的发生时刻和忙期3.3.2 活动周期图建模2024/7/2852《系统建模与仿真》3.3.2 活动周期图建模n活动周期图法建模过程活动周期图法建模过程n（（1）辨识组成系统的实体及属性）辨识组成系统的实体及属性n辨识永久实体及临时实体，队列不作为实体考虑n（（2）分别画出个实体的活动周期图）分别画出个实体的活动周期图n以实际过程为依据，队列作为排队等待状态来处理n①交替原则：静寂状态和激活状态必须交替出现n②闭合原则：临时实体的ACD表示一个或单位实体从产生到消失的循环过程；永久实体的ACD表示一个或几个实体被占用和释放的循环往复过程2024/7/2853《系统建模与仿真》3.3.2 活动周期图建模加工加工空闲空闲安装安装就绪就绪等待等待D=10D=3机器机器工人工人2024/7/2854《系统建模与仿真》3.3.2 活动周期图建模n（（3）将各实体的）将各实体的ACD连接成系统连接成系统ACDn以各实体之间的协同活动为纽带进行连接n（（4）增添必要的虚拟实体）增添必要的虚拟实体nACD中，当一个活动的所有前置静寂状态均取非零值时，该活动才有可能发生，可以增添某些必要的虚拟实体，并假定它们与另外的实体协同完成某项活动n为实体活动的发生加上某种附加条件，从而实现“隔时隔时发生发生”的建模效果2024/7/2855《系统建模与仿真》3.3.2 活动周期图建模n（（5）标明活动发生的约束条件和占用资源的数量）标明活动发生的约束条件和占用资源的数量n①活动是否可以发生的判断条件n②永久实体在参加一次协同活动时被占用和活动完成时释放的数量n（（6）给出模型参数的取值、参变量的计算方法及）给出模型参数的取值、参变量的计算方法及属性描述变量的取值方法，并给出排队规则和服务属性描述变量的取值方法，并给出排队规则和服务规则规则2024/7/2856《系统建模与仿真》3.3.2 活动周期图法建模举例n例例3：机床加工系统的活动周期图法建模：机床加工系统的活动周期图法建模 ——操作工有休息饮茶的权利操作工有休息饮茶的权利n考虑一个简单的加工车间。

车间内有数台自动机床，由一名工人负责看管n工人的任务是：①如果机床的刀具完好，则为机床安装工件，然后按下运行按钮；②如果机床的刀具损坏，则先要重装刀具，然后执行任务①n只有当机床完成一次自动加工工序，并停止运行后，工人才能执行上述两项任务假定每台机床均可加工各种工件，并且不会发生工件短缺的现象建模的目的是为了研究工人的忙闲率2024/7/2857《系统建模与仿真》3.3.2 活动周期图法建模举例n建模考虑的两类实体：机床、工人机床、工人n（（1）工人）工人n活动：安装工件安装工件(RESET)，安装刀具安装刀具(RETOOL)，其他其他活动活动(AWAY)n三种活动均为激活状态n否则，处于静寂状态“等待等待”，该状态取决于激活状态2024/7/28《系统建模与仿真》583.3.2 活动周期图法建模举例n（（2）机床）机床n三种激活状态：安装刀具安装刀具，安装工件安装工件，加工加工(RUWNING)n引入“预备预备”、“停机停机”两种静寂状态：满足交替原则的要求2024/7/28《系统建模与仿真》593.3.2 活动周期图法建模举例n工人只要不从事“安装刀具安装刀具”和“安装工件安装工件”的工作，就可从事“其他活动其他活动”。

即，“等待等待”是“其其他活动他活动”的唯一前置条件n问题：限定工人每隔问题：限定工人每隔2h才能休息才能休息10min，如何在活，如何在活动周期图中表示？动周期图中表示？n办法：引入虚拟实体办法：引入虚拟实体——工人休息的权力工人休息的权力2024/7/28《系统建模与仿真》603.3.2 活动周期图法建模举例n权力实体协同工人实体完成“饮茶饮茶”活动，其生命周期中要完成“计时计时”（RECORD）这一活动n为了满足交替原则，增添“有权有权”(YES)和“无权无权”(NO)两种状态n权力实体的引入满足了每隔一段时间方可进入某一活动的建模需要2024/7/28《系统建模与仿真》613.3.2 活动周期图法建模举例2024/7/28《系统建模与仿真》623.3.2 活动周期图法建模举例n模型参数模型参数：“机床数量”n模型参变量模型参变量：“累计加工的工件数”n判断当机床处于“停机停机”状态且工人处于“等待等待”状态时，机床是否需要重换刀具，从而决定是进入“安装刀具安装刀具”还是“安装工件安装工件”n属性变量属性变量：“加工时间”、“安装刀具时间”和“安装工件时间”、“饮茶时间”和“轮休时间”2024/7/28《系统建模与仿真》633.3.2 活动周期图法建模举例n服务规则服务规则n当工人处于“等待等待”状态时，是先饮茶休息，还是先工作（假定机床处于“停机停机”状态且权力处于“有权有权”状态），其选择取决于模型参数的值n活动周期图中允许进行分支处理分支处理，这时分支状态需要有一个判断变量，根据判断变量的取值情况，可以确定实体的走向。

2024/7/28《系统建模与仿真》643.3.2 活动周期图法建模举例n例例4：货物运转系统：货物运转系统n大型货车从工厂拉货到转运站，将货卸在固定的仓位运来的货物经分拣后放在另外的专用仓位，由小货车运往客户运转站内有两个卸货仓位，4个装货仓位，每个仓位前均只能停放一辆货车货物由10名工人负责装卸，装卸一车货物需要2名工人n运送货物的大小货车首先从公路上拐进运转站门口的一个停车场，然后经过一条通道驶往各自的仓位为了便于办理手续，通道被分为两半，左边出车，右边进车，而且进出通道只能容两辆小货车同时行进大车的优先级高于小车，出车的优先级高于进车仓位有空闲时才放货车进入通道2024/7/28《系统建模与仿真》65停车停车场场通通道道3.3.2 活动周期图法建模举例n建模目的是研究在一定的货物吞吐量下设几个卸货仓位比较合适不考虑货物数量的影响n实体实体：大货车、小货车、卸货仓位、装货仓位、工人、进站通道和出站通道n7个实体：2个临时实体和5个永久实体2024/7/28《系统建模与仿真》663.3.2 活动周期图法建模举例n（（1）大货车）大货车n由系统“外部外部”逐个“到达到达”，经停车场“排队排队”后，“驶入驶入”卸货仓位“等候等候”工人“卸货卸货”，“卸空卸空”后“驶离驶离”转运站。

n激活状态激活状态：“到达”、“驶入”、“卸货”和“驶离”n协同活动协同活动：“外部”、“等候”、“排队”和“卸空”n“驶入驶入”活动发生的条件之一：至少有一个卸货仓位空闲（空闲卸仓个数UNBAY>0）n（（2）小货车）小货车n与大货车类似2024/7/28《系统建模与仿真》67leaveemptyunloadoutsidewaitarrivequeuemove大货车大货车exitfullloadelsewheredockedcomeparkenter小货车小货车2024/7/2868《系统建模与仿真》2024/7/28《系统建模与仿真》693.3.2 活动周期图法建模举例n（（3）装、卸仓位）装、卸仓位n（（4）装、卸工人）装、卸工人n（（5）进、出通道）进、出通道unloadunbay卸货仓位卸货仓位loadbay装货仓位装货仓位unloadloadlabour装装卸卸工工leaveroadoutmoveexit出口通道leaveroadinmoveenter进口通道2024/7/2870《系统建模与仿真》unloadunbayloadbayunloadloadlabourleaveemptyunloadoutsidewaitarrivequeuemoveleaveroadoutmoveexitexitfullloadelewheredockedcomeparkenterleaveroadinmoveenter2024/7/2871《系统建模与仿真》2024/7/28《系统建模与仿真》723.3.2 活动周期图法建模举例n模型参数模型参数：装卸工人的数量，装卸仓位的数量n参变量：参变量：当前卸货仓位的数量UNBAY，装货仓位的数量BAY，工人的可用数量LABOUR，进、出通道数ROADIN和ROADOUTn属性变量属性变量：各个活动的忙期，随机变量n排队规则排队规则：FIFOn服务规则服务规则：大小货车各排一队，装卸工、进出通道优先为大货车服务，优先安排货车离开货场2024/7/28《系统建模与仿真》733.3.3 模型的人工运行n首先确定系统的初始状态n按下列原则运行模型：n规则规则1——活动的发生与执行活动的发生与执行n（1）活动的所有前置状态中均有实体停留，且各类永久实体的数量超过或等于相应资源占用量；n（2）活动发生的约束条件已经满足。

n依次检查每一活动，以判断此活动是否可以开始，即此活动所要求的足够的实体集合是否已经存在于所有有关的前置队列中如果含有，则将这个实体集合的标志移入此活动的矩形内，且计算出此活动的终止时间，并将此时间写在该活动的矩形内当所有活动都检查完后，转向规则22024/7/28《系统建模与仿真》743.3.3 模型的人工运行n规则规则2——确定当前时间确定当前时间n检查所有活动的终止时间，选其最小值，并设置时钟值为此选择值，然后转向规则3n规则规则3——活动的完成活动的完成n从所有已发生的活动中，检出终止时间等于当前时间的临时实体，删掉为其标注的终止时间；然后将相应临时实体的标记移至其相关的后续状态中n参与活动的各永久实体的资源量相应增加，将参与活动的永久实体的后续状态作标记，转规则12024/7/28《系统建模与仿真》753.4 实体流图和活动周期图的比较n第一：第一：nEFC以临时实体在系统中的流动过程为主线，永久实体浓缩于表示状态和事件的图示符合中，队列作为一种特殊实体nACD基于各类临时和永久实体的行为模式，有独特的图示标识，队列成为实体生命周期的一种状态n第二：第二：nEFC是带有小循环的树形流程图nACD中，各类实体是环形的循环图，整个系统由多个环套在一起2024/7/28《系统建模与仿真》763.4 实体流图和活动周期图的比较n第三：第三：nEFC中，事件有显式的表达nACD中，事件蕴含在活动中，没有显式表达n第四：第四：nEFC中，状态判断框的作用非常重要nACD中，将需作判断的状态用“空闲”、“等待”等静寂状态表示，对实体是否处于该状态的判断也无需标注在图中，而是作为模型运行时的一般规则3.5 Petri网建模方法n改变活动周期图建模方法：改变活动周期图建模方法：1.取消临时实体ACD中的“源”状态，即不再考虑临时实体的生命周期循环2.将活动看作是“开始事件+状态+结束事件”，则，建模元素就变成“事件”和“状态”，后者包括ACD中的激活状态和静寂状态3.不强调实体模型之间的独立性n用集合论的语言描述后，可以建立规范的Petri网方法2024/7/28《系统建模与仿真》773.5.1 Petri网的基本概念n Petri网是由节点节点和有向弧有向弧组成的一种有向图有向图n它有两类节点：n库所库所，即状态元素，它表示一个场所，而且在该场所存放了一定的资源，用 “○”表示；n变迁变迁，它指资源的消耗、使用以及对应状态元素的变化，用 “∣”表示。

另外，资源指的是与系统状态发生变化有关的因素2024/7/28《系统建模与仿真》783.5.1 Petri网的基本概念2024/7/28《系统建模与仿真》79nPetri网定义：网定义：n三元组N=(S,T;F)称为Petri网的充要条件是：3.5.1 Petri网的基本概念nS：库所集；T：变迁集nF：由一个S元素和一个T元素组成的有序偶的集合，称为N的流关系ndom（F）：F所含序偶的第一个元素的集合ncod（F）：第二个元素的集合nN不能有孤立元素，即S,T,F均不能为空集3.5.2 网系统n网是系统静态结构的基本描述网是系统静态结构的基本描述n容量、标识容量、标识和权重权重3.5.2 网系统n例例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 网系统S1S2S3 K=1000K=5 S4S7S5S6K=100K=100t2t13.5.2 网系统n（1）容量K(s)标识库所s中允许存放令牌的最大数量，其值标在表示库所的圆圈旁，不标明时容量为∞n（2）权W(x,y)表示变迁发生时消耗和产出的令牌数量，其值标在弧（x，y）上；不标明时表示权为1n（3）令牌表示原料、部件、产品、人员、工具、设备、数据和信息等组成系统的“资源”，标识M(s)的值用令牌数表示3.5.2 网系统2024/7/28《系统建模与仿真》853.5.3 Petri网的变迁原则n当变迁不断发生时，网系统的状态也不断发生变化，这一过程称网系统的执行2024/7/28《系统建模与仿真》863.5.3 Petri网的变迁原则n1）一个变迁被授权发生，当且仅当该变迁的每一个输入库所中的令牌数大于或等于输入弧的权值，并且该变迁的输出库所中已有的令牌数与输出孤权值之和小于输出库所的容量；简单地说就是“前面够用，后面够放”n2）变迁发生(点火)的充要条件是该变迁是授权的n3）变迁发生时，从该变迁的输入库所中移出与输入弧权值相等的令牌数，输出库所中产生与输出弧权值相等的令牌数。

2024/7/28《系统建模与仿真》87 p1 p2 t1 t2 p4 p5 p3 t3 t4 p6 p7 t6 t5 （（a））初始初始 p2 p1 t1 t2 p4 p5 p3 t3 t4 t5 t6 （（b）引发）引发t1 p6 p7 3.5.3 Petri网的变迁原则 p1 p2 t1 t2 p4 p5 p3 t5 t6 p6 p7 (c) 引发引发t2 t3 t4 p2 p1 t1 t2 p4 p5 p3 t5 t6 p6 p7 （（d ）引发）引发t1和和t2 t3 t4 3.5.3 Petri网的变迁原则3.5.4 Petri网的行为性质•Petri网的模型只给出系统的静态结构及特征， 系统的动态行为是在Petri网的运行过程中体现出来的，主要由它的一些性质来描述•状态标识为一个向量，代表网中相应序号库所中所含令牌的数量，它反映了令牌在网中的分布情况定义定义 (可达性可达性)　　对于对于Petri网网N , 若存在若存在t∈∈T 使得使得M[t>M’，则称，则称M’是从是从M 直接可达的若存在变迁序直接可达的若存在变迁序列列Ρ=t1，，t2，，…，，tk和标识序列和标识序列σ=M1，，M2，，…，，Mk 使使得得M[t1> M1[ t2> M2…Mk- 1[tk>Mk , 则称则称Mk是从是从M 可可达的，记作达的，记作Mo[σ>M 。

所有由所有由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网的行为性质 s3s1s2t3t2t1(1,0,0)(0,0,1)(0,1,1)(1,ω,0)(1, ω ,0)(0, ω ,1)(0, ω ,1)t1t1t2t2t3t33.5.4 Petri网的行为性质定义定义 (有界性有界性)如果对于如果对于s∈∈S 及任意及任意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网的行为性质n定义定义 (死锁死锁)　对给定初始标识即初始令牌分布M0的一个Petri网R(N，M0) ，称其一个变迁节点t为死锁，如果对由初始令牌分布M0可达的任一令牌分布M∈R(N，M0)下，此节点变迁t都是不使能即不具发射权的n在工程系统如柔性生产系统等的设计中，务必要从结构上尽可能避免死锁的存在，以保证系统的信息和物料的运行过程不致瘫痪s4s3s1s2t3t2t1t43.5.4 Petri网的行为性质定义定义(活性活性)　　对对t∈∈T 和和M ∈∈R (N，，M 0)，如果存在，如果存在M’∈∈R (N ,M ) , 使得使得M’[ t> , 则称则称 t 是活的是活的所有的所有的 t∈∈T 都是活的都是活的, 则称则称网网N 是活的是活的 活性保证了系统不会出现死锁, 生产可以正常连续进行 在活性 Petri 网中, 无论怎样选取点火序列, 都保证不会出现死锁。

死锁的判别死锁的判别：：一个一个Petri网网(N，，M0)的一个变迁的一个变迁t是死锁是死锁的，当且仅当此变迁节点的，当且仅当此变迁节点t不出现在不出现在Petri网的可达树的网的可达树的任一分支上任一分支上3.5.4 Petri网的行为性质 s8s9s7s6s5s10s4s3s1s2t8t4t3t7t6t2t1t5M0=(1,1,1,0,0,0,0,0,0,0)t1 、t2 冲突，让t1发生发生 s8s9s7s6s5s10s4s3s1s2t8t4t3t7t6t2t1t5M0=(1,0,0,1,0,0,0,0,0,0)t3发生发生 s8s9s7s6s5s10s4s3s1s2t8t4t3t7t6t2t1t5M0=(1,0,0,0,0,1,0,0,0,1)t6发生发生 s8s9s7s6s5s10s4s3s1s2t8t4t3t7t6t2t1t5M0=(1,1,1,0,0,0,0,0,0,0)t2发生发生 s8s9s7s6s5s10s4s3s1s2t8t4t3t7t6t2t1t5M0=(0,0,0,0,1,1,0,0,0,0)t4发生发生M0=(0,0,0,0,0,1,1,0,0,1)t5 、t6并发并发 s8s9s7s6s5s10s4s3s1s2t8t4t3t7t6t2t1t5M0=(0,1,0,0,0,0,0,1,1,0)t7 、t8并发并发 s8s9s7s6s5s10s4s3s1s2t8t4t3t7t6t2t1t5M0=(1,1,1,0,0,0,0,0,0,0) s8s9s7s6s5s10s4s3s1s2t8t4t3t7t6t2t1t5思考题n加工车间加工车间Petri网系统网系统n某加工车间有3台不同的机器M1,M2和M3，两个操作工F1和F2。

操作工F1可以操作机器M1和M2，操作工F2可以操作机器M1和M3工件分为两个阶段加工，第1阶段必须使用机器M1加工，第2阶段可采用M2或M3加工当M2和M3均处于空闲状态时，工件在M2上加工，否则哪个空闲就在哪个上面加工n建立该加工车间的建立该加工车间的Petri网系统模型网系统模型3.5.5 Petri网的类型n1）基本）基本Petri网网n在最简单的Petri网系统中，规定网中每一个库所的容量为1其库所也可以称为条件，变迁称为事件，所以基本的Petri网又称为条件/事件系统n2）低级）低级Petri网网n如果网中每一个库所的容量和权重为大于或者等于1的任意整数，这样的Petri网称为库所/变迁网2024/7/28《系统建模与仿真》1083.5.4 Petri网的类型n3）定时）定时Petri网网n在这种Petri网络中，将各事件的持续时间标在库所旁边，于是库所中新产生的标记经过一段时间后才加入到Petri网的运行；或者将时间标在变迁上，于是经过授权的变迁延迟一段时间后发生，或者变迁发生后，马上从输入库所中移去相应的标记，但在输出库所中延迟一段时间产生标记n4）高级）高级Petri网网n该网可以简化复杂的网络模型，表达更多的信息。

2024/7/28《系统建模与仿真》1093.5.6 Petri网的特点n1）能够很好地描述和表达离散事件动态系统(DEDS)建模中经常遇到的并行、同步、冲突和因果依赖等关系n2）为形式化分析提供了良好的条件，因为Petri网有良好的数学基础和语义清晰的语法n3）使用图形来描述系统，使系统形象化，易于理解，降低了建模的难度，提高了模型的可读性n4）对于柔性制造系统(FMS)那样的分布式递阶结构，可以分层次建立Petri图n5）与系统结构关系密切，对系统内部的数据流和物流都可以描述，容易在控制模型的基础上直接实现控制系统2024/7/28《系统建模与仿真》110本章总结n在离散事件系统中，实体可以分为两大类：临时实体和永久实体n实体流图法采用与计算机程序流程图相类似的图示符号和原理，建立表示临时实体产生、在系统中流动、接受永久实体“服务”，以及消失等过程的流程图借助实体流程图，可以表示事件状态变化及实体间相互作用的逻辑关系本章总结n活动周期图，描述了实体的状态变化过程和实体间的交互作用关系，反映了各类实体的行为模式，从而可以更好地表达众多实体的并发活动和实体之间的协同关系n活动周期图建模方法将实体的状态分成了静寂和激活两种，分别表示无活动发生和实体的活动，进而将各种实体的活动周期图合并连接成系统活动周期图。

本章总结nPetri网是一种用简单图形表示的组合模型，特别对描述和分析资源并发和冲突系统有独到之处nPetri网是由节点和有向弧组成的一种有向图它有两类节点：一类为库所，即状态元素；另一类为变迁网是系统静态结构的基本描述，要模拟系统的动态特性，需要定义网系统此时，需了解Petri网的变迁原则以及分类和特点。