基于malab的mgsk排队系统仿真时间方法

基于malab的mgsk排队系统仿真时间方法

0排队模型的仿真研究队列理论是研究随机服务系统的数学理论和方法。在某些特定情况下排队队列达到稳定的时候,排队系统的各个参数可以通过数学推导得到。但当排队过程不具备马尔科夫性时,用数学推导的方式研究排队系统是异常困难的。然而随着计算机技术的发展,运用计算机仿真的方法研究排队模型已成为解决这类排队问题的有效方法。排队系统的仿真问题国内已经有很多人在研究,并且已经取得了一些成果。张建航等用蒙特卡洛模拟的方法初步解决了排队理论中最为基础的单服务员排队模型(M/M/1模型)的仿真模拟问题;李鹏和王珊珊在论文中给出了较为详细的单服务台排队模型的仿真方法;宋振峰等更进一步研究了M/M/m非混合制排队模型的仿真方法。国内文献相对缺乏对M/G/s/K这类更为复杂的多服务台混合制排队模型的仿真研究。本文将以Matlab为编程平台,研究M/G/s/K模型的仿真算法。1顾客接待费的时间本文根据多服务台混合排队模型的特性,绘制了该模型的运行模式,如图1所示。在M/G/s/K排队模型中,顾客的其到达过程服从参数为λ的Poisson流,等待队列为容量为K-s,当系统中有新顾客到来时,如果等待队列中人数已满,此顾客就会被拒绝在排队系统外,从而造成了服务系统的顾客损失,如果等待队列中人数未满,则此名顾客加入等待队列,等候接受服务。系统中有多个服务台,每个顾客接受服务所要花费的时间服从一般分布G。在等待队列中,顾客接受服务服从先到先服务(FCFS)的原则。2仿真问题的求解本文运用时间步长法的思想对多服务台混合制排队模型M/G/s/K进行仿真,假设所有事件(顾客到达,服务开始,顾客离去)均是在每一个步长结束的瞬间发生的,这样,就将此问题转化成为了离散化的问题,从而有利于运用计算机进行仿真。为了方便排队系统中所有的顾客信息、顾客排队等候情况和各服务台的服务情况更新,本文首先构建3个矩阵:顾客信息矩阵、等待队列信息矩阵和服务台状态矩阵,用来辅助仿真算法的实现。下面介绍这3个矩阵所存储的信息、矩阵的初始化方法和更新算法。2.1客户信息矩阵顾客信息矩阵是存储仿真时段T内到达的所有顾客的信息矩阵。(1)顾客信息矩阵顾客信息矩阵为一个h×3的矩阵,其中h为仿真时间T内到达顾客的人数,矩阵的每一列存放着一名顾客的信息,顾客信息矩阵每一行所存放的具体信息如表1所示。其中,第三行中所指的示性指标定义:一名顾客到达排队系统的时候,若等待队列已满,此顾客被排队系统拒绝,则相应的矩阵列的第三行所记录的示性指标为0;若顾客到达排队系统的时候,等待队列人数未满,此名顾客被排队系统接受,相应的矩阵列的第三行所记录的示性指标为1。(2)顾客的服务时间分布设所要仿真的时间段的长度为T,用随机数发生器产生泊松分布Poisson(λt)的随机数h,作为这段时间内出现的顾客总人数。由于顾客到达间隔服从参数不变的负指数分布,由泊松过程理论可知,在一个固定时间段T内如果给定了乘客到达的人数h,那么每个顾客到达时间独立地服从这一时间段上均匀分布。独立地取h个服从(0,T)上的均匀分布的随机数,精确到秒,作为这h名顾客的到达时刻,并将其输入顾客信息矩阵的第一行。根据前面排队模型所描述的每位顾客的服务时间分布,用随机数发生器产生h个相互独立的服从分布G的随机数,作为每位顾客接受服务台服务所要花费的时间,精确到秒后,将这h个数据输入到顾客信息矩阵的第二行。用数字0初始化顾客信息矩阵的第三行所有元素。(3)顾客信息矩阵更新顾客信息矩阵的前两行需在仿真开始之前就先行确定,在仿真过程中不需进行更新,而第三行应随着仿真时钟的推进而不断更新,当仿真时钟在t时刻,第i名顾客到达排队系统,且此时等待队列中人数未满,则此顾客被等待队列接受,由2.1节所给出的示性指标定义,更新顾客信息矩阵第三行第i列的元素为1,否则,不对矩阵进行更新。2.2等待队列信息矩阵等待队列信息矩阵是存放在等待队列中等待顾客的信息矩阵。(1)顾客之间的关系等待队列信息矩阵大小为2×(K-s)。其中,K为系统所能容纳的最大顾客数;s为系统中的服务台个数;矩阵的每列代表等待队列中的一个位置,若第i个座位未被占据,则矩阵第i列元素均为0;若座位被顾客占据,则等待队列信息矩阵的第i列记录了这名顾客的相关信息,具体每行所记录的信息内容如表2所示。有一点值得强调的是,假设在队列中,顾客均趋向于在最前面的等待位置就坐,也就是说,若等待队列中有a名顾客在等待,则这a名顾客的信息要根据到达时刻的先后顺序依次占据等待队列信息矩阵的前a列,后面的K-s-a列矩阵元素以0填充,矩阵的具体形式如下所示:[c1c2c3⋯ca0⋯0b1b2b3⋯ba0⋯0]2×(Κ-s)[c1b1c2b2c3b3⋯⋯caba00⋯⋯00]2×(K−s)(2)矩阵初始化在仿真开始之前,队列中无顾客在等候,所以将该矩阵初始化为2×(K-s)的零矩阵。(3)第三,有待顾客进入第三列等待队列信息矩阵中的元素应随着仿真时钟的推进而不断更新,每次仿真时钟刷新之后,矩阵就应按照如下算法进行更新:①若仿真时钟所指时刻刚好有顾客结束服务离开系统或此时有服务台处于空闲状态,如果等待队列中仍有乘客在等待,则此服务台接受占据等待矩阵第一列的乘客,并将等待矩阵中所有其他顾客的信息前移一列。用0元素填充不存储有等待顾客信息的矩阵列。如果等待队列中没有顾客在等待,即此时等待队列信息矩阵为一个零矩阵,则不对等待队列信息矩阵做任何变换。②若仿真时钟所指时刻有新顾客到达,如果等待队列不满,则将新到的顾客的信息置于当前等待队列中最后一名顾客的信息之后,即用此顾客的信息替代第一个元素全为0的矩阵列,如果等待队列人数已满,则等待矩阵不更新,此乘客被拒绝。③若仿真时钟所指时刻无顾客结束服务,也无新顾客到达,则矩阵不发生更新。2.3服务台状态矩阵服务状态矩阵是存放每个服务台动态信息的矩阵。(1)矩阵各行元素所存状态服务台状态矩阵为一个4×s的矩阵。其中s为系统中服务台的个数,矩阵的每一列储存一个服务台的信息,若第p个服务台空闲,则矩阵的第p的各行列元素为0;若此服务台处于忙碌状态,则矩阵第p列的各行元素所存放的信息如表3所示。其中,对第四行中服务台忙闲状态的示性指标定义如下:(2)矩阵初始化在仿真开始之前,所有服务台均处于空闲状态,所以用4×s的零矩阵作为服务台状态矩阵的初始化矩阵。(3)基于m/g/s/k排队模型的仿真算法随着仿真时钟的推进,服务台状态矩阵自身的元素需要不断进行更新,每次仿真时钟刷新之后,此矩阵就应按照如下算法进行更新。①若在仿真时钟所指的时刻有服务台处于空闲状态,且等待队列中有顾客在等待,则空闲的服务台依乘客到达时间的顺序接受等待队列中的顾客,更新接受了新顾客的服务台所对应的矩阵列元素。②若在仿真时钟所指的时刻,有服务台在刚好完成了对当前顾客的服务任务,如果此时等待队列中有顾客在排队,则服务台同样依据乘客到达等待队列的时间先后,依次接收等待队列中的顾客,并更新相应的矩阵列元素;否则,等待队列中没有顾客在等待,则设置服务台为空闲状态,将矩阵相应列的4个数值全部归零。③若以上所述的情况均不发生,则服务台状态矩阵不发生更新。至此,以上3个矩阵所存放的信息,初始化方法及其更新的算法介绍完毕,在此基础上,给出了M/G/s/K排队模型的仿真算法,算法流程如图2所示。其中,流程图中有两个更新模块,每个更新模块都有各自的更新流程,更新模块1的流程如图3所示。更新模块2的流程如图4所示。以上就是本文所给出的M/G/s/K排队模型的仿真算法。为说明此算法是有效的,这里还需对其进行有效性检验。3/m/3/5排队模型前面已经提到,当排队过程不具备马尔科夫性时,对排队模型进行基于排队理论的分析非常困难,而当M/G/s/K排队模型中顾客服务时间的分布服从特定分布负指数分布时,模型就转化成为M/M/s/K排队,且此模型具备马尔科夫性,可以较为方便地运用排队理论对这种排队模型进行分析,进而可以通过对比运用排队理论分析和仿真算法模拟所得到的结果是否具有一致性来判断此仿真算法是否对M/M/s/K排队模型有效,而M/M/s/K排队模型与M/G/s/K排队模型的仿真算法仅在服务时间的随机数生成方面有所不同,因此,如果此仿真算法通过了其对M/M/s/K排队模型仿真的有效性检验,就可以认为此算法对M/G/s/K排队模型的仿真也是有效的。下面运用一个汽车加油站的排队案例来验证此算法对于M/M/s/K排队模型的有效性。某汽车加油站有2台加油机,汽车按照Poisson流到达,每分钟到达率为2辆,且汽车加油的时间服从均值为2min的负指数分布,该加油站的空间有限,最多同时只能容纳3辆汽车排队,若某辆汽车到达时,加油站中已经存在2+3=5辆汽车在系统中,则其不得不开到另外的加油站进行加油。此系统可以看成一个M/M/2/5排队系统,此类排队模型可以直接通过排队理论的分析得到此排队系统达到稳定状态之后的状况,参考文献中所给出的M/M/s/K排队模型的求解方法。此系统中汽车每分钟到达率为λ=2,加油机每分钟服务率为μ=0.5,加油机服务强度为ρ=λ/μ=4,服务台个数为s=2,系统能容纳的最大汽车数为K=5,则有:系统空闲概率为:p0=[s-1∑n=0ρnn!+ρs(1-ρΚ-s+1s)s!(1-ρs)]-1={1+4+42[1-(4/2)5-2+1]2!(1-4/2)}-1=0.008p0=[∑n=0s−1ρnn!+ρs(1−ρK−s+1s)s!(1−ρs)]−1={1+4+42[1−(4/2)5−2+1]2!(1−4/2)}−1=0.008顾客损失率为:p=ρΚs!sΚ-sp0=45×0.0082!×25-2=0.512p=ρKs!sK−sp0=45×0.0082!×25−2=0.512加油站内在等待的汽车数平均值为:Lq=p0ρsρss!(1-ρs)2[1-ρΚ-s+1s-(1-ρs)(Κ-s+1)ρΚ-ss]=0.008×42×(4/2)2!(1-4/2)2[1-(4/2)5-2+1-(1-4/2)⋅(5-2+1)×(4/2)5-2]=2.18Lq=p0ρsρss!(1−ρs)2[1−ρK−s+1s−(1−ρs)(K−s+1)ρK−ss]=0.008×42×(4/2)2!(1−4/2)2[1−(4/2)5−2+1−(1−4/2)⋅(5−2+1)×(4/2)5−2]=2.18加油站内汽车的平均数目为:L=Lq+s+p0s-1∑n=0(n-1)ρnn!=2.18+4(1-0.512)=4.13L=Lq+s+p0∑n=0s−1(n−1)ρnn!=2.18+4(1−0.512)=4.13汽车在加油站内排队等待的平均时间为:Wq=Lλ(1-p)-1μ=4.132(1-0.512)-2=2.23min=133.8sWq=Lλ(1−p)−1μ=4.132(1−0.512)−2=2.23min=133.8s由大数定律可知,若一个仿真算法有效,当仿真次数趋于无穷大的时候,仿真结果的均值应依概率1收敛于排队理论计算得到的结果。用上文给出的方法对该汽车加油站排队案例进行仿真,取1s为一个步长,汽车每秒钟的到达率为λs=2/60,汽车接受加油服务中以秒计算的服务率为μs=1/120,取仿真运行的总时间为10h,即36000s,运行已经编辑好的Matlab程序100次,求出所得结果的均值。将得到的