第2章 离散事件系统仿真

1、生产系统建模与仿真生产系统建模与仿真 Modeling and Simulation of Production System第第2章章 离散事件系统仿真基础离散事件系统仿真基础 第2章 离散事件系统仿真基础 2.1 基本概念 2.2 蒙特卡洛方法 2.3 离散事件系统仿真的基本原理 2.4 离散事件系统仿真的一般步骤 基本要求v了解蒙特卡洛方法的应用v了解离散事件系统仿真的一般步骤v 了解离散事件系统仿真基本原理v 理解离散事件系统仿真的基本要素v 理解蒙特卡洛方法的基本思想离散事件系统离散事件系统v零件并行加工系统离散事件系统v零件简单加工系统离散事件系统v 系统状态是离散变化的，而引发状

2、态变化的事系统状态是离散变化的，而引发状态变化的事件是随机发生的，因此这类系统的模型很难用数件是随机发生的，因此这类系统的模型很难用数学方程来描述。学方程来描述。v由于离散事件系统固有的随机性由于离散事件系统固有的随机性 ,对这类系统的对这类系统的研究往往十分困难。经典的概率及数理统计理论研究往往十分困难。经典的概率及数理统计理论和随机过程理论虽然为之提供了理论基础和随机过程理论虽然为之提供了理论基础,并并 能能对一些简单系统提供解析解对一些简单系统提供解析解,但对于实际工程中的但对于实际工程中的大量系统大量系统 ,唯有依靠计算机仿真技术才能提供较唯有依靠计算机仿真技术才能提供较为完整的结果。

3、为完整的结果。 离散事件系统仿真的基本要素v实体 (Entity) v属性 (Attribute) v状态 (State) v事件(Event) v活动(Activity) v进程(Process) v仿真时钟(Simalation Clock) v统计累加器 (Statistical Accumulator)离散事件系统仿真的基本要素v实体 (Entity) 通常是指需要在模型中明确表示的系统中的任何对象或要素,是描述系统 的三个基本要素 (即实体 、属性、活动)之一。v临时实体 、永久实体 在系统中只存在一段时间的实体,通常被称为临时实体 。到达 通过 离开 永久驻留在系统中的实体。是系统

4、活动的必要条件。 离散事件系统仿真的基本要素v属性 (Attribute) 离散事件系统仿真的基本要素v属性选取原则 :v 便于实体的分类 。v 便于对实体行为的捕述。v 便于排队规则的确定 。离散事件系统仿真的基本要素v状态 (State) 系统中所有实体的属性的集合 ,它包含了描述系统在任何时间所必需的所有信息。例如：进行作业的操作工人数、等待服务队列中的工件数 ,或正在加工处理中的工件数 以及下一个工件到达加工设备的时间等。 离散事件系统仿真的基本要素v事件(Event) 指引起系统状态发生变化的事情。 离散事件系统仿真的基本要素v活动(Activity) 实体在两个事件之间保持某一状态

5、的持续过程称为活动(Activity)。 例如，在上述简单加工系统中，一个零件从“开始加工”到“加工结束”可看做是一个“加工”活动。 离散事件系统仿真的基本要素v进程(Process) 进程(Process)描述了它所包括的事件及活动之间的逻辑关系和时序关系，一个进程由与某类实体相关的若干有序事件及活动组成。 例如：把一个零件到达系统、等待加工(排队)、开始加工、加工结束离开系统的过程看做是一个进程。事件、活动和进程之间的关系 离散事件系统仿真的基本要素v进程(Process) 离散事件系统仿真的基本要素v仿真时钟(Simalation Clock) 用于记录仿真过程中当前时间的一个特殊变量。

6、 离散事件系统仿真的基本要素v统计累加器 (Statistical Accumulator) 统计累加器的构件, 用来跟踪记录各种输出性能指标在仿真进程中的中间结果,通过统计分析，得到更有价值的信息。 例如在上述的简单加工系统中,通常用于观察的性能指标主要有：迄今为止所加工完的零件数量、系统平均队长、零件平均等待时间、最大系统逗留时间以及设备的利用率等。 蒙特卡罗方法 v蒙特卡罗方法又称统计测试法、随机抽样技术，是一种随机模拟方法，以概率和统计理论方法为基础的一种计算方法，是使用随机数（或更常见的伪随机数）来解决很多计算问题的方法,是一种与一般数值计算方法有本质区别的计算方法, 蒙特卡洛方法属

7、于试验数学的一个分支。 蒙特卡罗方法 v基本思想 当实验次数充分多时,某一事件出现的频率近似等于该事件发生的概率。 pnN一种一种“绝处逢生绝处逢生”的方法的方法。蒙特卡罗方法 v例子：计算单位圆形面积 对要计算的圆形构造一个外接正方形。 在该正方形区域中随机采样 Ns个点,则显然有些点落在圆形内,有些点落在了圆形的外面。 圆形面积的计算表达式 。 蒙特卡罗方法 v例子2 假设我们有个y=x2的表达式，如何用MC方法求得函数在0,1区间的定积分呢？ 蒙特卡罗方法 蒙特卡罗方法 v蒙特卡罗方法的应用要点 首先,对问题建立一个简单且便于实现的概率统计模型 ,使要求的解恰好是所建模型的概率分布或数学

