第5章离散事件系统仿真方法1030.ppt

1、第五章 离散事件系统仿真方法,5.1 制造系统仿真的调度策略,事件、活动、进程是描述离散系统状态变化的基本术语。,事件:,此外，仿真模型中还存在程序事件，即根据需要设定的事件。,事件是引起系统状态转变的行为和起因，是系统状态变化的 驱动力。,例如：仓储系统中物品的入库到达是一个事件，物品的出库离 去是另一个事件。,例如：在仿真过程中为了使仿真结束，专门定义一个事件，使 其终止仿真。,5.1 制造系统仿真的调度策略,例如：仓储“物品到达”是一个事件，该事件的发生可能会使仓 储系统的货位从“空闲”状态变为“非空闲”状态。从“物品到达” 事件直到“物品取出”，物品都处在货位中存储的状态，即处于 “存

2、储”活动中。因此，“存储”活动的开始和结束标志着物品的 到达和离去，标志着货位的空闲与非空闲的转变。,活动:,活动是事件与事件之间的过程，是系统状态转移的标志。,5.1 制造系统仿真的调度策略,进程是有序的事件与活动组成的过程，它描述了其中的事件、 活动的相互逻辑关系和时序关系。,进程：,例如：一种物品进入仓库，经过在货位的存储，直到从仓库中 出库，物品经历了一个进程。,事件、活动与进程之间的关系,5.1 制造系统仿真的调度策略,与事件、活动、进程相对应，离散事件系统的仿真策略可以 分为：事件调度法、活动扫描法、进程交互法等。,仿真时钟是离散系统系统仿真中的重要术语，它决定着仿真 事件的推进机

3、制、仿真精度和仿真效率。,随着面向对象技术的发展，基于消息驱动的仿真策略受到人 们重视。,5.1 制造系统仿真的调度策略, 事件调度法（event scheduling）,事件调度法（event scheduling）以事件为分析系统的基本单位，通过定义事件、事件发生的时间顺序及其系统状态的变化，并以事件来驱动仿真模型的运行。,事件（event）是离散事件系统的基本概念，事件的发生引起 系统状态的改变。,仿真模型中的事件存放于“事件表”中，通过时间控制模块从事 件表中选择最先发生的事件；重置仿真时钟，并调用与该事件 对应的事件处理模块；更新系统状态，决定未来将要发生的事 件；当当前事件结束后，

4、返回时间控制模块；重复事件的选择 与处理，直到仿真结束。,5.1 制造系统仿真的调度策略,事件调度法的仿真过程：,5.1 制造系统仿真的调度策略,总体上，仿真模型可以分为三个层次：仿真总控程序、 模 型单元子程序以及公共子程序。,5.1 制造系统仿真的调度策略,事件调度法仿真模型中总控程序的任务：,（2）事件辨识：辨识将要发生的事件,（3）事件执行：执行当前发生的事件，将已发生的事件从事 件表中移出,5.1 制造系统仿真的调度策略, 活动扫描法（activity scanning）,事件调度法是一种预定事件发生时间的策略，仿真模型中必 须预定系统中最先发生的事件，以便启动仿真进程。,此外，事件

5、处理子程序中除要修改系统状态外，还要预定本类 事件的下一事件将要发生的时间。因此，该方法对活动持续时 间确定的系统较为方便。,当事件的发生不仅与时间有关，并且只有在满足某些条件才发 生的系统而言，由于系统活动的持续时间不确定，无法预定活 动的开始或终止时间，事件调度法就存在不足。,5.1 制造系统仿真的调度策略,活动扫描法（activity scanning）以“活动”作为分析系统的基 本单元，认为仿真系统的运行是由若干活动构成，每一活动 对应一个活动处理模块，处理与活动相关的事件。,一个活动可以由“开始（激发）”和 “结束（终止）”两个事件 表示，每一事件都有相应的活动处理模块。处理中的操作

6、能 否进行取决于时间及系统状态。,一个实体可以有几个活动处理模块。 每一个进入系统的主动 实体都处于某种活动的状态。活动的激发与终止都会形成新 的事件。,5.1 制造系统仿真的调度策略,用各实体时间元的最小值推进仿真时钟； 按优先序执行激活实体的活动处理，使测试通过的事件得以 发生； 改变系统状态，确定相关事件的发生时间。,“活动处理”是活动扫描法的基本处理单元。,活动扫描法的基本思想：,活动扫描法不断扫描系统，检验哪些活动可以激发，哪些活 动继续保持，哪些活动可以终止。,5.1 制造系统仿真的调度策略,活动扫描法仿真的基本过程：,5.1 制造系统仿真的调度策略,5.1 制造系统仿真的调度策略

