6 排队模型

仿真常用于排队模型（queueing model）的分析。在图 1 所示的那个简单但典型的排队模型中，顾客不时到来并加入排队线（queue，waiting line），最终接受服务，最后离开系统。术语顾客（customer）指的是任何可被视为向系统请求服务的实体。因此，许多服务设施、生产系统、修理与维护设施、通信与计算机系统，以及运输和物料搬运系统都可以被视为排队系统。

排队模型——无论是用数学方法求解，还是通过仿真进行分析——都为分析人员提供了强有力的工具，用以设计和评价排队系统（queueing system）的性能。典型的系统性能度量包括服务台利用率（server utilization，服务台忙碌时间所占的百分比）、排队线的长度，以及顾客的延误（delay）。在设计或试图改进一个排队系统时，分析人员（或决策者）相当经常地需要在服务台利用率与顾客满意度（以队伍长度和延误来衡量）之间进行权衡。排队论与仿真分析被用来把这些系统性能度量预测为输入参数的函数。输入参数包括顾客的到达率、顾客的服务需求、服务台的工作速率，以及服务台的数量与布置方式。在一定程度上，某些输入参数处在管理层的直接控制之下。因此，只要对给定系统而言性能度量与输入参数之间的关系已经有充分的理解，性能度量也就处在他们的间接控制之下。

对于相对简单的系统，这些性能度量可以用数学方法算出——与采用仿真模型相比，这在时间和费用上都节省很多——但是，对于复杂系统的切合实际的模型，通常必须使用仿真。尽管如此，解析上可处理的模型虽然往往需要许多简化假设，但对于粗略估计系统性能仍然很有价值。这些粗略估计随后可借助一个详细而更真实的仿真模型加以细化，同时也提供了一种途径，用以检验仿真模型是否已被正确地编程。简单模型对于建立对排队系统动态行为以及各种性能度量之间关系的理解也很有用。本章不去发展排队的数学理论，而是转而讨论若干众所周知的模型。关于排队论的入门性论述，建议读者参阅 Hillier 与 Lieberman [2005] 或 Winston [2004] 中的综述性章节。更广泛且着眼于应用的论述，由 Cooper [1990]、Gross 与 Harris [1997]、Hall [1991] 以及 Nelson [1995] 给出。后两本著作尤其强调工程与管理方面的应用。

本章讨论排队的一般特征、重要性能度量的含义与相互关系、如何由仿真估计性能的均值度量、改变输入参数所产生的影响，以及少数几个重要且基本的排队模型的数学解。

图 1 简单的排队模型。

1 排队系统的特征

排队系统的关键要素是顾客与服务台。术语"顾客"可以指人、机器、卡车、修理人员、病人、托盘、飞机、电子邮件、箱子、订单或脏衣服——任何到达某一设施并需要服务的东西。术语"服务台"可能指接待员、修理人员、机械师、医务人员、自动存取机器（例如起重机）、机场跑道、自动包装机、订单拣选员、计算机中的 CPU，或者洗衣机——任何提供所请求服务的资源（人、机器等）。尽管本书所用的术语是一位顾客到达一座服务设施，但有时却是服务台移动到顾客那里；例如，修理人员移动到一台出了故障的机器处。这绝不会使模型失效，而仅仅是一个术语上的问题。表 1 列举了若干不同系统，连同由到达的顾客和一个或多个服务台所构成的子系统。本节的其余部分将更详细地描述排队系统的各个组成要素。

表 1 排队系统示例

系统	顾客	服务台
接待处	人	接待员
修理设施	机器	修理人员
汽车修理厂	卡车	机械师
机场安检	旅客	行李 X 光机
医院	病人	护士
仓库	托盘	叉车
机场	飞机	跑道
生产线	箱子	装箱机
仓库	订单	订单拣选员
道路网络	汽车	交通信号灯
杂货店	购物者	收银台
洗衣房	脏衣物	洗衣机/烘干机
作业车间	工件	机器/工人
木材堆场	卡车	高架起重机
锯木厂	原木	锯机
计算机	电子邮件	CPU、磁盘
电话	呼叫	交换机
售票处	足球迷	售票员
公共交通	乘客	公共汽车、列车

1.1 呼叫总体

潜在顾客的总体被称为呼叫总体（calling population），可以假定为有限的或无限的。例如，考虑一家小型公司的员工个人电脑，由三名技术人员组成的 IT 小组提供支持。当某台电脑出现故障、需要新软件等情形时，就由 IT 小组中的一名成员来处理。这些电脑就是顾客，它们在需要关注的那一刻到达。IT 小组成员则是提供服务，即进行修理、软件更新等工作的服务台。这里的呼叫总体是有限的，由公司的这些个人电脑构成。

在潜在顾客数量庞大的系统中，呼叫总体通常被假定为无限的。对此类系统而言，这一假定通常是无害的，而且还可能简化模型。无限总体的例子包括一家餐馆、银行或其他类似服务设施的潜在顾客，也包括一家超大型公司员工的个人电脑。尽管实际的总体可能是有限的但很大，但只要任意时刻正在接受服务或等待服务的顾客人数只占潜在顾客总体的很小比例，使用无限总体模型一般而言就是安全的。

有限总体模型与无限总体模型之间的主要差别在于到达率是如何定义的。在无限总体模型中，到达率（即单位时间内的平均到达数）不受已经离开呼叫总体并加入排队系统的顾客人数的影响。当到达过程在时间上是齐次的（例如没有高峰时段），到达率通常被假定为常数。另一方面，对于有限呼叫总体模型，进入排队系统的到达率确实取决于正在接受服务和正在等待的顾客人数。举一个极端的情形，假定呼叫总体只有一名成员，例如一架公务机。当这架公务机正由一天 24 小时值班的机械师小组进行维修时，到达率为零，因为不存在其他可能到达该服务设施（机械师小组）的潜在顾客（飞机）。一个更典型的例子是分配给一名护士的五名住院病人。当所有病人都在休息且护士空闲时，到达率达到最大，因为下一瞬间任何一名病人都可能呼叫护士请求帮助。而在五名病人都已呼叫过护士的那些时刻（四人在等待护士，一人正在接受服务），到达率为零；也就是说，在护士完成对某位病人的服务之前，不可能有到达发生——此时该病人返回呼叫总体，重新成为一名潜在到达者。当五名病人都在休息时到达率最大，这看起来也许有些奇怪。但到达率的定义是下一单位时间内的期望到达数，因此当所有病人在下一单位时间内都可能呼叫护士时，这一期望值最大。

1.2 系统容量

在许多排队系统中，允许处在排队线或系统中的顾客数量是有限制的。例如，一座自动洗车房可能只允许排 10 辆车等待进入洗车机构。让汽车在街道上排队可能过于危险（或是违法的）。一位到达时发现系统已满的顾客并不进入系统，而是立即返回呼叫总体。有些系统，例如面向学生的演唱会门票现场销售，可被视为具有无限容量，因为对被允许等待购票的学生人数没有任何限制。后面将会看到，当系统容量有限时，需要在到达率（arrival rate，即单位时间内的到达数）与有效到达率（effective arrival rate，即单位时间内到达并进入系统的顾客数）之间作出区分。

1.3 到达过程

对于无限总体模型，到达过程通常用相继顾客的到达间隔时间（interarrival time）来刻画。到达可能发生在预定时刻，也可能发生在随机时刻。当发生在随机时刻时，到达间隔时间通常用一个概率分布来刻画。此外，顾客可能一次到达一位，也可能成批到达。批量可以是固定大小，也可以是随机大小。

随机到达最重要的模型是泊松到达过程（Poisson arrival process）。若 $A_{n}$ 表示顾客 n − 1 与顾客 n 之间的到达间隔时间（ $A_{1}$ 是第一位顾客的实际到达时刻），那么，对于泊松到达过程， $A_{n}$ 服从均值为 $1 / \lambda$ 时间单位的指数分布。到达率为每时间单位 λ 位顾客。在长度为 t 的时间区间内的到达数，记为 $N(t)$ ，服从均值为 λt 位顾客的泊松分布。

泊松到达过程已经被成功地用作以下情形的模型：人们到达餐馆、免下车银行以及其他服务设施；呼叫到达呼叫中心；需求（或对某项服务、某件产品的订单）的到达；失效零部件或机器到达修理设施。典型地，泊松到达过程被用来描述一个庞大的呼叫总体，顾客从中独立地作出关于何时到达的决定。

第二类重要的到达是计划到达（scheduled arrival），例如到达医生办公室的病人，或到达机场的定期航班。在这种情形下，通常更容易对相对计划到达时刻的正、负偏差建模，而不是对到达间隔时间本身建模。

第三种情形是假定队列中至少总有一位顾客在场，因而服务台绝不会因为缺少顾客而空闲。例如，顾客可以代表某种产品的原材料，并且假定总有充足的原材料可供使用。

对于有限总体模型，到达过程以一种完全不同的方式来刻画。当某位顾客处在排队系统之外、并且是潜在呼叫总体的成员时，就把该顾客定义为待服务的（pending）。例如，一位住院病人在休息时是待服务的，而在其呼叫护士的那一刻起就不再是待服务的。把某位给定顾客的运行时间（runtime）定义为：从离开排队系统起、到该顾客下一次到达排队系统为止的这段时间的长度。令 $A_{1} ^ {( i )} , A_{2} ^ {( i )} , . . .$ . 为顾客 i 的相继运行时间；令 $S_{1} ^ {( i )} , S_{2} ^ {( i )} , \ldots$ . 为相应的相继服务时间；令 $W_{Q 1} ^ {( i )} , W_{Q 2} ^ {( i )} , . . .$ . 为每次访问排队系统时相应的、开始服务前的等待时间。于是， $W_{n} ^ {( i )} = W_{O n} ^ {( i )} + S_{n} ^ {( i )}$ 是顾客 i 在第 n 次访问期间在系统中度过的总时间。图 2 针对医院例子中的 3 号病人说明了这些概念。总的到达过程是全体顾客到达时刻的叠加。图 2 显示了 3 号病人的第一次和第二次到达，但这两个时刻未必是系统的两次相继到达。例如，若假定所有病人在时刻 0 都是待服务的，则系统的第一次到达发生在时刻 $A_{1} = \operatorname* {m i n} \{A_{1} ^ {( 1 )} , A_{1} ^ {( 2 )} , A_{1} ^ {( 3 )} , A_{1} ^ {( 4 )} , A_{1} ^ {( 5 )} \} . \mathrm {{\bar {I f}}} {A_{1}} = A_{1} ^ {( 2 )}$ , 那么 2 号病人就是时刻 0 之后的第一个到达者（即第一个呼叫护士的人）。如前面所讨论的，到达率不是常数，而是待服务顾客人数的函数。

有限总体模型的一项重要应用是机器修理问题。机器是顾客，运行时间也称为故障前时间（time to failure）。当一台机器发生故障时，它到达排队系统（修理设施），并在那里停留到它被服务（修好）为止。某一类机器的故障前时间已用指数分布、Weibull 分布和伽马分布加以刻画。具有指数运行时间的模型有时在解析上是可处理的；第 5 节给出了一个例子。相继的故障前时间通常假定在统计上相互独立，但它们也可能依赖于其他因素，例如一台机器自上次大修以来的使用年限。

3 号病人的状态：

图 2 有限总体模型的到达过程。

1.4 排队行为与排队规则

排队行为（queue behavior）指的是顾客在排队等待服务开始期间的行为。在某些情形下，到来的顾客有可能止步（balk，看到队伍太长就离开）、中途退出（renege，在排队过程中看到队伍移动太慢而离开），或者转队（jockey，如果认为自己所排的队伍较慢就从一条队移到另一条队）。

排队规则（queue discipline）指的是队列中顾客的逻辑排序，它决定当某个服务台空闲时将选择哪一位顾客接受服务。常见的排队规则包括先进先出（FIFO）、后进先出（LIFO）、随机顺序服务（SIRO）、最短加工时间优先（SPT），以及按优先级服务（PR）。在制造系统中，排队规则有时基于交货期，以及某一给定类型工件的预计加工时间。注意，FIFO 排队规则意味着服务开始的顺序与到达的顺序相同，但由于服务时间长短不同，顾客离开系统的顺序却可能不同。

1.5 服务时间与服务机构

相继到达者的服务时间记为 $S_{1} , S_{2} , S_{3} , . . .$ 。它们可以是常数，也可以是随机时长。在后一种情形下， $\{S_{1} , S_{2} , S_{3} , \ldots \}$ 通常被刻画为一列独立同分布的随机变量。指数分布、Weibull 分布、伽马分布、对数正态分布和截断正态分布，都已被成功地用作不同情形下服务时间的模型。有时，对某一给定类型、类别或优先级的所有顾客，服务是同分布的，而不同类型的顾客却可能具有完全不同的服务时间分布。此外，在某些系统中，服务时间取决于一天中的时段，或者取决于排队线的长度。例如，当排队线很长时，服务提供者可能工作得比平常更快，从而有效地缩短了服务时间。

一个排队系统由若干服务中心（service center）以及相互连接的队列构成。每个服务中心由若干并行工作的服务台组成，其个数记为 c；也就是说，一旦到达队首，顾客就占用第一个可用的服务台。并行服务机构分为单服务台 $( c = 1 )$ 、多服务台 $( 1 < c < \infty )$ ，或无限服务台（c ）。自助服务设施通常被刻画为具有无限多个服务台。

例 1

考虑一家折扣仓储店，顾客或者自助购物，或者等待三名店员中的一位提供服务，最后在向唯一的收银员付款后离开。该系统由图 3 中的流程图表示。由队列 2 和服务中心 2 构成的子系统在图 4 中给出了更详细的展示。服务机构的其他变型包括批量服务（一个服务台同时为若干位顾客服务），以及一位顾客同时需要若干个服务台。在这家折扣仓储店中，一名店员可能同时拣取若干份小额订单，但搬动一件重物却可能需要两名店员。

图 3 具有三个服务中心的折扣仓储店。

图 4 服务中心 2，其中有 c = 3 个并行服务台。

例 2

某糖果制造商有一条生产线，由三台机器组成，机器之间由在制品库存缓冲区隔开。第一台机器制作并包装单块糖果，第二台机器把 50 块糖装入一个盒子，第三台机器封合并包裹这个盒子。两个库存缓冲区的容量各为 1000 盒。如图 5 所示，该系统被建模为具有三个服务中心，每个中心有 c = 1 个服务台（一台机器），机器之间带有队列容量约束。假定在第一个队列处总有充足的原材料供应。由于存在队列容量约束，机器 1 在其库存缓冲区（队列 2）被装满时停机，而机器 2 在其缓冲区被排空时停机。简而言之，该系统由三个串联的单服务台队列构成，带有队列容量约束，并在第一个队列处有一个连续的到达流。