8、期望。 其次,根据概率统计模型的特点和实际计算的需要 ,对模型进行改进 ,以便减小仿真结果的方差,降低成本 、提高效率。 再次,建立随机变量的抽样方法 ,其 中包括产生伪随机数及各种分布随机变量抽样序列的方法。 最后,给出问题解的统计估计值及其方差或标准差 。 蒙特卡罗方法 v蒙特卡罗方法的应用或实施过程 ,主要包括如下三个步骤 :(l)构造或描述概率过程 如例 2-2中单位圆形面积的计算,就必须事先构造出一个人为的概率过程 ,使得它的某些参量正好是所求问题的解。(2)以已知概率分布进行抽样(3)建立各种估计量离散事件系统仿真的基本原理 v随机离散事件 随机离散事件主要包括:零件毛坯的到达(E

9、A)、零件在设备I上加工完毕后离开(EW1)和零件在设备上加工完毕后离开（EW2）。 离散事件系统仿真的基本原理 v并行加工中心系统的离散事件和系统状态 可见，随机发生的离散事件是导致系统状态发生变化的原因。离散事件系统就是通过对这些随机离散事件按发生时刻的先后进行排序，并根据不同事件发生时系统状态变化的影响来模拟实际系统运行特性的。随机离散事件是离散事件系统仿真中的要素之一，在离散事件系统仿真中有着特别重要的地位和作用。 离散事件系统仿真的基本原理 v仿真时钟的推进方式 仿真时钟表示了仿真运行的系统时间，是离散事件系统仿真中的基本组成部分之一。 （1）面向事件的仿真时钟推进方式 （2）面向时

10、间间隔的仿真时钟推进方式离散事件系统仿真的基本原理 v（1）面向事件的仿真时钟推进方式 仿真时钟是按照下一个离散事件预计要发生的时刻, 以不同时间间隔向前推进的。其实现，是对各离散事件按发生时间的先后次序进行排列，然后仿真时钟则按照这些事件顺序发生的时刻向前推进。 离散事件系统仿真的基本原理 v（1）面向事件的仿真时钟推进方式v原理 离散事件系统仿真的基本原理v（1）面向事件的仿真时钟推进方式v实例分析离散事件系统仿真的基本原理v（1）面向事件的仿真时钟推进方式v实例分析离散事件系统仿真的基本原理v（1）面向事件的仿真时钟推进方式v实例分析离散事件系统仿真的基本原理v（1）面向事件的仿真时钟推

11、进方式v实例分析离散事件系统仿真的基本原理v（1）面向事件的仿真时钟推进方式v实例分析离散事件系统仿真的基本原理v（1）面向事件的仿真时钟推进方式v实例分析离散事件系统仿真的基本原理v（1）面向事件的仿真时钟推进方式v实例分析离散事件系统仿真的基本原理v（1）面向事件的仿真时钟推进方式v实例分析离散事件系统仿真的基本原理v（1）面向事件的仿真时钟推进方式v实例分析离散事件系统仿真的基本原理v（1）面向事件的仿真时钟推进方式v实例分析离散事件系统仿真的基本原理v（1）面向事件的仿真时钟推进方式v实例分析离散事件系统仿真的基本原理v（1）面向事件的仿真时钟推进方式v实例分析2离散事件系统仿真的基本

12、原理 v（1）面向事件的仿真时钟推进方式v特点 离散事件系统仿真的基本原理 v（2）面向时间间隔的仿真时钟推进方式 在这种时钟推进方式下，仿真时钟按照某一足够小的时间间隔等距地向前推进，使得时间间隔中基本上不会同时出现两个或两个以上的离散事件，每次仿真时钟向前推都需要对所有活动的完成时刻进行扫描。 离散事件系统仿真的基本原理 v（2）面向时间间隔的仿真时钟推进方式v原理离散事件系统仿真的基本原理 v（2）面向时间间隔的仿真时钟推进方式v特点离散事件系统仿真的基本原理 v结论离散事件系统仿真的基本原理 v未来事件表 概念 为了在仿真执行过程中跟踪未来(仿真)时间假定发生的各种事件，常常需要把发生

13、时间大于仿真时钟当前时刻的所有事件放在一个时序列表中。这种由发生时间大于当前时刻的随机离散事件所构成的时序列表，即被称为未来事件表( Future Event Calendar)。 事件按其所发生的时间顺序由先向后排列 离散事件系统仿真的基本原理 v未来事件表离散事件系统仿真的基本原理 v在仿真执行的过程中，当t = TNOW时，系统中应包括以下内容: 被仿真系统在t时所处的状态。 系统在t时正在执行的活动。 由t时刻发生事件所产生的新的未来事件以及由它们构成的未来事件表。系统统计数据的当前值和累计数等。 离散事件系统仿真的基本原理 v未来事件产生的逻辑关系 离散事件系统仿真的基本原理 v 未

14、来事件时刻表生成未来事件表的长度和内容都是随着仿真过程的推进而不断变化的未来事件表的长度和内容都是随着仿真过程的推进而不断变化的它不仅是仿真时钟向前推进的依据，同时也是控制仿真运行的依据。它不仅是仿真时钟向前推进的依据，同时也是控制仿真运行的依据。离散事件系统仿真的基本原理 离散事件系统仿真的基本原理 v例子简单加工系统仿真运行（零件的到达、零件加工完后离开和仿真的结束，各事件处理的内容 ） 离散事件系统仿真的基本原理 离散事件系统仿真的基本原理 离散事件系统仿真的基本原理 离散事件系统仿真的基本原理 v仿真运行的终止 1.规定仿真运行时间长度TE 当仿真时钟推进到时刻TE (即TNOWTE)时，则仿真运行终止。2.规定某个未来事件E 在仿真运行中，如果系统发现规定的某个未来事件E已经发生，则立即终