多服务台等待制排队模型M／G／c／∞的蒙特卡洛模拟

王培勋 王志芳

（西安财经学院 统计学院，陕西 西安 710100）

多服务台等待制排队模型M／G／c／∞的蒙特卡洛模拟

＊王培勋 王志芳

（西安财经学院 统计学院，陕西 西安 710100）

文章以排队论为基础，用蒙特卡洛在Matlab上对多服务台等待制排队模型M／G／c／∞进行了模拟，得到了系统的一些指标，如系统队长，顾客逗留时间等，并通过两个实例说明了该方法的可行性，为处理此类排队问题提供了一个新的方法.

多服台等待制模型；蒙特卡洛模拟；排队论；动态模拟

0 引言

排队论，或称随机服务系统理论，是通过对服务对象到来及服务时间的统计研究，得出诸如等待时间排队长度，忙期长短等这些数量指标的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统能满足服务对象的需求，又能使机构的费用最经济或某些指标最优，这些指标一般可以通过数学推导得到.但是在实际问题中所碰到的排队问题往往不具有马尔科夫性，这时用数学推导就比较困难.随着计算机技术的发展，运用计算机仿真的方法来研究排队模型已成为解决这类排队问题的有效方法.国内外学者在研究这类问题已经取得了一些成果，如张建航等在论文中给出了单服务台排队模型M／M／1／∞的蒙特卡洛模拟，得到了顾客的等待时间和系统队长［1］，李鹏等通过Matlab平台对单服务台有限队长的排队系统进行了仿真，仿真出各个顾客到达时刻与离开时刻曲线，等待时间与停留时间曲线［2］，吴可嘉在Excel上实现了对单对多服务台的模拟，得出了学校食堂应该再增加一个窗口可以满足服务需求的结论［3］.但是目前对多服务台等待制排队模型M／G／c／∞的模拟还是比较少的，本文运用蒙特卡洛模拟方法，研究M／G／c／∞模型的仿真算法.

1 排队论及M／G／c／∞模型介绍

排队论是研究系统随机聚散现象和随机服务系统工作过程的数学理论和方法，排队论的排队规则分为3类：损失制、等待制和混合制.其中，损失制是指顾客到达时，如果所有服务台都没有空闲，该顾客不愿等待，就随即从系统消失；等待制是指顾客到达时，如果所有服务台都没有空闲，他们就排队等待；混合制是指既有等待又有损失的情况，如顾客等待时考虑排队的队长、等待时间的长短等因素而决定去留.

本文所模拟的是多服务台等待制排队模型M／G／c／∞，系统空间是无限的，顾客来源也是无限的，即设系统有c个服务窗口并联排列，各服务窗口独立工作，又各窗口的服务时间服从一般分布G，假设顾客按参数为λ的泊松分布到达，即顾客到达的间隔服从指数分布，如果顾客到达系统时c个服务窗都忙着，则顾客排队等待，并且假设各个服务窗口工作时相互独立的遵循先到先服务原则，允许永远排队.

2 随机数的产生

1）在各种统计计算中常需要产生各种概率分布的随机数，而大多数概率分布的随机数的产生均基于均匀分布U（0，1）的随机数，产生随机数的基本方法有三种，逆变换法，合成方法，筛选方法.这里我们用拟变换法来产生分布函数的随机数.首先介绍逆变换法.设随机变量X的分布函数为F（X），定义F－1（y）＝infx：F（x）≥ ｝｛y，0≤y≤1，有如下定理：

定理设随机变量U～U（0，1），则X＝F－1（U）的分布函数为F（x）［4］.

由此定理我们可以知道要产生来自F（x）的随机数，只要先产生来自U（0，1）的随机数u，然后计算F－1（u）即可，具体步骤是首先由U（0，1）抽取u，然后计算x＝F－1（u），其中F－1如上诉中定义.当我们得到了分布函数的随机数的产生方法以后，我们就可以进行随机模拟了，随机模拟方法也称为蒙特卡洛模拟方法，它是以概率统计理论为基础，利用电子计算机数字模拟技术，解决一些很难直接用数学求解或用其他方法不能解决的问题，它的实质是运用一连串的随机数来模拟可能出现的随机现象.

2）仿真系统模拟，设T为模拟系统的总服务时间，t为时间变量，t1为顾客的到达系统的时间，d为1×c矩阵，第j列记录第j个服务台上顾客的离开的时间，t2＝min（d），即顾客最早离开服务台的时间，n为在t时刻当前到达系统中的顾客数，A为在t时刻到达系统中的所有顾客总数.设循环变量为i，g（i）记录在一次循环中不同事件发生的时间间隔，h（i）记录在一次循环中系统中的顾客数，c为1×c矩阵，记录c个服务台的工作状态，其中元素为1表示该服务台正忙，元素为0表示该服务台处于空闲状态，设变量b为系统当前的顾客数.

模拟算法；

Step1 初始化，输入模拟系统的总服务时间T，设t＝0，n＝0，A＝0此时系统中没有顾客，所有服务台都空闲，c矩阵各列元素都为0，d矩阵各列元素都是∞，b＝0.

