Skip to content

模型Model

M/M/1 排队模型

施工中 · 内容逐步修订

M/M/1 queue

从单服务台的生灭速率推出几何稳态、负载条件与平均等待,区分队内和系统内指标。

形式陈述 ​

为什么服务者平均忙不到百分之百,顾客仍可能等很久?M/M/1 是回答这个问题的最小随机排队模型。

模型假设:到达为速率 λ>0 的Poisson 过程;服务时长独立同分布为速率 μ>0 的指数分布,与到达独立;只有一个服务者,先来先服务,服务者有任务就工作;容量无限,无拒绝、放弃或中断。两处 M 表示无记忆的到达间隔与服务时长,1 表示单服务台。

系统人数 N(t) 包含正在服务的人,是生灭过程:λn=λ,μn=μ 对 n≥1,μ0=0。出发速率不超过 λ+μ,所以链非爆炸。令负载 ρ=λ/μ。当且仅当 ρ<1 时存在平稳概率

πn=(1−ρ)ρn,n≥0.

稳态指标为

L=ρ1−ρ,Lq=ρ21−ρ,W=1μ−λ,Wq=ρμ−λ.

L,W 对整个系统计数和计时;Lq,Wq 只对等待区计数和计时。

直觉

当系统已有很多人时,下一次变化仍是以速率 λ 增加一人、以速率 μ 减少一人。人数多不会让单个服务台变快。若两速率接近,偶尔积累的长队需要很久才能消退。

逐边平衡给出 πn+1=ρπn,所以 πn=π0ρn。几何级数只有 ρ<1 时可归一化,且 π0=1−ρ。服务者忙的概率因而为 P(N>0)=ρ,不是每时每刻都忙相同比例。

由几何级数求导,EN=ρ/(1−ρ)。正在服务的人数是 1{N>0},故 Lq=L−ρ=ρ2/(1−ρ)。在平稳队列中,每位顾客前方人数有限且每段服务几乎必然有限,所以其逗留时间有限。对其平稳标记到达过程应用Little 定律的非负期望恒等式:先由已算出的 L,Lq<∞ 推出对应等待均值有限,再分别除以有效到达率 λ,得到 W,Wq。这没有预先假设所求均值可积,并核验了 W−Wq=1/μ 为平均服务时间。

例子与边界

设 λ=μ/2,即平均负载一半。则 L=1、Lq=1/2,平均总逗留时间 W=2/μ,其中等待 Wq=1/μ。所以平均服务者有一半时间空闲,顾客的平均等待仍与实际服务时间一样长。原因是空闲时段不能预先替未来顾客服务,而聚集到达会形成等待。

若将到达率提高到 λ=3μ/4,服务能力不变,W 增为 4/μ,是原来的两倍。若关注尾部人数,几何分布还给出 P(N≥k)=ρk;这比只报告平均值更能看见长队风险。

λ=μ 时,形式权重恒为一,总和发散,链零常返而无平稳概率。可用实际跳变时刻的嵌入离散 Markov 链核验这个较强结论:在正整数上,它向上、向下的概率各为 1/2。在 0,K 吸收的有限区间内,首次到边界的步数有几何尾上界(每 K 步都有至少 2−K 的机会连续向下走到零)。从 i 先到 K 的概率及平均退出步数分别解

hi=12(hi−1+hi+1),h0=0, hK=1;ei=1+12(ei−1+ei+1),e0=eK=0,

所以 hi=i/K、ei=i(K−i)。从一出发,让 K→∞,不返回零的概率至多 1/K,故返回几乎必然;但返回前所需步数的期望至少 K−1。在正整数处各停留时间独立于跳转方向,均为速率 2λ 的指数时间,故连续时间的平均返回也无穷。零态的平均停留 1/λ 有限,不改变这一结论。

λ>μ 时嵌入链向上概率为 p=λ/(λ+μ)>1/2。同一有限区间首步方程给 hi=[1−(μ/λ)i]/[1−(μ/λ)K],所以从一出发有概率 1−μ/λ>0 永不返回零;仍无平稳概率。将 1/(μ−λ) 代入非正分母得到的未定义值或负数,不是可用的平均等待答案。

若服务时长固定而均值仍为 1/μ,人数过程一般不再是这条生灭链,平均等待也改变。若有多个服务者,总完成速率在低人数状态为 nμ,高人数状态才饱和为服务台数乘 μ,不能只把本页 μ 换成总能力而保留所有公式。

推论与应用

M/M/1 提供稳定性和拥堵的基准,但它的精确公式依赖完整模型。保留 Poisson 到达、改成一般服务时长后,Pollaczek–Khinchine 平均公式会显示服务时间二阶矩的作用。把多个这样的节点按概率路由连接,需另核验Jackson 网络条件。

参考资料
关系图谱14 个相邻概念 · 3 类关系

拖动节点调整位置。

显示关系

显示:依赖

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

上位 / 更一般

下位 / 直接特例

暂未标注直接特例。

类型化关系