图 5 糖果生产线。

2 排队记号

鉴于排队系统的多样性，Kendall [1953] 提出了一套用于并行服务台系统的记号体系，并已被广泛采用。这一约定的简化版本基于 $A / B / c / N / K$ 的格式。这些字母代表如下系统特征：

A 表示到达间隔时间的分布。

B 表示服务时间的分布。

c 表示并行服务台的个数。

N 表示系统容量。

K 表示呼叫总体的规模。

A 与 B 的常用符号包括 M（指数分布或马尔可夫的）、D（常数或确定性的）、 $E_{k}$ （k 阶厄兰分布）、PH（相位型）、H（超指数分布）、G（任意分布或一般分布），以及 GI（一般独立分布）。

例如， $M / M / 1 / {\infty} / {\infty}$ 表示一个单服务台系统，它具有无限的排队容量和无限的潜在到达者总体。其到达间隔时间与服务时间均服从指数分布。当 N 与 K 为无穷时，可以从记号中省略。例如， $M / M / 1 / {\infty} / {\infty}$ 常被缩写为 $M / M / 1$ 。照料 5 名住院病人的那位护士可以表示为 $M / M / 1 / 5 / 5$ 。本章其余各处对并行服务台系统所使用的附加记号列于表 2。这些记号的含义可能因系统不同而略有差异。所有系统都将假定采用 FIFO 排队规则。

表 2 并行服务台系统的排队记号

$P_n$	稳态下系统中有 n 位顾客的概率
$P_n(t)$	时刻 t 系统中有 n 位顾客的概率
$\lambda$	到达率
$\lambda_e$	有效到达率
$\mu$	单个服务台的服务率
$\rho$	服务台利用率
$A_n$	顾客 n − 1 与顾客 n 之间的到达间隔时间
$S_n$	第 n 位到达顾客的服务时间
$W_n$	第 n 位到达顾客在系统中度过的总时间
$W_n^Q$	顾客 n 在队列中等待度过的总时间
$L(t)$	时刻 t 系统中的顾客数
$L_Q(t)$	时刻 t 队列中的顾客数
L	系统中顾客的长期按时间平均数
$L_Q$	队列中顾客的长期按时间平均数
w	每位顾客在系统中度过的长期平均时间
$w_Q$	每位顾客在队列中度过的长期平均时间

3 排队系统的长期性能度量

排队系统主要的长期性能度量是：系统中与队列中顾客的长期按时间平均数（L）与（ $L_{Q} )$ 、每位顾客在系统中与队列中度过的长期平均时间（w）与（ $w_{Q} )$ ，以及服务台利用率，即一个服务台忙碌时间所占的比例（ρ）。术语"系统"通常指排队线加上服务机构，但一般而言可以指排队系统的任意子系统；另一方面，术语"队列"仅指排队线本身。其他值得关注的性能度量包括：在队列中被延误超过 $t_{0}$ 时间单位的顾客所占的长期比例、因容量限制而被拒之门外的顾客所占的长期比例，以及排队线中顾客数多于 $k_{0}$ 位的时间所占的长期比例。

本节针对一般的 $G / G / c / N / K$ 排队系统定义主要的各项性能度量，讨论它们之间的相互关系，并说明如何由一次仿真运行来估计它们。估计量有两类：普通样本平均，以及按时间积分（或按时间加权）的样本平均。

3.1 系统中顾客的按时间平均数 L

考虑一个排队系统在一段时间 $T ,$ 上的情形，令 $L ( t )$ 表示时刻 t 系统中的顾客数。图 6 给出了这样一个系统的一次仿真。令 $T_{i}$ 表示在 [0, T] 期间系统内恰有 i 位顾客的总时间。

图 6 时刻 t 系统中的顾客数 $L ( t )$ 。

由图 $^ {6 ,}$ 可见， $T_{0} = 3 , T_{1} = 12 , T_{2} = 4$ , 以及 $T_{3} = 1$ 。（那些长度合计为 $T_{1} = 12$ 的线段在图 6 中被标注为 $" T_{1} "$ ，等等。）一般地， $\textstyle \sum_{i = 0} ^ {\infty} T_{i} = T$ 。系统中按时间加权平均的顾客数定义为

\widehat {L} = \frac {1}{T} \sum_{i = 0} ^ {\infty} i T_{i} = \sum_{i = 0} ^ {\infty} i \left(\frac {T_{i}}{T}\right)\tag{1}

对于图 $6 , \widehat {L} = [ 0 ( 3 ) + 1 ( 12 ) + 2 ( 4 ) + 3 ( 1 ) ] / 20 = 23 / 20 = 1 . 15$ 位顾客。注意， $T_{i} / T$ 正是系统内恰有 i 位顾客的时间所占的比例。估计量 $\widehat {L}$ 是时间加权平均的一个例子。

通过考察图 $^ {6 ,}$ 可以看出，函数 $L ( t )$ 下方的总面积可以分解成若干个高为 i、长为 $T_{i}$ 的矩形。例如，面积为 $3 \times T_{3}$ 的那个矩形，其底边从 $t = 7 \mathrm{t o} t = 8$ （因此 $T_{3} = 1 ) ;$ 然而，多数矩形被拆成了若干段，例如面积为 $2 \times T_{2}$ 的那个矩形，其底边的一段位于 $t = 5$ 与 $t = 7$ 之间，其余部分位于 $t = 8$ 与 $t = 10$ 之间（因此 $T_{2} = 2 + 2 = 4 )$ 。由此可知，总面积由 $\textstyle \sum_{i = 0} ^ {\infty} i T_{i} = \int_{0} ^ {T} L ( t ) d t$ 给出，从而

\widehat {L} = \frac {1}{T} \sum_{i = 0} ^ {\infty} i T_{i} = \frac {1}{T} \int_{0} ^ {T} L (t) d t\tag{2}

式 (1) 与式 (2) 中的这两个表达式对任意排队系统恒等成立，而与服务台个数、排队规则或任何其他特殊情况无关。式 (2) 也印证了"按时间积分平均"这一术语。

许多排队系统就其平均性能而言表现出某种长期稳定性。对此类系统，随着时间 $T$ 增大，所观测到的系统中按时间平均的顾客数 $\widehat {L}$ 趋近于一个极限值，记为 $L ,$ 称之为系统中顾客的长期按时间平均数——即，以概率 1，

\widehat {L} = \frac {1}{T} \int_{0} ^ {T} L (t) d t \longrightarrow L \text{as} T \longrightarrow \infty\tag{3}

估计量 $\widehat {L}$ 被称为对 L 强相合的（strongly consistent）。若仿真运行长度 T 足够长，估计量 $\widehat {L}$ 就会任意地接近 L。遗憾的是，当 $T < \infty$ 时， $\widehat {L}$ 依赖于时刻 0 的初始条件。

式 (2) 与式 (3) 既可应用于整个排队系统，也可应用于排队系统的任意子系统。若 $L_{Q} ( t )$ 表示队列中等待的顾客数， $T_{i} ^ {Q}$ 表示在 $[ 0 , T ]$ 期间恰有 i 位顾客在队列中等待的总时间，则

\widehat {L} _ {Q} = \frac {1}{T} \sum_{i = 0} ^ {\infty} i T_{i} ^ {Q} = \frac {1}{T} \int_{0} ^ {T} L_{Q} (t) d t \longrightarrow L_{Q} \text{as} T \longrightarrow \infty\tag{4}

其中 $\widehat {L} _ {Q}$ 是从时刻 0 到时刻 T 期间所观测到的按时间平均的队列中等待顾客数，而 $L_{Q}$ 是队列中等待顾客的长期按时间平均数。

例 3

假定图 6 表示一个单服务台队列——即一个 $G / G / 1 / N / K$ 排队系统 $( N \geq 3 , K \geq 3 )$ 。那么队列中等待的顾客数由 $L_{Q} ( t )$ 给出，定义为

L_{Q} (t) = \left\{\begin{array}{l l} 0 & \text{if L(t) = 0} \\ L (t) - 1 & \text{if }L(t)\geq 1 \end{array} \right.

并如图 7 所示。因此， $T_{0} ^ {Q} = 5 + 10 = 15 , T_{1} ^ {Q} = 2 + 2 = 4 ,$ , 且 $T_{2} ^ {Q} = 1$ 。于是，

\widehat {L} _ {Q} = \frac {0 (15) + 1 (4) + 2 (1)}{20} = 0. 3 \text{customers}

3.2 平均每位顾客在系统中度过的时间 w

如果把某个排队系统仿真一段时间，比如说 T，那么我们可以记录在 [0, T] 期间每位顾客在系统中度过的时间，记为 $W_{1} , W_{2} , \ldots , W_{N}$ ，其中 N 是 [0, T] 期间的到达数。平均每位顾客在系统中度过的时间称为平均系统时间（average system time），由普通样本平均给出

\widehat {w} = \frac {1}{N} \sum_{i = 1} ^ {N} W_{i}\tag{5}

对于稳定系统，当 $N \longrightarrow \infty$ 时

\widehat {w} \longrightarrow w\tag{6}

以概率 1 成立，其中 w 称为长期平均系统时间（long-run average system time）。

图 7 时刻 t 队列中等待的顾客数 $L_{Q} ( t )$ 。

若所考虑的系统只是队列本身，则式 (5) 与式 (6) 写作

\widehat {w} _ {Q} = \frac {1}{N} \sum_{i = 1} ^ {N} W_{i} ^ {Q} \longrightarrow w_{Q} \mathrm{as} N \longrightarrow \infty\tag{7}

其中 ${W} _ {i} ^ {Q}$ 是顾客 i 在队列中等待的总时间， $\widehat {w} _ {Q}$ 是所观测到的平均在队列中等待的时间（称为延误，delay），而 $w_{Q}$ 是长期平均的每位顾客延误。与 $\widehat {L} .$ 类似，估计量 $\widehat {w}$ 与 $\widehat {w} _ {Q}$ 也受到时刻 0 的初始条件以及运行长度 T 的影响。

例 4

对于图 6 所示的系统历史， $N = 5$ 位顾客到达， $W_{1} = 2$ ，且 $W_{5} = 20 - 16 = 4 .$ 但除非对系统了解更多，否则无法算出 $W_{2} , W_{3}$ 与 $W_{4}$ 。假定系统有一个服务台并采用 FIFO 排队规则。这意味着顾客离开系统的顺序与到达的顺序相同。图 6 中 $L ( t )$ 的每一次向上跳跃代表一次到达。到达发生在时刻 0、3、5、7 和 16。类似地，离开发生在时刻 2、8、10 和 14。（在时刻 20 可能发生过、也可能没有发生过一次离开。）在这些假定下，显然有 $W_{2} = 8 - 3 = 5 , W_{3} = 10 - 5 = 5 , W_{4} = 14 - 7 = 7$ ，因此

\widehat {w} = \frac {2 + 5 + 5 + 7 + 4}{5} = \frac {23}{5} = 4. 6 \text{time units}

于是，平均而言，这些顾客在系统中度过了 4.6 个时间单位。至于在排队线中度过的时间，可以算出 $W_{1} ^ {Q} = 0 , W_{2} ^ {Q} = 0 , W_{3} ^ {Q} = 8 - 5 = 3 , W_{4} ^ {Q} = 10 - 7 = 3$ , 以及 ${\cal W} _ {5} ^ {Q} = 0 ;$ 于是，

\widehat {w} _ {Q} = \frac {0 + 0 + 3 + 3 + 0}{5} = 1. 2 \mathrm{timeunits}

3.3 守恒方程：±b L = λ ±b w

对于图 6 所展示的系统，在 $T = 20$ 个时间单位内有 $N = 5$ 次到达，因此所观测到的到达率为 $\widehat {\lambda} = \bar {N} / T = 1 / 4$ 位顾客每时间单位。回顾 $\widehat {L} = 1 . 15$ 且 $\widehat {w} = 4 . 6 ;$ 因此可得

\widehat {L} = \widehat {\lambda} \widehat {w}\tag{8}

$L , \lambda .$ 与 w 之间的这一关系并非巧合；它对几乎所有排队系统或子系统都成立，而与服务台个数、排队规则或任何其他特殊情况无关。令 $T \longrightarrow \infty$ 且 $N \longrightarrow \infty$ ，式 (8) 变为

L = \lambda w\tag{9}

其中 $\widehat {\lambda} \longrightarrow \lambda$ ，而 λ 是长期平均到达率。式 (9) 称为守恒方程（conservation equation），通常归功于 Little [1961]。它表明：在任意时刻系统中顾客的平均数，等于每时间单位的平均到达数乘以平均在系统中度过的时间。对于图 6，平均每 4 个时间单位有一次到达，且每次到达平均在系统中度过 4.6 个时间单位，因此在任意时刻平均会有 $( 1 / 4 ) ( 4 . 6 ) = 1 . 15$ 位顾客在场。

式 (8) 也可以按如下方式重新考察图 6 而导出：图 8 给出的系统历史 $L ( t )$ 与图 6 完全一样，其中每位顾客在系统中的时间 $W_{i}$ 用一个矩形来表示。这一表示同样假定是单服务台、FIFO 排队规则的系统。第三位与第四位顾客的矩形分别被分成了两段和三段。对每个 $i = 1 , 2 , \dots , N$ ，第 i 个矩形的高为 1、长为 $W_{i}$ 。由此可知，全体顾客的系统时间总和由"系统中顾客数"函数 L(t) 下方的总面积给出，即

\sum_{i = 1} ^ {N} W_{i} = \int_{0} ^ {T} L (t) d t\tag{10}

因此，把式 (2) 与式 (5) 相结合，并代入 $\widehat {\lambda} = N / T$ ，可得

\widehat {L} = \frac {1}{T} \int_{0} ^ {T} L (t) d t = \frac {N}{T} \frac {1}{N} \sum_{i = 1} ^ {N} W_{i} = \widehat {\lambda} \widehat {w}

这就是 Little 的式 (8)。此处给出的直观而非形式化的推导依赖于单服务台 FIFO 的假定，但这些假定并非必要。事实上，作为推导关键的式 (10) 在极大的范围内（至少近似地）成立，因此式 (8) 与式 (9) 同样如此。习题 14 与习题 15 要求读者在不同假定下推导式 (10) 与式 (8)。

图 8 单服务台 FIFO 系统的系统时间 $W_{i}$ 。

技术性说明：若 $W_{i}$ 是顾客 i 在 [0, T] 期间的系统时间，则式 (10) 从而式 (8) 精确成立。有些作者选择把 $W_{i}$ 定义为顾客 i 的总系统时间；这一改动只会影响那些在时刻 T 之前到达、却直到时刻 T 之后才离开的顾客 i（图 8 中的第 5 位顾客可能就是如此）的 $W_{i}$ 值。作了这一定义上的改变之后，式 (10) 与式 (8) 只近似成立。尽管如此，随着 $T \longrightarrow \infty \mathrm{a n d} N \longrightarrow \infty .$ ，式 (8) 中的误差趋于零，因此针对长期性能度量的守恒方程 (9)——即 $L = \lambda w$ ——仍然精确成立。

3.4 服务台利用率

服务台利用率（server utilization）定义为一个服务台忙碌时间所占的比例。所观测到的服务台利用率记为 ${\widehat {\rho}} ,$ 是在一个指定的时间区间 [0, T] 上定义的。长期服务台利用率记为 $\rho .$ 对于表现出长期稳定性的系统，

\widehat {\rho} \longrightarrow \rho \text{as} T \longrightarrow \infty

例 5

由图 6 或图 8，并假定系统有一个服务台，可以看出服务台利用率为 $\widehat {\rho} =$ （总忙碌时间） $\textstyle / T = ( \sum_{i = 1} ^ {\infty} T_{i} ) / T = ( T - T_{0} ) / T = 17 / 20$

G/G/1/∞/∞ 队列中的服务台利用率

考虑任意一个单服务台排队系统，其平均到达率为每时间单位 λ 位顾客，平均服务时间为 $E ( S ) = 1 / \mu$ 个时间单位，且排队容量与呼叫总体均无限。注意， $E ( S ) = 1 / \mu$ 意味着：当服务台忙碌时，它平均以每时间单位 $\mu$ 位顾客的速率工作； $\mu$ 称为服务率。服务台自身是一个子系统，可以被当作一个排队系统来看待；因此，守恒方程 (9) $L = \lambda w$ 可以应用于该服务台。对于稳定系统，到达服务台的平均到达率，记为 $\lambda_{s} .$ ，必须与到达系统的平均到达率 λ 相同（当然 $\lambda_{s} \le \lambda$ ——顾客被服务的速度不可能快于他们到达的速度——但是，若 $\lambda_{s} ~ < ~ \lambda .$ ，则排队线的长度将趋于以每时间单位 $\lambda - \lambda_{s}$ 位顾客的平均速率增长，于是我们将得到一个不稳定系统）。对于服务台子系统，平均系统时间为 $w = E ( S ) = \mu^{- 1}$ 。服务台子系统中的实际顾客数为 0 或 1，如图 9 所示（针对图 6 所代表的系统）。因此，服务台子系统中的平均顾客数 $\widehat {L} _ {s} .$ 由下式给出

\widehat {L} _ {s} = \frac {1}{T} \int_{0} ^ {T} (L (t) - L_{Q} (t)) d t = \frac {T - T_{0}}{T}

在此情形下， $\widehat {L} _ {s} = 17 / 20 = \widehat {\rho} .$ 一般地，对于一个单服务台队列，在任意时刻正在接受服务的平均顾客数等于服务台利用率。当 $T \longrightarrow \infty$ 时， ${\widehat {L}} _ {s} =$ $\widehat {\rho} \longrightarrow L_{s} = \rho$ 。把这些结果代入服务台子系统的 $L = \lambda w$ ，得到

\rho = \lambda E (S) = \frac {\lambda}{\mu}\tag{11}

图 9 时刻 t 正在接受服务的顾客数 $L ( t ) - L_{Q} ( t )$ 。

也就是说，单服务台队列中的长期服务台利用率等于平均到达率除以平均服务率。要使一个单服务台队列稳定，到达率 λ 必须小于服务率 $\mu {:}$

\lambda < \mu

或

\rho = \frac {\lambda}{\mu} < 1\tag{12}

如果到达率大于服务率 $( \lambda > \mu )$ ，服务台最终将落后得越来越远。过一段时间之后，服务台将始终处于忙碌状态，且排队线的长度将趋于以每时间单位 $( \lambda - \mu )$ 位顾客的平均速率增长，因为离开将以每时间单位 $\mu$ 的速率发生。对于稳定的单服务台系统 $( \lambda < \mu \mathrm{o r} \rho < 1 )$ ，诸如平均队长 $L_{Q}$ （以及 $L , w ,$ , 和 $w_{Q} )$ 这类长期性能度量有良好定义且具有意义。对于不稳定系统 $( \lambda > \mu )$ ，长期服务台利用率为 1，而长期平均队长为无穷大；即

