多服务台混合制排队模型M/G/s/K的仿真研究

摘 要:为更快、更方便地得到一般服务时间的多服务台混合制中M/G/s/K排队系统在达到稳定之后的系统状态,通过离散化处理仿真时间方法,并借鉴时间步长法的思想,给出一种基于Matlab编程的仿真算法。通过实验说明了该方法的有效性。对于处理此类排队问题提供了一个新的方法。

关键词:多服务台混合制排队模型; M/G/s/K排队模型; 时间步长法; Matlab编程

中图分类号:TN911-34; TP274文献标识码:A

文章编号:1004-373X(2010)17-0142-04

Simulation of M/G/s/K Multi-server Mixed Queuing Model

CHEN Shi

(School of Finance and Statistics, East China Normal University, Shanghai 200241, China)

Abstract: On the purpose of obtaining the system state of M/G/s/K multi-server mixed queuing model after arriving at stable state in a faster and convenient manner, through performing the simulated time with discrete method and utilizing the thoughts of fix-time incrementing method, an algorithm based on Matlab programming to implement the simulation of M/G/s/K queuing model is proposed, and the validity of this simulation algorithm is demonstrated. A new method to deal with problems of this category is provided.

Keywords: mixed queuing model of multi servers; M/G/s/K queuing model; fix-time incrementing method; Matlab programming

0 引 言

排队论是研究随机服务系统的数学理论和方法。在某些特定情况下排队队列达到稳定的时候,排队系统的各个参数可以通过数学推导得到。但当排队过程不具备马尔科夫性时,用数学推导的方式研究排队系统是异常困难的。然而随着计算机技术的发展,运用计算机仿真的方法研究排队模型已成为解决这类排队问题的有效方法。

排队系统的仿真问题国内已经有很多人在研究,并且已经取得了一些成果。张建航等用蒙特卡洛模拟的方法初步解决了排队理论中最为基础的单服务员排队模型(M/M/1模型)的仿真模拟问题[1];和王珊珊在论文中给出了较为详细的单服务台排队模型的仿真方法[2];宋振峰等更进一步研究了M/M/m非混合制排队模型的仿真方法[3]。国内文献相对缺乏对M/G/s/K这类更为复杂的多服务台混合制排队模型的仿真研究。

本文将以Matlab为编程平台,研究M/G/s/K模型的仿真算法。

1 M/G/s/K模型介绍

本文根据多服务台混合排队模型的特性,绘制了该模型的运行模式,如图1所示。

图1 多服务台混合排队模型的运行模式

在M/G/s/K排队模型中,顾客的其到达过程服从参数为λ的Poisson流,等待队列为容量为K-s,当系统中有新顾客到来时,如果等待队列中人数已满,此顾客就会被拒绝在排队系统外,从而造成了服务系统的顾客损失,如果等待队列中人数未满,则此名顾客加入等待队列,等候接受服务。系统中有多个服务台,每个顾客接受服务所要花费的时间服从一般分布G。在等待队列中,顾客接受服务服从先到先服务(FCFS)的原则。

2 M/G/s/K排队模型的仿真算法

本文运用时间步长法的思想对多服务台混合制排队模型M/G/s/K进行仿真,假设所有事件(顾客到达,服务开始,顾客离去)均是在每一个步长结束的瞬间发生的,这样,就将此问题转化成为了离散化的问题,从而有利于运用计算机进行仿真。

为了方便排队系统中所有的顾客信息、顾客排队等候情况和各服务台的服务情况更新,本文首先构建3个矩阵:顾客信息矩阵、等待队列信息矩阵和服务台状态矩阵,用来辅助仿真算法的实现。下面介绍这3个矩阵所存储的信息、矩阵的初始化方法和更新算法。

2.1 顾客信息矩阵

顾客信息矩阵是存储仿真时段T内到达的所有顾客的信息矩阵。

(1) 矩阵储存的信息

顾客信息矩阵为一个h×3的矩阵,其中h为仿真时间T内到达顾客的人数,矩阵的每一列存放着┮幻顾客的信息,顾客信息矩阵每一行所存放的具体信息如表1所示。

表1 顾客信息矩阵

矩阵行矩阵行存放的信息

1顾客到达排队系统的时刻

2顾客接受服务台服务所花费的时间

3顾客是否被排队系统接受的示性指标

