第五章
离散事件系统仿真
组员：王茂馨、汤丹、施天娇、 马慧蓉、刘珠珠、刘素瑞、刘 璠、钱漾、蔡跃宇、金臻、景 象
知识点
基本概念
离散事件的基本要素
离散事件系统仿真模型的部件和结构 离散事件系统特点
仿真时钟的推进机制 离散事件系统仿真策略
基本概念
离散事件系统 系统的状态仅在离散的时间点上方式变化的系
下次事件时间推进机制原理图
结论
固定步长时间推进机制可以通过调整步
长来调整仿真的效率 和精确度，但存在 着影响效率的多余计算和仿真精度误差。 下次事件时间推进机制不存在多余的计 算，具有高的仿真精 度，但没有调整仿 真效率和仿真精确度的手段。 固定步长时间推进机制适合于对事件的 发生在时间轴上呈均 匀分布的系统的仿 真；下次事件时间推进机制适合于事件 发生数小的系统仿真。
模型说明： 服务员两名， 队列一条 “∆”表示某顾客产生的时刻，也为相应进程开始的时 刻； “□”表示某顾客离去的时刻，也为相应进程撤销的时 刻； 符号“X”表示排队顾客开始接受服务的时刻； 虚线表示进程的排队时间； 波纹线表示顾客得到服务的时间。
进程交互法中实体的进程不断推进，直到某些延 迟发生后才暂停，延迟可分为： 无条件延迟：实体停留在进程中的某点不再向前 移动，直到预 先确定的延迟期满。例如，顾客停 留在服务通道中直到服务完 成。
统，而且这些离散时间点一般是不确定。 面向事件：反映系统各部分相互作用的一些事 件，模型为反映事件状态的数集，仿真结果是 产生处理这些事件的时间历程 连续系统：时间常为均匀间隔计时；系统动力 学模型由表征系统变量间关系的方程描写，结 果常为变量随时间的变化历程
典型的离散系统
订票系统、库存系统、加工制造系
活动扫描法的基本思想
用各实体时间元的最小值推进仿真时钟； 按优先序执行激活实体的活动处理，使测 试通过的事件得以 发生； 改变系统状态， 确定相关事件的发生时间。
活动扫描法仿真的基本过程
时间元的取值的两种方法
三段扫描法
借鉴事件调度法的某些思想，对活动扫描 法进行改进，提出的三段扫描法。兼有活 动扫描法简单和调度法高效的优点。
一种逻辑结构将这些部件组织起来以便于编码、 调试。
部件
系统状态：它由一组系统状态变量构成，用它来描述系统
在不同时刻的状态。 仿真时钟：用来提供仿真时间的当前时刻的变量，它描述 了系统内部的变化。 时间表：在仿真过程中按时间顺序所发生的事件类型和时 间对应的一张表。 统计计数器：由于控制与储存关于仿真过程中的结果的统 计信息，在计算机仿真中经常设计一些工作单位来进行统 计中的计数用，这些工作单元就叫做统计计数器。
事件、活动和进程三者之间的关系
仿真时钟 离散事件动态系统的状态本来就只在离散时间点上发生变
化，因而不需要进行离散化处理。 离散事件系统一般不以时间推动，但事件间有时序关系， 仿真中仍必须有控制时间的部件 由于引起状态变化的事件发生时间的随机性，仿真钟的推 进步长则完全是随机的 两个相邻发生的事件之间系统状态不会发生任何变化，因 而仿真钟可以跨过这些不活动周期 仿真钟推进呈现跳跃性，推进速度具有随机性
离散系统仿真事例 ——淮安22路公交汽车
始发点：动物园
终点站：枚乘东路
初始事件：从动物园出发 状态：车上乘客数量（随机变量）
活动：两站之间的行驶过程和时间（注意在行
驶过程中状态是不会发生变化的） 事件:到站和离站
离散事件系统仿真的部件 与结构
离散事件仿真模型都有许多通用的部件，并用
条件延迟：延迟期的长短与系统状态有关，事先 无法确定。条件延迟发生后，实体停留在进程中 的某点，直到条件得以满足后才继续向前移动。 例如，队列中的顾客一直在排队，直到服 务台空 闲且己处于队首时才能离开队列接受服务。
进程交互法的基本思想
通过所有进程中时间值最小的无条件延迟复活点 来推进仿真 时钟；
个时刻推进到另一个时刻的方法， 以便 模拟动态系统的运行过程。
离散事件系统仿真的时间推进机制

固定步长时间推进制（fixed-increment time advance mechanism）