\frac {1}{T} \int_{0} ^ {T} L_{Q} (t) d t \longrightarrow + \infty \text{as} T \longrightarrow \infty

类似地， $L = w = w_{Q} = \infty$ 。因此，这些长期性能度量对于不稳定队列是没有意义的。量 $\lambda / \mu$ 也称为提供负载（offered load），它是对施加于系统之上的工作负载的一种度量。

G/G/c/∞/∞ 队列中的服务台利用率

考虑一个有 c 个相同服务台并行工作的排队系统。如果一位到达的顾客发现不止一个服务台空闲，那么该顾客在选择服务台时并不偏向任何一个特定的服务台。（例如，服务台的选择可以随机作出。）到达以速率 λ 从一个无限呼叫总体发生，且每个服务台以每时间单位 $\mu$ 位顾客的速率工作。由式 (9) $L = \lambda w$ 单独应用于服务台子系统，通过与单服务台情形类似的论证可得如下结果：对于处于统计平衡的系统，平均忙碌服务台数（记为 $L_{s} .$ ）由下式给出

L_{s} = \lambda E (S) = \frac {\lambda}{\mu}\tag{13}

显然， $0 \leq L_{s} \leq c .$ 。长期平均服务台利用率定义为

\rho = \frac {L_{s}}{c} = \frac {\lambda}{c \mu}\tag{14}

因而 $0 \leq \rho \leq 1$ 。利用率 $\rho$ 可以解释为：从长期看，任意一个服务台忙碌时间所占的比例。

$G / G / c / {\infty} / {\infty}$ 系统的最大服务率为 $c \mu$ ，它出现在所有服务台都忙碌之时。为使系统稳定，平均到达率 λ 必须小于最大服务率 $c \mu ;$ 也就是说，系统稳定当且仅当

\lambda < c \mu\tag{15}

或等价地说，当且仅当提供负载 $\lambda / \mu$ 小于服务台个数 c。若 $\operatorname{I f} \lambda > c \mu$ ，则到达平均而言发生得比系统能够处理的更快，所有服务台将持续忙碌，且排队线的长度将以每时间单位 $( \lambda - c \mu )$ 位顾客的平均速率增长。这样的系统是不稳定的，长期性能度量 $( L , L_{Q} , w$ , 以及 $w_{Q} )$ 对于这类系统同样没有意义。

注意，条件 (15) 推广了条件 (12)，而稳定系统利用率的公式——式 (14)——则推广了式 (11)。

当某些服务台比其他服务台工作得更多时，式 (13) 与式 (14) 也同样适用；例如，当顾客偏向某一个服务台而不选其他服务台时，或者当某些服务台仅在其他所有服务台都忙碌时才服务顾客时。在这种情形下，由式 (13) 给出的 $L_{s}$ 仍然是平均忙碌服务台数，但由式 (14) 给出的 $\rho$ 却不能应用于单个服务台。此时， $\rho$ 必须解释为所有服务台的平均利用率。

例 6

顾客以 $\lambda = 50$ 位顾客每小时的速率随机到达一个执照办理处。目前有 20 名办事员，每人平均服务 $\mu = 5$ 位顾客每小时。因此，由式 (14) 给出的、一名服务台的长期（或稳态）平均利用率为

\rho = \frac {\lambda}{c \mu} = \frac {50}{20 (5)} = 0. 5

而平均忙碌服务台数为

L_{s} = \frac {\lambda}{\mu} = \frac {50}{5} = 10

因此，从长期看，一名典型办事员只有 50% 的时间在忙着服务顾客。办公室主任问是否可以减少服务台数量。由式 (15) 可知，为使系统稳定，服务台个数必须满足

c > \frac {\lambda}{\mu}

或 $c > 50 / 5 = 10$ 。因此，可供这位主任考虑的方案包括 $c = 11 , \mathrm{o r} c = 12 .$ 或 $c = 13 , \ldots$ 。注意， $c \geq 11$ 只是在这样的意义上保证长期稳定：当所有服务台都忙碌时，它们平均能够处理到来的工作负载 $( \mathrm{i} . \mathrm{e} . , c \mu > \lambda )$ 。由于顾客延误、排队线长度等其他因素，这位办公室主任很可能希望服务台数多于最少的服务台数 $( c = 11 )$ 。一个稳定的队列平均而言仍然可能有很长的队伍。

图 10 确定性队列 $( D / D / 1 )$

服务台利用率与系统性能

正如此处以及后面几节将要说明的，对于给定的利用率 $\rho .$ ，系统性能可能差异极大。考虑一个 $G / G / 1 / {\infty} / {\infty}$ 队列，即一个到达率为 $\lambda$ 、服务率为 $\mu ,$ 、利用率为 $\rho = \lambda / \mu < 1$ 的单服务台队列。考察一个极端情形： $D / D / 1$ 队列，它具有确定性的到达时间与服务时间。于是所有到达间隔时间 $\left\{A_{1} , A_{2} , \ldots \right\}$ 都等于 $E ( A ) = 1 / \lambda$ ，而所有服务时间 $\{S_{1} , S_{2} , \ldots \}$ 都等于 $E ( S ) = 1 / \mu$ 。假定一位顾客在时刻 0 到达了一个空系统，则系统以一种完全确定的、可预测的方式演化，如图 10 所示。可以看到 $L = \rho = \lambda / \mu , w = E ( S ) = \mu^{- 1}$ , 且 $L _ {\mathcal {Q}} = w _ {\mathcal {Q}} = 0$ 。通过改变 $\lambda$ 与 $\mu ,$ ，服务台利用率可以取 0 与 1 之间的任意值，然而却从不出现任何队伍。那么，如果不是高的服务台利用率，究竟是什么导致队伍形成呢？一般而言，正是到达间隔时间与服务时间的变异性（variability）导致队伍长度发生波动。

例 7

考虑一位医生，他每隔 10 分钟预约一位病人，并与第 i 位病人相处 $S_{i}$ 分钟，其中

S_{i} = \left\{\begin{array}{l l} 9 \text{minutes with probability} 0. 9 \\ 12 \text{minutes with probability} 0. 1 \end{array} \right.

因此，到达是确定性的 $( A_{1} = A_{2} = \cdot \cdot \cdot = \lambda^{- 1} = 10 )$ ，但服务是随机的（或概率性的），其均值与方差由下式给出

E (S_{i}) = 9 (0. 9) + 12 (0. 1) = 9. 3 \mathrm{minutes}

图 11 时刻 t 医生办公室中的病人数。

以及

\begin{array}{r l} V (S_{i}) & = E (S_{i} ^ {2}) - [ E (S_{i}) ] ^ {2} \\ & = 9^{2} (0. 9) + 12^{2} (0. 1) - (9. 3) ^ {2} \\ & = 0. 81 \text{minutes} ^ {2} \end{array}

此处， $\rho = \lambda / \mu = E ( S ) / E ( A ) = 9 . 3 / 10 = 0 . 93 < 1$ ，系统是稳定的，且这位医生从长期看将有 93% 的时间处于忙碌状态。在短期内，只要病人只需要 9 分钟的服务，队伍就不会形成；但由于服务时间的变异性，有 10% 的病人将需要 12 分钟，这转而又会造成一条临时队伍的形成。

假定对该系统进行仿真，服务时间为 $S_{1} = 9 , S_{2} = 12 , S_{3} = 9 , S_{4} = 9 , S_{5} =$ 9, . . . . 。假定在时刻 0 一位病人到达并发现医生空闲，其后的病人精确地在时刻 10、20、30, . . . 到达，则系统按图 11 所示的方式演化。队列中的延误为 $W_{1} ^ {Q} = W_{2} ^ {Q} = 0 , W_{3} ^ {Q} = 22 - 20 = 2 , W_{4} ^ {Q} = 31 - 30 = 1 , W_{5} ^ {Q} = 0$ 。一个相对较长的服务时间（此处为 $S_{2} = 12 )$ 的出现导致了一条排队线临时形成。一般而言，由于到达间隔分布与服务分布的变异性，相对较小的到达间隔时间与相对较大的服务时间偶尔确实会出现，这些转而导致队伍变长。反之，一次大的到达间隔时间或一次小的服务时间的出现，则倾向于缩短一条已经存在的排队线。利用率、服务与到达间隔的变异性以及系统性能之间的关系，将在第 4 节中作更详细的探讨。

3.5 排队问题中的成本

在许多排队情形中，成本可以与排队线或服务台的各个方面相联系。假定系统为队列中的每位顾客承担成本，比如说按每位顾客每小时 10 美元的费率计。如果顾客 j 在队列中度过 $W_{i} ^ {\boldsymbol {Q}}$ 小时，那么 $\begin{array} {r} {\dot {\sum} _ {j = 1} ^ {N} ( \mathbb {S} 1 \dot {0} \cdot W_{j} ^ {Q} )} \end{array}$ 就是在仿真期间到达的 N 位顾客的总成本。于是，平均每位顾客的成本为

\sum_{j = 1} ^ {N} \frac {\mathbb {S} 10 \cdot W_{j} ^ {Q}}{N} = \mathbb {S} 10 \cdot \widehat {w} _ {Q}

这里用到了式 (7)。若平均每小时有 $\widehat {\lambda}$ 位顾客到达，则平均每小时的成本为

\left(\widehat {\lambda} \frac {\text{customers}}{\text{hour}}\right) \left(\frac {10 \cdot \widehat {w} _ {Q}}{\text{customer}}\right) = 10 \cdot \widehat {\lambda} \widehat {w} _ {Q} = 10 \cdot \widehat {L} _ {Q} / \text{hour}

最后一个等式由式 (8) 得到。推导平均每小时成本的另一种途径是考虑式 (2)。若 $\dot {T} _ {i} ^ {\dot {Q}}$ 是在区间 [0, T] 上系统内恰有 i 位顾客的总时间，则 $10 $i T_{i} ^ {Q}$ 就是系统在恰有 i 位顾客在场的那段时间内所发生的成本。因此，总成本为 $\scriptstyle \sum_{i = 1} ^ {\infty} ( \mathbb {S} 10 \cdot i T_{i} ^ {Q} )$ ，而平均每小时的成本为

