第三章离散事件系统仿真课件.ppt

1、3.1 3.1 离散事件仿真的基本概念离散事件仿真的基本概念3.1.1.3.1.1.事件事件o事件是描述系统的一个基本要素。事件是指引起系统状态事件是描述系统的一个基本要素。事件是指引起系统状态变化的行为，系统的动态过程是靠事件来驱动的变化的行为，系统的动态过程是靠事件来驱动的。例如，在物流系统中，工件到达可以定义为一类事件。因为工件到达仓库，仓库货位的状态会从空变为满，或者引起原来等待入库的队列长度的变化。o事件一般分为两类：必然事件和条件事件事件一般分为两类：必然事件和条件事件。只与时间有关的事件称为必然事件。如果事件发生不仅与时间因素有关，而且还与其它条件有关，则称为条件事件。系统仿真过

2、程，最主要的工作就是分析这些必然事件和条件事件。3.1.2 成分成分 描述系统的另一基本要素是成分。成分与实体是同描述系统的另一基本要素是成分。成分与实体是同一概念，只是根据习惯，在描述系统时用实体，而一概念，只是根据习惯，在描述系统时用实体，而在模型描述中用成分。成分分为主动成分和被动成在模型描述中用成分。成分分为主动成分和被动成分。分。可以主动产生活动的成分称为主动成分，如物流系统中的工件，它的到达将产生入库活动或排队活动。本身不产生活动， 只在主动成分作用下才产生状态变化的那些成分称为被动成分。3.1.3 进程进程由若干事件与若干活动组成的过程称为进程。由若干事件与若干活动组成的过程称为

3、进程。它描述了各事件活动发生的相互逻辑关系及时序关系。例如，工件由车辆装入进货台；经装卸搬运进入仓库；经保管、加工到配送至客户的过程就是一个进程。事件、活动与进程的关系如图 3-1所示进程3.1.4.3.1.4.仿真时钟仿真时钟o仿真时钟用于表示仿真事件的变化。o由于仿真实质上是对系统状态在一定时间序列的动态描述，因此，仿真时钟一 般是仿真的主要自变量，仿真时钟的推进是系统仿真程序的核心部分。o应当指出，仿真时钟所显示的是仿真系统对应实际系统的运行时间，而不是计算机运行仿 真模型的时间。仿真时间与真实时间将设定成一定比例关系，使得像物流系统这样复杂的系统， 利用计算机仿真只需要几分钟就可以完成

4、，而真实系统的运行则需要若干天，甚至若干月。 3.1.5 随机事件随机事件事件发生的结构可能有多种,称为随机事件.如物流系统中工件的到达、运输车辆的到达和运 输事件等一般都是随机的。3.1.6 随机变量随机变量描述随机事件多种发生的结果的变量,称为随机变量.说明说明:对受随机因素影响的系统进行仿真时，首先要建立随机变量模型，即确定系统的随机变量 ,并确定这些随机变量的分布类型和参数。对于分布类型是已知或者是可以根据经验确定的随机 变量，只要确定它们的参数就可以了。无论是确定随机变量的分布类型还是确定其参数，都要以调研观测的数据为依据。 3.2 3.2 排队系统 3.2.1 排队系统基本概念 许

5、多系统都可以归结为服务系统，服务系统的主要特征是出现排队现象，因此也称为排队系统。 顾客到达时刻不确定，接受服务的时间不确定，导致排队系统在某时刻的状态（例如队列长短）不确定,故又称随机排队系统。3.2.2 随机排队系统的三个组成部分1. 到达模式动态实体产生的规律。2.服务机构: 1）数量 2）速度（一般也是一个随机变量） 3.排队规则：如先进先出，后进先出，优先权，随机服务等。 3.2.3 排队系统的结构1.一线一服务设备（单队列单服务台）2.多线一服务设备3.一线串联服务 4.一线多设备5.多线多设备 3.2.4 3.2.4 到达模式到达模式 常见的到达模式有：1.1.确定型到达模式：确

6、定型到达模式： 顾客到达时间有某种确定规则，最简单的是等距到达如生产线上的零部件按相等时间间隔到达。2.2.泊松到达模式泊松到达模式 在长度为t的区间内到达数（随机变量）为N(t)1)一次出现一个到达 Lim N(t)=0 (当t0时)2)在区间（a, a+t）之间的到达数的分布只与区间长t有关，而与区间起点a无关。3)在不重叠的时间区间内到达数是独立的随机变量，（与以前区间内到达的数量无关）这一性质是在假定顾客总体是无限的情况下才具有。(无后效性)3 3均匀分布的到达模式：均匀分布的到达模式：两次到达时间的间隔在区间0,a之间均匀分布。即大于a的到达时间时间间隔的概率为零，而到达时间间隔在区

