基础排队模型：M/M/1 与 Little 定律 | 自在学

08 M/M/1 排队模型与 Little 定律

午餐窗口平均每分钟来两个人，每分钟能服务 $2.4$ 人。服务能力确实大于到达量，但顾客并不会每隔半分钟整齐地出现，服务也不总是同样长。连续来了几个人，再碰上一位需要较久处理的顾客，队伍就会留下来。我们要算的，正是这些波动累积以后，人数和等待时间会变成什么样。

这一章把两件事放在一起做：用随机模型预测长期指标，再沿一份具体的到达、服务记录检查这些指标是怎样统计的。若“系统内人数”漏掉了正在服务的人，或者把观察窗以外的时间也算进面积，即使模拟运行了很久，结果仍会错。

状态里要包括正在服务的人

M/M/1 模型采用以下假设：到达是速率 $\lambda>0$ 的 Poisson 过程；服务时间独立同分布，服从 $\operatorname{Exp}(\mu)$ ，其中 $\mu>0$ ；到达与服务相互独立；只有一个服务台，等候空间无限，顾客按先到先服务，服务台有顾客就工作，没有中途离开或拒绝进入。

记 $N(t)$ 为系统内人数，包含正在服务的那一位。排队人数和忙碌指示量则是

N_q(t)=(N(t)-1)_+,\qquad I(t)=\mathbf1_{\{N(t)>0\}},

所以逐时刻都有 $N(t)=N_q(t)+I(t)$ 。系统只有一位顾客时， $N=1$ ，但 $N_q=0$ ；“没人排队”和“系统空了”是两种状态。

第一个 M 指指数到达间隔，第二个 M 指指数服务时间，1 指一个服务台。服务的无记忆性使当前人数足以决定接下来的变化。若服务每次固定需要三分钟，那么“这一位刚开始服务”和“已经服务了两分半”即使人数相同，下一次离开的机会也不同，只记人数便不够了。

从人数写出生成矩阵

有 $n\ge1$ 人时，下一次到达的速率是 $\lambda$ ，下一次服务完成的速率是 $\mu$ 。队里有十个人，也只有一个人在接受服务，总离开速率仍是 $\mu$ ，不是 $n\mu$ 。

因此非零的生成矩阵元素为

q_{n,n+1}=\lambda\quad(n\ge0),\qquad q_{n,n-1}=\mu\quad(n\ge1),

q_{00}=-\lambda,\qquad q_{nn}=-(\lambda+\mu)\quad(n\ge1).

在状态零没有服务完成事件。每行的和为零，而所有离开速率不超过 $\lambda+\mu$ ，所以第五章的有界速率论证排除了有限时间内的无穷次跳变。

人数状态链：向右一次到达，向左一次服务完成；零状态没有向下转移

短时间 $h$ 内， $n\ge1$ 时有

p_{n,n+1}(h)=\lambda h+o(h),\qquad p_{n,n-1}(h)=\mu h+o(h),

p_{nn}(h)=1-(\lambda+\mu)h+o(h).

在零状态，应改为 $p_{00}(h)=1-\lambda h+o(h)$ 。这些式子描述短时间终点的状态，不表示在任意长度的区间内只能发生一次事件。

到达使人数增加一，服务完成使人数减少一；图中 Q(t) 表示本章的系统人数 N(t)

平稳概率为什么要求服务能力严格富余

令 $\rho=\lambda/\mu$ 。假设存在平稳分布 $p_n$ ，先把相邻状态之间的概率流算清楚。零状态的平衡给出

\lambda p_0=\mu p_1.

内部状态满足

\lambda p_{n-1}+\mu p_{n+1}=(\lambda+\mu)p_n\quad(n\ge1).

把第二式重排为

\lambda p_n-\mu p_{n+1} =\lambda p_{n-1}-\mu p_n.

也就是说，每条边的净流相同。第一条边的净流已经是零，所以所有边都有

\lambda p_n=\mu p_{n+1},\qquad p_{n+1}=\rho p_n.

这不是凭图形猜出的候选关系，而是从零边界和全部平衡方程递推得到的。

内部状态 n≥1 的相邻转移；乘上各出发状态的概率，才能得到概率流

由 $p_n=p_0\rho^n$ 和归一化，

1=p_0\sum_{n=0}^{\infty}\rho^n.

当 $\rho\ge1$ 时， $p_0>0$ 会让总和发散；取 $p_0=0$ 又会使全部概率为零。因而不存在平稳概率分布。只有时得到

\boxed{p_n=(1-\rho)\rho^n,\qquad n=0,1,2,\ldots.}

