离散事件系统仿真方法

1、2022-6-24Su Chun, Southeast University1离散事件系统仿真方法离散事件系统仿真方法 提纲提纲 离散事件系统仿真策略离散事件系统仿真策略 仿真时钟推进机制仿真时钟推进机制 消息驱动的仿真机制消息驱动的仿真机制 混合系统仿真策略混合系统仿真策略 蒙特卡罗仿真方法蒙特卡罗仿真方法2022-6-24Su Chun, Southeast University2离散事件系统仿真策略离散事件系统仿真策略 事件事件、活动活动、进程进程是描述离散系统状态变化的基本术语。 事件事件: 此外，仿真模型中还存在程序事件，即根据需要设定的事件程序事件，即根据需要设定的事件。 事件是引

2、起系统状态转变的行为和起因，是系统状态变化的事件是引起系统状态转变的行为和起因，是系统状态变化的 驱动力驱动力。 例如：仓储系统中物品的入库到达是一个事件，物品的出库离 去是另一个事件。 例如：在仿真过程中为了使仿真结束，专门定义一个事件，使 其终止仿真。2022-6-24Su Chun, Southeast University3离散事件系统仿真策略离散事件系统仿真策略 例如：仓储“物品到达”是一个事件，该事件的发生可能会使仓 储系统的货位从“空闲”状态变为“非空闲”状态。从“物品到达” 事件直到“物品取出”，物品都处在货位中存储的状态，即处于 “存储”活动中。因此，“存储”活动的开始和结束

3、标志着物品的 到达和离去，标志着货位的空闲与非空闲的转变。 活动活动: 活动是事件与事件之间的过程，是系统状态转移的标志活动是事件与事件之间的过程，是系统状态转移的标志。2022-6-24Su Chun, Southeast University4离散事件系统仿真策略离散事件系统仿真策略 进程是有序的事件与活动组成的过程，它描述了其中的事件、进程是有序的事件与活动组成的过程，它描述了其中的事件、 活动的相互逻辑关系和时序关系活动的相互逻辑关系和时序关系。 进程：进程： 例如：一种物品进入仓库，经过在货位的存储，直到从仓库中 出库，物品经历了一个进程。事件、活动与进程之间的关系事件、活动与进程之

4、间的关系2022-6-24Su Chun, Southeast University5离散事件系统仿真策略离散事件系统仿真策略 与事件事件、活动活动、进程进程相对应，离散事件系统的仿真策略可以 分为：事件调度法事件调度法、活动扫描法活动扫描法、进程交互法进程交互法等。 仿真时钟仿真时钟是离散系统系统仿真中的重要术语，它决定着仿真 事件的推进机制、仿真精度和仿真效率。 随着面向对象技术的发展，基于消息驱动消息驱动的仿真策略受到人 们重视。2022-6-24Su Chun, Southeast University6离散事件系统仿真策略离散事件系统仿真策略 从功能上，仿真模型可以分为：总控程序（仿

5、真模型执行机制）总控程序（仿真模型执行机制）模型单元处理程序（系统实体、事件、状态等之间的关系描述）模型单元处理程序（系统实体、事件、状态等之间的关系描述）公共子程序（随机数、仿真结果分析公共子程序（随机数、仿真结果分析）2022-6-24Su Chun, Southeast University7离散事件系统仿真策略离散事件系统仿真策略 事件调度法事件调度法（event schedulingevent scheduling） 事件调度法（事件调度法（event scheduling）以事件为分析系统的基本单位， 通过定义事件、事件发生的时间顺序及其系统状态的变化，并 以事件来驱动仿真模型的运

6、行。 事件（事件（event）是离散事件系统的基本概念，事件的发生引起 系统状态的改变。 仿真模型中的事件存放于“事件表事件表”中，通过时间控制模块从事 件表中选择最先发生的事件；重置仿真时钟仿真时钟，并调用与该事件 对应的事件处理模块；更新系统状态，决定未来将要发生的事 件；当当前事件结束后，返回时间控制模块；重复事件的选择 与处理，直到仿真结束。2022-6-24Su Chun, Southeast University8离散事件系统仿真策略离散事件系统仿真策略 事件调度法的仿真过程事件调度法的仿真过程：2022-6-24Su Chun, Southeast University9离散事件

