M/M/c 待ち行列

窓口が $c$ 個の M/M/c で、定常確率 $p_{0}$ と客が待つ確率を求め、 $L_{q}$ ・ $W_{q}$ ・ $W = W_{q} + \frac{1}{μ}$ を計算して、M/M/1 と平均系内滞在時間を比べられる

前提

M/M/1 待ち行列とリトルの公式（大学数学オペレーションズ・リサーチ）

この技能までの道筋（85 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
確率の定義と和事象・余事象（数学A 場合の数と確率）
期待値（数学A 場合の数と確率）
確率変数と確率分布（数学B 統計的な推測）
平均と合計（算数いろいろな文章題）
平均値・中央値・最頻値（中学数学データの活用）
代表値（平均値・中央値・最頻値）（数学I データの分析）
分散と標準偏差（数学I データの分析）
変量の変換と平均・分散（数学I データの分析）
確率変数の期待値・分散と $a X + b$ （数学B 統計的な推測）
分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
3 次式までの展開と因数分解（数学I 数と式）
微分係数と導関数の定義（数学II 微分法と積分法）
多項式の微分（数学II 微分法と積分法）
多項式の不定積分（数学II 微分法と積分法）
定積分の計算（数学II 微分法と積分法）
連続型確率変数と確率密度関数（数学B 統計的な推測）
等間隔にならんだ数の和（算数計算と数のきまり）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
積と商の微分（数学III 微分法）
合成関数の微分（数学III 微分法）
円の周の長さと面積（算数平面図形）
おうぎ形の弧の長さと面積（算数平面図形）
弧の長さからおうぎ形の中心角と面積を求める（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
弧度法と単位円による三角関数（数学II 三角関数）
$sin x / x$ の極限（数学III 極限）
加法定理と 2 倍角・半角・積和の公式（数学II 三角関数）
三角関数の導関数（数学III 微分法）
根号の乗除と加減（中学数学数と式）
指数の拡張と指数関数（数学II 指数関数と対数関数）
対数の定義と性質（数学II 指数関数と対数関数）
自然対数の底 $e$ （数学III 極限）
指数関数・対数関数の導関数（数学III 微分法）
基本的な関数の不定積分（数学III 積分法）
置換積分（数学III 積分法）
部分積分（数学III 積分法）
定積分の置換・部分積分と偶関数・奇関数（数学III 積分法）
広義積分（大学数学微分積分）
一様分布・指数分布（大学数学確率・統計）
条件付き確率と乗法定理（数学A 場合の数と確率）
マルコフ連鎖と推移確率（大学数学確率・統計）
定常分布（大学数学確率・統計）
無限等比級数と無限級数（数学III 極限）
出生死滅過程の定常分布（大学数学オペレーションズ・リサーチ）
確率変数の和と積（独立な場合）（数学B 統計的な推測）
独立な試行と反復試行（数学A 場合の数と確率）
二項分布（数学B 統計的な推測）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
1 次方程式の解き方（中学数学方程式）
比例・反比例の式とグラフ（中学数学関数）
関数 $y = a x^{2}$ の式と変域（中学数学関数）
平方完成と 2 次関数のグラフ（数学I 2次関数）
2 次不等式（数学I 2次関数）
剰余の定理・因数定理と高次方程式（数学II 複素数と方程式）
増減表と極値（数学II 微分法と積分法）
関数の連続性と中間値の定理（数学III 極限）
平均値の定理（数学III 微分法）
第 2 次導関数とグラフの凹凸（数学III 微分法）
増減・凹凸・漸近線とグラフ（数学III 微分法）
テイラー展開（大学数学微分積分）
べき級数と収束半径（大学数学微分積分）
幾何分布・ポアソン分布（大学数学確率・統計）
M/M/1 待ち行列とリトルの公式（大学数学オペレーションズ・リサーチ）

説明