它确实是不变分布：取统一时钟速率 $r=\lambda+\mu$ ，则 $R=I+Q/r$ 为随机矩阵；逐项平衡给 $pR=p$ ，从而 $p R^{}$ 。第五章的 Poisson 加权表示于是给。这里的速率一致有界，统一时钟构造也适用于这个可数状态空间。

几何平稳分布在 ρ 小于一时能够归一化，尾概率为 ρ 的相应幂

对这个不可约生灭模型， $\lambda<\mu$ 是通常所说的稳定条件。下面所有标为“稳态”的公式都带着这个条件。若系统刚从空状态启动，有限时刻的分布和一段模拟的平均值，不必等于稳态值。

只做流量检查会得到较弱的 $\lambda\le\mu$ ：稳定时到达率等于离开率，后者不超过服务能力。等号究竟能不能取，必须再检查归一化； $\lambda=\mu$ 恰好就是不能漏掉的临界情形。它没有平稳概率分布，但这也不意味着每条样本路径都单调上升。

人数的均值和尾部

由几何尾和，整数 $k\ge0$ 时

\mathbb P(N\ge k)=\sum_{n=k}^{\infty}(1-\rho)\rho^n=\rho^k.

把非负整数变量写成指示函数之和，得到平均系统人数

L=\mathbb E N=\sum_{k=1}^{\infty}\mathbb P(N\ge k) =\boxed{\frac{\rho}{1-\rho}}.

忙碌概率为 $\mathbb P(N>0)=\rho$ ，所以

\boxed{L_q=\mathbb E N_q=L-\rho=\frac{\rho^2}{1-\rho}.}

不能从 $L$ 中一律减去一。窗口并非始终忙碌，平均在服务台上的人数是 $\rho$ ；这是把逐时刻等式 $N=N_q+I$ 取期望的结果。

一位顾客从到达到离开

用 $a_i$ 表示第 $i$ 位顾客的到达时刻， $s_i$ 表示其服务时长， $b_i$ 表示开始服务的时刻，表示离开时刻。系统初始为空，按到达顺序编号。先到先服务意味着

b_i=\max(a_i,d_{i-1}),\qquad d_i=b_i+s_i.

第一位直接取 $b_1=a_1$ 。他的排队时间与系统停留时间分别为

v_i=b_i-a_i,\qquad w_i=d_i-a_i=v_i+s_i.

若记相邻到达间隔 $x_i=a_i-a_{i-1}$ ，则

v_i=\max(v_{i-1}+s_{i-1}-x_i,0).

前一位还没离开，就等剩下的这段；前一位早已离开，就直接开始服务。这个递推不要求服务时间是指数分布，给定记录即可逐人计算。

三位顾客的完整记录

到达时刻为 $1,2,4$ 分钟，服务时长为 $3,2,1$ 分钟。计算结果是

顾客	到达 $a_i$	服务 $s_i$	开始 $b_i$	离开

第二位在 $t=2$ 到达，但窗口要到 $t=4$ 才空出来，因此排队两分钟。第三位到达时，第一位恰好离开，第二位已经排在前面，仍要等到 $t=6$ 。这份记录的总系统停留时间是十人·分钟，总排队时间是四人·分钟。

Little 定律：先把同一块面积认出来

顾客 $i$ 在 $[a_i,d_i)$ 占据系统一个位置。因此

N(t)=\sum_i\mathbf1_{\{a_i\le t<d_i\}}.

在任意观察窗 $[u,T]$ 内积分，得到精确恒等式

\boxed{\int_u^T N(t)\,dt =\sum_i\bigl[\min(d_i,T)-\max(a_i,u)\bigr]_+.}

右边每一项是该顾客的停留区间与观察窗重叠的长度。按时刻数人数，和按顾客数他在窗口内占了多久，计算的是同一块面积。它对每一份记录成立，不需要等待模拟误差消失，也不要求 Poisson 到达。

逐顾客截取到观察窗内的停留，与系统人数曲线的面积严格相等

回到三位顾客。若观察到 $T=7$ ，所有停留都完整包含在窗内，面积为 $3+4+3=10$ 。若只看到 $T=5$ ，三段在窗内的长度是 $3,3,1$ ，面积只有七人·分钟。从人数曲线看，同样是

\int_0^5N(t)\,dt=1\times(2-1)+2\times(5-2)=7.

时刻四同时一进一出，人数不变。第二、三位在五分钟以后还要分别停留一、两分钟，正好解释完整总停留十与窗口面积七之间的差三。

从有限窗走到长期关系

