“这是 Pollaczek–Khinchine 的均值公式,本页不把它与完整分布的变换公式混同。它适用的等待逐位满足Lindley 递推。”
形式陈述
服务时间不服从指数分布时,当前人数不能完整预测未来;但在每位顾客到达时记录已有工作量,就能得到一个简单而精确的递推。
考虑无限容量、先来先服务、无中断且有任务就工作的单服务台。输入是按到达次序排列的序列
递推本身不需要独立性。若到达间隔构成更新过程,服务时长 IID 且与到达独立,就得到常见 GI/G/1 模型。设均值有限,则
直觉
下一位到来之前,服务者最多能消化
令
每个后缀和代表从某位过去顾客起累计的净工作量,取最大值等于找到最后一次空闲以后尚未消化的欠账。对于原来允许的任意
其中
例子与边界
取前三位服务时长为
第二位先于第三位一单位到达,却需服务四单位,所以第三位正好等三单位。第三位及前面欠账合计四单位,距离第四位到来还有五单位,因此队伍在第四位之前清空。计算同时解释了每次截零对应的实际空闲。
实现只保留当前
负漂移的作用可以从反向累积和看见。把 IID 净增量扩成双向序列
几乎必然有限,空和为零。逐项展开就有
若
多服务台、抢占优先级或顾客会放弃时,单个标量不再完整描述未来。需要工作量向量、优先级状态或剩余耐心等信息,不能把原递推当成通用排队公式。
推论与应用
Lindley 递推直接支持仿真,也把稳定性转成随机游走漂移问题。Poisson 到达这一附加结构能将稳态均值化简为Pollaczek–Khinchine 公式;一般更新到达仍能运行本递推,却通常没有同样的简单均值表达式。
参考资料
- Robert G. Gallager, MIT 6.262,Chapter 4, §4.5.3, G/G/1 queue。
- Ward Whitt, 2012,The M/G/1 Queue。