为什么要有多个服务台
“稳态单服务台排队”一课推导了 M/M/1 系统的人数分布。实际的服务系统常有多个相同的服务台,而一个核心的设计问题是延迟如何随服务台数目变化。本单元把 M/M/1 一课的生灭平衡论证推广到 个服务台,并加入 Little 定律,用它在平均顾客数与平均逗留时间之间换算。假设与前相同:到达间隔与服务时间均为指数分布,没有顾客中途离开,等待空间无限。
模型与定义
定义 8.8.1
(M/M/c 排队)
顾客按速率 的 Poisson 过程到达。共有 个相同的服务台;每个服务时间是速率 的指数随机变量,所有随机变量相互独立。顾客按先到先服务的次序受理,若所有服务台都忙,到达的顾客须等待。令 为系统内的顾客数(包括等待及正在接受服务者)。则 是连续时间生灭链,每个状态的出生率均为 ,状态 的死亡率为 ,因为只有 个服务台在工作。
定义 8.8.2
(提供负荷、利用率与性能指标)
提供负荷是 ,即若服务台不受限制时平均会有多少个在忙;利用率是 。用 表示系统内有 位顾客的稳态概率, 为系统内平均人数, 为平均等待人数,、 则为到达顾客在系统内及在队列中的平均时间。
主要结果
定理 8.8.3
(M/M/c 排队的稳态分布)
稳态分布存在,当且仅当 。此时
证明
(割方程与归一化)
稳态的生灭链在 与 之间的割上,两个方向的概率流相等:。因此 。当 时乘积为 。当 时,每多一项因子为 ,得 。
这些权重可求和,当且仅当 收敛,即 ;此时 是它们之和的倒数,即所述公式,而割方程蕴含平衡方程。若 ,权重不可求和,不存在稳态分布。
定理 8.8.4
(Erlang C 等待概率与平均队长)
若 ,到达顾客须等待的概率是 Erlang C 量
平均队长为
证明
(尾部求和与看到时间平均的到达者)
第一式是对稳态分布的几何尾部求和:。Poisson 到达流所见的系统处于稳态分布(PASTA 性质),故到达者恰在 时须等待,概率为 。至于 ,令 :
其中用到 。
证明透视
Erlang C 公式背后的两种平均
证明中有两个看似相同、平均方式却不同的量。 时 之和是时间平均:所有服务台都忙的时间比例。等待概率则是顾客平均:到达时发现所有服务台都忙的顾客比例。把两者等同的唯一一步是 PASTA 性质,这也是除了生灭结构之外唯一用到 Poisson 到达的地方。相比之下,队长公式自始至终都是时间平均,不需要这一步;它只是对几何尾部的代数运算,而几何尾部之所以存在,是因为 。
定理 8.8.5
(Little 定律)
设系统处于稳态,顾客以长期速率 进入,且各长期平均存在。若 为系统内顾客数的时间平均, 为顾客在系统内逗留的平均时间,则 。对单独的等待队列同样有 。
证明
(面积论证(概要))
在长时段 内,积分 等于各顾客在系统内逗留时间之和,只差相对于 可忽略的边界项。若约有 位顾客进入,则总和约为 。除以 即得 。此论证适用于任何顾客集合及任何子系统,特别是队列。边界项的严格控制留待以后处理。
由于每位顾客的平均服务时间为 ,有 ;对服务台应用 Little 定律,得 。当 ,公式化为 M/M/1 的结果:,,。
例题
例题 8.8.6
(两个服务台)
设 ,,(每小时)。则 ,。归一化常数为 ,故 。于是 ,而 时 ;验算:。等待概率为 。于是
验算:。
例题 8.8.7
(合并服务台与分开排队)
把上面的两服务台系统与两个各自独立的单服务台队列比较,各接收一半的到达:,,。每个队列 ,由 Little 定律 小时;合并系统(总服务能力相同)则为 小时。分开排队时,顾客可能在另一个服务台空闲时仍在等待;合并排队消除了这种情况。
例题 8.8.8
(增设第三个服务台)
取 ,,:,,。则 ,故 。因此 ,, 小时, 小时,。验算 成立。第三个服务台使平均等待从 小时降至 小时。
常见错误与细微之处
常见错误
(用 而不是 判断稳定性)
当 、,提供负荷 ,但两服务台系统仍然稳定,因为 。事实上 正是稳定条件;当 , 是充分而非必要的。
常见错误
(混淆 与 )
也包括正在接受服务者,M/M/c 中 。在两服务台例子中 ,但 ;用错其中一个除以 ,便会把 当成 。
常见错误
(有顾客被拒绝时仍用原到达率套用 Little 定律)
Little 定律使用的是实际进入系统的顾客速率。若有部分到达者被拒绝, 必须换成进入速率;沿用原到达率会低估 。
反例模式
没有 Poisson 输入时,到达者未必看到时间平均
声称:在任何稳定的单服务台队列中,到达者须等待的概率等于服务台忙碌的时间比例。取在时刻 0、1、2 等定时到达的顾客,每次服务都历时半小时。服务台有一半时间在忙,但每位顾客都在下一位到达前半小时离开,所以从没有到达者需要等待。等待概率是 ,而不是 。Erlang C 的等同需要 Poisson 到达,因为 Poisson 到达者看到的是稳态分布。
稳态分布及 Erlang C 公式依赖指数服务时间;Little 定律则不依赖。与分开排队的比较只在总到达率相同、服务台相同的前提下成立,而且只比较平均值。
习题
练习 8.8.9
(当 ,,(每小时),计算 、、 与 。)
基础
解答(3)
- 1
计算负荷与
,。则 ,故 。
- 2
套用 Erlang C 公式
,。
- 3
用 Little 定律换算
小时, 小时,。验算:。
练习 8.8.10
(当 ,(每小时),求使稳态分布存在的最少服务台数目,以及此时的利用率。)
基础
解答(2)
- 1
写出稳定条件
稳定性要求 ,即 。
- 2
取最小整数
故 ,此时 。若 ,则 ,不存在稳态分布。
练习 8.8.11
(某稳定系统平均有 位顾客,每小时有 位顾客到达。求 。若平均服务时间为 小时,求 与 。)
核心
解答(2)
- 1
对整个系统用 Little 定律
小时。
- 2
减去服务时间,再对队列用 Little 定律
小时,。
练习 8.8.12
(对 、 的系统,列出 并计算 。)
核心
解答(2)
- 1
列出稳态概率
由于 ,,,而 时 。总和为 。
- 2
对几何尾部求和
,所以 。