单排队模型的随机模拟

詹晓琳，张 瑜

（上海第二工业大学理学院，上海201209）

单排队模型的随机模拟

詹晓琳，张 瑜

（上海第二工业大学理学院，上海201209）

单服务台的排队模型（M/M/1等待制排队模型）是排队论中简单且重要的排队系统。随机模拟是求解排队系统和分析排队系统非常有效的方法。针对单服务台的排队模型，给出了两种不同随机模拟的方法和必要的数学算法，并进一步比较了两种算法的优劣。

单服务台排队模型；随机模拟；排队系统

0 引言

排队论又称为随机服务系统理论。随机服务系统是指对随机发生的需求提供服务的系统。现实世界中广泛存在着各种各样的随机服务系统，如病人候诊、飞机等待起飞、原材料等待加工、电话等待转接等等。这里将要求得到服务的对象称为“顾客”，将提供服务的服务者称为“服务台”。这里“随机”是指顾客相继到达的时间间隔和服务时间这两个量中至少有一个是随机的。排队系统研究的主要内容是排队系统的运行指标和排队系统的优化问题。随机模拟方法是利用随机数对随机系统的仿真，通常是利用计算机并通过建立数学逻辑模型对现实系统进行仿真，最终实现模拟的目的，又称为计算机模拟方法[1-2]。这是一条解决具有随机因素的复杂实际问题的有效途径。因此，随机模拟是研究排队系统性能、求解排队系统运行指标非常有效的方法。本文针对单服务台等待制的排队模型提供两种不同的模拟思想，并给出相应的具体算法，最终利用Matlab软件实现算法。最后，对两种算法的优劣进行比较。

1 排队系统及主要运行指标

实际的排队系统各有不同，但概括起来都由3个基本部分组成：输入过程，排队及排队规则和服务机制。输入过程是说明顾客按怎样的规律到达系统；排队及排队规则是排队队伍是否有限和服务台对排队顾客进行服务时所遵循的规则；服务机制主要包括服务台的数量及其连接形式（串联或并联）、顾客是单个还是成批接受服务及服务时间的分布。

描述一个排队系统运行状况的主要数量指标有：（1）队长和排队长，队长是指系统中的排队等待的顾客数与正在接受服务的顾客数之和，排队长是指系统中正在排队等待服务的顾客数。（2）等待时间和逗留时间，等待时间是指从顾客达到时刻起到开始接受服务止这段时间，逗留时间是指顾客到达时刻起到他接受服务完成止这段时间。（3）忙期和闲期，忙期是指服务台连续忙碌的时间，闲期是指服务台连续保持空闲的时间。以上6个量均是随机变量，通常排队论中关心的是当系统达到平衡状态时以上6个变量的平均值，相应的符号定义如下：平均队长L，平均排队长Lq，平均等待时间Wq，平均逗留时间W，平均忙期B，平均闲期。

2 M/M/1等待制排队模型的数学特性

本文中研究的单服务台等待制排队模型的定义如下：顾客源无限，顾客单个到达，顾客相继达到的时间间隔服从参数为λ的指数分布；服务台的数量是一个，顾客单个接受服务，服务时间服从参数为µ的指数分布；排队系统容量无限，允许无限排队，排队规则为先到先服务（FCFS）。利用排队论广泛采用的“Kendall记号”，该模型记为M/M/1/∞/∞/FCFS ，根据排队论的约定该模型可以简记为M/M/1。

定义ρ= λ/µ，不难得出ρ是指系统中至少有一个顾客的概率，即服务台处于忙碌状态的概率，因而也称ρ为服务强度或服务利用率。此外，只有在ρ<1的条件下才能使系统达到统计平衡。由概率统计的理论分析可以得到M/M/1系统在平衡状态时的6个重要指标的数学特性如下[3]

这是6个指标的理论值，由理论值的表达式不难看出，他们之间有如下关系：L=λW,Lq=λWq,W=前两个关系称为Little公式，是排队论中一个非常重要的公式。在M/M/1系统的随机模拟中，本文仅关注其中的3个指标：平均排队长Lq, 平均等待时间Wq, 平均忙期B, 以及服务利用率, 期望得到上述4个指标的模拟值。通过模拟值与理论值的误差大小说明模拟的有效性。其余3个运行指标的模拟值可以用类似算法得到。

3 M/M/1等待制排队模型的随机模拟

M/M/1等待制排队模型在现实生活中随处可见，它是一种简单而重要的排队模型，对于该模型的随机模拟的研究可以帮助研究更复杂的多服务台的排队模型的随机模拟。当多服务台的排队系统在输入过程、排队及排队规则或是服务机制中的一方面或多方面比较复杂时，有关它的运行指标的理论值将很难获得，这时，随机模拟成为一种获得近似值的唯一方法。同时，当单服务台排队系统的1ρ<的条件不满足时，系统无法达到平衡，此时6个运行指标的理论值失效，但这些运行指标的实际值可以通过随机模拟近似获得。本文在以下三点假设下，对M/M/1系统在两种不同的模拟思想下提出两种不同的模拟算法对该系统进行了随机模拟。

假设3 时间单位为分钟，一个工作日的服务时间为8小时，即480分钟，服务满480分钟时不再服务下一位顾客，无论是否有顾客排队。

3.1 “下一顾客法”的随机模拟