7、间0 a取值有相同的概率1/1+a。3.3 手工仿真手工仿真步骤o1、确定仿真的每个输入的特征。o2、构造一个仿真表。2001.9.10例例1 1：排队系统：排队系统p仿真方法仿真方法：手工仿真p仿真初始条件仿真初始条件：系统中没有顾客，即：排队的队列中没有顾客等待，服务台无服务对象。p仿真开始仿真开始：以第一个顾客到达时刻为仿真的起始点。服务台排队队列o排队系统顾客总体顾客总体服务员服务员等待线等待线o模型： 实体：顾客、服务员状态：系统中的顾客数、服务员忙闲事件：到达事件、离开事件（完成服务） 活动：(比如存款、取款)o? 事件何时出现？ 在仿真中，通过随机数随机数来产生！oStep 1:

8、确定输入数据的特征对于单人理发馆系统：上午 8：00 开门，下午 4：00 关门，顾客的到达是随机的，为每个顾客服务的时间长度也是随机的。假若顾客到达时间间隔服从0，7的均匀分布，对每一位顾客的服务时间服从1，4 的均匀分布。我们对到达系统的前 6 个顾客采用仿真的思想进行描述。显然，描述该系统的状态是服务员的状态（忙或闲）、以及顾客排队等待的队长。到达事件到达事件统计特性o假定：假定：到达事件-顾客到达间隔时间为【0，7】小时的均匀分布到达。那么到达时间间隔取值为 0 小时的概率为0.125；到达时间间隔取值为 1 小时钟的概率为 0.125；到达时间间隔取值为 2 小时的概率为0.125，

9、 ，到达时间间隔为7 小时的概率为 0.125。顾客到达的时间间隔发生的概率、累积 概率以及可能的随机数表示如表 3.1 所示。 到达时间间隔概率累积概率随机数表示随机数表示（小数）00.1250.125012400000.12410.1250.2501252490. 1250.24920.1250.3752503740. 2500.37430.1250.5003754990. 3750.49940.1250.6255006240. 5000.62450.1250.7506257490. 6250.74960.1250.8757508740. 7500.87470.1251.000875999

10、0. 8750.999表表 3.1 顾客到达时间间隔的随机数表示顾客到达时间间隔的随机数表示 服务事件服务事件统计特性o服务时间服从服务时间服从1，4的均匀分布，那么服务时间的均匀分布，那么服务时间取值为取值为 1 小时的概率为小时的概率为 0.25；服务时间取值为；服务时间取值为 2 小时的概率为小时的概率为 0.25；服务时间取值为；服务时间取值为 3 小时的概小时的概率为率为 0.25；服务时间取值为；服务时间取值为 4 小时的概率为小时的概率为 0.25。服务时间的发生的概率、累积概率以及可能的随服务时间的发生的概率、累积概率以及可能的随机数表示如表机数表示如表 3.2 所示。所示。

11、服务时间发生概率累积概率随机数表示随机数表示（小数）10.250.250240.000.2420.250.5025490.250.4930.250.7550740.500.7440.251.0075990.750.99表表 3.2 服务时间的随机数表示服务时间的随机数表示 oStep 2: 构造仿真表通过在 0.0000.999 这 1000 个小数中随机抽取，我们得到第 2 个顾客，第 3 个顾客， ,第 6 个顾客到达时间间隔对应的随机数（第 1 个顾客的到达时间为仿真开始时间）如表 3.3 的 第二列所示。根据随机抽取的随机数可确定他们到达的时间间隔如表3.3 的第三列所示。 顾客到达间

12、隔时间的随机数到达间隔时间1-20.260230.550440.128150.270260.8006表表 3.3 顾客到达时间隔的确定顾客到达时间隔的确定 通过在 0.000.99 这 100 个小数中随机抽取，得到理发员为各个顾客服务时间对应的随机数，如表 3.4 的第二列所示。根据随机抽取的随机数可确定各顾客被服务的时间，如表 3.4的第三列所示。顾客服务时间的随机数服务时间10.26220.18130.56340.30250.12160.804表表 3.4 服务员对各顾客服务时间的确定服务员对各顾客服务时间的确定 根据表 3.3 顾客到达时间间隔和表 3.4 顾客被服务的时间，可对到达系