7、系统仿真策略离散事件系统仿真策略 事件调度法仿真模型中总控程序的任务：（2）事件辨识事件辨识：辨识将要发生的事件（3）事件执行事件执行：执行当前发生的事件，将已发生的事件从事 件表中移出2022-6-24Su Chun, Southeast University10离散事件系统仿真策略离散事件系统仿真策略 活动扫描法活动扫描法（activity scanningactivity scanning） 事件调度法是一种预定事件发生时间预定事件发生时间的策略，仿真模型中必 须预定系统中最先发生的事件，以便启动仿真进程。 此外，事件处理子程序中除要修改系统状态外，还要预定本类 事件的下一事件将要发生的

8、时间。因此，该方法对活动持续时 间确定的系统较为方便。 当事件的发生不仅与时间有关，并且只有在满足某些条件才发 生的系统而言，由于系统活动的持续时间不确定，无法预定活 动的开始或终止时间，事件调度法就存在不足。2022-6-24Su Chun, Southeast University11离散事件系统仿真策略离散事件系统仿真策略 活动扫描法（活动扫描法（activity scanning）以“活动”作为分析系统的基 本单元，认为仿真系统的运行是由若干活动构成，每一活动 对应一个活动处理模块，处理与活动相关的事件。 一个活动可以由“开始（激发）”和 “结束（终止）”两个事件 表示，每一事件都有相

9、应的活动处理模块。处理中的操作能 否进行取决于时间及系统状态时间及系统状态。 一个实体可以有几个活动处理模块。每一个进入系统的主动 实体都处于某种活动的状态。活动的激发与终止都会形成新 的事件。2022-6-24Su Chun, Southeast University12离散事件系统仿真策略离散事件系统仿真策略 用各实体时间元的最小值推进仿真时钟； 按优先序执行激活实体的活动处理，使测试通过的事件得以 发生； 改变系统状态，确定相关事件的发生时间。 “活动处理活动处理”是活动扫描法的基本处理单元。是活动扫描法的基本处理单元。 活动扫描法的基本思想活动扫描法的基本思想： 活动扫描法不断扫描系统

10、，检验哪些活动可以激发，哪些活 动继续保持，哪些活动可以终止。2022-6-24Su Chun, Southeast University13离散事件系统仿真策略离散事件系统仿真策略 活动扫描法仿真的基本过程活动扫描法仿真的基本过程：2022-6-24Su Chun, Southeast University14离散事件系统仿真策略离散事件系统仿真策略2022-6-24Su Chun, Southeast University15离散事件系统仿真策略离散事件系统仿真策略2022-6-24Su Chun, Southeast University16离散事件系统仿真策略离散事件系统仿真策略 面向

11、活动仿真模型总控程序的算法结构包括： 时间扫描时间扫描 活动例程扫描活动例程扫描 由于事件直接影响系统状态，活动扫描要反复进行，包括确 定事件和条件事件。2022-6-24Su Chun, Southeast University17离散事件系统仿真策略离散事件系统仿真策略 进程交互法（进程交互法（Process InteractionProcess Interaction） 事件调度法和活动扫描法的基本模型单元分别是事件处理事件处理和 活动处理活动处理。它们都针对具体事件而建立，各处理相对独立。 进程交互法进程交互法的基本模型单元是进程进程。进程针对某类实体的生命 周期而建立，一个进程包含了

12、实体流动中发生的所有事件。 以单服务台排队服务系统为例，顾客生命周期的进程为：2022-6-24Su Chun, Southeast University18离散事件系统仿真策略离散事件系统仿真策略2022-6-24Su Chun, Southeast University19离散事件系统仿真策略离散事件系统仿真策略 为每个实体建立一个进程，以反映某个实体从产生开始到结束为止的全部活动。 进程交互法的特点进程交互法的特点：2022-6-24Su Chun, Southeast University20离散事件系统仿真策略离散事件系统仿真策略顾客排队进程模型顾客排队进程模型模型说明模型说明： 服

13、务员两名， 队列一条 “”表示某顾客产生的时刻，也为相应进程开始的时刻； “”表示某顾客离去的时刻，也为相应进程撤销的时刻； 符号“X”表示排队顾客开始接受服务的时刻； 虚线表示进程的排队时间； 波纹线表示顾客得到服务的时间。2022-6-24Su Chun, Southeast University21离散事件系统仿真策略离散事件系统仿真策略 进程交互法中实体的进程不断推进，直到某些延迟发生后才暂 停。延迟可以分为： 进程中的复活点进程中的复活点表示延迟结束后实体所到达的位置，即进程继 续推进的起点。 条件延迟：条件延迟：延迟期的长短与系统状态有关，事先无法确定。条 件延迟发生后，实体停留在