\sum_{i = 1} ^ {\infty} \frac {10 \cdot i T_{i} ^ {Q}}{T} = 10 \cdot \widehat {L} _ {Q} / \text{hour}

这里用到了式 (2)。在这些成本表达式中， $\widehat {L} _ {Q}$ 可以由 $L_{Q}$ 代替（若已知队列中顾客的长期数），或者由 L 或 $\widehat {L}$ 代替（若顾客在受到延误之外，其在接受服务期间也会发生成本）。

服务台也可能给系统带来成本。若一组 c 个并行服务台 $( 1 \leq c < \infty )$ 的利用率为 $\rho ,$ 且每个服务台在忙碌时每小时带来 5 美元的成本，则每小时的总服务台成本为

\$5 \cdot c \rho

因为 $c \rho$ 是平均忙碌服务台数。若服务台成本只在服务台空闲时才发生，则每小时的服务台成本为

\$5 \cdot c (1 - \rho)

因为 $c ( 1 - \rho ) = c - c \rho$ 是平均空闲服务台数。在许多问题中，会把这些不同成本中的两项或更多项合并成一个总成本。习题 1、 $8 , 12 ,$ , 和 19 说明了这类问题。在大多数情形下，目标是通过改变那些处在管理层控制之下的参数——例如服务台个数、到达率、服务率和系统容量——来使总成本最小（在给定某些约束的条件之下）。

4 无限总体马尔可夫模型的稳态行为

本节给出若干可用数学方法求解的排队模型的稳态结果。对于无限总体模型，假定到达服从速率为每时间单位 λ 次到达的泊松过程——即，假定到达间隔时间服从均值为 $1 / \lambda$ 的指数分布。服务时间可以是指数分布的（M）或任意分布的（G）。排队规则将是 FIFO。由于对到达过程所作的指数分布假定，这些模型被称为马尔可夫模型（Markovian model）。

如果一个排队系统处在某一给定状态的概率不随时间变化，即

P (L (t) = n) = P_{n} (t) = P_{n}

与时间 t 无关，则称该系统处于统计平衡（statistical equilibrium）或稳态（steady state）。两条性质——从任意起始状态趋近于统计平衡，以及一旦达到统计平衡便保持在其中——是许多随机模型的特征，尤其是下面各小节所研究的所有系统的特征。另一方面，如果一位分析人员关心的是一个队列在相对较短时期内的暂态（transient）行为，并且被给定了某些特定的初始条件（例如空闲且为空），那么这里将要给出的结果就不合适了。此时，一次暂态的数学分析，或者更有可能地，一个仿真模型，将是被选用的分析工具。

下面各小节给出其解的那些数学模型，即使在该模型的假定并不严格成立时，也可用来获得近似结果。这些结果可以被看作是对系统行为的一种粗略指引。随后便可以用仿真进行更精细的分析。然而应当记住：数学分析（当它适用时）给出的是模型参数的真值（例如 L），而仿真分析给出的则是该参数的一个统计估计值 $( \mathrm{e . g . ,} \ \widehat {L} )$ 。另一方面，对于复杂系统，仿真模型往往比数学模型是更为忠实的表示。

对于此处研究的这些简单模型，稳态参数 L（系统中顾客数的按时间平均数）可以按下式计算：

L = \sum_{n = 0} ^ {\infty} n P_{n}\tag{16}

其中 $\{P_{n} \}$ 是发现系统中有 n 位顾客的稳态概率（如表 2 中所定义）。正如第 3 节所讨论并由式 (3) 所表达的那样，L 也可以被解释为系统的一种长期性能度量。一旦给定 L，其他的稳态参数便可以方便地由 Little 方程 (9)——分别应用于整个系统和单独应用于队列——算出：

\begin{array}{c} w = \frac {L}{\lambda} \\ w_{Q} = w - \frac {1}{\mu} \\ L_{Q} = \lambda w_{Q} \end{array}\tag{17}

其中 λ 是到达率，μ 是每个服务台的服务率。

对于本节所考察的 $M / G / c / {\infty} / {\infty}$ 队列而言，要存在统计平衡，一个必要且充分的条件是 $\lambda / ( c \mu ) < 1$ ，其中 λ 是到达率， $\mu$ 是单个服务台的服务率，c 是并行服务台的个数。对于这些容量无限、呼叫总体无限的模型，假定理论上的服务台利用率 $\rho = \lambda / ( c \mu )$ 满足 $\rho < 1$ 。对于系统容量有限或呼叫总体有限的模型，量 $\lambda / ( c \mu )$ 可以取任意正值。

4.1 具有泊松到达与无限容量的单服务台队列：M/G/1

假定服务时间的均值为 $1 / \mu$ 、方差为 $\sigma^{2}$ ，并且只有一个服务台。若 $\rho = \lambda / \mu <$ 1，则 $M / G / 1$ 队列具有稳态概率分布，其稳态特征如表 3 所示。一般地，稳态概率 $P_{0} , P_{1} , P_{2} , \dots .$ 没有简单的表达式。当 $\lambda < \mu .$ ，量 $\rho = \lambda / \mu$ 就是服务台利用率，或者说服务台忙碌时间的长期比例。由表 $3 , 1 - P_{0} = \rho$ 也可以看出，它还能解释为系统中含有一位或多位顾客的稳态概率。还要注意， $L - L_{Q} = \rho$ 是正在接受服务的顾客的按时间平均数。

表 3 $M / G / 1$ 队列的稳态参数

\begin{array}{l l} \hline \rho & \frac {\lambda}{\mu} \\ L & \rho + \frac {\lambda^{2} (1 / \mu^{2} + \sigma^{2})}{2 (1 - \rho)} = \rho + \frac {\rho^{2} (1 + \sigma^{2} \mu^{2})}{2 (1 - \rho)} \\ w & \frac {1}{\mu} + \frac {\lambda (1 / \mu^{2} + \sigma^{2})}{2 (1 - \rho)} \\ w_{Q} & \frac {\lambda (1 / \mu^{2} + \sigma^{2})}{2 (1 - \rho)} \\ L_{Q} & \frac {\lambda^{2} (1 / \mu^{2} + \sigma^{2})}{2 (1 - \rho)} = \frac {\rho^{2} (1 + \sigma^{2} \mu^{2})}{2 (1 - \rho)} \\ P_{0} & 1 - \rho \\ \hline \end{array}

例 8

顾客到达一家免预约的修鞋店，看上去是随机的。假定到达按速率 $\lambda = 1 . 5$ 每小时的泊松过程发生。经过几个月的观察发现，唯一一位工人的修鞋时间平均为 30 分钟，标准差为 20 分钟。因此平均服务时间 $1 / \mu = 1 / 2$ 小时，服务率为每小时 $\mu = 2$ ，且 $\sigma^{2} = ( 20 ) ^ {2}$ minutes^2 1/9 hour^2。这里的"顾客"是需要修鞋的人，而恰当的模型是 $M / G / 1$ 队列，因为只知道服务时间的均值与方差，并不知道它们的分布。这位工人忙碌的时间比例为 $\rho = \lambda / \mu = 1 . 5 / 2 = 0 . 75$ ，并且由表 3，店内顾客的稳态按时间平均数为

\begin{array}{r l} L & = 0. 75 + \frac {(1 . 5) ^ {2} [ (0 . 5) ^ {2} + 1 / 9 ]}{2 (1 - 0 . 75)} \\ & = 0. 75 + 1. 625 = 2. 375 \text{customers} \end{array}

因此，一位在任意时刻记录该修鞋系统状态的观察者会发现平均有 2.375 位顾客（从长期看）。

更仔细地考察表 3 中的公式，可以揭示 $M / G / 1$ 队列中排队线与延误的来源。例如， $L_{Q}$ 可以改写为

L_{Q} = \frac {\rho^{2}}{2 (1 - \rho)} + \frac {\lambda^{2} \sigma^{2}}{2 (1 - \rho)}

第一项只涉及平均到达率 λ 与平均服务率 $\mu$ 之比。正如第二项所示，若 λ 与 $\mu$ 保持不变，则排队线的平均长度 $( L_{Q} )$ 取决于服务时间的变异性 $\sigma^{2}$ 。如果两个系统具有相同的平均服务时间与平均到达间隔时间，那么，服务时间变异性更大（ $\sigma^{2}$ 更大）的那个系统，平均而言往往会有更长的队伍。直观地看，如果服务时间高度可变，那么出现一次很大的服务时间（比如说远大于平均服务时间）的概率就很高，而当大的服务时间确实发生时，队伍形成以及顾客延误增加的倾向就高于平常。（读者不应把"稳态"与低变异性或短队伍混为一谈；一个处于稳态或统计平衡的系统，可能高度可变，也可能有很长的排队线。）

例 9

有两位工人竞争一份工作。Able 声称自己的平均服务时间比 Baker 的更快，但 Baker 声称自己更加稳定，尽管没有那么快。到达按速率 $\lambda = 2$ 每小时（每分钟 1/30）的泊松过程发生。Able 的服务统计量是：平均服务时间 24 分钟，标准差 20 分钟。Baker 的服务统计量是：平均服务时间 25 分钟，但标准差只有 2 分钟。如果以队列的平均长度作为录用标准，应当录用哪一位工人？对于 Able， $\lambda = 1 / 30$ 每分钟， $1 / \mu = 24$ 分钟， $\sigma^{2} = 20^{2} = \hat {400}$ minutes^2， $\rho = \lambda / \mu = 24 / 30 = 4 / 5$ ，平均队长计算如下：

L_{Q} = \frac {(1 / 30) ^ {2} [ 24^{2} + 400 ]}{2 (1 - 4 / 5)} = 2. 711 \text{customers}

对于 Baker， $\lambda = 1 / 30$ 每分钟， $1 / \mu = 25$ 分钟， $\sigma^{2} = 2^{2} = 4$ minutes^2， $\rho = 25 / 30 = 5 / 6$ ，平均队长为

L_{Q} = \frac {(1 / 30) ^ {2} [ 25^{2} + 4 ]}{2 (1 - 5 / 6)} = 2. 097 \text{customers}

尽管 Able 的平均工作速度更快，但其更大的服务变异性导致平均队长比 Baker 的大约 30%。以平均队长 $L_{Q} ,$ 为准，Baker 胜出。另一方面，到达时发现 Able 空闲从而毫无延误的到达者比例为 $P_{0} = 1 - \rho = 1 / 5 = 20 \%$ , 而发现 Baker 空闲从而毫无延误的到达者比例为 $P_{0} = 1 - \rho = 1 / 6 = 16 . 7 \%$ 。

$M / G / 1$ 队列中有一种特别值得注意的情形，即服务时间服从指数分布时，这将在下面加以描述。

M/M/1 队列。 假定一个 $M / G / 1$ 队列中的服务时间服从均值为 $1 / \mu ;$ 的指数分布，那么由方程 $E ( X ) = \frac {1} {\lambda}$ 与 $V ( X ) = \frac {1} {\lambda^{2}}$ 所给出的方差为 $\sigma^{2} = 1 / \mu^{2}$ 。指数分布的均值与标准差相等，因此当服务时间的标准差近似等于其均值时， $M/M/1$ 队列常常是一个有用的近似模型。表 4 中给出的稳态参数，可以通过把 $\sigma ^ {\hat {2}} = 1 / \mu^{2}$ 代入表 3 中的公式而算出。另一种方法是，用式 (16) 从表 4 给出的稳态概率 $P_{n}$ 算出 L，然后再由式 (17) 中的方程算出 w、 $w_{Q} .$ 与 $L_{Q}$ 。读者可以证明：把 $\rho = \lambda / \mu$ 代入表 4 中每个方程的右端，即可得到每个参数的两个表达式彼此等价。

表 4 $M / M / 1$ 队列的稳态参数

L \quad \frac {\lambda}{\mu - \lambda} = \frac {\rho}{1 - \rho}

w \quad \frac {1}{\mu - \lambda} = \frac {1}{\mu (1 - \rho)}

w_{Q} \frac {\lambda}{\mu (\mu - \lambda)} = \frac {\rho}{\mu (1 - \rho)}

L_{Q} \frac {\lambda^{2}}{\mu (\mu - \lambda)} = \frac {\rho^{2}}{1 - \rho}

P_{n} \left(1 - \frac {\lambda}{\mu}\right) \left(\frac {\lambda}{\mu}\right) ^ {n} = (1 - \rho) \rho^{n}

例 10

假定某家只有一张座椅的男女通用美发店的到达间隔时间与服务时间都已被证明服从指数分布。λ 与 $\mu$ 的值分别为每小时 2 位与每小时 3 位——也就是说，到达之间的时间平均为 $1 / 2$ 小时、且服从指数分布，而服务时间平均为 20 分钟、同样服从指数分布。服务台利用率以及店内有 $0 , 1 , 2 , 3 ,$ 位和 4 位或更多顾客的概率计算如下：

\rho = \frac {\lambda}{\mu} = \frac {2}{3}

P_{0} = 1 - \frac {\lambda}{\mu} = \frac {1}{3}

P_{1} = \left(\frac {1}{3}\right) \left(\frac {2}{3}\right) = \frac {2}{9}

P_{2} = \left(\frac {1}{3}\right) \left(\frac {2}{3}\right) ^ {2} = \frac {4}{27}

P_{3} = \left(\frac {1}{3}\right) \left(\frac {2}{3}\right) ^ {3} = \frac {8}{81}

P_{\geq 4} = 1 - \sum_{n = 0} ^ {3} P_{n} = 1 - \frac {1}{3} - \frac {2}{9} - \frac {4}{27} - \frac {8}{81} = \frac {16}{81}

由这些计算可知，美发师忙碌的概率为 $1 - P_{0} = \rho = 0 . 67$ ；因此，美发师空闲的概率为 0.33。系统中顾客的按时间平均数由表 4 给出为

L = \frac {\lambda}{\mu - \lambda} = \frac {2}{3 - 2} = 2 \text{customers}

一位到达者在系统中度过的平均时间可由表 4 或式 (17) 得到：

w = \frac {L}{\lambda} = \frac {2}{2} = 1 \text{hour}

顾客在队列中度过的平均时间可由式 (17) 得到：

w_{Q} = w - \frac {1}{\mu} = 1 - \frac {1}{3} = \frac {2}{3} \mathrm{hour}

由表 4，队列中的按时间平均数为