13、统的前 6 个顾客的进行模拟，模拟结果如表 3.5 所示。表 3.5 也称为仿真表。 顾客到达时刻（1）开始服务时刻（2）等待时间（3）=（2）-（1）服务时间（持续） （4）服务完成时刻（5）=（2）+（4）逗留时间（6）=（3）+（4）服务员空闲时间（7）=（2）本-（5）上10002 222022201 131036603 393347922 21140591121 112306151504 41943总和-41313-176表表 3.5 单人服务系统的仿真表单人服务系统的仿真表 顾客到达间隔时间的随机数到达间隔时间1-20.260230.550440.128150.270260.800

14、6顾客服务时间的随机数服务时间10.26220.18130.56340.30250.12160.804o仿真结果计算： 顾客的平均等待时间： 顾客的等待概率 服务员空闲的概率 平均服务时间 由表 1.5 中的数据可计算如下统计指标：（1）平均每位顾客的等待时间：4/6 0.667（分钟）（2）顾客要等待的概率：2 /6 0.333（3）服务员处于“忙”的状态的概率：1 - 6 /19 0.684（4）顾客在系统中的平均逗留时间为：17/6 2.833 （分钟）顾客到达时刻开始服务时刻等待时间服务时间（持续）服务完成时刻逗留时间服务员空闲时间100022202220131036603933479

15、221140591121123061515041943总和-413-176关于到达系统的前 6 位顾客的到达、接受服务及离开系统的描述如图 1.3 所示。12G1G2G3G3G4G4G5 G5G602367911 121519系统中顾客数 仿真时钟 图图 3.1 顾客在系统中的状态图顾客在系统中的状态图对于这样简单的系统我们可以采用手工模拟，并采用模拟表来描述，但实际系统往往比这复杂得多，这就需要更高级的处理技术。顾客到达时刻开始服务时刻等待时间服务时间（持续）服务完成时刻逗留时间服务员空闲时间10002220222013103660393347922114059112112306151504

16、1943总和-413-1763.4 未来事件表3.4.1 基本概念:o随着仿真时 钟的推进，某一随机事件的出现，必将引起新的未来事件，并使系统的状态发生变化，从而使 仿真进程得以持续。o令 TNOW 为仿真时钟的当前值，由事件发生时间大于 TNOW 的事件所构 成的时序列表称为未来事件表 FEL(Future Event List)。o未来事件表既是仿真时钟推进的依据， 同时，也是保证系统中的未来事件严格按时间顺序正确排列的工具。o未来事件表中包含由已发包含由已发 生事件触发的所有未来事件生事件触发的所有未来事件及其发生时刻及其发生时刻，当仿真时钟推进到下一个紧接事件时刻时，该事件 就发生，同

17、时，也表示一项或多项活动的开始。 3.4.2 未来事件表构造o下面以单服务台排队系统的仿真为例，说明如何构造未来事件表。在单服务台排队系统中 仅有两类随机离散事件，即顾客到达事件和服务完毕事件。o构造原则构造原则: : (1) (1)顾客到达时，若服务员空闲，则要 在未来事件表中添加该顾客的离开事件和下一顾客的到达事件；若服务员忙，则只在未来事件 表中添加下一顾客的到达事件即可。 (2)服务完成事件发生时，若队列长度大于零，则只在未来事件表中添加下一个即将被服务顾客的离开事件即可；若队列长度等于零，则不产生任何未来事 件。 (3)TNOW 为仿真时钟的当前值,(Di,ti)表示第i 个人离开的

18、事件；(Aj,tj)表示第j个人到达的事件。下面仍以前面构造模拟表的例子来说明未来事件表的制作。对于单人理发馆系统顾客的到 达间隔时间、理发员对每一顾客的服务时间可通过生成随机数得到，如表 3.6 的第二列、第三列 所示，表中数据可通过随机抽取随机数生成。顾客到达间隔时间服务时间1-2221343412521664表表 3.6 顾客的到达时间间隔和服务时间顾客的到达时间间隔和服务时间 下面我们给出仿真时钟为 7 分钟的未来事件表。 12G1G2G3G3G4G4G5 G5G602367911 121519系统中顾客数 图图 3.2 顾客在系统中的状态图顾客在系统中的状态图1当 TNOW=0 时，