Step2 产生第一个顾客进入系统的时间t1，这时循环变量i＝0.

Step3 进入循环，i＝i＋1，h（i）＝b，如果t1＜T，则有g（i）＝min（t1－t2）－t，否则结束.

Step4 如果t1＜t2，说明顾客进入系统的时间小于服务台上顾客的离开时间，使t＝t1，产生下一顾客进入系统的时间t1，这时总顾客数多了一个，A＝A＋1，n＝n＋1，b＝n，即系统中的顾客数也加1，如果有c（j）＝0，说明第j个服务台空闲，将系统中的顾客分配给第j个服务台，同时产生第j个服务台上顾客的离开时间.

Step5 如果t1≥t2，说明有顾客离开服务台，使t＝t2，系统中的顾客减少了一个，n＝n－1，b＝n，此时如果系统中还有顾客，就上前服务，同时产生其离开时间，然后转Step3，直至t1＞T.

3 实例分析

实例1 设有3个打字员，平均打印文件的速度为μ＝6份／小时，文件到达率为15份／小时，试求1）在打字室内现在有的平均文件数；2）每份文件在打字室平均停留时间；3）3个打字员均不空闲的概率.

我们可以看到这是M／M／c／∞模型，运用排队论的数学计算公式有：

如果用上文给出的方法进行仿真，题中顾客的到达时间和接受服务的时间都服从泊松过程，由概率知识可知，当随机过程是强度为λ的泊松过程时，其点间间距是相互独立的随机变量，且服从参数为λ的指数分布，即

表1 模拟结果与理论值对比

对比理论计算结果和仿真结果发现，两者非常接近，说明本文提出仿真方法有效可行，我们可以通过增加模拟次数来提高模拟精度.

实例2 某高校工商银行设有三个服务台，营业时间为早上8时到下午16时，新来的顾客到达后，若已有顾客正在接受服务，则需要排队等待.假设顾客流为负指数分布，且顾客到来的平均时间间隔为2.5 min，窗口的服务时间服从U（2，4）分布，求系统队长，顾客的逗留时间和顾客的等待概率.由题可知，为M／G／c／∞模型，其中G～U（2，4），该模型不具有马尔可夫性，用数学推导的方式比较困难的，这时可以用计算机进行模拟，首先产生窗口服务时间U（a，b）的随机数，其密度函数如下：

由逆变换法，有ti＝a＋（b－a）ui，i＝1，2，…，ui～U（0，1）.此题中，a＝2，b＝4，由U（0，1）抽得u，则t＝2＋2u是来自u（2，4）的一个随机数，有了窗口服务时间的随机数，我们就可以根据前面介绍的算法编写Matlab程序，模拟100次，结果如表2.

表2 模拟结果

4 结语

本文用蒙特卡罗的思想，涉及了排队模型的仿真算法，并验证了该算法的有效性，蒙特卡洛模拟法在求解排队系统参数中，有一定的优越性和实用性，并且在其他排队系统的模拟中均有指导意义，由于随机服务系统本身的概率规律性，要用解析的方法来处理一个复杂的随机服务系统有时候比较困难，而模拟自身的特点成为解决这一问题很好的方法.本文介绍的仿真方法具有一定的普遍性，可以运用于商场，银行和医院等系统，如可以针对不同时段的顾客流量和服务水平的变化进行仿真，得到不同状况下商场应该设置多少个收款台，多少个服务员，才能适合变化的顾客流，提高顾客流服务量，实现自身系统的优化，对于指导生产生活有比较重要的现实意义.

［1］张建航，李宗成，宋晓峰.单服务员排队模型及其蒙特卡洛模拟［J］.现代电子技术，2006，29（24）：44-46

［2］李 鹏，王珊珊.用 Matlab实现排队过程的仿真［J］.电脑编程技巧与维护，2009，15：15-17

［3］吴可嘉.蒙特卡洛法在解决食堂窗口排队问题上的应用［J］.大连海事大学学报，2007（33）：149-152

［4］茆诗松，王静龙.高等数理统计［M］.北京：高等教育出版社，2006：401-404

［5］颜薇娜.基于蒙特卡洛模拟的商业银行排队问题研究［J］.技术经济与管理研究，2009（1）：20-22

［6］高静涛.基于 Matlab的排队问题仿真［J］.武汉工业学院学报，2007，26（2）：89-91

Monte Carlo Simulation ofM／G／c／∞ Multi Servers Queuing Model

Wang Peixun Wang Zhifang
（School of Statistics，Xi’an University of Finance and Economics，Xi’an 710100，China）

Based on queuing theory for the theoretical basis，Monte Carlo simulation in Matlab to simulation on the queuing model of multi severs is used，and after analying the model same indicators are got such as mean sojourn time of a served customer，average queue length.The validity of this simulation algorithm is demonstrated and a new method to deal with problems of this category is provided.

queuing model of multi servers；Monte Carlo simulation；queuing theory；dynamic simulation

王映苗】

1672-2027（2012）01-0095-04

TP311.1

A

2011-12-24

王培勋（1956-），男，甘肃岷县人，硕士，西安财经学院统计学院教授，主要从事统计建模研究.