为了看清条件，先假设初始为空，并考虑 $T>0$ 且已经有顾客到达的窗口。记 $A(T)$ 为截至 $T$ 的到达数，并用这些顾客的完整系统停留时间定义

\overline W_T=\frac1{A(T)}\sum_{a_i\le T}w_i.

这里包括观察窗结束时尚未离开的顾客，他们的完整 $w_i$ 需要继续观察才能知道。令

R(T)=\sum_{a_i\le T<d_i}(d_i-T)

为这些顾客尚在窗外的停留总长，则精确地有

\frac1T\int_0^TN(t)\,dt =\frac{A(T)}T\,\overline W_T-\frac{R(T)}T.

如果长期到达率 $A(T)/T\to\lambda_{\mathrm{eff}}$ ，每位到达顾客的平均完整停留 $\overline W_T\to W<\infty$ ，且边界项，就得到

\boxed{L=\lambda_{\mathrm{eff}}W.}

若开始观察时已有顾客，还会有左边界贡献，也要保留在有限窗恒等式中，并在取长期极限时说明其归一后消失。“时间很长”本身不是删掉边界项的理由。

一种能够保证这些长期平均的情形是再生系统：相继到达空系统的时刻形成独立同分布周期，每周期时长、人数和总停留面积都可积。设它们为 $X,C,H$ 。完整周期中，人数曲线面积就是这 $C$ 位顾客的停留总和；第七章的周期平均给出

L=\frac{\mathbb E H}{\mathbb E X},\qquad \lambda_{\mathrm{eff}}=\frac{\mathbb E C}{\mathbb E X},\qquad W=\frac{\mathbb E H}{\mathbb E C}.

于是 $L=\lambda_{\mathrm{eff}}W$ 。任意终点的部分周期，可夹在相邻完整周期的非负累计量之间；可积性使两边除以总时间后有相同极限。这也解释了为什么 Little 定律能适用于比 M/M/1 更广的系统，却不能把任意一段短窗的两个不同统计口径直接画上等号。

把顾客区间换成 $[a_i,b_i)$ ，同样得到排队部分的关系

\boxed{L_q=\lambda_{\mathrm{eff}}W_q.}

$W$ 和 $W_q$ 在这里都是平均时间，单个顾客的随机时间仍用 $w_i,v_i$ 表示。

把观察终点从七分钟移到五分钟，先预测哪位顾客的停留会被截短，再检查三段长度和人数面积。移动观察起点，还会出现已经在系统里的顾客。改变某一位的服务时间时，先到先服务递推也会移动后续离开时刻；这时应重新计算整份记录，而不能只把一根线随意拉长。

稳态平均等待与接近临界的代价

稳定、无限容量的 M/M/1 接纳全部到达，因此 $\lambda_{\mathrm{eff}}=\lambda$ 。代入人数公式，

\boxed{W=\frac{L}{\lambda}=\frac1{\mu-\lambda}},\qquad \boxed{W_q=\frac{L_q}{\lambda}=\frac{\lambda}{\mu(\mu-\lambda)}}.

还可用单个顾客的时间分解核对：

W=W_q+\frac1\mu.

以下四个量的名称和单位要一起保留。

统计对象	平均人数	每位顾客的平均时间
整个系统，含服务	$L=\rho/(1-\rho)$	$W=1/(\mu-\lambda)$
只看排队	$L_q=\rho^2/(1-\rho)$

例如到达每小时八人、服务每小时十人时， $\rho=0.8$ ，系统平均四人，其中排队平均 $3.2$ 人。平均系统停留半小时，排队 $0.4$ 小时，也就是二十四分钟。剩下的六分钟是平均服务时长； $3.2=8\times0.4$ 和 $4=8\times0.5$ 分别核对两个统计对象。

开头的午餐窗口取 $\lambda=2,\mu=2.4$ ，单位为每分钟。平均系统人数为五人，平均停留 $2.5$ 分钟。若到达增为每分钟 $2.39$ 人，服务能力保持不变，平均系统人数变成 $239$ ，平均停留变成一百分钟。两种情形都满足稳定条件，体验却相差很远。这个数也提醒我们：真实窗口若有放弃排队、有限座位或到达率随时间变化，就需要修改模型，而不能继续把无限容量稳态公式当作实测保证。

到达的顾客看见什么

上面的 $p_n$ 描述按时间观察的稳态人数。顾客到达前看到的分布是否也相同，需要另一个理由。

