Pollaczek–Khinchine 平均等待公式

形式陈述

两台服务者平均处理速度相同，只是其中一台耗时更不稳定，顾客平均等待会相同吗？M/G/1 的平均等待公式给出精确答案。

假设到达为速率 $\lambda>0$ 的Poisson 过程，服务时长 $S\ge0$ 构成独立同分布序列、与到达独立，采用无限容量单服务台、先来先服务、无放弃且不故意空闲的规则。令服务时长的期望 $b=ES\in(0,\infty)$ 、 $\rho=\lambda b<1$ 。若 $ES^2<\infty$ ，稳态平均排队等待为

EW_q=\frac{\lambda ES^2}{2(1-\rho)},\qquad EW=b+\frac{\lambda ES^2}{2(1-\rho)}.

这是 Pollaczek–Khinchine 的均值公式，本页不把它与完整分布的变换公式混同。它适用的等待逐位满足Lindley 递推。

直觉

新顾客要先等当前服务者做完剩余工作，再等队列中排在自己前面的顾客。当前服务的剩余时长会被长度偏倚放大：观察时刻更容易落在长服务里。这正是检查悖论进入排队公式的位置。

令 $R$ 为平稳时刻正在执行的服务的剩余时长，空闲时置零。把服务区单独作为 Little 定律的系统，忙的比例为 $\lambda b=\rho$ 。服务区间之间可能夹有空闲时间，长度偏倚应按实际占用时间计算。

具体地，记忙时所处服务的总长为 $L$ 、已服务时间为 $A$ 。按Little 定律页的平稳标记计数测度论证，把每个到达点沿其有限等待时间平移到服务开始点，不改变单位时间强度 $\lambda$ ；其服务标记仍服从原来的 $S$ 分布。对任意非负可测 $\varphi$ ，逐段积分给出

E[\mathbf1_{\{\text{忙}\}}\varphi(L,A)] =\lambda\int_{[0,\infty)}\int_0^s\varphi(s,a)\,da\,P(S\in ds).

取 $\varphi=1$ 得忙概率 $\lambda b$ ，再除以它，便得到条件忙时的长度律 $sP(S\in ds)/b$ ，且给定长度 $s>0$ 后，所处阶段在 $[0,s]$ 上均匀。零时长服务不占用时间。这个长度—阶段观察律与以 $S\mid S>0$ 为间隔的平稳更新过程相同，所以检查悖论的剩余时间公式给出 $E(R\mid\text{忙})=ES^2/(2b)$ ，进而 $ER=\lambda ES^2/2$ ；服务开始时刻本身无须构成更新过程。

这里队列只使用已经发生的到达和独立服务数据，不预知未来 Poisson 增量。在这一不预知条件下，PASTA 将到达前瞬间的状态分布与平稳时间观察的分布对应，所以新到达者看到同一个 $ER$ 和平均排队人数 $L_q$ ；不能把到达者已加入队列后的状态拿来作这个比较。排在前方但尚未服务的每位顾客平均需 $b$ 时间，于是

EW_q=ER+bL_q.

再用Little 定律 $L_q=\lambda EW_q$ ，移项得到 $(1-\rho)EW_q=\lambda ES^2/2$ 。服务时间与其开始前排队状态的独立性在这里保证了每个前方顾客的平均工作量确为 $b$ 。

先证明均值有限，再移项

上面的移项不能在无穷均值之间进行。先截断服务为 $S^{(M)}=S\wedge M$ ， $M>0$ ，负载仍小于一。独立到达间隔 $A\sim\operatorname{Exp}(\lambda)$ 给净增量 $Y^{(M)}=S^{(M)}-A$ 。其矩母函数在零附近有限，且在零点的导数为 $EY^{(M)}<0$ ，所以可选 $\theta>0$ 使 $r_M=E e^{\theta Y^{(M)}}<1$ 。对 Lindley 页的反向上确界，并集界与Markov 不等式给出 $x>0$ 时

P(W_q^{(M)}>x) \le e^{-\theta x}\sum_{k\ge1}r_M^k =e^{-\theta x}\frac{r_M}{1-r_M}.

这证明截断模型的等待均值有限，因而可合法使用前面的均值等式。

让各截断模型共享同一份双向服务与到达序列。每个有限反向和随 $M$ 增加而增加，上确界与递增极限可交换，故 $W_q^{(M)}\uparrow W_q$ 。由单调收敛定理，

EW_q =\lim_{M\to\infty}\frac{\lambda E(S\wedge M)^2} {2(1-\lambda E(S\wedge M))} =\frac{\lambda ES^2}{2(1-\rho)}.

有限二阶矩时右边有限；二阶矩无穷时则为 $+\infty$ ，而分母仍严格为正。

例子与边界

固定平均服务时间 $b$ 和负载 $\rho\in(0,1)$ 。若服务时间恒为 $b$ ，则 $ES^2=b^2$ ，

EW_q^{\rm deterministic}=\frac{\rho b}{2(1-\rho)}.

若服务指数分布且均值仍为 $b$ ， $ES^2=2b^2$ ，等待翻倍为 $\rho b/(1-\rho)$ ，与M/M/1吻合。比较并没有改变平均处理能力，差别完全来自服务波动。

若服务以相等概率取 $b/2$ 与 $3b/2$ ，则均值为 $b$ ，二阶矩为 $5b^2/4$ ，平均等待是确定服务情形的 $5/4$ 倍。这里两点分布提供可以逐项核验的方差效应。

稳定性 $\rho<1$ 只保证工作量不持续逃向无穷，不保证平均等待有限。例如服务尾部满足 $ES<\infty$ 、 $ES^2=\infty$ ，仍可选足够小的 $\lambda$ 使系统稳定，但 $EW_q=\infty$ 。

若到达不是 Poisson，顾客可能系统性地避开或追上忙时，PASTA 这一步失效。先来先服务也很重要：不同优先级会改变谁在谁前面，不能把所有类别的等待直接套进同一个公式。

推论与应用

公式可写成 $EW_q=\rho b(1+c_s^2)/(2(1-\rho))$ ，其中 $c_s^2=\operatorname{Var}(S)/b^2$ 。它把减少服务波动与降低负载的作用分别显出，同时提醒：这只是平均值，无法据此承诺等待的尾部百分位。

参考资料

Ward Whitt, 2012，The M/G/1 Queue, Pollaczek–Khinchine results。
Robert G. Gallager, MIT 6.262，Chapter 4, queueing and residual-service applications。

形式陈述 ​

先证明均值有限，再移项 ​

反向链接

形式陈述

先证明均值有限，再移项