L_{Q} = \frac {\lambda^{2}}{\mu (\mu - \lambda)} = \frac {4}{3 (1)} = \frac {4}{3} \mathrm{customers}

最后，注意：把 $w = w_{Q} + 1 / \mu$ 整体乘以 $\lambda$ ，并利用 Little 方程 (9)，得到

L = L_{Q} + \frac {\lambda}{\mu} = \frac {4}{3} + \frac {2}{3} = 2 \text{customers}

例 11

对于服务率为每小时 $\mu = 10$ 位顾客的 $M / M / 1$ 队列，考虑当到达率 λ 以 20% 的步长从 5 增加到 8.64、然后再增加到 $\lambda = 10$ 时，L 与 w 如何增长：

$\lambda$	5.0	6.0	7.2	8.64	10.0
$\rho$	0.500	0.600	0.720	0.864	1.0
$L$	1.00	1.50	2.57	6.35	$\infty$
$w$	0.20	0.25	0.36	0.73	$\infty$

对于任意 $M / G / 1$ 队列，若 $\lambda / \mu \geq 1$ ，排队线的长度将趋于持续不断地增长；长期性能度量 $L ,$ w、 $w_{Q} ,$ 与 $L_{Q}$ 全都无穷大 $( L = w = w_{O} = L_{O} = \infty )$ ；且不存在稳态概率分布。正如这里对 $\lambda < \mu ,$ 所表明的，若 $\rho$ 接近于 1，排队线与延误往往会很长。注意，平均系统时间 w 与系统中平均数 L 作为 $\rho .$ 的函数，其增长是高度非线性的。例如，当 λ 增加 20% 时，L 先是增加 50%（从 1.00 到 1.50），然后增加 71%（到 2.57），再增加 147%（到 6.35）。

例 12

若到达以 $\lambda = 10$ 每小时的速率发生，且管理层可以在两名服务提供者之间做选择，其中一位以 $\mu_{1} = 11$ 位顾客每小时的速率工作、另一位以 $\mu_{2} = 12$ 位顾客每小时的速率工作，则相应的利用率为 $\rho_{1} = \lambda / \mu_{1} = 10 / 11 = 0 . 909$ 与 $\rho_{2} = \lambda / \mu_{2} = 10 / 12 = 0 . 833$ 。若采用 $M / M / 1$ 队列作为近似模型，那么，使用第一位服务提供者时，系统中的平均顾客数由表 4 得

L_{1} = \frac {\rho_{1}}{1 - \rho_{1}} = 10

而使用第二位服务提供者时，系统中的平均顾客数为

L_{2} = \frac {\rho_{2}}{1 - \rho_{2}} = 5

因此，服务率从每小时 11 位顾客提高到每小时 12 位（仅仅 9.1% 的提高），就会使系统中的平均顾客数从 10 下降到 5，即下降了 50%！

利用率与服务变异性的影响

对于任意 $M / G / 1$ 队列，如果队伍太长，它们可以通过降低服务台利用率 $\rho$ 或降低服务时间变异性 $\sigma^{2} .$ 来缩短。这些论断几乎适用于所有队列，而不只是 $M / G / 1$ 队列。利用率因子 $\rho$ 可以通过降低到达率 $\lambda ,$ 、提高服务率 $\mu ,$ 或增加服务台个数来降低，因为一般地有 $\rho = \lambda / ( c \mu )$ ，其中 c 是并行服务台的个数。增加服务台的影响将在下面几个小节中加以研究。

一个正随机变量 X 的变异系数的平方（squared coefficient of variation，cv）定义为

(\mathrm{cv}) ^ {2} = \frac {V (X)}{[ E (X) ] ^ {2}}

它是对一个分布变异性的一种度量。它的值越大，该分布相对于其期望值就越加可变。对于确定性的服务时间， $V ( X ) = 0$ ，因此 $\operatorname{c v} = 0$ 。对于 k 阶厄兰服务时间， $V ( X ) = 1 / ( k \mu^{2} )$ 且 $E ( X ) = 1 / \mu$ ，因此 $\mathrm{c v} = 1 / \sqrt {k}$ 。对于服务率为 $\mu .$ 的指数服务时间，平均服务时间为 $E ( X ) = 1 / \mu$ 、方差为 $V ( X ) = 1 / \mu^{2}$ ，因此 $\mathbf{c} \mathbf{v} = 1$ 。如果服务时间的标准差大于其均值 $( \mathrm{i . e . , i f cv > 1} )$ ，那么超指数分布（hyperexponential distribution）提供了一个好的模型，它可以达到任意大于 1 的期望变异系数。习题 16 给出了它出现的一个场合。

任意 $M / G / 1$ 队列的 $L_{Q}$ 公式都可以用变异系数来改写，方法是注意到 $\mathrm{( c v )} ^ {2} = \sigma^{2} / ( 1 / \mu ) ^ {2} = \sigma^{2} \mu^{2}$ 。因此，

\begin{array}{r l} L_{Q} & = \frac {\rho^{2} (1 + \sigma^{2} \mu^{2})}{2 (1 - \rho)} \\ & = \frac {\rho^{2} (1 + (\mathrm{cv}) ^ {2})}{2 (1 - \rho)} \\ & = \left(\frac {\rho^{2}}{1 - \rho}\right) \left(\frac {1 + (\mathrm{cv}) ^ {2}}{2}\right) \end{array}\tag{18}

第一项 $\rho^{2} / ( 1 - \rho )$ 正是 $M / M / 1$ 队列的 $L_{Q}$ 。第二项 $\left( 1 + ( \mathrm{c v} ) ^ {2} \right) / 2$ 对 $M / M / 1$ 公式作出修正，以考虑非指数的服务时间分布。 $w_{Q}$ 的公式可以通过施加同样的修正因子，从相应的 $M / M / 1$ 公式得到。这两个因子 $\rho^{2} / ( 1 - \rho )$ 与 $\left( 1 + \left( \mathrm{c v} \right) ^ {2} \right) / 2$ ，为深入了解服务台利用率与服务台变异性对队列拥挤程度的相对影响提供了某种洞察：当 $\rho \ \to \ 1$ 时， $L_{Q}$ 急剧增大；而对于固定的 $\rho .$ ，它随 $( \mathbf{c} \mathbf{v} ) ^ {2}$ 线性增长。

4.2 多服务台队列：M/M/c/∞/∞

假定有 c 条通道在并行运转。这些通道各自具有独立且相同的指数服务时间分布，均值为 $1 / \mu$ 。到达过程是速率为 λ 的泊松过程。到达者将加入一个单一的队列，并进入第一个可用的服务通道。该排队系统如图 12 所示。如果系统中的顾客数 $n < c ,$ ，一位到达者将进入某条可用的通道。然而，当 $n \geq c .$ 时，若有到达发生，就会形成队列。

提供负载定义为 $\lambda / \mu .$ 若 $\lambda \ge c \mu$ ，则到达率大于或等于系统的最大服务率（即所有服务台都忙碌时的服务率）；因此，系统无法处理加于其上的负载，因而它不具有统计平衡。若 $\lambda > c \mu$ ，排队线的长度以每时间单位 $\lambda - c \mu$ 位顾客的平均速率增长。顾客以每时间单位 $\lambda$ 的速率进入系统，却最多以每时间单位 $c \mu$ 的速率离开系统。

要使 $M / M / c$ 队列具有统计平衡，提供负载必须满足 $\lambda / \mu < c$ ，此时 $\lambda / ( c \mu ) = \rho ;$ 即为服务台利用率。稳态参数列于表 5。多数性能度量可以相当简单地用 $P_{0}$ （系统为空的概率）来表示，或者用 $\textstyle \operatorname{o r} \sum_{n = c} ^ {\infty} P_{n} .$ （所有服务台都忙碌的概率）来表示，后者记为 $P ( L ( \infty ) \geq c )$ ，其中 $L ( \infty )$ 是一个随机变量，表示在统计平衡状态下（经过很长时间之后）系统中的顾客数。于是， $P ( L ( \infty ) = n ) = P_{n} , n = 0 , 1 , 2 , \ldots .$ 计算所有性能度量都需要用到 $P_{0}$ 的值，而 $P_{0}$ 的方程比前面各种情形稍微复杂一些。不过，可从 www.bcnn.net 获取的电子表格 QueueingTools.xls 会为本章所述的这个排队模型以及所有排队模型执行这些计算。

图 12 多服务台排队系统。

表 5 $M / M / c$ 队列的稳态参数

ρ	λ/cμ
P0	{[∑n=0c-1/(λ/μ)n/n! ] + [ (λ/μ)c(1/c!) (cμ/cμ-λ)]}-1
	= {[∑n=0c-1/(cρ)n/n! ] + [ (cρ)c(1/c!) 1/1-ρ]}-1
P(L(∞)≥c)	(λ/μ)cP0/c!(1-λ/cμ) = (cρ)cP0/c!(1-ρ)
L	cρ + (cρ)c+1P0/c(c!(1-ρ)2) = cρ + ρP(L(∞)≥c)/1-ρ
w	L/λ
wQ	w - 1/μ
LQ	λwQ = (cρ)c+1P0/c(c!(1-ρ)2) = ρP(L(∞)≥c)/1-ρ
L - LQ	λ/μ = cρ

当 $c = 1$ （单服务台的情形）时，表 5 中的结果就简化为表 4 中的那些结果。注意，平均忙碌服务台数，或者说正在接受服务的平均顾客数，由简单的表达式 $L - L_{Q} = \lambda / \mu = c \rho$ 给出。

例 13

排队论早期的许多例子，涉及的是与工具库有关的实际问题。当机械师（假定来自一个无限呼叫总体）到来请求服务时，由管理员管理这些工具库。不过，这个例子同样容易地可以换成顾客到达一家电影院的售票处。假定到达是速率为每分钟 2 名机械师的泊松到达，服务时间服从均值为 40 秒的指数分布。

现在， $\lambda = 2$ 每分钟， $\mu = 60 / 40 = 3 / 2$ 每分钟。提供负载大于 1：

\frac {\lambda}{\mu} = \frac {2}{3 / 2} = \frac {4}{3} > 1

因此，如果系统要有统计平衡，就需要不止一个服务台。稳态的要求是 $c > \lambda / \mu = 4 / 3$ 。于是至少需要 $c = 2$ 名管理员。量 4/3 是忙碌服务台的期望数，而对于 $c \geq 2 , \rho = 4 / ( 3 c )$ 是每个服务台忙碌时间的长期比例。（如果只有 $c = 1$ 个服务台，会发生什么情况？）

设 $c = 2$ 名管理员。首先， $P_{0}$ 计算如下：

\begin{array}{l} P_{0} = \left\{\sum_{n = 0} ^ {1} \frac {(4 / 3) ^ {n}}{n !} + \left(\frac {4}{3}\right) ^ {2} \left(\frac {1}{2 !}\right) \left[ \frac {2 (3 / 2)}{2 (3 / 2) - 2} \right] \right\} ^ {- 1} \\ = \left\{1 + \frac {4}{3} + \left(\frac {16}{9}\right) \left(\frac {1}{2}\right) (3) \right\} ^ {- 1} = \left(\frac {15}{3}\right) ^ {- 1} = \frac {1}{5} = 0. 2 \end{array}

接着，所有服务台都忙碌的概率计算如下：

P (L (\infty) \geq 2) = \frac {(4 / 3) ^ {2}}{2 ! (1 - 2 / 3)} \left(\frac {1}{5}\right) = \left(\frac {8}{3}\right) \left(\frac {1}{5}\right) = \frac {8}{15} = 0. 533

于是，等待的机械师排队线的按时间平均长度为

L_{Q} = \frac {(2 / 3) (8 / 15)}{1 - 2 / 3} = 1. 07 \mathrm{mechanics}

而系统中的按时间平均顾客数由下式给出：

L = L_{Q} + \frac {\lambda}{\mu} = \frac {16}{15} + \frac {4}{3} = \frac {12}{5} = 2. 4 \text{mechanics}

由 Little 的关系式，一名机械师在工具库度过的平均时间为

w = \frac {L}{\lambda} = \frac {2 . 4}{2} = 1. 2 \text{minutes}

而等待一名管理员的平均时间为

w_{Q} = w - \frac {1}{\mu} = 1. 2 - \frac {2}{3} = 0. 533 \mathrm{minute}

M/G/c/∞ 队列的一个近似

回顾一下， $M / G / 1$ 队列的 $L_{Q}$ 与 $w_{Q}$ 公式可以通过把相应的 $M / M / 1$ 公式乘以修正因子 $\left( 1 + ( \mathrm{c v} ) ^ {2} \right) / 2$ 而得到，如式 (18) 所示。 $M / G / c$ 队列的近似公式可以通过对 $M / M / c$ 的 $L_{Q}$ 与 $w_{Q}$ 公式施加同样的修正因子而得到（对于 $1 < c < \infty$ ，不存在精确公式）。cv 越接近于 1，该近似越好。

例 14

回顾例 13。假定工具库里机械师的服务时间不是指数分布的，但已知其标准差为 30 秒。于是我们面对的是一个 $M / G / c$ 模型，而不是 $M / M / c$ 。平均服务时间为 40 秒，因此服务时间的变异系数为

\mathrm{cv} = \frac {30}{40} = \frac {3}{4} < 1

因此， $L_{Q}$ 与 $w_{Q}$ 的精度可以通过修正因子

\frac {1 + (\mathrm{cv}) ^ {2}}{2} = \frac {1 + (3 / 4) ^ {2}}{2} = \frac {25}{32} = 0. 78

加以改进。例如，当有 $c = 2$ 名管理员时，

L_{Q} = (0. 78) (1. 07) = 0. 83 \text{mechanics}

注意，由于服务时间的变异系数小于 1，以 $L_{Q}$ 度量的系统拥挤程度低于相应的 $M / M / 2$ 模型。

修正因子只适用于 $L_{Q}$ 与 $w_{Q} .$ 的公式。然后可以利用 Little 公式来计算 L 与 w。遗憾的是，对于稳态概率 $P_{n}$ ，并没有通用的修正方法。

服务台个数为无穷时的情形 (M/G/∞/∞)

至少在三种情形中，把服务台个数视为无穷是恰当的：

当每位顾客都是它自己的服务台时——换句话说，在一个自助服务系统中；
当服务容量远远超过服务需求时，如在一个所谓的"充裕服务台"（ample-server）系统中；并且
当我们想知道需要多少个服务台，才能使顾客极少受到延误时。