7、,5.1 制造系统仿真的调度策略,面向活动仿真模型总控程序的算法结构包括： 时间扫描 活动例程扫描,由于事件直接影响系统状态，活动扫描要反复进行，包括确 定事件和条件事件。,5.1 制造系统仿真的调度策略, 进程交互法（Process Interaction）,事件调度法和活动扫描法的基本模型单元分别是事件处理和 活动处理。它们都针对具体事件而建立，各处理相对独立。,进程交互法的基本模型单元是进程。进程针对某类实体的生命 周期而建立，一个进程包含了实体流动中发生的所有事件。,以单服务台排队服务系统为例，顾客生命周期的进程为：,5.1 制造系统仿真的调度策略,5.1 制造系统仿真的调度策略,为每

8、个实体建立一个进程，以反映某个实体从产生开始到 结束为止的全部活动。,进程交互法的特点：,5.1 制造系统仿真的调度策略,顾客排队进程模型,模型说明： 服务员两名， 队列一条 “”表示某顾客产生的时刻，也为相应进程开始的时刻； “”表示某顾客离去的时刻，也为相应进程撤销的时刻； 符号“X”表示排队顾客开始接受服务的时刻； 虚线表示进程的排队时间； 波纹线表示顾客得到服务的时间。,5.1 制造系统仿真的调度策略,进程交互法中实体的进程不断推进，直到某些延迟发生后才暂 停。延迟可以分为：,进程中的复活点表示延迟结束后实体所到达的位置，即进程继 续推进的起点。,条件延迟：延迟期的长短与系统状态有关，

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

10、兼有事件调度法和活动扫描法的特点，但其算法 比两者更为复杂。根据进程交互法建立的仿真模型称为面向 进程的仿真模型。,面向进程仿真模型总控程序设计采用两个事件表： 未来事件表（Future Event List，FEL） 当前事件表（Current Event List，CEL）,面向进程仿真模型总控程序步骤： 未来事件表扫描。从FEL的实体记录中检出复活时间最小的实 体，并将仿真时钟推进到该实体的复活时间； 移动记录。将FEL中当前时间复活的实体记录移至CEL中； 当前事件表扫描。,5.2 仿真时钟推进机制,仿真时间推进机制（time advance mechanism）是指在仿真进 程中将仿

11、真时间从一个时刻推进到另一个时刻的方法，以便 模拟动态系统的运行过程。,仿真时间推进机制的种类、仿真时间单位所代表的实际时间 的长短，直接影响仿真效率和仿真结果的有效性。,离散事件系统仿真的时间推进机制： 固定步长时间推进制（fixed-increment time advance mechanism） 下次事件时间推进机制（next event advance mechanism） 混合时间推进机制（mixed time advance mechanism）,5.2 仿真时钟推进机制,固定步长时间推进机制：在仿真过程中仿真时钟每次递增一 个固定的步长。该步长在仿真开始之前，根据模型特点确定，

12、 在仿真过程中保持不变。,该推进方式要求每次推进都要扫描所有正在执行的活动，以 检查此时间区间内是否有事件发生。,5.2 仿真时钟推进机制,T：仿真时钟 t：步长,固定步长时间推进机制原理框图,5.2 仿真时钟推进机制,5.2 仿真时钟推进机制,固定步长时间推进机制的特点：,每次步长推进，都要进行事件检查，占用计算和判断的时间， 影响仿真效率。步长t越小，问题越严重。,该机制将发生在同一步长内的事件都视为发生在该步长的末 尾，即认为它们是同步的。由此产生误差，影响仿真精度。 步长t越大，误差越严重。,合理确定t，是固定步长时间推进机制中的重要问题。,5.2 仿真时钟推进机制,下次事件时间推进机

13、制：仿真时钟按照下一个事件预计将要发 生的时刻，以不等的时间间隔向前推进。即仿真时钟每次都跳 跃性地推进到下一事件发生的时刻上去。,该推进机制中，仿真时钟的增量不定，取决于被仿真系统。,仿真时，需将事件按发生时间的先后次序排列，仿真时钟时间 则按事件顺序发生的时刻推进。当某一事件发生时，需立即计 算出下一事件发生的时刻，以便推进仿真时钟，直到仿真运行 结束。,5.2 仿真时钟推进机制,下次事件时间推进机制原理框图,5.2 仿真时钟推进机制,下次事件时间推进机制能在事件发生的时刻捕捉到发生的事件， 不会导致虚假的并发事件，精度高。,下次事件时间推进机制取消了不必要的计算和判断，有利于提 高仿真的

14、效率。,采用下次事件时间推进机制时，仿真效率主要取决于要发生的 事件数，即取决于被仿真的系统，用户无法控制调整。事件数 越多，发生得越频繁，仿真效率就越低。,对于仿真时间内事件大量发生的系统，下次事件时间推进机制 的仿真效率有可能比固定步长时间推进机制的仿真效率还低。 对长时间内只发生少量事件的系统仿真，采用下次事件时间推 进机制能获得高效率。,5.2 仿真时钟推进机制,固定步长时间推进机制可以通过调整步长来调整仿真的效率 和精确度，但存在着影响效率的多余计算和仿真精度误差。,结 论：,下次事件时间推进机制不存在多余的计算，具有高的仿真精 度，但没有调整仿真效率和仿真精确度的手段。,固定步长时