Poisson 到达的未来增量与当前系统状态独立。在一小格 $(t,t+h]$ 内，“格首为 $n$ 且发生一次到达”的概率为 $p_n\lambda h+O(h^2)$ 。如果格首状态与到达前状态不同，该小格内至少还发生过另一次事件；总速率有界，使这种差异只有。因此看到状态的到达强度是。所有到达的强度为，相除后，稳态到达者在看到的概率就是。这称为 Poisson 到达看见时间平均的性质。

这一步使用了外生 Poisson 到达与服务的独立性。若顾客总等系统空了才进入，到达者看到空系统的比例可以是一，而系统的空闲时间比例未必是一。一般到达不能自动使用相同结论。

平均值以外，等很久的概率

记一位稳态到达顾客的随机系统停留为 $V$ 。若他到达前看到 $n$ 人，按先到先服务，需要等前面 $n$ 人服务完，再完成自己的服务。正在服务者的剩余时间仍为 $\operatorname{Exp}(\mu)$ ，之后的服务也独立同分布，因此

V\mid\{\text{到达前有 }n\text{ 人}\} \sim\operatorname{Erlang}(n+1,\mu).

利用第六章的 Erlang 密度，对 $t>0$ 求混合：

\begin{aligned} f_V(t) &=\sum_{n=0}^{\infty}(1-\rho)\rho^n \frac{\mu^{n+1}t^n e^{-\mu t}}{n!}\\ &=\mu(1-\rho)e^{-\mu t} \sum_{n=0}^{\infty}\frac{(\rho\mu t)^n}{n!}\\ &=(\mu-\lambda)e^{-(\mu-\lambda)t}. \end{aligned}

所以 $V\sim\operatorname{Exp}(\mu-\lambda)$ ，其均值再次给出 $W=1/(\mu-\lambda)$ 。这也从分布直接确认了等待均值有限。

只算排队的随机时间 $V_q$ 时，看到空系统就不用等，故 $\mathbb P(V_q=0)=1-\rho$ 。看到人时要等个指数时间，正半轴上的密度为

\begin{aligned} f_{V_q}(t) &=\sum_{n=1}^{\infty}(1-\rho)\rho^n \frac{\mu^nt^{n-1}e^{-\mu t}}{(n-1)!}\\ &=\rho(\mu-\lambda)e^{-(\mu-\lambda)t},\qquad t>0. \end{aligned}

其积分只有 $\rho$ ，另外的概率在零点。相应地，对 $t\ge0$ ，

\mathbb P(V>t)=e^{-(\mu-\lambda)t},\qquad \mathbb P(V_q>t)=\rho e^{-(\mu-\lambda)t}.

因此“是否需要排队”的概率是 $\rho$ ，但“排队时间是参数 $\mu-\lambda$ 的指数变量”并不准确；只有条件在确实需要等待时，才得到这个指数分布。

对于每小时八人、十人的例子，停留超过一小时的概率是 $e^{-2}\approx0.1353$ ，排队超过一小时的概率是 $0.8e^{-2}\approx0.1083$ 。求百分之九十的顾客能在多久内离开，要解 $1-e^{-2t}=0.9$ ，得到小时。半小时的平均停留并不意味着绝大部分顾客都能在半小时内离开。

固定服务率，逐渐把到达率推近它，比较人数路径、时间占比和稳态预测。延长同一条路径时，已经发生的到达与服务记录应保留下来；窗口末端必须截在你选定的时刻。再将到达率与服务率一起加倍：稳态人数分布不变，时间尺度缩短一半。有限样本可能偏离理论值，尤其接近临界时，要留意启动状态和观察长度。

容量有限以后，进入率需要重算

若系统最多容纳 $K\ge1$ 人， $K$ 为整数，其中包括正在服务的一位，到达时已满的顾客被拒绝，则状态变为 $0,1,\ldots,K$ 。在 $K$ 处没有向 $K+1$ 的跳转；被拒绝的尝试不会改变人数。

相邻平衡仍给 $p_{n+1}=\rho p_n$ ，但归一化的总和现在是有限的：

\boxed{p_n=\frac{\rho^n}{\sum_{j=0}^K\rho^j},\qquad0\le n\le K.}

所有正的 $\lambda,\mu$ 都可归一化。特别地， $\rho=1$ 时各状态概率均为 $1/(K+1)$ ，不应把它代进含 $1-\rho$ 的无限容量公式。

Poisson 到达在进入前看到满载的概率为 $p_K$ ，所以接纳率与拒绝率是

\lambda_{\mathrm{eff}}=\lambda(1-p_K),\qquad \lambda_{\mathrm{reject}}=\lambda p_K.

从服务一侧也能核对：服务台忙碌概率为 $1-p_0$ ，离开率为 $\mu(1-p_0)$ 。把各边平衡相加，恰好得到