$M / G / \infty$ 队列的稳态参数列于表 6。在表中，λ 是泊松到达过程的到达率， $1 / \mu$ 是一般服务时间分布（包括指数分布、常数分布或任何其他分布）的期望服务时间。

表 6 $M / G / \infty$ 队列的稳态参数

$P_0$	$e^{-\lambda/\mu}$
$w$	$\frac{1}{\mu}$
$w_Q$	0
$L$	$\frac{\lambda}{\mu}$
$L_Q$	0
$P_n$	$\frac{e^{-\lambda/\mu}(\lambda/\mu)^n}{n!}, n=0,1,\ldots$

例 15

在推出其全新的、仅限订阅者的在线计算机信息服务之前，The Connection 必须就可同时登录的用户数来规划其系统容量。如果该服务取得成功，预计顾客将按每小时 $\lambda = 500$ 的速率登录（服从一个泊松过程），并保持连接平均 $1 / \mu = 180$ 分钟（或 3 小时）。在真实系统中，同时在线的用户数会有一个上限，但出于规划的目的，The Connection 可以假定同时在线的用户数是无穷的。对该系统的一个 $M / G / \infty$ 模型意味着，同时在线用户的期望数为 $L = \lambda / \mu = 500 ( 3 ) = 1500$ ，因此肯定需要大于 1500 的容量。为了确保在 95% 的时间里提供充足的容量，The Connection 可以把同时在线用户数取为满足下式的最小的 c 值：

P (L (\infty) \leq c) = \sum_{n = 0} ^ {c} P_{n} = \sum_{n = 0} ^ {c} \frac {e^{- 1500} (1500) ^ {n}}{n !} \geq 0. 95

容量 $c = 1564$ 个同时在线用户满足这一要求。

4.3 具有泊松到达与有限容量的多服务台队列：M/M/c/N/∞

假定服务时间服从速率为 $\mu ,$ 的指数分布，有 c 个服务台，且系统总容量为 $N \geq {\mathfrak {c}}$ 位顾客。如果在系统已满时发生一次到达，该到达者就被拒之门外、不进入系统。与前一节一样，假定到达以速率为每时间单位 λ 次到达的泊松过程随机发生。对于任意满足 $\rho \neq 1$ 的 λ 与 µ 的值， $M / M / c / N$ 队列都具有统计平衡，其稳态特征如表 7 所示（ $\rho = 1$ 情形的公式可在 Hillier 与 Lieberman [2005] 中找到）。

表 7 $M / M / c / N$ 队列的稳态参数

\begin{array}{l l} (N = \text{System Capacity}, a = \lambda / \mu , \rho = \lambda / (c \mu)) \\ \hline P_{0} & \left[ 1 + \sum_{n = 1} ^ {c} \frac {a^{n}}{n !} + \frac {a^{c}}{c !} \sum_{n = c + 1} ^ {N} \rho^{n - c} \right] ^ {- 1} \\ P_{N} & \frac {a^{N}}{c ! c^{N - c}} P_{0} \\ L_{Q} & \frac {P_{0} a^{c} \rho}{c ! (1 - \rho) ^ {2}} \left[ 1 - \rho^{N - c} - (N - c) \rho^{N - c} (1 - \rho) \right] \\ \lambda_{e} & \lambda (1 - P_{N}) \\ w_{Q} & \frac {L_{Q}}{\lambda_{e}} \\ w & w_{Q} + \frac {1}{\mu} \\ L & \lambda_{e} w \end{array}

有效到达率（effective arrival rate） $\lambda_{e}$ 定义为：每时间单位进入并留在系统中的平均到达数。对于所有系统， $\lambda_{e} \leq \lambda _ {\mathrm{:}}$ ；对于容量无限的系统， $\lambda_{e} = \lambda ;$ ；但对于诸如此处所讨论的这类在系统已满时把顾客拒之门外的系统，则有 $\lambda_{e} \ < \ \lambda$ 。有效到达率由下式计算：

\lambda_{e} = \lambda (1 - P_{N})

因为 $1 - P_{N}$ 正是一位顾客在到达时发现有空位、从而能够进入系统的概率。当人们利用 Little 方程 (17) 来计算在系统中度过的平均时间 w 与在队列中度过的平均时间 $w_{Q} ,$ 时，必须用 $\lambda_{e}$ 替换 λ。

例 16

例 10 中描述的那家男女通用美发店只能容纳三位顾客：一位正在接受服务，两位正在等待。当系统已满时，额外的顾客被拒之门外。提供负载如前所述地确定，即 $\lambda / \mu = 2 / 3$ 。为计算这些性能度量，首先计算 $P_{0} \mathrm {{:}}$

P_{0} = \left[ 1 + \frac {2}{3} + \frac {2}{3} \sum_{n = 2} ^ {3} \left(\frac {2}{3}\right) ^ {n - 1} \right] ^ {- 1} = 0. 415

系统中有三位顾客（系统已满）的概率为

P_{N} = P_{3} = \frac {(2 / 3) ^ {3}}{1 ! 1^{2}} P_{0} = \frac {8}{65} = 0. 123

于是，队列的平均长度（等待理发的顾客数）由下式给出：

L_{Q} = \frac {(27 / 65) (2 / 3) (2 / 3)}{(1 - 2 / 3) ^ {2}} \left[ 1 - (2 / 3) ^ {2} - 2 (2 / 3) ^ {2} (1 - 2 / 3) \right] = 0. 431 \text{customer}

现在，有效到达率 $\lambda_{e}$ 由下式给出：

\lambda_{e} = 2 \left(1 - \frac {8}{65}\right) = \frac {114}{65} = 1. 754 \text{customers per hour}

因此，由 Little 方程，预期在队列中等待的时间为

w_{Q} = \frac {L_{Q}}{\lambda_{e}} = \frac {28}{114} = 0. 246 \mathrm{hour}

而预期在店内的总时间为

w = w_{Q} + \frac {1}{\mu} = \frac {66}{114} = 0. 579 \mathrm{hour}

最后一次应用 Little 方程，得到店内（在队列中加上正在理发）的期望顾客数为

L = \lambda_{e} w = \frac {66}{65} = 1. 015 \text{customers}

注意， $1 - P_{0} = 0 . 585$ 是正在接受服务的平均顾客数，或者说，等价地，是单个服务台忙碌的概率。因此，服务台利用率，即服务台忙碌时间的长期比例，由下式给出：

1 - P_{0} = \frac {\lambda_{e}}{\mu} = 0. 585

读者应当把这些结果与在未对该系统施加容量约束之前的男女通用美发店的结果作一比较。具体地说，在容量有限的系统中，提供负载 $\lambda / \mu$ 可以取任意正值，并且不再等于服务台利用率 $\rho =$ $\lambda_{e} / \mu$ 。注意，当系统施加了容量约束时，服务台利用率从 67% 下降到 58.5%。

5 有限总体模型的稳态行为 (M/M/c/K/K)

在许多实际问题中，无限呼叫总体的假定会导致无效的结果，因为呼叫总体实际上是小的。当呼叫总体较小时，系统中存在一位或多位顾客对未来到达的分布有着强烈的影响，而使用无限总体模型可能产生误导。典型例子包括一小群不时发生故障并需要修理的机器，或者一小群由一组护士负责照看的病人。在极端情形下，如果所有机器都已损坏，就不可能发生机器新的"到达"（故障）；类似地，如果所有病人都已请求过帮助，就不可能有到达发生。与此形成对照的是无限总体模型，在那类模型中，顾客到达系统的到达率 λ 被假定与系统的状态无关。

考虑一个有 K 位顾客的有限呼叫总体模型。对总体中每一位成员而言，从一次服务访问结束到其下一次请求服务之间的时间，假定服从均值为 $1 / \lambda$ 个时间单位的指数分布；服务时间同样服从指数分布，均值为 $1 / \mu$ 个时间单位；有 c 个并行服务台，系统容量为 K，因而所有到达者都会留下接受服务。图 13 描绘了这样一个系统。

该模型的稳态参数列于表 8。使用一个电子表格或一个符号计算程序来求这些复杂公式的值是有用的。例如，图 14 是为符号计算程序 MATLAB 编写的一个过程，用以计算 $M / M / c / K / K$ 队列的稳态概率。可从 www.bcnn.net 获取的电子表格 QueueingTools.xls 也执行这些计算。

图 13 有限总体的排队模型。

表 8 $M / M / c / K / K$ 队列的稳态参数

\left[ \sum_{n = 0} ^ {c - 1} \binom {K} {n} \left(\frac {\lambda}{\mu}\right) ^ {n} + \sum_{n = c} ^ {K} \frac {K !}{(K - n) ! c ! c^{n - c}} \left(\frac {\lambda}{\mu}\right) ^ {n} \right] ^ {- 1}

P_{n} \qquad \left\{\begin{array}{l l} \binom {K} {n} \left(\frac {\lambda}{\mu}\right) ^ {n} P_{0}, & n = 0, 1, \ldots , c - 1 \\ \frac {K !}{(K - n) ! c ! c^{n - c}} \left(\frac {\lambda}{\mu}\right) ^ {n} P_{0}, & n = c, c + 1, \ldots , K \end{array} \right.

L\qquad \sum_{\substack{n = 0\\ K}}^{K}nP_{n}

L_{Q}\qquad \sum_{\substack{n = c + 1\\ K}}^{K}(n - c)P_{n}

\lambda_{e} \quad \sum_{n = 0} ^ {K} (K - n) \lambda P_{n}

w \qquad L / \lambda_{e}

w_{Q} \qquad L_{Q} / \lambda_{e}

\rho \qquad \frac {L - L_{Q}}{c} = \frac {\lambda_{e}}{c \mu}

有效到达率 $\lambda_{e}$ 有若干种有效的解释：

$\lambda_{e}$ 是顾客到达该队列的长期有效到达率；
是顾客进入服务的长期有效到达率；
是顾客退出服务的长期速率；
是顾客进入呼叫总体（并开始一段新的运行时间）的长期速率；
是顾客退出呼叫总体的长期速率。

例 17

有两名工人负责照看 10 台铣床。这些机器平均运行 20 分钟，然后需要平均 5 分钟的服务时段，两个时间都服从指数分布。因此， $\lambda = 1 / 20$ 且 $\mu = 1 / 5$ 。计算该系统的各项性能度量。

所有的性能度量都依赖于 $P_{0} ,$ ，其为

\left[ \sum_{n = 0} ^ {2 - 1} \binom {10} {n} \left(\frac {5}{20}\right) ^ {n} + \sum_{n = c} ^ {10} \frac {10 !}{(10 - n) ! 2 ! 2^{n - 2}} \left(\frac {5}{20}\right) ^ {n} \right] ^ {- 1} = 0. 065

p = zeros(K+1,1);
% Note:
% p(1) = lim_t->infty Pr{N(t)=0}
% p(n+1) = lim_t->infty Pr{N(t)=n}, for n=1,2,...,K-1
% p(K+1) = lim_t->infty Pr{N(t)=K}
crho = lambda/mu;
Kfac = factorial(K);
cfac = factorial(c);
% get p(1)
for n=0:c-1
    p(1)=p(1) + (Kfac/(factorial(n)*factorial(K-n)))*(crho^n);
end
for n=c:K
    p(1)=p(1) + (Kfac/((c^(n-c))*factorial(K-n)*cfac))*(crho^n);
end
p(1)=1/p(1);
% get p(n+1), 0 < n < c
for n=1:c-1
    p(n+1)=p(1) * (Kfac/(factorial(n)*factorial(K-n)))*(crho^n);
end
% get p(n+1), c <= n <= K
for n=c:K
    p(n+1)=p(1) * (Kfac/((c^(n-c))*factorial(K-n)*cfac))*(crho^n);
end
% return probability vector
mmcKK = p;

图 14 计算 $M / M / c / K / K$ 队列的 $P_{n}$ 的 MATLAB 过程。

由 $P_{0} ,$ 我们可以得到其他的 $P_{n}$ ，由此可以算出等待服务的平均机器数，

L_{Q} = \sum_{n = 3} ^ {10} (n - 2) P_{n} = 1. 46 \text{machines}

有效到达率，

\lambda_{e} = \sum_{n = 0} ^ {10} (10 - n) \left(\frac {1}{20}\right) P_{n} = 0. 342 \text{machines / minute}

以及队列中的平均等待时间，

w_{Q} = L_{Q} / \lambda_{e} = 4. 27 \mathrm{minutes}

类似地，我们可以算出正在接受服务或等待接受服务的机器期望数，

L = \sum_{n = 0} ^ {10} n P_{n} = 3. 17 \text{machines}

正在接受服务的平均机器数由下式给出：

L - L_{Q} = 3. 17 - 1. 46 = 1. 71 \mathrm{machines}

每台机器必定处于运行中、等待服务中或正在接受服务这三种状态之一，因此平均运行中的机器数由下式给出：

K - L = 10 - 3. 17 = 6. 83 \mathrm{machines}

一个经常被问到的问题是：如果增加或减少服务台个数，会发生什么？如果本例中工人数增加到三名（c = 3），那么运行中机器的按时间平均数增加到

K - L = 7. 74 \mathrm{machines}

平均增加了 0.91 台机器。

反过来，如果服务台减少到一个，会发生什么？此时运行中机器的按时间平均数减少到

K - L = 3. 98 \mathrm{machines}

从两个服务台减到一个，平均导致运行中的机器减少了近三台。习题 17 要求读者考察增加或删减一个服务台对服务台利用率的影响。

例 17 说明了若干已被发现几乎对所有队列都成立的一般关系。如果服务台个数减少，那么延误、服务台利用率以及一位到达者必须等待才能开始服务的概率都会上升。

6 排队网络

在本章中，我们着重研究了 $G / G / c / N / K$ 类型的单个队列。然而，许多系统很自然地被建模为单个队列所构成的网络，其中从一个队列离开的顾客可以被路由到另一个队列。例 1（尤其参见图 3）与例 2（参见图 5）就是这方面的例证。

对排队网络之数学模型的研究超出了本章的范围；例如可参见 Gross 与 Harris [1997]、Nelson [1995] 以及 Kleinrock [1976]。不过，有若干基本原理对于粗略建模非常有用，也许可以在开展一次仿真研究之前加以使用。以下结果假定系统稳定、呼叫总体无限且系统容量不受限制：

只要在队列中没有顾客被创造或消灭，那么从长期看，离开一个队列的离开率就等于进入该队列的到达率。
若顾客以速率 $\lambda_{i} .$ 到达队列 i，且其中比例 $0 \leq p_{i j} \leq 1$ 的顾客在离开时被路由到队列 j，那么从长期看，从队列 i 流向队列 j 的速率为 $\lambda_{i} p_{i j}$ 。
进入队列 $j , \lambda_{j}$ 的总到达率是来自所有来源的到达率之和。若顾客以速率 $a_{j} ,$ 从网络之外到达，则

\lambda_{j} = a_{j} + \sum_ {\text{all} i} \lambda_{i} p_{i j}

若队列 j 有 $c_{j} < \infty$ 个并行服务台，每个以速率 $\mu_{j}$ 工作，则每个服务台的长期利用率为

\rho_{j} = \frac {\lambda_{j}}{c_{j} \mu_{j}}

且队列要稳定必须满足 $\rho_{j} < 1$ 。

若对于每个队列 j，来自网络之外的到达构成一个速率为 $a_{j} ,$ 的泊松过程，并且若有 $c_{j}$ 个相同的服务台提供均值为 $1 / \mu_{j}$ 的指数分布服务时间（其中 $c_{j}$ 可以为 $\infty )$ ，那么在稳态下，队列 j 的行为就像一个到达率为 $\lambda_{j} = a_{j} + \textstyle \sum _ {\mathrm{a l l} ~ i} \lambda_{i} p_{i j}$ 的 $M / M / c_{j}$ 队列。