14、进程中的某点，直到条件得以满足 后才继续向前移动。例如，队列中的顾客一直在排队，直到服 务台空闲且己处于队首时才能离开队列接受服务。 无条件延迟无条件延迟：实体停留在进程中的某点不再向前移动，直到预 先确定的延迟期满。例如，顾客停留在服务通道中直到服务完 成。2022-6-24Su Chun, Southeast University22离散事件系统仿真策略离散事件系统仿真策略 通过所有进程中时间值最小的无条件延迟复活点来推进仿真 时钟； 当时钟推进到一个新的时刻点后，如果某一实体在进程中解 锁，就将该实体从当前复活点一直推进到下一次延迟发生为 止。 进程交互法的基本思想进程交互法的基本思想：

15、2022-6-24Su Chun, Southeast University23离散事件系统仿真策略离散事件系统仿真策略2022-6-24Su Chun, Southeast University24离散事件系统仿真策略离散事件系统仿真策略 进程交互法兼有事件调度法和活动扫描法的特点，但其算法 比两者更为复杂。根据进程交互法建立的仿真模型称为面向面向 进程的仿真模型进程的仿真模型。 面向进程仿真模型总控程序设计采用两个事件表：面向进程仿真模型总控程序设计采用两个事件表： 未来事件表（未来事件表（Future Event ListFuture Event List，FELFEL） 当前事件表（当

16、前事件表（Current Event ListCurrent Event List，CELCEL） 面向进程仿真模型总控程序步骤：面向进程仿真模型总控程序步骤： 未来事件表扫描。从未来事件表扫描。从FELFEL的实体记录中检出复活时间最小的实的实体记录中检出复活时间最小的实 体，并将仿真时钟推进到该实体的复活时间；体，并将仿真时钟推进到该实体的复活时间； 移动记录。将移动记录。将FELFEL中当前时间复活的实体记录移至中当前时间复活的实体记录移至CELCEL中；中； 当前事件表扫描。当前事件表扫描。2022-6-24Su Chun, Southeast University25仿真时钟推进机制

17、仿真时钟推进机制 仿真时间推进机制（仿真时间推进机制（time advance mechanism）是指在仿真进 程中将仿真时间从一个时刻推进到另一个时刻的方法，以便 模拟动态系统的运行过程。 仿真时间推进机制的种类、仿真时间单位所代表的实际时间 的长短，直接影响仿真效率和仿真结果的有效性。 离散事件系统仿真的时间推进机制： 固定步长时间推进制固定步长时间推进制（fixed-increment time advance mechanism） 下次事件时间推进机制下次事件时间推进机制（next event advance mechanism） 混合时间推进机制混合时间推进机制（mixed tim

18、e advance mechanism）2022-6-24Su Chun, Southeast University26仿真时钟推进机制仿真时钟推进机制 固定步长时间推进机制固定步长时间推进机制：在仿真过程中仿真时钟每次递增一 个固定的步长。该步长在仿真开始之前，根据模型特点确定， 在仿真过程中保持不变。 该推进方式要求每次推进都要扫描所有正在执行的活动，以 检查此时间区间内是否有事件发生。2022-6-24Su Chun, Southeast University27仿真时钟推进机制仿真时钟推进机制T：仿真时钟t：步长固定步长时间推进机制原理框图固定步长时间推进机制原理框图2022-6-24

19、Su Chun, Southeast University28仿真时钟推进机制仿真时钟推进机制2022-6-24Su Chun, Southeast University29仿真时钟推进机制仿真时钟推进机制 固定步长时间推进机制的特点固定步长时间推进机制的特点： 每次步长推进，都要进行事件检查，占用计算和判断的时间， 影响仿真效率。步长步长t越小，问题越严重越小，问题越严重。 该机制将发生在同一步长内的事件都视为发生在该步长的末 尾，即认为它们是同步的。由此产生误差，影响仿真精度。 步长步长t越大，误差越严重越大，误差越严重。合理确定t，是固定步长时间推进机制中的重要问题。2022-6-24S

20、u Chun, Southeast University30仿真时钟推进机制仿真时钟推进机制 下次事件时间推进机制：下次事件时间推进机制：仿真时钟按照下一个事件预计将要发 生的时刻，以不等的时间间隔向前推进以不等的时间间隔向前推进。即仿真时钟每次都跳 跃性地推进到下一事件发生的时刻上去。 该推进机制中，仿真时钟的增量不定，取决于被仿真系统。 仿真时，需将事件按发生时间的先后次序排列，仿真时钟时间 则按事件顺序发生的时刻推进。当某一事件发生时，需立即计 算出下一事件发生的时刻，以便推进仿真时钟，直到仿真运行 结束。2022-6-24Su Chun, Southeast University31仿