下次事件时间推进机制（next event advance mechanism）
混合时间推进机制（mixed time advance mechanism）
下次事件时间推进机制
仿真时钟按照下一个事件预计将要发
生 的时刻，以不等的时间间隔向前推进。 即仿真时钟每次都跳 跃性地推进到下一 事件发生的时刻上去。
被仿真系统。
该推进机制中，仿真时钟的增量不定，取决于
固定步长时间推进机制的特点
每次步长推进，都要进行事件检查，占用计算
和判断的时间，影响仿真效率。步长∆t越小， 问题越严重。 该机制将发生在同一步长内的事件都视为发生 在该步长的末 尾，即认为它们是同步的。由此 产生误差，影响仿真精度。步长∆t越大，误差 越严重。
离散事件系统的特点
模型的多数变量在一定时间内保持常数，且仅
在某些时刻才发生改变，这些变量称之为逐段 常数变量。 模型的一些变量随着仿真时钟的推进，逐步线 性递减直到为零，这些变量叫做递减时标变量。 模型状态发生变化的时刻，也就是某个递减时 标变量值为零的时刻。
仿真时钟的推进机制
是指在仿真进程中将仿真时间从一
形状、颜色、到达时间、加工时间、离开时间就 是属性 状态 在某一确定时刻，系统的状态是系统中所有实体 的属性的集合
离散事件系统的基本要素

实体 永久实体：永久驻留在系统中，是系统处于活动的 必要条件 临时实体：仅在系统中存在一段时间，按一定规律 到达 例：单机器加工系统中，工件是临时实体，机器是 永久实体 两者的关系：临时实体按一定规律出现在仿真系统 中，引起永久实体状态变化，又在永久实体作用下 离开系统，如此整个系统呈现出动态变化的过程
事件调度法
用事件的观点分析真是系统，通过
定义及每个事件引起系统状态的变 化，按时间顺序确定并执行每个事 件发生时有关的逻辑关系
事件调度法的过程
事件调度法仿真模型中总控程序 的任务
活动扫描法
以活动作为分析系统的基本
单元，认为 仿真系统的运行是由若干活动构成，每 一活动对应一个活动处理模块，处理与 活动相关的事件。 一个实体可以有几个活动处理模块。每 一个进入系统的主动实体都处于某种活 动的状态。活动的激发与终止都会形成 新 的事件。
当时钟推进到一个新的时刻点后，如果某一实体 在进程中解 锁，就将该实体从当前复活点一直 推进到下一次延迟发生为止。
进程交互法
进程交互法的基本模型单元是进程。进程针对 某类实体的生命周期而建立，一个进程包含了实 体流动中发生的所有事件。 以单服务台排队服务系统为例，顾客生命周期的 进程为：
进程交互法的特点：
为每个实体建立一个进程，以反映某个实体从
产生开始到结束为止的全部活动。
顾客排队进程模型
• • • • • •
统、交通系统、计算机系统、网络 系统等
单服务台 排队系统
系统工作时间长度固定 顾客到达时间随机
服务员服务时间随机
工作情况，以决定是否增加服
务台要求通过仿真估计系统
属性 属性的集合来描述实体的状态 用来反映实体的某些性质 例：单机器加工过程中，工件是一个实体，材质、
可能由闲变为忙，或是队列状态发生变化。 工件加工完毕离开系统，此事件可能使机 器的状态由忙变闲，同时生产线上现有工 件数减一。
进程 相当于系统的子系统，包含若干个事件及活动间的逻辑关
系和时序关系 例：一个工件到达系统→排队→机器为之加工→加工完毕 后离去的过程，可视为一个进程。 事件、活动和进程三者之间的关系如图

固定步长时间推进机制
在仿真过程中仿真时钟每次递增一个固
定的步长。该步长在仿真开始之前，根 据模型特点确定，在仿真过程中保持不 变。
该推进方式要求每次推进都要扫描所有
正在执行的活动，以 检查此时间区间内 是否有事件发生。
固定步长时间推进机制原理图
T:仿真时钟 ∆t :步长
仿真时钟推进机制
活动 导致系统状态变化的一个过程为活动 活动表示两个可区分事件之间的过程，标志着系
统状态的转移 例：工件开始加工到该工件加工完毕后离开生产 线可视为一个活动，在此过程中机器处于忙状态
事件
引起系统状态发生变化的行为
离散事件系统本质是由事件驱动的 例：工件的到达，系统状态中机器的状态

定时子程序：该程序根据时间表来确定下一事件，并将仿
真时钟推进到下一事件的发生时间。 初始化子程序：在仿真开始时对系统进行初始化工作。 事件子程序：一个事件子程序对应于一种类型的事件，它 在相应的事件发生时，就转入该事件的处理子程序，并更 新系统状态。 仿真报告子程序：在仿真结束后，用来计算和打印仿真结 果。 主程序：调用定时子程序，控制整个系统的仿真过程，并 确定一下事件，产地控制给各事件子程序以更新系统状态。