其中,第三行中所指的示性指标定义:一名顾客到达排队系统的时候,若等待队列已满,此顾客被排队系统拒绝,则相应的矩阵列的第三行所记录的示性指标为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所示。

表2 等待队列信息矩阵

矩阵行矩阵行存放的信息

1顾客进入等待队列的时刻

2顾客接受服务台服务所要花费的时间

有一点值得强调的是,假设在队列中,顾客均趋向于在最前面的等待位置就坐,也就是说,若等待队列中有a名顾客在等待,则这a名顾客的信息要根据到达时刻的先后顺序依次占据等待队列信息矩阵的前a列,后面的K-s-a列矩阵元素以0填充,矩阵的具体形式如下所示:

c1c2c3…ca0…0

b1b2b3…ba0…02×(K-s)

(2) 矩阵初始化

在仿真开始之前,队列中无顾客在等候,所以将该矩阵初始化为2×(K-s)的零矩阵。

(3) 矩阵的更新算法

等待队列信息矩阵中的元素应随着仿真时钟的推进而不断更新,每次仿真时钟刷新之后,矩阵就应按照如下算法进行更新:

① 若仿真时钟所指时刻刚好有顾客结束服务离开系统或此时有服务台处于空闲状态,如果等待队列中仍有乘客在等待,则此服务台接受占据等待矩阵第一列的乘客,并将等待矩阵中所有其他顾客的信息前移┮涣歇。用0元素填充不存储有等待顾客信息的矩阵列。如果等待队列中没有顾客在等待,即此时等待队列信息矩阵为一个零矩阵,则不对等待队列信息矩阵做任何变换。

② 若仿真时钟所指时刻有新顾客到达,如果等待队列不满,则将新到的顾客的信息置于当前等待队列中最后一名顾客的信息之后,即用此顾客的信息替代┑谝桓霆元素全为0的矩阵列,如果等待队列人数已满,则等待矩阵不更新,此乘客被拒绝。

③ 若仿真时钟所指时刻无顾客结束服务,也无新顾客到达,则矩阵不发生更新。

2.3 服务台状态矩阵

服务状态矩阵是存放每个服务台动态信息的矩阵。

(1) 矩阵储存的信息

服务台状态矩阵为一个4×s的矩阵。其中s为系统中服务台的个数,矩阵的每一列储存一个服务台的信息,若第p个服务台空闲,则矩阵的第p的各行列元素为0;若此服务台处于忙碌状态,则矩阵第p列的各行元素所存放的信息如表3所示。

表3 服务台状态矩阵

矩阵行矩阵行存放的信息

1服务台当前所服务的顾客的开始服务时刻

2服务台当前所服务的顾客服务结束的时刻

3服务台当前所服务顾客进入排队系统的时刻

4服务台忙闲状态的示性指标

其中,对第四行中服务台忙闲状态的示性指标定义如下:

服务台忙闲状态的示性指标=

0,服务台目前空闲1,服务台目前忙碌

(2) 矩阵初始化

在仿真开始之前,所有服务台均处于空闲状态,所以用4×s的零矩阵作为服务台状态矩阵的初始化矩阵。

(3) 矩阵的更新算法

随着仿真时钟的推进,服务台状态矩阵自身的元素需要不断进行更新,每次仿真时钟刷新之后,此矩阵就应按照如下算法进行更新。

① 若在仿真时钟所指的时刻有服务台处于空闲状态,且等待队列中有顾客在等待,则空闲的服务台依乘客到达时间的顺序接受等待队列中的顾客,更新接受了新顾客的服务台所对应的矩阵列元素。

② 若在仿真时钟所指的时刻,有服务台在刚好完成了对当前顾客的服务任务,如果此时等待队列中有顾客在排队,则服务台同样依据乘客到达等待队列的时间先后,依次接收等待队列中的顾客,并更新相应的矩阵列元素;否则,等待队列中没有顾客在等待,则设置服务台为空闲状态,将矩阵相应列的4个数值全部归零。

③ 若以上所述的情况均不发生,则服务台状态矩阵不发生更新。

至此,以上3个矩阵所存放的信息,初始化方法及其更新的算法介绍完毕,在此基础上,给出了M/G/s/K排队模型的仿真算法,算法流程如图2所示。

图2 多服务台混合排队系统M/G/s/K仿真流程图

其中,流程图中有两个更新模块,每个更新模块都有各自的更新流程,更新模块1的流程如图3所示。

图3 更新模块1具体流程

更新模块2的流程如图4所示。