21、真时钟推进机制仿真时钟推进机制下次事件时间推进机制原理框图下次事件时间推进机制原理框图2022-6-24Su Chun, Southeast University32仿真时钟推进机制仿真时钟推进机制 下次事件时间推进机制能在事件发生的时刻捕捉到发生的事件，下次事件时间推进机制能在事件发生的时刻捕捉到发生的事件， 不会导致虚假的并发事件，精度高不会导致虚假的并发事件，精度高。 下次事件时间推进机制取消了不必要的计算和判断，有利于提 高仿真的效率。 采用下次事件时间推进机制时，仿真效率主要取决于要发生的采用下次事件时间推进机制时，仿真效率主要取决于要发生的 事件数，即取决于被仿真的系统事件数，即取

22、决于被仿真的系统，用户无法控制调整。事件数 越多，发生得越频繁，仿真效率就越低。 对于仿真时间内事件大量发生的系统，下次事件时间推进机制对于仿真时间内事件大量发生的系统，下次事件时间推进机制 的仿真效率有可能比固定步长时间推进机制的仿真效率还低。的仿真效率有可能比固定步长时间推进机制的仿真效率还低。 对长时间内只发生少量事件的系统仿真，采用下次事件时间推对长时间内只发生少量事件的系统仿真，采用下次事件时间推 进机制能获得高效率。进机制能获得高效率。2022-6-24Su Chun, Southeast University33仿真时钟推进机制仿真时钟推进机制 固定步长时间推进机制固定步长时间推

23、进机制可以通过调整步长来调整仿真的效率 和精确度，但存在着影响效率的多余计算和仿真精度误差。结结 论论： 下次事件时间推进机制下次事件时间推进机制不存在多余的计算，具有高的仿真精 度，但没有调整仿真效率和仿真精确度的手段。 固定步长时间推进机制固定步长时间推进机制适合于对事件的发生在时间轴上呈均 匀分布的系统的仿真；下次事件时间推进机制下次事件时间推进机制适合于事件发 生数小的系统仿真。2022-6-24Su Chun, Southeast University34仿真时钟推进机制仿真时钟推进机制 混合时间推进机制：混合时间推进机制：固定步长时间推进机制和下次事件时间推 进机制的结合体。仿真时

24、钟每次推进一个固定时间步长的整数 倍(nt，n1)。步长t可以在仿真前确定，并能在仿真过程 中调整以获得必要的仿真精度和仿真效率。 与下次事件时间推进机制相似，混合时间推进机制可以跳过没 有事件发生的时间，避免多余的计算和判断。 n n取决于下次事件的发生时间，即取决于仿真系统的状态取决于下次事件的发生时间，即取决于仿真系统的状态。2022-6-24Su Chun, Southeast University35仿真时钟推进机制仿真时钟推进机制 混合时间推进机制的原理：混合时间推进机制的原理：2022-6-24Su Chun, Southeast University36仿真时钟推进机制仿真时钟

25、推进机制 仿真效率与仿真精度：仿真效率与仿真精度： 仿真精度仿真精度是指仿真结果与实际系统行为结果的接近程度。仿 真结果与实际结果越接近，仿真精度越高。 仿真效率仿真效率是指对同一系统在同样一段时间的行为进行一次仿 真时，所耗费计算机机时的多少。费时少则效率高，费时多 则效率低。 对同一系统而言，仿真效率和仿真精度均与仿真模型、仿真 算法及时间推进机制有关。2022-6-24Su Chun, Southeast University37仿真时钟推进机制仿真时钟推进机制 固定步长时间推进机制固定步长时间推进机制的效率完全取决于步长，步长越长则效 率越高，步长越短则效率越低。若要完全消除因步长而造

26、成的 误差则步长需趋于0，仿真时间趋于无穷大。 下次事件时间推进机制下次事件时间推进机制的效率完全取决于在仿真时间内发生的 事件数，用户无法改变仿真效率。 混合时间推进机制混合时间推进机制的效率不仅与步长有关，而且与事件的时间 分布有关。步长越长，事件在时间轴上的分布越不均匀，效率 就越高，反之越低，2022-6-24Su Chun, Southeast University38仿真时钟推进机制仿真时钟推进机制 在同样的仿真精度下，采用混合时间推进机制的效率不低于采在同样的仿真精度下，采用混合时间推进机制的效率不低于采 用固定步长时间推进机制的效率用固定步长时间推进机制的效率。 对同一实际系统