\lambda(1-p_K)=\mu(1-p_0).

这时 $\rho$ 可以大于一，却不能被解释成忙碌比例。Little 定律中的 $W$ 若指被接纳顾客的平均停留，对应流量必须是 $\lambda_{\mathrm{eff}}$ 。

有限容量要区分尝试、接纳和拒绝；顾客平均时间必须使用同一群人的有效流量

例：一个服务位，加两个等待位

设每小时尝试到达五人，服务率为每小时四人， $K=3$ 。 $\rho=5/4$ ，把权重 $1,5/4,25/16,125/64$ 同乘六十四，得到

(p_0,p_1,p_2,p_3)=\frac1{369}(64,80,100,125).

接纳率为

\lambda_{\mathrm{eff}}=5\left(1-\frac{125}{369}\right) =\frac{1220}{369}\approx3.306\text{ 人/小时}.

服务一侧给 $4(1-64/369)=1220/369$ ，两者相同。平均系统人数为

L=\frac{80+2\cdot100+3\cdot125}{369}=\frac{655}{369}.

所以被接纳顾客的平均停留为

W=\frac{L}{\lambda_{\mathrm{eff}}} =\frac{131}{244}\text{ 小时}\approx32.21\text{ 分钟}.

若误除以原始到达率五，就把没有进入系统的人也算进了顾客平均。另一个检查是减去十五分钟的平均服务： $W_q=70/244$ 小时，约 $17.21$ 分钟，与 $L_q/\lambda_{\mathrm{eff}}$ 一致，其中。

练习

1．从人数判断下一次变化

系统内有四人，一台服务台， $\lambda=3,\mu=5$ ，单位为每分钟。求下一次人数变化的平均等待，以及变化为离开的概率。若当前为空，两项如何改变？

2．人数的尾概率

仍取 $\lambda=3,\mu=5$ 。求稳态空闲概率、系统至少两人的概率、队列至少两人的概率。最后两项为什么不同？

3．把记录重新算一遍

顾客到达于 $0,1,5$ 分钟，服务时长为 $2,4,1$ 分钟。求开始、离开、排队时间，并求观察窗 $[0,6]$ 内系统人数与排队人数曲线的面积。

4．短窗数据不足

十分钟内人数曲线面积为二十四人·分钟，窗内恰有六位顾客完成了从到达到离开的完整停留。仅凭这些信息，能否确定这六人的平均停留为四分钟？需要补充什么？

5．两侧都有截取

某系统的三段停留区间是 $[-2,3)$ 、 $[1,6)$ 、 $[4,9)$ ，观察窗为 $[0,5]$ 。求窗口人数面积，并说明为什么完整停留总和不能直接使用。

稳定的无限容量 M/M/1 中，从平均系统人数 L 得到平均排队人数 Lq 应减去什么？

Little 定律的有限窗面积恒等式只有在 λ<μ 且观察时间足够长时才精确成立。

无限容量 M/M/1 在 λ=μ 时，由于平均到达率和服务能力相等，仍有可归一化的平稳分布。

9．同比加速与增加一个服务台

比较 $(\lambda,\mu)=(4,6)$ 与 $(8,12)$ 的两个 M/M/1，单位为每小时。哪些稳态人数指标不变，时间指标怎样变化？若改成两个各以速率六服务的窗口，能否把它当作一个速率十二的 M/M/1？

10．等待的概率与平均

稳定 M/M/1 取每小时 $\lambda=4,\mu=6$ 。求无需排队的概率、排队超过十五分钟的概率，以及系统停留的百分之九十分位数。

11．从目标反推服务率

每小时到达九人。希望稳定 M/M/1 的平均系统停留不超过十二分钟，并且系统内至少五人的概率不超过 $0.1$ 。写出两个条件，求应选择的最低服务率。

12．有限容量的临界比值

只有一个服务位和一个等待位， $\lambda=\mu=2$ ，单位为每小时。求稳态分布、接纳率、忙碌比例、平均系统人数与被接纳顾客的平均停留。

13．到达观察不总等于时间观察

每隔两分钟固定来一位顾客，每位服务恰好一分钟，系统从空开始。顾客到达前看到忙碌的长期比例是多少？按时间观察的忙碌比例是多少？这是否与 Little 定律矛盾？

14．不要从跳变记录直接平均人数

某段精确记录中，人数在 $[0,8)$ 为零，在 $[8,9)$ 为一，在 $[9,10]$ 为二。求这十分钟的平均系统人数。把三个状态值 $0,1,2$ 等权平均会发生什么？

k

=

p

pR^k=p

d_i