19、顾客到达时，服务员处于空闲 状态，则要在未来事件表中添加该顾客的离开事件和下一顾客的到达事件。此时，第一位顾客 的离开事件记为（D1,2），下一顾客的到达事件记为（A2,2）。由于我们的仿真时间为 7 分钟， 故要添加终止事件（E,7），则添加后的未来事件表如表 3.7 所示。 仿真仿真时钟时钟系统状态系统状态未来事件（未来事件（FELFEL）累计占用累计占用时间时间说明说明队列中顾客队列中顾客数数服务员状服务员状态态0 00 0闲闲（D1,2D1,2）、（）、（A2,2A2,2）、）、（E,7E,7）0 0G1 G1 到到达达表表 3.7 TNOW=0 时的未来事件表时的未来事件表 (1)顾

20、客到达时，若服务员空顾客到达时，若服务员空闲，则要闲，则要 在未来事件表中添在未来事件表中添加该顾客的离开事件和下一加该顾客的离开事件和下一顾客的到达事件；顾客的到达事件；若服务员若服务员忙，则只在未来事件忙，则只在未来事件 表中添表中添加下一顾客的到达事件即可。加下一顾客的到达事件即可。 (2)服务完成事件发生时，服务完成事件发生时，若队列长度大于零，则只在若队列长度大于零，则只在未来事件表中添加下一个即未来事件表中添加下一个即将被服务顾客的离开事件即将被服务顾客的离开事件即可；若队列长度等于零，则可；若队列长度等于零，则不产生任何未来事不产生任何未来事 件。件。2下一事件为第一位顾客离开（

21、同时，第二位顾客到达，这两事件为同时事件），故设TNOW=2 时，由于队列长度等于零，则不产生任何未来事件。则要在未来事件表中删除（D1,2） 即可，系统状态仍为“闲”，累计占用时间为 2，仿真时钟推进到 2，队列中顾客数为， 未来事件表如表 3.8 所示。表表 3.8 TNOW=2 3.8 TNOW=2 时的未来事件表时的未来事件表仿真仿真时钟时钟系统状态系统状态未来事件（未来事件（FELFEL）累计占用累计占用时间时间说明说明队列中顾客队列中顾客数数服务员状态服务员状态0 00 0闲闲（D1,2D1,2）、（）、（A2,2A2,2）、）、（E,7E,7）0 0G1 G1 到到达达2 20

22、0闲闲（A2,2A2,2）、（）、（E,7E,7）2 2G1 G1 离离开开(1)顾客到达时，若服务员空顾客到达时，若服务员空闲，则要闲，则要 在未来事件表中添在未来事件表中添加该顾客的离开事件和下一加该顾客的离开事件和下一顾客的到达事件；若服务员顾客的到达事件；若服务员忙，则只在未来事件忙，则只在未来事件 表中添表中添加下一顾客的到达事件即可。加下一顾客的到达事件即可。 (2)服务完成事件发生时，服务完成事件发生时，若队列长度大于零，则只在若队列长度大于零，则只在未来事件表中添加下一个即未来事件表中添加下一个即将被服务顾客的离开事件即将被服务顾客的离开事件即可；可；若队列长度等于零，则若队列

23、长度等于零，则不产生任何未来事不产生任何未来事 件件。3接下来事件表中还是 TNOW=2 时，为第二位顾客到达，仿真时钟不变，则新的未来事件表如表 3.9 所示。表表3 3.9 TNOW=2 .9 TNOW=2 时的未来事件表时的未来事件表仿真仿真时钟时钟系统状态系统状态未来事件（未来事件（FELFEL）累计占用累计占用时间时间说明说明队列中顾客队列中顾客数数服务员状服务员状态态0 00 0闲闲（D1,2D1,2）、（）、（A2,2A2,2）、）、（E,7E,7）0 0G1 G1 到到达达2 20 0闲闲（A2,2A2,2）、（）、（E,7E,7）2 2G1 G1 离离开开2 20 0闲闲（D

24、2,3D2,3）、（）、（A3,6A3,6）、）、（E,7E,7）2 2G2 G2 到到达达(1)顾客到达时，若服务员空顾客到达时，若服务员空闲，则要闲，则要 在未来事件表中添在未来事件表中添加该顾客的离开事件和下一加该顾客的离开事件和下一顾客的到达事件；顾客的到达事件；若服务员若服务员忙，则只在未来事件忙，则只在未来事件 表中添表中添加下一顾客的到达事件即可。加下一顾客的到达事件即可。 (2)服务完成事件发生时，服务完成事件发生时，若队列长度大于零，则只在若队列长度大于零，则只在未来事件表中添加下一个即未来事件表中添加下一个即将被服务顾客的离开事件即将被服务顾客的离开事件即可；若队列长度等于