窓口が $c$ 個ある待ち行列 M/M/c（到着はポアソン到着、サービス時間は指数分布、窓口は $c$ 個、待合室は無制限）について、混み具合を計算できるようになります。具体的には、系が空である確率 $p_{0}$ 、到着した客が待たされる確率、平均待ち行列長 $L_{q}$ 、平均待ち時間 $W_{q}$ 、平均系内滞在時間 $W$ を求めます。銀行やコールセンターの窓口を何個にするか、窓口を 1 つの速い窓口にまとめるのとどちらがよいか、といった比較に使います。

なぜそうしてよいのか

客の到着率を $λ$ 、1 つの窓口のサービス率を $μ$ とし、系内人数 $n$ を状態とする出生死滅過程で考えます。出生率はいつも $λ$ です。死滅率は $n$ によって変わります。 $n$ 人いるとき、サービス中の窓口は $min (n, c)$ 個です。それぞれが独立に率 $μ$ の指数分布でサービスを終えるので、「どれか 1 つが終わる」率は $min (n, c) μ$ になります（独立な指数分布の最小値は、率を足した指数分布に従うため）。つまり $n \leq c$ では死滅率が $n μ$ と人数に比例して増え、 $n \geq c$ では全窓口がふさがっているので $c μ$ で頭打ちになります。

出生死滅過程の釣り合いの式 $λ p_{n - 1} = min (n, c) μ p_{n}$ を順に解きます。 $a = λ / μ$ 、 $ρ = λ / (c μ)$ とおくと、 $n \leq c$ では $p_{n} = p_{0} \frac{a ^{n}}{n !}$ 、 $n \geq c$ では $p_{n} = p_{0} \frac{a ^{c}}{c !} ρ^{n - c}$ となります。後半は公比 $ρ$ の等比数列です。確率の総和が 1 になるには、この無限等比級数が収束する必要があります。そのための条件が $ρ < 1$ で、これは「窓口全体の処理能力 $c μ$ が到着率 $λ$ を上回る」という意味です。 $\sum p_{n} = 1$ から $p_{0}$ が決まります。

客が待たされるのは、到着したときに $c$ 個の窓口が全部ふさがっている（ $n \geq c$ ）場合です。ポアソン到着では、到着客が見る系の状態の分布は定常分布と一致します。したがって待つ確率は $P (N \geq c) = \sum_{n \geq c} p_{n}$ です。待ち行列にいる人数は $n - c$ 人なので、 $L_{q} = \sum_{n \geq c} (n - c) p_{n}$ は $\sum_{k \geq 0} k ρ^{k} = \frac{ρ}{( 1 - ρ ) ^{2}}$ を使って計算できます。あとは待ち行列部分にリトルの公式を当てはめると $W_{q} = L_{q} / λ$ が得られます。サービス時間の平均は窓口 1 つ分の $1/ μ$ なので、 $W = W_{q} + \frac{1}{μ}$ となります。なお $c = 1$ とおくと、すべて M/M/1 の公式に戻ります。

手順