27、进行仿真时，采用混合时间推进机制的效率不对同一实际系统进行仿真时，采用混合时间推进机制的效率不 低于采用下次事件时间推进机制的效率。低于采用下次事件时间推进机制的效率。2022-6-24Su Chun, Southeast University39消息驱动的仿真机制消息驱动的仿真机制（message-driving）的仿真机制是面向对象（面向对象（object-orientedobject-oriented） 程序设计方法在系统仿真中的应用。 以面向对象的观点，制造系统S是由对象（如加工设备、生 产计划等）以及对象之间的关系组成。 在数学上，系统S可以表示为： S=（O，R） 式中：O =Oi

28、 是系统中对象的集合。其中：Oi表示系统中的 对象i，i=1，2，n；n为系统中对象的数目。 R=Rij是系统中对象之间关系的集合。其中：i，j=1， 2，n，且ij；Rij表示对象i与j之间的关系。2022-6-24Su Chun, Southeast University40消息驱动的仿真机制消息驱动的仿真机制 消息驱动的仿真机制提供了自然、 能反映现实世界的开发环 境。它将被仿真的系统视为实体（entity）的集合，实体之间 通过消息（message）进行通信，系统中的事件即是实体之间 消息的传递。 对象（类）具有用属性（attribute）、状态（state）以及方 法（method）

29、表示的自身行为特性。对象之间的联系用消息（ message）来描述。系统的动态过程就是由对象的方法以及对 象之间相互联系的消息组成。 消息驱动的仿真中，实体（entity）有两个形式：活动、等待。 如果实体当前正在执行动作，则是“活动”的；否则，实体状态 为“等待”。只有当一个体接收到一个消息而满足了等待条件或 它的等待时间期满时，它才能由等待状态转为活动状态。2022-6-24Su Chun, Southeast University41消息驱动的仿真机制消息驱动的仿真机制 实体（entity） 消息体（message） Create短语：创建新的实体 Free短语：终结实体 Sendmes

30、sage短语：实体之间发送消息 Wait短语：用于定义实体等待一段时间或等待接收消息 消息驱动的仿真模型的基本要素：2022-6-24Su Chun, Southeast University42混合系统仿真策略混合系统仿真策略2022-6-24Su Chun, Southeast University43蒙特卡罗仿真方法蒙特卡罗仿真方法 蒙特卡罗（Monte Carlo）法亦称为随机仿真（random simulation）方法、随机抽样（random sampling）技术或统计 试验（statistical testing）方法。 20世纪40年代，Monte Carlo仿真首先应用于核

31、武器研制。 美国 “曼哈顿计划”的主持人之一数学家冯诺依曼首先采用数 学方法直接模拟裂变物质的中子随机扩散，并以位于摩纳哥国 的世界闻名赌城蒙特卡罗作为秘密代号。 用赌城名比喻随机仿真，风趣贴切，该方法很快得到接受。 此后，人们便把这种计算机随机仿真方法称为蒙特卡罗方法 目前，蒙特卡罗方法已经在物理、工程技术、经济、金融、社 会、决策等领域得到广泛应用。2022-6-24Su Chun, Southeast University44蒙特卡罗仿真方法蒙特卡罗仿真方法 蒙特卡罗方法以统计抽样理论为基础，根据实际系统抽象出概率模型或随机过程，产生随机数，并通过对随机变量统计、抽样实验或随机模拟，以统

32、计特征量作为待解问题的数值解。 蒙特卡罗方法的基本原理：蒙特卡罗方法的基本原理： 根据实际问题建立概率统计模型，所构造模型的主要特征参量 要与实际问题或系统相一致； 建立随机变量的抽样方法，包括产生伪随机数及各种分布随机 变量抽样序列的方法； 分析仿真试验结果，给出问题的概率解或解的精度估计。 按照所建立的模型进行仿真试验、计算，求出问题的随机解。2022-6-24Su Chun, Southeast University45蒙特卡罗仿真方法蒙特卡罗仿真方法 蒙特卡罗方法的优点：蒙特卡罗方法的优点： 收敛速度、计算的复杂性与问题维数无关，计算时间仅与维 数成比例。 在某些领域（如粒子物理等），该方法具有其他数值计算方 法不能替代