25、零，则可；若队列长度等于零，则不产生任何未来事不产生任何未来事 件。件。4.逐渐按仿真时钟向前推进，得到 TNOW=7 时的未来事件表如表 3.10 所示。 表表 3.10 TNOW=7 3.10 TNOW=7 时的未来事件表时的未来事件表仿真仿真时钟时钟系统状态系统状态未来事件（未来事件（FELFEL）累计占用累计占用时间时间说明说明队列中顾客数队列中顾客数服务员状态服务员状态0 00 0闲闲（D1,2D1,2）、）、（A2,2A2,2）、（）、（E,7E,7）0 0G1 G1 到到达达2 20 0闲闲（A2,2A2,2）、（）、（E,7E,7）2 2G1 G1 离离开开2 20 0闲闲（D

26、2,3D2,3）、）、（A3,6A3,6）、（）、（E,7E,7）2 2G2 G2 到到达达3 30 0闲闲（A3,6A3,6） 、（、（E,7E,7）3 3G2 G2 离离开开6 60 0闲闲（D3,9D3,9）、）、（A4,7A4,7）、）、 （E,7E,7）3 3G3 G3 到到达达7 71 1忙忙（A5,9A5,9）、）、 （E,7E,7）4 4G4 G4 到到达达(1)顾客到达时，若服务员空顾客到达时，若服务员空闲，则要闲，则要 在未来事件表中添在未来事件表中添加该顾客的离开事件和下一加该顾客的离开事件和下一顾客的到达事件；若服务员顾客的到达事件；若服务员忙，则只在未来事件忙，则只在

27、未来事件 表中添表中添加下一顾客的到达事件即可。加下一顾客的到达事件即可。 (2)服务完成事件发生时，服务完成事件发生时，若队列长度大于零，则只在若队列长度大于零，则只在未来事件表中添加下一个即未来事件表中添加下一个即将被服务顾客的离开事件即将被服务顾客的离开事件即可；若队列长度等于零，则可；若队列长度等于零，则不产生任何未来事不产生任何未来事 件。件。12G1G2G3G3G4G4G5 G5G602367911 121519系统中顾客数 图图 3.2 顾客在系统中的状态图顾客在系统中的状态图仿真仿真时钟时钟系统状态系统状态未来事件（未来事件（FELFEL）累计占用累计占用时间时间说明说明队列中

28、顾客数队列中顾客数服务员状态服务员状态0 00 0闲闲（D1,2D1,2）、）、（A2,2A2,2）、（）、（E,19E,19）0 0G1 G1 到达到达2 20 0闲闲（A2,2A2,2）、（）、（E,19E,19）2 2G1 G1 离开离开2 20 0闲闲（D2,3D2,3）、）、（A3,6A3,6）、（）、（E,19E,19）2 2G2 G2 到达到达3 30 0闲闲（A3,6A3,6） 、（、（E,19E,19）3 3G2 G2 离开离开6 60 0闲闲（D3,9D3,9）、）、（A4,7A4,7）、）、 （E,19E,19）3 3G3 G3 到达到达7 71 1忙忙（A5,9A5,9

29、）、）、 （E,19E,19）4 4G4 G4 到达到达9 91 1忙忙（D4,11D4,11）、（）、（E,19E,19）6 6G3 G3 离开离开9 91 1忙忙（A6A6，1515）、（）、（E,19E,19）6 6G5 到达到达11111 1忙忙（D5,12D5,12）、（）、（E,19E,19）8 8G4 离开离开12120 0闲闲（E,19E,19）9 9G5 G5 离开离开15150 0闲闲（D6,19D6,19）、）、 （E,19E,19）9 9G6 G6 到达到达19190 0闲闲（E,19E,19）1313G6 离开离开TNOW=19 时的未来事件表时的未来事件表(1)顾客到达时，若服务员空顾客到达时，若服务员空闲，则要闲，则要 在未来事件表中添在未来事件表中添加该顾客的离开事件和下一加该顾客的离开事件和下一顾客的到达事件；若服务员顾客的到达事件；若服务员忙，则只在未来事件忙，则只在未来事件 表中添表中添加下一顾客的到达事件即可。加下一顾客的到达事件即可。 (2)服务完成事件发生时，服务完成事件发生时，若队列长度大于零，则只在若队列长度大于零，则只在未来事件表中添加下一个即未来事件表中添加下一个即将被服务顾客的离开事件即将被服务顾客的离开事件即可；若队列长度等于零，则可；若队列长度等于零，则不产生任何未来事不产生任何未来事 件。件。