以上就是本文所给出的M/G/s/K排队模型的仿真算法。为说明此算法是有效的,这里还需对其进行有效性检验。

图4 更新模块2具体流程

3 仿真算法有效性的验证

前面已经提到,当排队过程不具备马尔科夫性时,对排队模型进行基于排队理论的分析非常困难,而当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排队模型的仿真也是有效的。

下面运用一个汽车加油站的排队案例[7]来验证此算法对于M/M/s/K排队模型的有效性。

某汽车加油站有2台加油机,汽车按照Poisson流到达,每分钟到达率为2辆,且汽车加油的时间服从均值为2 min的负指数分布,该加油站的空间有限,最多同时只能容纳3辆汽车排队,若某辆汽车到达时,加油站中已经存在2+3=5辆汽车在系统中,则其不得不开到另外的加油站进行加油。

此系统可以看成一个M/M/2/5排队系统,此类排队模型可以直接通过排队理论的分析得到此排队系统达到稳定状态之后的状况,参考文献[7]中所给出的M/M/s/K排队模型的求解方法。此系统中汽车每分钟到达率为Е=2,加油机每分钟服务率为μ=0.5,加油机服务强度为ρ=λ/μ=4,服务台个数为s=2,系统能容纳的最大汽车数为K=5,г蛴:

系统空闲概率为:

p0=∑s-1n=0ρ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=ρKs!sK-sp0=45×0.0082!×25-2=0.512

加油站内在等待的汽车数平均值为:

Lq=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+p0∑s-1n=0(n-1)ρnn!=

2.18+4(1-0.512)=4.13

汽车在加油站内排队等待的平均时间为:

Wq=Lλ(1-p)-1μ=4.132(1-0.512)-2

=2.23 min=133.8 s

由大数定律可知,若一个仿真算法有效,当仿真次数趋于无穷大的时候,仿真结果的均值应依概率1收敛于排队理论计算得到的结果。

用上文给出的方法对该汽车加油站排队案例进行仿真,取1 s为一个步长,汽车每秒钟的到达率为λs=2/60,汽车接受加油服务中以秒计算的服务率为μs=1/120,取仿真运行的总时间为10 h,即36 000 s,运行已经编辑好的Matlab程序100次,求出所得结果的均值。将得到的仿真结果与理论结果进行比较,如表4所示。

表4 理论结果与仿真结果的比较

分析方式

/指标种类平均等待队长平均在队列中的等待时长 /s顾客损失率 /%

排队论分析结果2.18133.851.20

仿真100次结果均值2.10133.551.21

对比理论计算结果和仿真结果发现,两者非常接近,从而可以认为本文所给出的仿真算法对于M/M/s/K排队模型是有效的,进而认为该仿真算法对于M/G/s/K排队模型是有效的。

4 结 语

运用时间步长法,设计了一种M/G/s/K排队模型的仿真算法,并验证了该算法的有效性。

本文所给出的算法流程具有广泛的适应性,只要通过一些必要的修改,就能胜任其他种类排队模型仿真任务。相对于以往文献中所给出的排队模型的仿真方法,该算法可以满足更多情况下对于排队模型仿真的需要。

参考文献

[1]张建航,李宗成,宋晓峰.单服务员排队模型及其蒙特卡洛模拟[J].现代电子技术,2006,29(24):44-46.

[2],王珊珊.用Matlab实现排队过程的仿真[J].电脑编程技巧与维护,2009(15):15-17.

[3]宋振峰,席志红,刘飞.基于Matlab的M/M/m排队模型的仿真[J].现代电子技术,2005,28(6):29-31.

[4]颜薇娜.基于蒙特卡洛模拟的商业银行排队问题研究[J].技术经济与管理研究,2009(1):20-22.

[5]吴可嘉.蒙特卡洛法在解决食堂窗口排队问题上的应用[J].大连海事大学学报,2007,33(S1):149-152.

[6]高静涛,史百战.基于Matlab的排队问题仿真[J].武汉工业学院学报,2007,26(2):89-91.

[7]胡运权,郭耀煌.运筹学教程[M].北京:清华大学出版社,2007.

[8]苏金明,阮沈勇.Matlab实用教程[M].北京:电子工业出版社,2008.

[9]Sheldon M Ross.随机过程[M].北京:中国统计出版社,1997.

[10]范影乐,杨胜天,李轶.Matlab仿真应用详解[M].北京:人民邮电出版社,2001.