$a = \frac{λ}{μ}$ と利用率 $ρ = \frac{λ}{c μ}$ を計算し、 $ρ < 1$ を確かめる（ $ρ \geq 1$ なら定常分布はなく、行列は限りなく伸びる）
空の確率を求める: $p_{0} = [n = 0 \sum c - 1 \frac{a ^{n}}{n !} + \frac{a ^{c}}{c ! ( 1 - ρ )}]^{- 1}$
客が待つ確率（全窓口がふさがっている確率）を求める: $C = P (N \geq c) = p_{0} \frac{a ^{c}}{c ! ( 1 - ρ )}$
平均待ち行列長と平均待ち時間を求める: $L_{q} = C \frac{ρ}{1 - ρ}$ 、 $W_{q} = \frac{L _{q}}{λ} = \frac{C}{c μ - λ}$
平均系内滞在時間を求める: $W = W_{q} + \frac{1}{μ}$ 。必要なら $L = λW = L_{q} + a$ も求める
比較したい M/M/1（例えばサービス率 $c μ$ の窓口 1 つ）の $W = \frac{1}{μ ^{'} - λ}$ と並べて比べる

例題

客が率 $λ = 3$ （人/時）のポアソン到着で訪れ、各窓口のサービス時間が平均 $\frac{1}{2}$ 時間の指数分布（ $μ = 2$ ）に従う、窓口 2 個の M/M/2 待ち行列がある。平均系内滞在時間 $W$ （時間）を求めよ。

例題の解答

手順1: $a = λ / μ = \frac{3}{2}$ 、 $ρ = \frac{λ}{c μ} = \frac{3}{4} < 1$ なので定常状態がある（ $a > 1$ でも $c = 2$ なので安定である）。
手順2: $\sum_{n = 0}^{1} \frac{a ^{n}}{n !} = 1 + \frac{3}{2} = \frac{5}{2}$ である。また $\frac{a ^{2}}{2 ! ( 1 - ρ )} = \frac{9/4}{2 \cdot \frac{1}{4}} = \frac{9}{2}$ である。よって $p_{0} = (\frac{5}{2} + \frac{9}{2})^{- 1} = \frac{1}{7}$ 。
手順3: 待つ確率は $C = \frac{1}{7} \cdot \frac{9}{2} = \frac{9}{14}$ 。
手順4: $L_{q} = \frac{9}{14} \cdot \frac{3/4}{1/4} = \frac{27}{14}$ 、 $W_{q} = \frac{L _{q}}{λ} = \frac{27/14}{3} = \frac{9}{14}$ である。検算すると $\frac{C}{c μ - λ} = \frac{9/14}{4 - 3} = \frac{9}{14}$ で一致する。
手順5: $W = \frac{9}{14} + \frac{1}{2} = \frac{16}{14} = \frac{8}{7}$ （時間）。このとき $L = λW = \frac{24}{7}$ 。
手順6（比較）: 2 つの窓口を、サービス率 $4$ の速い窓口 1 つにまとめた M/M/1 では $W = \frac{1}{4 - 3} = 1$ となり、M/M/2 の $\frac{8}{7}$ より短い。客が 1 人しかいないとき、M/M/2 では片方の窓口が遊んでいて率 $2$ でしか処理できないためである。一方、窓口ごとに別々の列を作り、到着を半分ずつ（各 $λ = \frac{3}{2}$ ）振り分ける場合を考える。これは M/M/1 が 2 つあるのと同じで $W = \frac{1}{2 - \frac{3}{2}} = 2$ となり、共通の列で待つ M/M/2 の $\frac{8}{7}$ よりずっと長い。

答え: $\frac{8}{7}$

よくある誤り

安定条件を $λ / μ < 1$ と考えてしまう誤り。正しくは $ρ = \frac{λ}{c μ} < 1$ である。例えば $λ = 3, μ = 2, c = 2$ では $λ / μ = \frac{3}{2} > 1$ だが、 $ρ = \frac{3}{4} < 1$ なので定常状態がある。
死滅率を人数によらず $c μ$ としてしまい、 $p_{n} = p_{0} (\frac{λ}{c μ})^{n}$ とする誤り。これはサービス率 $c μ$ の M/M/1 の分布である。正しくは $n < c$ では死滅率が $n μ$ なので $p_{n} = p_{0} \frac{a ^{n}}{n !}$ となり、等比数列になるのは $n \geq c$ の部分だけである。
サービス時間を $1/ (c μ)$ として $W = W_{q} + \frac{1}{c μ}$ とする誤り。1 人の客を担当するのは窓口 1 つだけなので、正しくは $W = W_{q} + \frac{1}{μ}$ （例題では $\frac{9}{14} + \frac{1}{2}$ であり、 $\frac{9}{14} + \frac{1}{4}$ ではない）。
待つ確率を $P (N > c)$ とする、あるいは $p_{0}$ の和で $\frac{a ^{c}}{c !}$ を二重に数える誤り。到着客は $c$ 個の窓口が全部ふさがっている $N \geq c$ のときに待つので、正しくは $C = P (N \geq c)$ である。また $p_{0}$ の式の有限和は $n = 0$ から $c - 1$ までで、 $n = c$ 以降は $\frac{a ^{c}}{c ! ( 1 - ρ )}$ にまとめて含まれている。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

M/M/c 待ち行列

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題