例 18

再次考察例 1 中所描述并在图 3 中显示的折扣店。假定顾客以每小时 80 位的速率到达，且在这些到达者中，有 40% 选择自助服务；于是，到达服务中心 1 的到达率为 $\lambda_{1} = ( 80 ) ( 0 . 40 ) = 32$ 每小时，而到达服务中心 2 的到达率为 $\lambda_{2} = ( 80 ) ( 0 . 6 ) = 48$ 每小时。假定服务中心 2 处的 $c_{2} = 3$ 名店员各以 $\mu_{2} = 20$ 位顾客每小时的速率工作。那么这些店员的长期利用率为

\rho_{2} = \frac {48}{(3) (20)} = 0. 8

所有顾客都必须到服务中心 3 的收银员那里。到达服务中心 3 的总到达率为 $\lambda_{3} = \lambda_{1} + \lambda_{2} = 80$ 每小时，而与服务中心 1 的服务率无关，因为从长期看，离开每个服务中心的离开率必定等于进入它的到达率。如果该收银员以 $\mu_{3} = 90$ 每小时的速率工作，那么收银员的利用率为

\rho_{3} = \frac {80}{90} = 0. 89

7 粗略建模：一个示例

在本节中，我们说明如何运用本章所介绍的工具，在着手进行一次更详细的仿真之前开展一次粗略分析（rough-cut analysis）。粗略建模在若干方面是有用的：在某些情形下，粗略分析的结果已经如此有说服力，以致不再需要那次详细的仿真，从而节省大量的时间与金钱。更为典型的是，粗略模型让分析人员更好地理解待建模的系统——这是一种在构建详细且往往复杂的仿真模型之前的"带妆彩排"。此外，在粗略阶段所得到的性能度量还为仿真输出提供了一种合理性检验（sanity check），有可能避免因仅仅是在编写仿真程序时出错而得出错误的结论。

例 19

在某驾照办理分处，经理收到了许多关于换发驾照时长时间延误的投诉。为了给增加人手找到定量的支持依据，她请来了一位运筹分析人员。该设施的示意图如图 15 所示。

分处的营业时间为上午 8:00 至下午 4:00，历史上平均每天办理 464 名驾驶员。所有到达者必须首先到两名办事员之一那里办理登记。经理手上有几天里针对办事员收集的时间研究数据，发现平均登记时间为 2 分钟，标准差约为 0.4 分钟。登记之后，有 15% 的驾驶员需要参加一场大约持续 20 分钟的笔试；关于考试时间有很好的数据，因为这些试卷在发出与交回时都有时间戳记。这些多项选择题由一台光学扫描仪几乎瞬时地批阅完成。所有到达者都必须等待拍摄照片并制作驾照；这个工位每小时可处理约 60 名驾驶员，但由于有些照片不得不重拍，个别时间高度可变。

分处经理想知道：增加一名登记办事员，或者增加一个新的拍照工位，对顾客延误的相对影响分别是多大，而且这两项变更中是否有任何一项会影响为参加笔试的驾驶员所需的椅子数量（她目前拥有的 20 把椅子一直都是够用的）。

这是一个非常适合采用仿真的应用，但经理所聘请的这位分析人员认为，一次快速的排队近似既能提供有用的洞察，也能对仿真模型起到核对作用。

图 15 驾照办理分处的顾客流。

为开展一次粗略分析，分析人员把该驾照分处表示为一个排队网络，其中登记办事员为队列 1（ $c_{1} = 2$ 个服务台，每个以 $\mu_{1} = 30$ 名驾驶员每小时 $= 0 . 5$ 名驾驶员每分钟的速率工作），笔试工位为队列 2（ $c_{2} = \infty$ 个服务台，因为可以有任意多的人同时参加笔试，平均服务时间 $1 / \mu_{2} = 20$ 分钟），拍照工位为队列 3（ $c_{3} = 1$ 个服务台，以 $\mu_{3} = 1$ 名驾驶员每分钟的速率工作）。分析人员选择略去对试卷的光学扫描，因为它发生得非常快。尽管分处经理说正午前后的到达更为密集，但出于粗略分析的目的，分析人员把全天的到达率建模为每小时 $464 / 8 = 58$ 次到达。

到达各个队列的到达率如下：

\lambda_{1} = a_{1} + \sum_{i = 1} ^ {3} p_{i 1} \lambda_{i} = 58 \text{drivers per hour}

\lambda_{2} = a_{2} + \sum_{i = 1} ^ {3} p_{i 2} \lambda_{i} = (0. 15) \lambda_{1} \text{drivers per hour}

\lambda_{3} = a_{3} + \sum_{i = 1} ^ {3} p_{i 3} \lambda_{i} = (1) \lambda_{2} + (0. 85) \lambda_{1} \text{drivers per hour}

注意，来自网络之外的到达只发生在队列 1，因此 $a_{1} = 50$ 且 $a_{2} = a_{3} = 0$ 。求解这个方程组得到 $\lambda_{1} = \lambda_{3} = 58$ 与 $\lambda_{2} = 8 . 7$ 。分析人员选择以分钟为单位工作，因此把这些值换算为 $\lambda_{1} = \lambda_{3} = 0 . 97$ 每分钟与 $\lambda_{2} = 0 . 15$ 每分钟。

分析人员把到达过程近似为泊松过程——其合理性在于存在一个庞大的潜在顾客总体，他们（大体上）独立地作出何时到达的决定——并把每个队列的服务时间近似为指数分布。服务时间的近似对于队列 $^ {3 ,}$ 是合理的，因为经理相信拍照时间相当可变；而对于队列 2 则是无害的，因为无限服务台 $M / G / \infty$ 队列的结果只依赖于服务率，而不依赖于分布。然而，登记时间的变异系数为 $\mathrm{c v} = 0 . 4 / 2 = 0 . 2 < 1$ ，因此分析人员决定也对登记结果施加修正因子 $( 1 + \mathbf{c} \mathbf{v} ^ {2} ) / 2 = 0 . 52$ 。

现在，分析人员已掌握必要的信息，可以把驾照分处的每一个工位近似为一个独立的队列（这是又一个近似，因为在现实中它们并不独立）。登记办事员被近似为一个 $M / G / c_{1}$ 队列，考试工位被近似为一个 $M / G / \infty$ 队列，拍照工位被近似为一个 $M / M / c_{3}$ 队列。于是，在当前的设置之下，登记工位是一个 $M / G / 2$ ；利用表 5 中的公式再乘以 0.52，得到 $w_{Q} = 16 . 5$ 分钟。如果增加第三名办事员，队列中的等待时间就下降到 0.4 分钟，这是一项巨大的节省。

当前的拍照工位可以建模为一个 $M / M / 1$ 队列，得到 $w_{Q} = 32 . 3$ 分钟；增加第二个拍照工位 $\left( M / M / 2 \right)$ 会使队列中的时间下降到 0.3 分钟，这一节省甚至比增加一名办事员还大。

如果需要，考试工位可以利用表 6 中 $M / G / \infty$ 队列的结果来分析。例如，任意时刻正在参加考试的人数期望值为 $L = \lambda_{2} / \mu_{2} =$ $0 . 15 / ( 1 / 20 ) = 3$ ，这一数值不受办事员或拍照工位数量变化的影响，因为这些变化并不改变 $\lambda_{2}$ 或 $\mu_{2}$ 。

经理是否应当期望：如果实施了其中一项或两项变更，就会精确地看到这些结果呢？不应如此，因为这个模型在若干方面都是粗略的：排队结果是稳态的，而实际的驾照办理机构每天只营业 8 小时，且到达率不是常数。对系统加以简化时略去了试卷批阅、员工休息等环节。然而，这些结果确实为增加一名或多名员工提供了一个有说服力的理由，并提供了一个基线，用以核对一个包含所有相关特征的详细仿真模型。

8 小结

排队模型已经广泛地用于分析服务设施、生产与物料搬运系统、电话与通信系统，以及许多其他可能发生拥挤或稀缺资源竞争的情形。本章介绍了排队模型的基本概念，并说明了如何运用仿真（以及在某些情况下的数学分析）来估计一个系统的性能度量。

可以用仿真来生成一个复杂系统的一段或多段人造历史。这种由仿真生成的数据又可被用来估计系统所期望的性能度量。本章介绍了常用的性能度量，包括 $L , L_{Q} ,$ , w、 $w_{Q} , \rho$ 以及 $\lambda_{e} ,$ ，并给出了据以从数据中估计它们的公式。

在仿真任何随时间演化的系统时，分析人员必须决定要研究的究竟是暂态行为还是稳态性能。对于某些队列的稳态行为存在着简单的公式，但要由仿真生成的数据估计稳态性能度量，就必须认识到初始条件对稳态性能估计量可能产生的有害影响，并加以处理。如果初始条件不能代表稳态，或者仿真运行长度太短，这些估计量就可能严重偏离（偏高或偏低）。

无论分析人员关心的是系统的暂态性能还是稳态性能，都应当认识到：从对一个随机队列的仿真中得到的那些估计，恰恰就是估计而已。每一个这样的估计都含有随机误差，需要进行恰当的统计分析才能评估该估计的精度。

在本章的最后三节中，我们说明了一批简单模型可以用数学方法求解。尽管这类模型背后的假定在实际应用中可能并不被严格满足，这些模型在提供性能度量的粗略估计方面仍然有用。在许多情形下，具有指数分布到达间隔时间与服务时间的模型会对系统行为给出保守的估计。例如，如果模型预测平均等待时间 w 为 12.7 分钟，那么真实系统中的平均等待时间很可能小于 12.7 分钟。指数模型的这种保守性质源于：(a) 诸如 w 与 $L ,$ 这样的性能度量一般是到达间隔时间与服务时间方差的增函数（回顾一下 $M / G / 1$ 队列），以及 (b) 指数分布具有相当高的变异性，其标准差始终等于其均值。因此，如果真实系统的到达过程或服务机构比指数分布的到达间隔时间或服务时间变异性更小，那么系统中的平均数 $L ,$ 与在

系统中度过的平均时间 w 就很可能会小于指数模型所预测的值。当然，如果到达间隔时间与服务时间比指数随机变量更加可变，那么 M/M 排队模型就有可能低估拥挤程度。

数学排队模型的一项重要应用是确定一个工作站或服务中心所需的最少服务台数。相当常见的情况是：如果到达率 λ 与服务率 µ 已知或者可以被估计出来，那么简单的不等式 $\lambda / ( c \mu ) < 1$ 就可以用来对一个工作站的服务台个数 c 给出初始估计。对于一个拥有许多工作站的大系统而言，若要对工作站 i 的服务台个数 $c_{i} ,$ 的各种可能组合 $( c_{1} , c_{2} , \ldots )$ 逐一做仿真，可能非常耗时。因此，由少量分析所得的粗略估计可以节省大量的计算机时间与分析人员的时间。

最后，排队的那些简单指数模型的定性行为可以推广到更复杂的系统。一般而言，正是服务时间的变异性与到达过程的变异性导致排队线堆积并形成拥挤。对于大多数系统，如果到达率上升、或者服务率下降、或者服务时间与到达间隔时间的方差增大，那么系统就会变得更加拥挤。可以通过增加服务台个数，或者通过减小服务时间的均值与变异性来降低拥挤程度。简单的排队模型在量化这些关系以及评价各种备选系统设计方面，可以提供很大的帮助。

参考文献

COOPER, R. B. [1990], Introduction to Queueing Theory, 3d ed., George Washington University, Washington, DC.

DESCLOUX, A. [1962], Delay Tablesfor Finite- and Infinite-Source Systems, McGraw-Hill, New York.

GROSS, D., AND C. HARRIS [1997], Fundamentals ofQueueing Theory, 3d ed., Wiley, New York.

HALL, R. W. [1991], Queueing Methods: For Services and Manufacturing, Prentice Hall, Englewood Cliffs, NJ.

HILLIER, F. S., AND G. J. LIEBERMAN [2005], Introduction to Operations Research, 8th ed., McGraw-Hill, New York.

KENDALL, D. G. [1953], “Stochastic Processes Occurring in the Theory of Queues and Their Analysis by the Method of Imbedded Markov Chains,” Annals ofMathematical Statistics, Vol. 24, pp. 338–354.

KLEINROCK, L. [1976], Queueing Systems, Vol. 2: Computer Applications, Wiley, New York.

LITTLE, J. D. C. [1961], “A Proof for the Queueing Formula $L = \lambda w , ^ {\ast}$ Operations Research, Vol. 16, pp. 651– 665.

NELSON, B. L. [1995], Stochastic Modeling: Analysis & Simulation, Dover Publications, Mineola, NY.

WINSTON, W. L. [2004], Operations Research: Applications and Algorithms, 4th Edition, Duxbury Press, Pacific Grove, CA.

习题

