平均负荷不足以描述排队
即使平均到达率低于服务率,服务站仍可能排队,因为到达及服务完成并非完全定时。模型可以量化这种波动,但结论依赖明确的假设。
定义 8.3.1
(M/M/1 排队及其交通强度)
顾客按速率 的 Poisson 过程到达,服务时间是速率 的独立指数随机变量,到达与服务相互独立。一个服务台在系统非空时持续工作,按先到先服务次序服务;等候空间无限,顾客不会中途离开。令 为等候及正在接受服务的顾客数。它是一条连续时间 Markov 链,从 以速率 跳到 ,从 以速率 跳到 。交通强度是 。
稳态平衡
定理 8.3.2
(M/M/1 排队的稳态分布)
若 ,队长链有唯一的稳态分布
若 ,则不存在稳态概率分布。
证明
(平衡方程强制几何分布)
稳态分布 必须平衡总流量。在零状态,;在 ,
零状态方程给出 。若对某个 有 ,从第 个方程减去它,便剩下 。由归纳,对所有 有 ,因此任何稳态分布都须有 。
若 ,归一化给出 ,故 。反过来,这些概率之和为一并满足平衡方程。对此不可约、无爆炸的生灭链,归一化的不变分布是唯一稳态分布;这里使用这个标准的连续时间 Markov 链结果。
若 ,被强制的序列 之和发散,除非 ,而此时每个 。两者都不能和为一,所以不存在稳态概率分布。这是稳态陈述,并不是说每次有限观察中队伍每时每刻都必然增长。
证明透视
从每个状态一条总方程到每条边一条割方程
不显然的一步是归纳:它把每条总流量方程化为更简单的陈述,即从 上升到 的流量等于从 下降到 的流量。这之所以可行,是因为链只在相邻状态之间跳动: 与 之间的割恰好被一个向上转移和一个向下转移穿过。割方程一旦成立,几何形式便随即得出。
假设 只在一处使用,就是归一化。平衡方程本身对每个 都成立; 时失败的是:被强制的序列不能成为概率分布。唯一性并未在此证明,它来自不可约性与无爆炸性,经引用的 Markov 链结果得到。把 代入公式会给出 ,这表明假设被违反,而不是出现了负概率。
平均人数与服务能力比较
定理 8.3.3
(稳态平均数)
当 ,在稳态下
其中 只计等待者。
证明
(对几何分布求和)
对 求导得 ,所以
服务台繁忙恰在 时,概率为 。由于 ,得 。
这些是稳态平均数,不是容量上限,也不是某一时刻的保证。
例题 8.3.4
(稳定的服务站)
若每小时 、,则 、。系统平均人数为 ,等候的平均人数为 。繁忙概率为 不代表系统每时每刻恰有两人。
例题 8.3.5
(比较两个服务率)
假设某个示范成本模型每小时按 收取服务能力成本,并按系统内每名平均顾客收取三个成本单位。固定 ,只比较 和 。当 ,、。总成本率分别是 和 ,故 在这两个选项中较好。能力成本公式是明确的建模假设,不是普遍的人员配置定律;此比较不能证明其他服务率之间的最优性。
例题 8.3.6
(接近临界的负荷)
保持 ,把到达率提高到 。则 ,而
到达率从 增至 ,只增加百分之四十五,平均人数却乘以 。当 趋近一,稳态平均数无界增长;到 时便不存在稳态分布。
常见错误
反例模式
有限平均数不能界定每次观察
在到达率为 2、服务率为 3 的服务站中,每个稳态概率都是正数。稳态平均人数为二,但观察到至少三人的概率是几何尾概率 。不能把平均人数说成队伍人数上限。
常见错误
(在 时使用稳定公式)
若 、,公式 给出 名顾客。这个数字没有意义:定理的假设 不成立,根本没有可供平均的稳态分布。
常见错误
(混淆系统内人数与等候人数)
包括正在接受服务的顾客, 则不包括。在稳定服务站中两者分别是 与 。差额是繁忙概率 ,而不是 ,因为服务台有 的概率空闲。
练习
快速检查
(若 、,求 、 和 。)
解答 · 答案
、、。
快速检查
(在 、 的稳定服务站,求稳态下的 。)
解答 · 答案
几何尾和为 。
快速检查
(解释为什么此模型中 没有稳态概率分布。)
解答 · 答案
时,平衡强制每个 。常数非负序列之和为 或发散,永远不会等于一。
快速检查
(若 、,求稳态繁忙概率和平均等候人数。)
解答 · 答案
,故繁忙概率为 ,。