[军事/政治]第六章 离散事件系统仿真

[军事/政治]第六章 离散事件系统仿真 第六章 离散事件系统仿真 离散事件系统是指受事件驱动、系统状态跳跃式变化的动态系统(系统的迁移发生在一串离散事件点上。这种系统往往是随机的(具有复杂的变化关系(难于用常规的微分方程、差分方程等方程模型来描述(一般只能用流图或网络图描述(如果应用理论分析方法难于得到解析解，甚至无法解决(无疑仿真技术为解决这类问题提供了有效的手段。 离散事件系统大量地存在于我们的周围(超级市场管理系统、银行服务系统、公交管理系统、车间加工调度系统等(其中到达市场和银行的顾客、上车和下车的旅客、等待加工的工件，都是影响系统变化的“事件”(是在离散时刻随机产生的。利用仿真技术对这些系统进行研究分析(可以了解它们的动态运行规律(从而帮助人们做出是否需要增加新的市场和银行的决定，可以协助人们合理地调度车辆和安排工序( 本章首先介绍离散事件系统仿真的基本概念，并对几种典型随机分布，变量的数字仿真问题作了说明(然后介绍主要的仿真方法。着重结合实际例子介绍排队网络、随机库存系统、等儿类离散事件系统的仿真方法。最后介绍Petri网和形式化描述的建模方 1 法。 6(1离散事件系统与模型 对离散事件系统的研究(最早可追溯到对排队现象和排队网络的分析，排队论最早由A(K(Erlang于1918年提出，在管理通信和各类服务系统中有着广泛的应用。离散事件系统大量地存在于客观现实之中，如交通管理系统、库存管理系统、加工系统、能源规划、电话通信系统、人口管理等，排队论、网络分析、数学规划和调度排序等方法是解决这类问题的主要数学方法。但是，利用仿真技术对离敞事件系统进行研究，在国内还是最近20年的事。随着计算机技术、信息处理技术、控制技术、人工智能技术等新技术在军事指挥，军事训练、现代通信、制造等领域的发展和应用，出现了一大批存在着离散事件过程的人造系统(例如(武器群指挥衽制决策系统(其中影响其决策的因素很多(如攻防双方兵力损毁的概率事件等)、计算机生成兵力、记算机,通信网络系统、柔性制造系统等。 从这些由错综复杂且丰}{互作用的离敞事件构成的离散事件系统或连续,离澈混合系统的研究，逐渐成为仿真技术应用的重要领域，不难看到，离做事 2 件系统仿真发展中的一个显著的特点是，更加依附于实际背景和贴近于实际应用。IE因为发展比较晚，所以还是一个十分不成熟的技术分支，目前尚缺乏能为大家公认的、通用的数学模型，这些问题的求解又难于利用解析的方法，而且所需要的真实系统的数据源受到限制致使其模型验证也存在一定难度。总之，该领域所要探讨的问题还很多，其技术正在进一步得到发展。 6(1(1描述离散事件系统的基本要素 为了正确地对系统建模，有必要弄清离散事件系统的一些基本要素:实体、活动、事件等。 1(实体(Entity) 与连续系统一样，离散事件系统也是由实体组成的。实体可分为临时实体和永久实体两大类。在系统只存在一段时间的实体叫临时实体，例如计算机系统中的待处理信息、电活交换系统中的电话呼叫、加工系统中等待加工的工件以及在商店排队等待的顾客等，系统的工作过程实质上就是这类实体流动和接受加工、处理的过程。永远存在于系统内的实体叫永久实体。例如上述系统中的计算机设备、电话交换系统，加工没备以及商店中的营业员等。临时实体按一定规 3 律不断地到达，在永久实体作用下通过系统，最后离开系统。系统状态的变化主要也就是由实体的状态变化而产生。 引起系统状态变化的行为称为事件。它是在某一时间点的瞬间行为(例如被处理信息、电话呼叫、顾客等的“到达”或“离开”。事件不仅用来协调两个实体之间的同步活动，还用于各实体之间传递信息。 3(活动(Activity) 把实体所作的或对实体施加的事件称之为活动(它是实体在两个事件之间保持某,状态的持续过程，例如信息处理过程、通话过程和顾客接受服务的过程. 4(进程(Process) 是由与某类实体相关的事件和若干活动组成的，它描述了这些事件和活动之间的相互逻辑关系和时序关系。例如，顾客到达系统---排队----开始接受服务----服务---服务完毕的过程就够成一个进程。 这里举一个排队系统例子来说明建模内容和方法。例如一个在有较大水位落差的河段上船闸运行系统，从上游新来的船只只到达船闸或当原有船只完成过闸过程时，系统状态就发生了变化(我们把从船只到达、过闸完毕这一类引起系统状态变化的行动称为 4 事件(当船只尚在船闸内(忙态)而又有新的船只到达时(则新到的船只就进入等候的队列(排队的队长加1)，把排队过程、船只过闸的过程称之为活动，可以把船只从船到达一进入排队的队列一开闸门一过闸服务一出闸门这三个事件和两项活动称之为过闸进程。图6(1描述了船只从到达到离开所发生的事件、活动和进程之间的关系。 图6.1 事件、活动与进程的关系 6(1(2离散事件系统模型 1(系统模型概述 离散事件系统研究和仿真中最基本的问题是系统的建模。那么，应采用什么方式来概括和抽象化分忻处理这些离散事件系统呢?自20世纪80年代初，美国哈佛大学著名学者Y(C.HO教授倡导对离敞事件动态系统DEDS(Distributedn’ent I=)ynamic Syslem)理论进行研究以来(这个问题受到了足够的重视，许多学者围绕这个问题从不同层次或用不同数学工具进行 5 了描述，形成了多种方法体系，并出观了多种形式的DEDS模型设计方法。例如，根据事件发生时间对所考察对象演变过程的分析而言是否有必要纳入研究范围，可划分为: (1)不带时标的DEDs模型:有限状态自动机模型、Petri网络模型、过程代数模型、时序逻辑模型等: (2)带时标的DEDS模型;赋时Petri网络模型、TIM,RTlL模型、双子代数模型、排队网络模型、Markov链与GSMP模型等。 或根据系统输入信息及状态演变的确定,不确定性，分成确定性DEPS模型和随机性DEDS模型;也可根据状态变化的量化特征，分成逻辑(定性)模型与数量(定量)模型等。 从现已见诸于文献的各类DEDS系统描述形式来看，DEDS建模与模型分析研究尚处千发展阶段。模型种类较多，但不同模型之间缺少必要的转换关系，且每一种模型描述形式往往只适用于一类或几类问题。也就是说，目前尚没有通 用的适合于各类研究对象的模型表示方式。从现有模型的形成过程看(DEDS建模的常用方法主要有排队论方法、网络图或事件图法、形式语言与自动机方 6 法、随机过程(例如，Markov过程和GSMP过程)描述法和抽象代数(例如，双子代数、极小代数、极大代数)方法等。 2(建模步骤 离散事件系统的建模，大致按下列步骤进行。 1)明确仿真目的 建模前，仿真工作者必须根据仿真目的，确定所需获取的某一事件或系统的哪一部分信息、模型的类型和所需资料及数据。目的不同，所建的模型也不同，衡量仿真结果逼真性的准则也就不同，甚至对某一仿真目的，模型是有效的，而对另一仿真目的，模型可能是无效的。在船闸运行系统中，如果仿真目的主要是要了解船闸服务时间的长短对船闸的利用率的影响，这种情况就属于离散事件系统的排队论模型。如果还要分析闸门启,闭的控制和动力学过程特性及注,放水过程特性，则系统应视为连续,离散混合型。 2)正确描述系统 (1)组成成分。组成成分是指对描述系统仿真目的有意义的实体，这些实体的行为往往是随机分布的。比如，船只、船闸是组成系统的实体。 (2)描述变舒和参数。描述变量和参数是指系统各实体的属性。描述变量包括内部变量和外部变量，除了输 7 人,输出变量外，其余均为状态变量参数可以在仿真前由用户设置或在仿真过程中根据用户的命令加以改变。比如。上例中的描述变量有:船只到达间隔时问、船闸服务过程时问、队列长度。 (3)相互关系。相互关系规定了系统中不同变量的相应关联(是指影响系统变化的各实体、变量和参数之问的连接关系_和作用关系、、相互关系映在各成分的活动之中，而活动又由事件所引发，所以弄清事件、活动的关系反系统描述中极为重要的。比如，船闸运行系统中的事件有:船只到划达。船闸开始服务、船闸结束服务、船只离开;活动有:排队服务、过闸服务等。按仿真目的表示出这些事件发生的顺序、活动持续过程(使描述出系统间的相互关系。由此可进一步画出系统的流图和网络图。图4(2为描述系统的流程图。 3)仿真模型的建立 流程图仅能表明整个过程中发生的“事件”表，要仿真这样一系列“事件”，必须知道确切的时间表，这就是仿真系统建模。假设船只到达的时问问隔是平均值为70min、变化范围为?14min的均匀分布随机数;船闸的服务时间是平均值为60min、变化范围为?7min的均匀分布随机数。则可得到系统的含有随机概率模 8 型的仿真系统模型(如图4(3所示)。 4)输出函数的确定 在建立了系统模型的基础上，还需要确定输出函数(根据仿真目的统计计箅出反映系统性能的数据，这些数据就是系统模型的输出。比如，求出船只的平均等待时问、最大队列长度和船闸利用率。 9 图6.2船闸服务系统流程图 图6(3船闸服务系统仿真模型图 6(2随机数和随机变量的产生 为了在数字机上进行随机系统的仿真研究，就要在数字机上产生所需要的随机噪声。这里研究的随机噪声是一种各态历经的平稳随机过程(因此它的统计特性完全可以用随机过程{x(t)}的一个样本函数x(t)的时间平均特性来加以描述。一般可以用x(t)的概率分布F(t)来描述它在幅度上的统汁特性，而用x(t) R(),S(,)的自相关函数或功率潜密度来描述它在时域xx 或在频域上的统计特性。 F(y),S(,)从理论上讲(任意一个随机噪声[ ]都可y由均匀分布白噪声x(t)通过一定的计算获得，其中 因此，在本节中首先要讲一下如何用计算机来产生均匀分布的白噪声。 6(2(1随机数的产生 利用数字机本身的数字计算功能来产生伪随机数。由于这种方法既不需要占用很多内存(又能重复 10 产生，因此是目前使用得较为广泛的方法。下面简单介绍乘同余法，它的递推公式为 6.1 即 其中[?]表示取整。 对于二进制机器，可按以下规则选择a,和m i (1)m=2,j是某个整数，一般m选择在机器所能表示数的范围内，同时，还要考虑公式计算得到的伪随机数序列的周期为m,4，它应大于试验的持续期; p/2(2)a一般取与a=2最接近而又满足a=8k?3的那个数，其中k为任意整数，P为机器字长。 比如，希望产生一个8000个数的序列(最小单位为1)，那么根据上述第fI)条，m应选择接近32000， 15现取m=2=32768，则机器的字K至少应为15位:根 7.5锯上述第(2)条a=2=18l，而与此数最接近的8k?3的数是179，I故a取179(k=22)。于是 设x=11(小于m的奇数)，按上述计算可得以下随机0 数列 11 x的范围是在0—32767之间。因为如果[(]正好是整i 数(则x=0:如果[(]=[178(99999]=178，则x=36767。 ii 用公式(6(1)的递推公式计算随机数，速度是相当快的。这样计算出来的伪随机数基本上符合均匀分市的统计特性。 6(2(2连续随机变量的产生 一般可以采用变换抽样法和舍选法产生连续随机变量。 1(变换抽样法 这种方法主要是应用人所共知的概率积分变换运算法(常称为反变换法)。 概率积分变换定理可以叙述如下:如果u(i= i 1区间内均匀分布的独立随机1(2(„)是一个在0, 变量(而另一给定分布函数F(x)的随机变量为x。则i -1这一随机变量x可以由其反分布函数F (u)求得其ii -1抽样值，即x= F (u). 图6.6可以用来说明这一定ii 理。 因为概率分布函数的变化区区间为[0，1]，所以F(x)的取值范围为[0，1]。现若以一在[0，1]上均匀 12 分布的随机数作为F(x)的取值规律，则落在区间Ax内的样本数的概率就是?F，因此随机变量x在区间?x内出现的概率密度函数的平均值为?F,?x，当?x趋于零时，其概率密度函数就等于dF,dx，即符合原来给定的密度分布函数。由以上的简单说明可知，可以用(0，1)均匀分布的随机数来实现某一随机变量概率分布函数的抽样，而每一概率抽样对应的随机变量值即为所要求的符合这种概率分布的随机变量的抽样值，或用下式表示: 其中，u为均匀分布随机变量抽样值。应用这一反变i 换定理可得到各种连续分布的随机变量。 图4(6概率分布函数曲线 1)均匀分布随机变量 若已知一随机变量概率密度为 13 xdux,a由f(x)求得 ，则x=a+(b-a)u F(x),,,u,bb,ab,a 2)指数分布随机变量 若已知一随机变量概率密度函数为 x1,,u,,x同样，由f(x)求得，。 F(x),,edu,1,e,ux,,ln(1,u),0,3)三角分布的随机变量 已知 则 应用反变换公式得 4.2 4)正态分布的随机变量 14 已知 对于这种非的正态分布，可以通过标准正态分布 ,,,x，u的随机变量求得，其关系为:。其中，x是N(0,1) 2,、u的随机变量，即标准正态分布的随机变量。分别 ,是所求的非标准的正态分布随机变量和方差和均值。 正态分布随机变量也常用近似抽样方法得到。根 ,,据中心极限定理:随机变量具有数学期望E()=a和 2,,,有限的方差D()=，在N次独立试验中得到的N个 ,,,观测值，，_，„，孙，当N充分大时，其统计1N2 量 以N(0,1)为极限分布。 现若取随机变量为(0，1)均匀分布随机数u，其均值 2,E(u)=l,2，方差=D(u)=1/12，所以可得统计量 N1 x,12N(ui,1/2) ,N,1i 渐进服从N(0,1) 正态分布。实际应用中常数取N=6或N=12: 3 当N=6 x,2(u,u),ii,221i,1 6 当N=12 x,(u,u),ii,221i,1 15 6.2.3离散随机变量的产生 随机变量如果只在离散时刻产生，就称为离散随机变量，其概率分布函数当然也是离散的。例如，库存系统中的需要就属于这种离散型随机变量，它的概率分布有:几何分布、泊松分布以及负二次项分布等，另外均匀分布也是较常用的一种模式。 离散随饥变量的产生也常采用反变换方法，但它的概率分布函数不是连续函数而是离散函数，所以不能直接利用反函数来求得随机变量抽样值(而是需要一个(0 1)均匀分带随机数作为分布函数抽样值来进行随机变量的抽样。 例:设有一随机变量x(其慨率分布和累积概率分布如表6(1所示 表6(1 概率分布和累积概率分布 若取(0，1)均匀分布随机数的一个值u=0.5l，i 16 以此模仿累积概率分布函数F(x)的取值(见图6(8)。 图6.8 离散随机变量概率分布曲线 0.01,u,0.61因为，所以随机变量x的对应抽样值为a=2 2i 以上的抽样过程可用以下算法表示: (1)产生(0，1)均匀分布随机数u。 I (2)读入随机变量累积概率分布函数F(I)(I=0,1,2,„,N)。 (3)将u与F(I)由小到大顺次比较，当F(I-1)I ?u?F(I)，则X=I。 I (4)重复步骤(1),(3)，不断产生随机变量x的抽样值。 6(3离散事件系统的仿真模型和仿真策略 图4(9说明了离散事件系统仿真的一般步骤，同时也表明了系统建模与仿真建模的关系。 17 图6。9 离散事件系统的一般步骤 6(3(1离散事件系统仿真模型 离散事件系统仿真建模的目的，是要建立与系统模型有同构或同态关系的、能在数字机上试验的模型(模型中有关对随机变量概率分布函数的仿真已经在6。2节中进行了讨沦。连续系统仿真建模需要通过各种算法将系统模型进行离散化(与连续系统不同(从描述形式来看，离散事件系统模型为直接用于仿真创造了条件。不过，为了正确地进行离散事件系统仿真建模，还须弄清离散事件系统仿真程序的主要成分组成、流程管理及相关的概念。 1(仿真程序的主要成分 采用事件步长法仿真程序的组成(主要有以下部分: (1)仿真时钟提供仿真时间的当前值。 18 (2)事件表由策划和事件调度生成的事件名称、时间的二维表，即有关未来事件的表。 (3)系统状态变量描述系统状态的变量。 (4)初始化子程序用于模型初始化。 (5)事件子程序每一类事件的服务子程序。 (6)调度子程序将未来事件插入事件表中的子程序。 (7)时钟推进子程序根据事件表决定下次(最早发生的)事件，然后将仿真时钟推进到该事件发生的时刻。 (8)随机数产生子程序产生给定分布的随机数的子程序。 (9)输出函数子程序用于系统性能分析的子程序。 (10)统计计数器用来存放与系统性能分析有关的统计数据的各个变量值。 (11)主程序调用上述各种子程序并完成仿真任务全过程。 2(仿真程序的流程管理 仿真流程管理(即仿真调度)是仿真建模的核心，在此主要讨论时间进程管理同时事件管理等。这个过程主要用到了仿真时钟和事件表两个概念。 1)仿真时钟 19 研究系统一般是为了认识其状态随时间变化的规律，所以需要一个仿真时间变量=离散事件系统仿真中时间的变化是用一个逻辑时钟时间的数来表示的:除了实时仿真以外，仿真时间意味着仿真时钟时间而不是仿真所用的机时，二者之间并没有直接的联系。它与所有实体的活动及所有事件的调度有关系，仿真时间与真实时间之间可以通过选定的时间比例尺相关联。每一事件通过被调度事件时间与仿真时钟相关联，当对应的物理事件发生时，事件时间就对应于实际系统的真实时问 下断介绍仿真时钟的两种推进方式: (1)时间步长法。在进行系统仿真的同时，可以把整个仿真过程分勾许多相等的时间问隔(时间步长的长度可根据实际问题分别取作秒、分、小时等、程序中按此步长前进的时钟就是仿真的时钟。 选取系统的一个初始状态作为仿真时钟的零点(仿真时钟每步进一次(就对系统的所有实体、属性和活动进行一次全面的扫描考察，按照预定的汁划和目标进行分析、计算和系统状态的变化，这个过程一直进行到仿真时钟结束为止。其流程图如网6(10所示。 20 图6。10 时间步长法方框图 (2)事件步长法。事件步长法是以事件发生的时间为增量，按照时间的进展。一步一步地对系统的行为进行仿真，直到预定的仿真时间结束为止。事件步长法的简要流程如图6(11所示。 事件步长法与时间步K法的主要区别是: ?事件步长法与时间步长法都是以时间为增量来考察系统状态的变化。随在时间步长法中，仿真时钟以等步长前进，而在事件步}?法中(仿真时钟的步长取决于事件之间的间隔。 21 ?时间步长法存一个步长内，认为系统所处的状态相同(因而所进步长的大小将影响仿真的精度。而在事件步长法中，每个事件的发生均有确切的时刻(不需要人为地选取步长，步长的大小埘对仿真精度影响较小。 ?时间步长法每步进一个步长就要对整个系统进行一次全面考察，即使状态没有发生变化时也要扫描。而事件步长法只是在某一事件发生时才进行扫描:无论用哪种方法仿真，在仿真过程中每一个事件点上总要判断和比较事件是否出现。因此，一般地讲，当判断比较的数目较大或事件变化呈周期性特点时，用时间步长法可以节省用机时间，而当相继两个事件出现的平均间隔较长时，更适合于用事件步长法。 如上所述(时间进程管理有面向事件的(这是一种变步长法;还有面向时间间隔的，这是一种定步长法。上节中的船闸运行系统模型的时间进程管理可以采用变步长法，事件的推进是由一个生成时划(船只的到达时刻)到F一时刻(船只的离开时刻)，而两个生成时刻间的差是随机的。采用面向事件的时问进程管理(其主要通道的选择也随之确定(即时间推进点是哪一事件的剩成时刻，就选择走向那个事件的通道。 22 下面介绍事件步长法中常用的事件表法。 2)事件表 为了使仿真程序能如实地模拟实际系统的变化(在某些离散事H。的仿真中，采用事件表的形式进行调度。事件表一般是一个有序的记录表(每个记录包括事件发生时间、事件类型等一些内容。 事件步长法中常用的事件表法的主要思路是将系统的仿真过程看成是一个事件点序列，根据事件出现的时序，用一个称之为事件表的来调度事件执行的顺序。对于那些当前需要处理的事件，列人事件表中(从中取出最接近的事件进行处理，处理完毕后自动退出事件表。在处理当前事件的过程中(往往会产 23 生一个后继事件，因此，必须预测出此后继事件的出现时间，并将它列入事件表中。这样，事件表好像一本记事簿，干完一件事后就把它从记事簿中勾销，而把新的要完成的工作再登记到记事簿中相应的地方去。以此使得系统的仿真过程有条不紊地进行下去。这种方法要求对系统的各种事件进行详细的描述，因此(当事件之间没有太多的相互作用和事件数目不是太多时(应用事件表法比较有效。 3)同时事件管理 在仿真中，对发生在同一时刻的几个事件的管理有以下方法。 (1)同类同时事件管理:发生在同一时刻且隶属于同一类型的几个事件叫同类同时事件。同类同时事件的发生会导致模型的下一状态出现多种可能值，即可能出现几种排队顺序。为此，我们需要先定好条件，以使状态取值成为惟,，也就是要规定一种排队规则来管理这同类同时事件。例如，先进先出(或先到先服务)规则、后进先出(或后到先服务)规则、随机规则以坟优先服务规则。 (2)混时事件管理:发生在同一时刻但不属于同一类型的几个事件叫混合同时事件。确定这些混合同时事件所造成的状态变化，通常有一步法与解结法。一 24 步法就是直接确定混合同时事件所形成的结果状态;解结法却是把几个同时事件分解成多个单独事件的序列进行处理。对于简单的情况，一步法与解结法将会得到相同的结果。但一步法不易写成通用形式，且流程管理中的通道选择较复杂;而解结法通用于各种仿真语言中，因为使用该法时模型结构简单，便于写成通用形式。 6(3(2离散事件系统仿真策略 因为模型类型不同，仿真方法大不相同。这里主要叙述排队网络模型的仿真方法。 根据离散事件模型的特点，实体活动、进程都是以事件为基础构成，其粒度又大于事件。从事件、活动、进程三个层次来组织事件即构成了处理离散事件模型的三种典型处理方法:事件调度法、活动描述法、进程交互法。图6(12,图6(14是排队网络系统常用的三种计算机仿真模型，相应采用三种不同的仿真策略，即事件调度、进程交互和活动扫描等仿真策略。在复杂系统仿真中，按进程来组织事件可以使众多的事件条理清晰，因而成为最通用的方法。 25 图6(12面向事件的仿真 图6。13 面向进程的仿真 26 图6 14面向活动的仿真 6(4排队系统仿真 人们在日常生活中经常遇到排队现象，如顾客到商店购买物品，旅客到车站 乘车就常常要排队。一般来说，当某个时刻要求服务的数量超过服务机构的容量时，就会出现排队现象。例如，在计算网络系统中，要求传输数据的是各个网络的节点，这里的服务机构是网络传输机构，而要求服务的是等待传输数据的节点。在各种排队系统中，顾客到达的时刻与接受服务的时间一般是不确定的，随着不同时机与条件而变化，因此排队系统在某时刻的状态也是随机的，排队现象几乎是不司避免的。 27 排队愈长就意味着浪费时间愈多，这一系统的效率就愈低。但是盲目地增加服务台也并不一定就能提高效率，因为有可能会使服务台空闲时间太多。故对排队问题的分析析实质上是一个平衡等待时间和服务台空闲时间的问题，也就是如何确定一个排队系统，能使临时实体和服务台两者都有利，即服务台利用率要高(实体等待时问又不太长。 本节先简单介绍一些排队论的基础，然后说明单服务台的排队系统仿真方法。 6(4(1排队系统的组成 一般的排队系统都有三个基本组成部分。 (1)到达模式:指临时实体按怎样的规律到达，一般用到达时间间隔的统计特征来描述。 (2)服务机构:指同一时刻有多少服务台(永久实体)可以接纳』临时实体，它们的服务要多少时间，它也具有一定的分布特征。 (3)排队规则:即服务台完成当前的服务后，从队列中选择下一个实体服务原则。 图6(15是排队系统的基本结构。图中的临时实体以一定的到达模式来到眼务机构请求服务，由于服务机构的服务员或设备有限，服务要有服务时间，因 28 此某些临时实体在来到服务机构以前不能马上得到服务，需要排队等待，一旦当服务机构完成对某个临时实体的服务之后，就可接纳新的动态实体。排队规则将确定在队列中哪一个动态实体可以最先得到服务。在很多实际问题中，临时实体的到达时间是随机的，服务机构的服务时间也是随机的(这样，临时实体排队的长度也会是随机的。如何通过已知的到达模式和服务时间的概率分布，来研究排队系统的队列长度和服务机构“忙”或“闲”的程度，就是离散事件仿真所要解决的问题。 图 4. 15排队系统的基本结构 6(4(2到达模式 先介绍将用到的一些基本概念。 (1) 平均到达问隔时间T在考虑模型的总时间Ta 中，共到达了n个临时实体的情况下的比值T,n。 ,(2) 平均到达速率 单位时间内到达的临时实体数。 1 ,,Ta 29 (3) 到达时间分布函数Ao(t) 到达间隔时间大于t的概率。因为累积分布函数F(t)是到达间隔时间小于t的概率，所以 A(t),1,F(t) 0 根据定义，函数A(t)在t=0时取最大值为1，当t增0 加时，A(t)逐渐减小。 0 (4) 到达时间变化系数 到达间隔时间的标准差S与平均到达间隔时间T的比值s,T。变化系数是aaaa 个无量纲的值，它描述了数据围绕平均值的分散程度。 到达模式按临时实体到来的方式可能是一个一个的，也可能是成批的;按相继到达的间隔时间可以是确定型的，也可以是随机型的;按到达过程可以是平稳的，指描述相继到达的间隔时间分布和所含参数(如期望值、方差等)都是与时间原点无关的，也可以是非平稳的。 6(4(3 服务机构 同到达时间一样，首先定义T为平均服务时间，s ,为平均服务速率，S(t)为服务时间大于t的概率。 0 在有多个服务台情形中，它们可以是平行排列(并行)的，可以是前后排列(串行)的，也可以是混合的;按服务方式可以对单独实体进行，也可以对成批顾客 30 进行;按服务时间可以是确定型的，也可以是随机型的;按服务过程可以是平稳的，也可以是非平稳的。非平稳情形的数学处理是很困难的，所以同到达过程一样，服务时间的分布都假定是平稳的。 6(4(4排队规则 临时实体依一定的次序和规则接受服务。 (1)先到先服务(FIFO) 即按到达次序接受服务。 (2)后到先服务(LIFO) 如乘用电梯的顾客常是后入先出的。仓库中存放的钢板也是如此。在情报系统中，最后到达的信息往往是最具有价值的，因而常采用后到先服务的规则。 (3)随机服务当服务台有空时，从等待的临时实体中随机地选取一名进行服务，而不管到达的先后，如电话交换台接通呼唤的电话就是如此。 (4)优先权服务根据队列中实体的重要程度选择最先服务者，如医院中急诊病人优先得到治疗。 (5)n个服务台的情形 当临时实体到达时，可以按如下规则在每个服务台前排成一个队，第1，n+l，2n+l，„个实体排入第一个队，第2，n+2，2n+2(„个实体排人第二个队等。或者所有实体排成一个公共的队，每当有一个服务台空闲时(队首的临时实体进 31 入服务。也可以这样来排成n个队:当某个实体到达时(以概率P排入第i个队(?Pi=1)。 i 6.4.5排队模型的分类和系统的主要统计性能 1(排队模型的分类 根据排队系统的三个组成部分中最主要的特征，肯德尔(Kendall)提出一个分类方法，针对单队多服务台且按FIFO规则服务的情形，将其表示为 X/Y/Z 式中 X——相继到达间隔时间的分布; Y--------服务时间的分布; Z——服务台的数目。 表示相继到达间隔时间和服务时间的各种分布的符号是: M——负指数分布 E——k阶爱尔朗分布 k D——确定性 GI——一般相互独立的随机分布 G——一般随机分布 例如，M,M,1表示相继到达间隔时间为负指数分布，服务时间也为负指数分布，且按m规则服务的单队单服务台排队系统模型的型式。 2(系统的统计性能 32 研究排队系统的目的是为了得到系统的统计性能，比较普遍使用的性能指标有以下四种。 (1)稳态平均排队时间d 6.9 式中Di为第i个实体的排队时间。平均排队时间就是实体在队列中的平均等待时间。 (2)实体通过系统的稳态平均滞留时间叫w 其中W为第i个实体通过系统时的滞留时间，它等于实体在队列中的等待时间D与该实体接受服务的时间i S之和。 i (3)稳态平均队长Q 4.10 其中Q(t)为t时刻的队列长度。 (4)系统中稳态平均实体数L 其中L(t)为t时刻系统中的实体数，它是在队列中的实体数Q(t)与正在接受服务的实体数S(t)之和。 上述四个性能指标存在的条件是服务台的利用率,, <1，的定义是 33 正常情况下服务台利用率小于1，这样每个临时实体才有希望得到服务。利用率越高，则临时实体排队等待的时间越长。因此设计系统的设备利用率是一个权衡过程，可以通过多次的仿真实验加以合理解决。在仿真实验中，对上述各个量的变化进行统计，以求出其平均值、方差、最大值、最小值等。这些值反映了一个服务系统的重要特征。 6.4.6单服务台排队系统仿真 若有一单服务台排队系统，为N个实体服务。实体到达间隔为某种概率分布的随机变量，以AT表K示;第K个实体到达时间用CAT表示;而第K个实体K 眼务的时间则用SK表示，其中K=1，2，„，N，并已K 知服务时间也是某种概率分布的随机变量。下面我们分析一下这一排队系统工作过程以及系统的时间流程: 设系统初始状态为无排队现象，服务台空闲。所以当t=0，第一个实体进入时，立即可以得到服务，服务时间为ST。第二个实体在AT时(即CAT= AT)1222到达，这时可能有两种情况: (1)若ST>CAT，则第2个实体需等待，等待时间为WT，l22 34 且WT=ST—CAT。 212 (2)若CAT>ST，则第一个实体在第二个实体到达前已2l 经离开服务台，则服务台处于空闲的时间为IDT2=CAT2一ST1，其中，IDK为服务台等待为第K个K 实体服务的空闲时间。如此继续下去。一般情况下的表达式如下: 若已有(i-1)个实体到达系统，同时又有(j-1)个实体已经离开，也就是说，下一步应是第i个实体到达，第J个实体离开，显然1?j?i?N。此外，由于i>j，故目前系统中的队长是(i-j-1)。第i个实体到达时间为NAT=CAT，而第j个实体离开时间应为 i NDT=CDT=CAT+WT+STjjjj 式中 WT——第j个实体等待服务的时间; j ST——第j个实体接受服务的时间。 j 现在必须确定应该先产生哪一个事件，是第i个实体到达还是第j个实体离开。这完全可以用NAT和NDT两个量的比较结果作出判断: (1)若DIF=NAT--NDT>0，则第j个实体应该先离开，此时队长必然要减少l。 (2)若DIF<0，则第i个实体先到达，此时队长必然增加1。 在这两种情况下，服务台都没有空闲时间。但是 35 如果队长原来已经为零，而DIF>O，即第j个实体先服务完，队伍里已没有实体，则服务台处于空闲状态，直到第i个实体到达，其等待时间IDTi=DIF。当然，如果DIF=0，即第i个实体到达和第i个实体离开两事件同时发生，则队长不变。 图4(16为这一单服务台排队系统的仿真流程。图中AT(K)，ST(K)，CAT(K)，IDT(K)分别表示AT，KST，CAT，IDT(K=1，2，„，N)，其中AT(K)，ST(K)KKK 可由另编的子程序产生。并设CAT1=ATl=0，即仿真从t=O开始，且 CAT= CAT+ ATKK-1K CLOCK表示仿真时间，OL(I)表示队长，其中I表示第i个实体到达后的队长(I=l，2(„(N)。 仿真可以输出以下的结果: (1)最大队长; (2)平均队长(包括队长为零时的情况); (3)非空平均队长(队长为零时除外); (4)系统中平均实体数; (5)系统中有n个实体的概率; (6)平均等待时间(包括所有实体); (7)平均等待时间(只包括正在等待的实体); (8)最大等待时间; 36 (9)系统中每一实体平均花费的时间; (10)服务台总的空闲时间; (11)服务台空期和忙期各占百分比。 由QL(I)(I=1，2，„，N)可以计算平均队长及最大队长;由IDT(I)(I=l，2，„，N)可以得到等待第i个实体进人服务台的空闲时间。由此计算平均空闲时间和最大空闲时间。 因第i个实体等待时间WTi=CDTi—Sti-CATi，由此可以计算总等待时间、最大和平均等待时间。由Wti+STi可以计算每一个实体在系统中花费的时间等。下面以一简单例子说明应用这一仿真流程进行仿真的结果。 例4—2设有一单服务台排队系统，共到达实体数为8，即N=8。其到达时间间隔和服务时间分别如下: 到达间隔为0，10，15，35，30，10，5，5 服务时间为22，15，10，5，15，15，10，10 试应用仿真流程进行仿真，求出平均队长及服务台平均空闲时间。 仿真时只需输入实体到达时间间隔和服务时间(或由子程序产生)，并分别存放于数组AT(I)及ST(I)中，即 A T(I)=(0，10，1 5，35，30，10，5，5) 37 ST(I)=(22，15，10，5，15，15，10，10) 仿真过程中，有数组QL(I)和IDT(I)分别记录每一个实体到达时的队长及服务台空闲时间。到仿真结束时QL(I)及IDT(I)如下: QL(I)=(0，1，1，0，0，1，2，1) IDT(I)=(0，0，0，15，25，0，0，0) 根据这两个数组中存放的数据，可以方便地求出平均队长及服务台平均空闲时间，即 0，1，1，0，0，1，2，1 平均队长=，取整为1 ,0.758 0，0，0，15，25，0，0，0 服务台平均空闲时间= ,58 作业: 38 39 40