某工具库具有指数分布的到达间隔时间与服务时间，为一群数量很大的机械师服务。到达之间的平均时间为 4 分钟。工具库管理员服务一名机械师平均需要 3 分钟。管理员的工资是每小时 10 美元，机械师的工资是每小时 15 美元。再配备一名工具库管理员是否可取？
某机场正在为螺旋桨驱动的飞机设计两条跑道（一条用于降落，一条用于起飞）。已知降落一架飞机的时间服从指数分布，均值为 1.5 分钟。如果假定飞机的到达是随机发生的，那么在平均空中等待时间不超过 3 分钟的条件下，可以容忍多大的到达率？
特罗普港（Port of Trop）一次只能服务一艘船。不过，还有可供另外三艘船系泊的空间。特罗普是一个受欢迎的停靠港，但如果没有可用的系泊空间，船只就不得不前往普普港（Port of Poop）。平均每周有七艘船到达，服从泊松过程。特罗普港有能力每周平均处理八艘船，服务时间服从指数分布。在特罗普港等待或正在接受服务的船只期望数是多少？
在大都会市政厅（Metropolis City Hall），有两名工作人员每天都"拉关系"（做交易）。需要拉的关系平均每 10 分钟出现一个，全天如此。拉一个关系平均需要 15 分钟。到达间隔时间与服务时间都服从指数分布。在随机时刻系统中没有任何需要拉的关系的概率是多少？等待被拉的关系的期望数是多少？两名拉关系者都忙碌的概率是多少？如果再增加一名拉关系者（以与前两人相同的速度工作），对性能有何影响？
在 Tony 与 Cleo 的面包店，只提供一种生日蛋糕。装饰这种蛋糕需要 15 分钟，这项工作由一位特定的面包师完成。事实上，这是这位面包师唯一的工作。如果要使等待装饰的队列平均长度不超过五个蛋糕，可以接受的平均到达间隔时间（服从指数分布）是多少？
病人按速率为每小时 1 位的泊松过程到达进行体检。体检需要三个阶段，每一阶段独立地服从指数分布，服务时间为 15 分钟。一位病人必须在下一位病人被允许进入治疗设施之前走完所有三个阶段。计算该系统被延误病人的平均数 $L_{Q} ,$ 。[提示：独立随机变量之和的方差等于方差之和。]
假定机械师按速率 λ = 每小时 10 位的泊松过程随机到达一个工具库。已知唯一一位工具管理员服务一名机械师平均需要 4 分钟，标准差约为 2 分钟。假定机械师的工资是每小时 15.00 美元。估计机械师等待工具的稳态平均每小时成本。
到达某机场的飞机都被引导到同一条跑道。在一天中的某个时段，这些到达构成一个速率为每小时 30 架的泊松过程。降落一架飞机的时间是 90 秒的常数。确定该机场的 $L$ 、 $w$ 、 $L_{Q}$ 与 $w_{Q}$ 。如果一架被延误的飞机平均每小时烧掉价值 5000 美元的燃油，确定等待降落所造成延误的平均每架飞机成本。
某机修车间修理小型电动机，这些电动机按速率为每周 12 台的泊松过程到达（每周工作 5 天、40 小时）。对以往数据的分析表明，发动机平均可在 2.5 小时内修好，方差为 1 小时^2。在不了解系统状态的情况下，一位顾客应当预期把一台电动机留在修理车间多少个工作小时？如果修理时间的方差可以被控制，那么多大的方差会把期望等待时间降到 6.5 小时？
到达某自助加油泵的顾客以每小时 12 位的泊松方式发生。服务时间的分布平均为 4 分钟，标准差为一又三分之一分钟。系统中的期望车辆数是多少？
Classic Car Care 有一名工人按四个步骤洗车——打皂、冲洗、擦干、吸尘。完成每一步的时间服从指数分布，均值为 9 分钟。每辆车在开始下一辆车的流程之前都要走完每一个步骤。平均而言，每 45 分钟有一辆车到来要求洗车，服从泊松过程。一辆车等待开始洗车的平均时间是多少？洗车系统中的平均车辆数是多少？洗一辆车所需的平均时间是多少？
某房间有 10 台棉纺织机。织机一旦完成设置便自动运行。设置时间服从指数分布，均值为 10 分钟。机器平均运行 40 分钟，也服从指数分布。织机操作工的工资是每小时 10 美元，而织机不运行则带来每小时 40 美元的成本。应当雇用多少名织机操作工才能使织机车间的总成本最小？如果目标变成"平均而言，任何织机等待操作工的时间不应超过 1 分钟"，应当雇用多少人？又应当雇用多少名操作工，以确保平均而言在任何时刻都至少有 7.5 台织机在运行？
考虑下列关于一个具有指数分布运行时间与服务时间的有限呼叫总体问题的信息：

\begin{array}{c} {K = 10} \\ {\frac {1}{\mu} = 15} \\ {\frac {1}{\lambda} = 82} \\ {c = 2} \end{array}

计算 $L_{Q}$ 与 $w_{Q} .$ 。求使 $L_{Q} = L / 2$ 成立的 λ 值。

假定图 6 表示一个后进先出（LIFO）单服务台系统的系统中顾客数。顾客不会被抢占（即被从服务中踢出），但在一次服务完成之后，最近的那位到达者接着开始服务。对于这个 LIFO 系统，把 L(t) 下方的总面积分摊给每一位顾客，正如在图 8 中对 FIFO 系统所做的那样。利用该图，证明式 (10) 与式 (8) 对单服务台 LIFO 系统成立。
重做习题 14，但假定

(a) 图 6 表示一个有 $c = 2$ 个服务台的 FIFO 系统。

(b) 图 6 表示一个有 $c = 2$ 个服务台的 LIFO 系统。

考虑一个具有如下类型服务分布的 $M / G / 1$ 队列：顾客按 $p$ 与 $1 - p .$ 的比例请求两种服务之一。第 i 类服务服从速率为 $\mu_{i} , i = 1 , 2$ 的指数分布。令 $X_{i}$ 表示一次第 i 类的服务时间，X 表示一次任意的服务时间。那么 $E ( X_{i} ) = 1 / \mu_{i} , V ( X_{i} ) = 1 / \mu_{i} ^ {2}$ 且

X = \left\{\begin{array}{l l} X_{1} & \text{with probability p} \\ X_{2} & \text{with probability (1 - p)} \end{array} \right.

随机变量 X 被称为具有参数为 $( \mu_{1} , \mu_{2} , p )$ 的超指数分布（hyperexponential distribution）。

(a) 证明 $E ( X ) = p / \mu_{1} + ( 1 - p ) / \mu_{2} {\mathrm{~ a n d ~}} E ( X^{2} ) = 2 p / \mu_{1} ^ {2} + 2 ( 1 - p ) / \mu_{2} ^ {2} .$

(b) 利用 $V ( X ) = E ( X^{2} ) - [ E ( X ) ] ^ {2}$ 证明 $V ( X ) = 2 p / \mu_{1} ^ {2} + 2 ( 1 - p ) / \mu_{2} ^ {2} - [ p / \mu_{1} + ( 1 - p ) / \mu_{2} ] ^ {2} \ /$

(c) 对于任意超指数随机变量，若 $\mu_{1} \ \ne \ \mu_{2}$ 且 $0 ~ < ~ p ~ < ~ 1$ ，证明其变异系数大于 1；即， $( \mathbf{c} \mathbf{v} ) ^ {2} = V ( X ) / [ E ( X ) ] ^ {2} > 1$ 。因此，超指数分布提供了一族统计模型，用以描述比指数分布服务时间更加可变的服务时间。[提示：利用 (a) 与 (b)，可以把 $( \mathbf{c} \mathbf{v} ) ^ {2} .$ 的代数表达式化成 $( \mathrm{c v} ) ^ {2} = 2 p ( 1 -$ $p ) ( 1 / \mu_{1} - 1 / \mu_{2} ) ^ {2} / [ E ( X ) ] ^ {2} + 1 .$ 的形式。]

(d) $\mu_{1} , \mu_{2}$ 与 p 的多种选择都可以得到相同的总均值 $E ( X )$ 与 $( \mathbf{c} \mathbf{v} ) ^ {2}$ 。如果希望得到一个均值为 $E ( X ) = 1$ 、变异系数为 $\operatorname{c v} = 2$ 的分布，请找出 $\mu_{1} , \mu_{2}$ 与 $p$ 的值来实现这一点。[提示：任意选取 $p = 1 / 4$ ；然后就 $\mu_{1}$ 与 $\mu_{2}$ 求解下列方程。]

\frac {1}{4 \mu_{1}} + \frac {3}{4 \mu_{2}} = 1

\frac {3}{8} \left(\frac {1}{\mu_{1}} - \frac {1}{\mu_{2}}\right) ^ {2} + 1 = 4

在例 $^ {17 ,}$ 中，以服务台利用率 $\rho$ （一个典型服务台忙碌时间所占的比例）为准，比较具有 $c = 1 , c = 2 ,$ , 与 $c = 3$ 个服务台的系统。
在例 17 中，把机器数目增加 2 台，然后以服务台利用率 $\rho$ （一个典型服务台忙碌时间所占的比例）为准，比较具有 $c = 1$ $c = 2 .$ , 与 $c = 3$ 个服务台的系统。
某小型木材堆场由一支 10 辆卡车的车队供货。有一台高架起重机可用来从卡车上卸下长原木。卸载一辆卡车平均需要 1 小时。卸完之后，一辆卡车平均需要 3 小时去装运下一批原木并返回木材堆场。

(a) 要用本章的模型来分析这一问题，需要作某些分布假定。请陈述这些假定并讨论其合理性。

(b) 只有一台起重机时，等待卸载的平均卡车数是多少？平均每小时有多少辆卡车到达堆场？到达时发现起重机忙碌的卡车占多大百分比？这与起重机忙碌时间的长期比例是否相同？

(d) 如果运到堆场的原木价值约为每车 200 美元，且起重机的长期成本为每台每小时 50 美元（无论忙碌还是空闲），请按每小时成本计算最优的起重机台数。

(e) 除 (d) 中的成本之外，如果管理层决定考虑闲置卡车与司机的成本，最优的起重机台数是多少？一辆卡车连同其司机一起估计每小时约花费 40 美元，并且在等待起重机时被视为闲置。

一个配有一名管理员的工具库为一群 10 名机械师服务。机械师工作一段服从指数分布的时间（均值 20 分钟），然后到工具库去领取一件专用工具。管理员的服务时间服从指数分布，均值为 3 分钟。如果管理员的工资是每小时 6 美元、机械师的工资是每小时 10 美元，那么再配备一名管理员是否可取？[提示：与习题 1 作比较。]
本题基于 Nelson [1995] 中的案例 8.1。拟建造一座大型购物商城。在繁忙时段，汽车的到达率预计平均为每小时 1000 辆，而在其他商城所做的研究表明顾客将花 3 小时购物。商城的设计者希望拥有充足的停车位，以便在 99.9% 的时间里都有足够的空位。他们应当设置多少个车位？[提示：把该系统建模为一个 $M/G/\infty$ 队列，其中车位就是服务台，并求出多少个车位才能以 0.999 的概率够用。]
在例 18 中，假定总到达率预期将上升到每小时 160 位。如果服务率不变，要使服务负荷刚好能被应付，服务中心 2 与服务中心 3 各需要多少名办事员？
一家小型复印店有一台自助复印机。目前只有供 4 个人排队的场地（包括正在使用机器的那个人）；当人数多于 4 人时，多余的人必须排到店外。店主希望尽可能避免人们排到店外。为此，他们正在考虑增加第二台自助复印机。据观察，自助顾客以每小时 24 位的速率到达，并且平均使用机器 2 分钟。请评估增加一台复印机的影响。请仔细陈述你所作的任何假定或近似。
某自助洗车房有 4 个洗车位。处在某个车位中时，顾客可以从三种选项中作选择：只冲洗；清洗并冲洗；以及清洗、冲洗并打蜡。每个选项都有固定的完成时间：只冲洗 3 分钟；清洗并冲洗 7 分钟；清洗、冲洗并打蜡 12 分钟。业主观察到，20% 的顾客选择只冲洗；70% 选择清洗并冲洗；10% 选择清洗、冲洗并打蜡。没有预约，顾客的到达率约为每小时 34 辆车。停车场上只有供 3 辆车等待的位置，因此目前有许多顾客流失。业主想知道：如果他们再增加一个车位，能多做多少生意。增加一个车位会占去停车场上的一个位置。

请为该建立一个排队模型。估计在当前系统与拟议系统中顾客流失的速率。请仔细陈述你所作的任何假定或近似。

找出实际应用中使用的排队模型的例子。一份很好的资料来源是《Interfaces》期刊。
通过比较两个 M/M/1 队列（每个的到达率为 λ、服务率为 µ）与一个到达率为 2λ、每个服务台服务率为 µ 的 $M / M / 2$ 队列的性能度量，研究合并服务台（pooling servers，即让多个服务台从单一队列中取顾客，而不是每个服务台各自拥有一个队列）的效果。
某修理与检验设施由两个工位组成：一个配有两名技术人员的修理工位，以及一个配有 1 名检验员的检验工位。每名修理技术人员以每小时 3 件物品的速率工作；检验员每小时可以检验 8 件物品。大约有 10% 的物品检验不合格并被送回修理工位。（这一比例即使对被修理过两次或更多次的物品也成立。）如果物品以每小时 5 件的速率到达，在假定泊松到达过程与指数分布服务时间的条件下，物品在这两个工位各自所经历的长期期望延误是多少？在不增加人员的条件下，系统所能承受的最大到达率是多少？
零件以每小时 50 件的速率到达某装配系统的第一级，随后还要经过另外四级，产品才算完成。每一级有 2% 的废品率，这意味着每一级中会有 2% 的产品被判定为缺陷品并被丢弃。

(a) 到达第五个装配工位的到达率是多少（单位：件每小时）？

(b) 如果这五个工位的平均装配时间各不相同，那么把这些工位按加工时间从小到大排序（或者反过来）是否有意义？为什么？

某呼叫中心负责回答有关财务跟踪、个人效率以及联系人管理软件方面的问题。呼叫以每分钟 1 次的速率到达，历史上 25% 的呼叫是关于财务类产品的，34% 是关于效率类产品的，41% 是关于联系人管理类产品的。回答一位来电者的问题平均需要 5 分钟。任一时刻能够接入的顾客数基本上是无限制的，但每条产品线各有自己的接线员（财务类 2 名、效率类 2 名、联系人管理类 3 名）。如果有合适的接线员空闲，呼叫就被立即路由给该接线员；否则，来电者被放入一个等待队列。公司希望通过对接线员进行交叉培训、使之能够回答任何产品线的呼叫，从而减少所需接线员的总数。由于这些接线员不可能在所有产品上都是专家，预计这会使处理一次呼叫的时间增加约 10%。要提供与当前系统相同服务水平的服务，需要多少名经过交叉培训的接线员？请通过对当前系统与拟议系统作近似来回答这一问题。

可从 www.bcnn.net 获取的材料清单

QueueingTools.xls