A6离散事件系统仿真基础.ppt

离散事件动态系统仿真基础,离散事件动态系统系统的状态只是在离散时间点上发生变化， 而且这些离散时间点一般是不确定的。 由于离散事件系统固有的随机性，对这类系统的研究往往十分困难。 经典的的概率及数理统计理论和随机过程理论虽然为这类系统提供了 理论基础，并能对一些简单系统提供解析解，但对工程实际中的大量实用系统，惟有依靠计算机仿真技术才能提供较为完整的结果。,队列,服务员,排队系统,离散事件动态系统仿真基础,离散事件动态系统仿真基础,基本概念: (1)实体: 分为临时实体和永久实体. 临时实体-在系统中只存在一段时间的实体 (顾客) 永久实体-永远驻留在系统中的实体 (服务员) (2)事件: 引起系统状态发生变化的行为.(这类系统是由事件来驱动的,为了 实现对系统中的事件进行管理,仿真模型中必须建立事件表） (3)活动: 通常用于表示两个可以区分的事件之间的过程，它标志着系统状 态的转移. ( 例如顾客开始接受服务到服务结束之间可称为活动) (4)进程: 进程由若干个有序事件及若干个有序 活动组成,它描述了所包含的事件及活 动间的相互逻辑关系及时序关系。 (5)仿真钟: 在离散事件系统中仿真钟的推进呈 现跳跃性,推进速度具有随机性. (6)统计计数器: 离散事件系统仿真的结果具有统计性质.,顾客到达事件,服务开始事件,服务结束事件,排队活动,服务活动,进程,离散事件系统仿真基础,仿真钟的推进离散事件系统仿真的基础 离散事件系统仿真的时钟推进方法有两大类： 1）事件调度法时钟是按下一个最早发生事件的发生时刻推进。 举例: 单服务台排队系统 事件表: 2）固定增量法类似于连续系统仿真中的定（等）步长算法。,顾客到达时间间隔 A,服务员空闲?,A 15 32 24 40 22,S 43 36 34 28 ,经过S,开始服务,时间,47,15,0,58,58,71,94,事件,顾客 1到达,顾客 2到达,顾客 1 服务完毕,顾客 2 开始服务,顾客 3 到达,顾客 2 服务完毕,仿真开始,服务员状态,排队长度,0,闲,闲,闲,忙,忙,忙,忙,0,1,1,1,1,0,0,15,47,58,71,94,仿真开始,服务员,队列,顾客,服务完毕,顾客离去,排队等待,离散事件系统仿真基础,单服务台排队系统仿真：1918年，Erlang提出排队系统，并将它用于电话系 统，其实质就是研究服务台与顾客之间的效率问题，希望服务台效率高，而顾客 的等待时间又不太长。 排队论又称随机服务理论。 （1）实体（顾客）到达模式：一般用到达时间间隔描述，可分为确定性到达及 随机性到达。随机性到达采用概率分布来描述，最长采用泊松到达。 泊松到达在 内到达的实体数 的概率为 其中 表示在 区间内到达实体的个数， 为到达概率。 到达时间间隔服从指数分布，其密度函数为 为到达时间间隔。 （2）服务模式：服务台为顾客服务的时间可以是确定性的，也可能是随机的。随机的服务时间也用概率分布来描述。,离散事件系统仿真基础,排队系统的组成: 1) 到达模式 : 指动态实体(顾客)按怎样的规律到达; 2) 服务模式 : 指同一时刻有多少服务设备可以接纳动态实体,它们的服务 需要多少时间; 3) 排队模式: 指对下一个实体服务的选择原则,通常采用: FIFO 先进先出 LIFO 后进先出 SIRO 随机服务,动态实体,排队,服务机构,离散事件系统仿真基础,研究排队系统的目的是为了得到系统的统计性能，比较普遍使用的性能有以下四种： （1）稳态平均延误时间 ：（实体在队列中的平均等待时间） 为第 个实体的延误时间； 是接受服务的实体数。 （2）实体通过系统的稳态平均滞留时间 为第 个实体通过系统时的滞留时间，它等于实体在队列中的等待时间 与 该实体接受服务的时间 之和。 （3）稳态平均队长 为 时刻的队列长度， 为系统运行时间。 （4）系统中稳态平均实体数 为 时刻系统中的实体数，它是在队列中的实体数 与正在接受服务的实体 数 之和。,离散事件系统仿真基础,上述四个性能指标存在的条件是服务台的利用率为： 的定义是： 平均服务时间 平均到达时间间隔 对于 M/M/1 排队系统，上述4项指标可解析计算得到，即,单服务台排队系统仿真举例,系统的有关参数： （1）实体到达模式：到达时间间隔 服从均值为 的指数分布，即 （2）服务模式：服务时间为 ，它也服从均值为 的指数分布，即 （3）服务规则：按 FIFO方式服务。 根据均匀分布的随机数求指数分布的方法（反变换法）： 令 u 是取值为0，1范围内服从均匀分布的随机变量，即 反变换法要求用 u 对 F(A)或 F(S) 进行取样，即令 可得：,离散事件系统仿真举例,事件调度法程序结构： 事件类型表 仿真结果： 理论计算结果： 由 可得 所以,仿真钟初始化，系统状态初始化 事件表初始化，统计计数初始化,主程序,输入仿真控制参数,调用初始化子程序,调用时间控制程序,调用事件 I 子程序,仿真结束否？,调用输出 报告子程序,主程序,操作事件表，确定下一个最早发生的事件（类型 I ）；推进仿真钟,修改系统状态，修改统计计数器 产生将来事件，加到事件表中,根据统计计数器进行统计分析 打印输出报告,初始化子程序,时间控制 子程序,报告产生器,时间类型,服务结束，离开系统,事件描述,属性