Skip to content

定理Theorem

Pollaczek–Khinchine 平均等待公式

施工中 · 内容逐步修订

Pollaczek-Khinchine mean formula

在稳定 M/G/1 队列中,将平均等待分解为剩余服务与前方顾客工作量,显出二阶矩效应。

形式陈述 ​

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

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

EWq=λES22(1−ρ),EW=b+λES22(1−ρ).

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

直觉

新顾客要先等当前服务者做完剩余工作,再等队列中排在自己前面的顾客。当前服务的剩余时长会被长度偏倚放大:观察时刻更容易落在长服务里。这正是检查悖论进入排队公式的位置。把剩余服务和前方工作量取期望之前,还需分别说明平稳观察、到达观察以及均值有限性的依据。

先建立平稳版本和截断均值 ​

在整条实线上取平稳 Poisson 到达点,并为各点独立附上服务标记。负漂移 λb<1 使从过去累积的净工作量向 −∞ 趋去;Lindley 页的过去上确界因而有限。按先来先服务从这份过去记录构造队列,给出平稳等待;同一构造与时间平移相容,因而整个队列状态过程也平稳。负漂移还使确定观察时刻的当前忙期只能开始于有限过去;有界窗口内到达有限,所以当时排队人数有限,每位顾客的等待和完成时刻均几乎必然有限。这些结论不先要求等待的期望有限。

先把服务截断为 S(M)=S∧M,M>0,负载仍小于一。独立到达间隔 A∼Exp(λ) 给净增量 Y(M)=S(M)−A。其矩母函数在零附近有限,且在零点的导数为 EY(M)<0,所以可选 θ>0 使 rM=EeθY(M)<1。对 Lindley 页的反向上确界,并集界与Markov 不等式给出 x>0 时

P(Wq(M)>x)≤e−θx∑k≥1rMk=e−θxrM1−rM.

积分尾界证明截断模型的到达顾客平均等待有限。下面先对这个有界服务模型证明均值等式,暂略去上标 (M);最后再去掉截断。这样不会在无穷均值之间移项。

服务开始的强度与时间观察的剩余量 ​

记第 i 位顾客的到达、开始服务时刻为 ai,ci=ai+Wq,i,服务标记为 Si。Little 定律页的平稳标记计数测度给出到达与联合标记 (Wq,S) 的期望测度 λdaG(dw,ds)。其中 G 的服务边缘分布仍为原来的 S。对非负可测 g,Tonelli 定理和时间平移换元给出

E∑0<ci≤Tg(Si)=λ∫R∫1{0<a+w≤T}g(s)G(dw,ds)da=λTEg(S).

只用每个 w 有限便可完成内层时间积分,不需要 EWq<∞,也不需要服务开始点构成更新过程。

令 R 为平稳时刻正在执行的服务的剩余时长,空闲时置零;忙时该服务总长为 L、已服务时间为 A。将上述服务开始点的强度与每段服务的占用区间结合,对任意非负可测 φ 有

E[1{忙}φ(L,A)]=λ∫[0,∞)∫0sφ(s,a)daP(S∈ds).

取 φ=1 得忙概率 λb,再除以它,便得到条件忙时的长度律 sP(S∈ds)/b,且给定长度 s>0 后,所处阶段在 [0,s] 上均匀。零时长服务不占用时间。这个长度—阶段观察律与以 S∣S>0 为间隔的平稳更新过程相同,所以检查悖论的剩余时间公式在这里也成立;直接取 φ(s,a)=s−a 则给

ER=λ∫s22P(S∈ds)=λES22.

不预知未来的到达为何看见相同分布 ​

这里的 PASTA 需要过程级的不预知条件:对包含过去到达与已到达顾客独立服务标记的历史 Ft,未来 Poisson 增量独立于 Ft。队列只按这份历史运行。不能仅凭到达间隔的边缘分布就使用 PASTA,也不能拿到达者已加入后的状态作比较。

其期望版本可直接证明。记 N(t) 为 (0,t] 内的到达数。若 H(t) 是有界、左连续、适应于 Ft 的观察量,把 (0,T] 分成确定小区间,并在 (tk,tk+1] 使用 H(tk)。未来增量独立性给出

E∑kH(tk)[N(tk+1)−N(tk)]=λ∑k(tk+1−tk)EH(tk).

网格趋细时,左连续性使左侧逐条记录趋于 ∑0<ai≤TH(ai)。若 |H|≤C,其绝对值受 CN(T) 控制,且 EN(T)=λT<∞;右侧由 C 控制。用控制收敛定理得到

E∑0<ai≤TH(ai)=λ∫0TEH(t)dt.

在平稳版本中,右侧等于 λTEH(0)。取到达前状态左极限的有界连续测试函数,就说明到达前观察与平稳时间观察同分布;非负无界观察量再由截断和单调收敛处理。队列在有限窗口内只有有限次到达和服务完成(零时长服务也只涉及有限个在场顾客),因此这里所需的左极限观察过程确实存在。

前方工作量与合法移项 ​

令 Nq(0) 为时刻零尚未开始服务的人数,B(0) 为这些顾客的完整服务时长之和。先来先服务下,本顾客等待 Wq,i 只由更早顾客及到达记录决定,独立于自己的 Si。再用平稳标记测度和 Tonelli,

EB(0)=λEarr(SWq)=λbEarrWq=bENq(0),ENq(0)=λEarrWq.

第二个恒等式也是等待区的 Little 定律。这一步并未假设“从队列随便选一人”的服务标记没有选择偏差,而是以到达顾客的 Wq⊥S 明确计算所需的占用加权均值。

到达前总工作量为 R+B,恰是新顾客的排队等待。PASTA 因而给出

EarrWq=ER+bLq,Lq=λEarrWq.

对当前有界服务模型,前面已证明 EarrWq<∞,其余各项也有限,所以可以移项,得到

EarrWq=λES22(1−λb).

以下省略到达均值的上标,与形式陈述的 EWq 一致。

去掉服务截断 ​

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

EWq=limM→∞λE(S∧M)22(1−λE(S∧M))=λES22(1−ρ).

有限二阶矩时右边有限;二阶矩无穷时则为 +∞,而分母仍严格为正。最后逐位顾客有 W=Wq+S,取非负期望便得总逗留时间公式。

例子与边界

固定平均服务时间 b 和负载 ρ∈(0,1)。若服务时间恒为 b,则 ES2=b2,

EWqdeterministic=ρb2(1−ρ).

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

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

稳定性 ρ<1 只保证工作量不持续逃向无穷,不保证平均等待有限。例如服务尾部满足 ES<∞、ES2=∞,仍可选足够小的 λ 使系统稳定,但 EWq=∞。

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

推论与应用

公式可写成 EWq=ρb(1+cs2)/(2(1−ρ)),其中 cs2=Var(S)/b2。它把减少服务波动与降低负载的作用分别显出,同时提醒:这只是平均值,无法据此承诺等待的尾部百分位。

参考资料
关系图谱28 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系