15、间推进机制适合于对事件的发生在时间轴上呈均 匀分布的系统的仿真；下次事件时间推进机制适合于事件发 生数小的系统仿真。,5.2 仿真时钟推进机制,混合时间推进机制：固定步长时间推进机制和下次事件时间推 进机制的结合体。仿真时钟每次推进一个固定时间步长的整数 倍(nt，n1)。步长t可以在仿真前确定，并能在仿真过程 中调整以获得必要的仿真精度和仿真效率。,与下次事件时间推进机制相似，混合时间推进机制可以跳过没 有事件发生的时间，避免多余的计算和判断。,n取决于下次事件的发生时间，即取决于仿真系统的状态。,5.2 仿真时钟推进机制,混合时间推进机制的原理：,5.2 仿真时钟推进机制,仿真效率与仿真精

16、度：,仿真精度是指仿真结果与实际系统行为结果的接近程度。仿 真结果与实际结果越接近，仿真精度越高。,仿真效率是指对同一系统在同样一段时间的行为进行一次仿 真时，所耗费计算机机时的多少。费时少则效率高，费时多 则效率低。,对同一系统而言，仿真效率和仿真精度均与仿真模型、仿真 算法及时间推进机制有关。,5.2 仿真时钟推进机制,固定步长时间推进机制的效率完全取决于步长，步长越长则效 率越高，步长越短则效率越低。若要完全消除因步长而造成的 误差则步长需趋于0，仿真时间趋于无穷大。,下次事件时间推进机制的效率完全取决于在仿真时间内发生的 事件数，用户无法改变仿真效率。,混合时间推进机制的效率不仅与步长

17、有关，而且与事件的时间 分布有关。步长越长，事件在时间轴上的分布越不均匀，效率 就越高，反之越低，,5.2 仿真时钟推进机制,在同样的仿真精度下，采用混合时间推进机制的效率不低于采 用固定步长时间推进机制的效率。,对同一实际系统进行仿真时，采用混合时间推进机制的效率不 低于采用下次事件时间推进机制的效率。,5.2 仿真时钟推进机制,（message-driving）的仿真机制是面向对象（object-oriented） 程序设计方法在系统仿真中的应用。,以面向对象的观点，制造系统S是由对象（如加工设备、生 产计划等）以及对象之间的关系组成。,在数学上，系统S可以表示为： S=（O，R） 式中：

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

19、程就是由对象的方法以及对 象之间相互联系的消息组成。,消息驱动的仿真中，实体（entity）有两个形式：活动、等待。 如果实体当前正在执行动作，则是“活动”的；否则，实体状态 为“等待”。只有当一个体接收到一个消息而满足了等待条件或 它的等待时间期满时，它才能由等待状态转为活动状态。,5.2 仿真时钟推进机制,实体（entity） 消息体（message） Create短语：创建新的实体 Free短语：终结实体 Sendmessage短语：实体之间发送消息 Wait短语：用于定义实体等待一段时间或等待接收消息 ,消息驱动的仿真模型的基本要素：,5.3 蒙特卡罗仿真方法,蒙特卡罗（Monte C

20、arlo）法亦称为随机仿真（random simulation）方法、随机抽样（random sampling）技术或统计 试验（statistical testing）方法。,20世纪40年代，Monte Carlo仿真首先应用于核武器研制。 美国 “曼哈顿计划”的主持人之一数学家冯诺依曼首先采用数 学方法直接模拟裂变物质的中子随机扩散，并以位于摩纳哥国 的世界闻名赌城蒙特卡罗作为秘密代号。,用赌城名比喻随机仿真，风趣贴切，该方法很快得到接受。 此后，人们便把这种计算机随机仿真方法称为蒙特卡罗方法,目前，蒙特卡罗方法已经在物理、工程技术、经济、金融、社 会、决策等领域得到广泛应用。,5.3

21、蒙特卡罗仿真方法,蒙特卡罗方法以统计抽样理论为基础，根据实际系统抽象出概率模型或随机过程，产生随机数，并通过对随机变量统计、抽 样实验或随机模拟，以统计特征量作为待解问题的数值解。,蒙特卡罗方法的基本原理：, 根据实际问题建立概率统计模型，所构造模型的主要特征参量 要与实际问题或系统相一致；, 建立随机变量的抽样方法，包括产生伪随机数及各种分布随机 变量抽样序列的方法；, 分析仿真试验结果，给出问题的概率解或解的精度估计。, 按照所建立的模型进行仿真试验、计算，求出问题的随机解。,5.3 蒙特卡罗仿真方法,蒙特卡罗方法的优点：, 收敛速度、计算的复杂性与问题维数无关，计算时间仅与维 数成比例。, 在某些领域（如粒子物理等），该方法具有其他数值计算方 法不能替代的作用。, 受问题条件的限制的影响较小。, 程序结构简单、清晰，便于编制和调试。,5.3 蒙特卡