“下一顾客法”的建模思想是以顾客为主线。首先，随机产生若干位顾客的到达间隔和服务时间；其次，在服务时间内逐个讨论并记录每个顾客的到达时间、离开时间、开始服务时间、等待时间；最后利用这些时间记录，分别设计算法模拟出4个运行指标。在记录时间和模拟运行指标的过程中，都是按照先到先服务的规则，分析好前一个顾客再分析下一个顾客，一个顾客一个顾客地逐一清点，直到服务时间结束。因此，称这种模拟方法为“下一顾客法”。

参数说明：ix为第i个顾客的到达间隔；iy为第i个顾客的服务时间；ia为第i个顾客到达的时刻；ib为第i个顾客服务开始的时刻；iw为第i个顾客等待的时间；il为第i个顾客的离开时刻；iaq为第i个顾客到达时的队长；ilq为第i个顾客离开时的队长。

具体算法如下：

1）首先获得关于4个时间的递推算法

2）其次分别讨论关于4个运行指标的算法

(4) Lq的算法相对复杂

首先，将ai, li, i=1,…,n按时间先后排列起来；

其次，逐一清点第i个顾客到达时的队伍长度, aqi=i−1−前(i−1)人中离开系统的人数；

然后，逐一清点第i个顾客离开时的队伍长度, lqi=max (前一时刻的队长−1, 0)；

3.2 “下一事件法”的随机模拟

“下一事件法”的建模思想是以时间为主线，所以这个算法在实现时为系统设置了一个系统时钟t，这个时钟记录着时刻的变化，并根据改变系统状态的事件的发生依次向前推进，直到服务时间结束。这里的系统状态是指顾客排队长度和服务台是否空闲。在这个系统中，显然“顾客到达”和“顾客离开”这两个事件是改变系统状态的事件。

参数说明：t为当前时钟；tA为有顾客到达的时刻；tD为有顾客离开的时刻；lW为顾客的排队长度；S为服务台的状态（=0S时定义服务台空闲，=1S时定义服务台忙）；x为顾客到达的时间间隔；y为顾客的服务时间。

具体算法如下：

首先，在服务开始时刻，将系统时钟置为t=0，Dt=999（至少大于一个工作日的服务时间480分钟），S=0（系统当前处于空闲状态），Wl=0（当前队列中无人排队）。让系统产生一个到达间隔x和服务时间y,更新At。其次，对系统进行判断，如果当前服务台为空，则直接为顾客提供服务，并产生一个服务时间y, 同时更新顾客离开时刻Dt；若服务台忙，则让顾客排队，因为实施的是等待制。之后继续比较At、Dt大小，并让系统时钟t调至较小的时刻，若是At较小，则按照有顾客到达的情况处理；反之，则按照有顾客离开的情况处理。若At, Dt相等，则同时处理顾客到达事件和顾客离开事件。在处理过程中，一旦出现服务台空闲就需要令Dt=999，这样可以保证系统时钟t在下一刻跳到“顾客到达”时刻。因为在模拟过程中，让t依事件发生的先后顺序，从一个事件的发生跳到下一个事件的发生时刻。所以称这种模拟方法为“下一事件法”。

图1 “下一事件法”算法流程图Fig. 1 “Next event” algorithm flowchart

4 结论

通过Matlab软件编程，分别实现两种算法，并将1 000个工作日的模拟值的平均值作为最终运行指标的模拟值，同时计算1 000个工作日模拟值的均方差。现将两种算法的理论值、模拟值和模拟值的均方差列于表1。

表1 两种算法的结果比较Tab. 1 Comparison of results of the two algorithms

通过模拟值的比较，可以看出“下一顾客法”对于服务利用率和平均忙期的模拟结果较优，“下一顾客法”对于平均排队长度和平均等待时间的模拟结果较优。在建模思想上，“下一顾客法”的建模思想比较简单，“下一事件法”的建模思想比较巧妙。在算法的复杂性方面，“下一顾客法”因为容易记录每一个顾客等待的时间，所以“平均等待时间”的算法相对简单；“下一事件法”因为容易记录顾客到达和顾客离开时的队长，所以关于“平均排队长”的算法相对简单。在算法的可推广方面，利用“下一顾客法”和“下一事件法”的建模思想都可以推广到多服务台的排队模型，且推广后的算法复杂程度基本相当。

[1] 高惠璇. 统计计算[M]. 北京: 北京大学出版社, 1995.

[2] 徐仲济. 蒙特卡洛方法[M]. 上海: 上海科学技术出版社, 1985.

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

[4] 严刚峰, 黄显核, 李思明. 排队过程的仿真研究[J]. 成都信息工程学院学报, 2008, 23(4): 393-400.

[5] 白涛, 曾建潮. 用MATLAB对离散系统进行仿真[J]. 计算机工程与应用, 2000, 36(9): 98-99.

[6] 董臻圃. 数学建模方法与实践[M]. 北京: 国防工业出版社, 2006.

Stochastic Simulation of Single-Server Queuing Model

ZHAN Xiao-lin, ZHANG Yu
( School of Science, Shanghai Second Polytechnic University, Shanghai 201209, P. R. China )

Single-server queuing model (i.e. M/M/1 waiting queuing model) is the simplest and most important queuing system in the queuing theory. Stochastic simulation is a very effective method to analyze and solve queuing problems. Two different stochastic simulation approaches and according algorithms are given to the single-server queuing model. Advantages and disadvantages of these two approaches are also analyzed.

single-server queuing model; stochastic simulation; queuing system

O212

A

1001-4543(2012)04-0302-05

2012-10-15;

2012-12-18

詹晓琳（1978－），女，安徽蚌埠人，副教授，硕士，主要研究方向为概率统计，电子邮箱xlzhan@sf.sspu.cn。