待ち行列理論シミュレーター (M/M/1)

到着率・サービス率と待ち行列の安定性

計算例 — 待ち行列理論シミュレーター (M/M/1)

利用率 ρ	0.750
L の M/M/1 予測値	3.000
シミュレーションの実際の到着率	3.0084
平均系内時間 W (顧客平均)	1.012
リトルの法則による L の予測	3.045
観察者が数えた L (時間平均)	3.044
上記2つの差	0.0006
数えられた L の標準誤差	0.121

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

ρの崖 🖖

L = ρ/(1−ρ) は滑らかには増加しません。ρ = 1 に垂直漸近線があるため、利用率が90%から99%にじわじわと上がると、平均待ち行列長は9人から99人へと跳ね上がります。処理能力の限界に達した時点では、行列は無限大に発散するのです。これが「ρの崖」です。利用率80%と85%の待ち行列にはほとんど違いを感じませんが、95%まで押し上げると待ち時間は膨れ上がります。W = 1/(μ−λ) にも同じ特異点があるためです。分子が大きくなるのではなく、分母がゼロに近づいていくのです。コールセンターや病院の救急外来など、現実のシステムが100%の処理能力を大きく下回るように意図的に余裕を持たせているのはこのためです。一見「無駄」に見えるこのゆとりこそが、私たちを崖から守ってくれているのです。

行列を作るのはランダム性 🖖

M/M/1 の2つの「M」は「マルコフ（Markovian）」を表しています。単一のサーバーに対して、到着がランダム（ポアソン分布）であり、サービス時間もランダム（指数分布）に変化するという意味です。ここには驚くべき事実が隠されています。サーバーの平均処理速度が顧客の到着速度を上回っていても、行列はできるのです。もし全員が時計仕掛けのように規則正しく現れ、すべての仕事に同じ時間がかかるなら、余力のあるサーバーに行列ができることは決してありません。待ち時間は過負荷からではなく、ばらつきから生まれます。λ を μ より十分に低く設定しても、行列はできたり消えたりを繰り返します。両方のパターンを「規則的」に設定すると、上のグラフは 0 と 1 から決して離れません。間隔も仕事もすべて同じであれば、利用率が 1 を下回る限り、サーバーは次の到着までに必ず処理を終えているからです。

前提をほとんど必要としないリトルの法則 🖖

ここに示されている L と W は独立したものではありません。L = λW、同様に Lq = λWq を満たしています。この等式は前提条件をほとんど必要としません。ジョン・リトルが1961年に証明したこの法則に必要なのは、長期的な到着率が存在して有限であること、そして長期的な平均系内時間も同様であること、それだけです。ポアソン到着も、指数サービスも、独立性も、単一サーバーであることも、さらには確率分布の定常状態すら必要ありません。その真価は上の表で確認できます。どちらかのストリームに規則的またはバースト的なパターンを入れると、ρ/(1−ρ) の値は、ある設定では4倍大きすぎ、別の設定では15倍も小さくなります。一方、λW と独立して数えた L は、調べた405通りの設定すべてにおいて、その差が顧客 0.011 人分以内に収まっています。この関係は、病院の病棟、工場の仕掛品、店舗の在庫にも当てはまります。つまり、平均内容は到着率と平均滞在時間の積に等しいのです。

2つの平均値と、顧客に属するただ1つの値 🖖

両方のパターンを「規則的」に設定し、表の2つの行を見比べてください。到着した顧客が目にする待ち行列は 0.000 です。同じ待ち行列を時間経過で数える観察者は 0.751 を得ます。どの顧客も空のシステムに入っていきますが、サーバーは4分の3の時間は稼働しています。どちらも正しいのです。なぜなら、L は待ち行列の長さを時間で重み付けするのに対し、到着する側の視点では顧客で重み付けしており、この2つの異なる重み付けを一致させるものは何もないからです。リトルの法則は時間平均と顧客平均を組み合わせますが、それらが一致するとは決して主張しません。ポアソン到着の場合、これらは一致するため、その違いを見落としがちです。到着はどの瞬間でも等確率で起こるため、顧客の視点は時間の公平なサンプルになります。これが PASTA 特性であり、待ち行列ではなく到着に属する性質です。到着を「バースト的」に切り替えると、同じシミュレーションで時間平均 21.482 に対して 27.011 という結果が出ます。バーストとは、ほとんどの顧客が到着するタイミングであり、かつ行列が最も長くなるタイミングだからです。

全プロセスの詳細解説

1時間あたり3人が到着する待ち行列と、20%の増加 5 ステップ
顧客は1時間に3人到着し、サーバーは1時間に4人を処理します。 サーバーは4分の1の時間は待機していることになり、余裕があるように聞こえます。これによって生じる待ち行列を計算し、さらに到着が20%増加するとどうなるかを導いてください。
1. 連鎖は釣り合っています。つまり、各状態へ入る率は出る率と等しくなり、Pₙ = (1 − ρ)ρⁿ が導かれます。これは待ち行列の長さに関する幾何分布であり、ρはサーバーが稼働している時間の割合です。ここでは ρ = 0.75 となります。
  
  $P_{n} = (1 - ρ) ρ^{n}, ρ = \frac{λ}{μ} = \frac{3}{4} = 0.750$
2. この分布の平均は ρ/(1 − ρ) です。分母にあるものに注目してください。1時間あたりの処理人数の余裕ではなく、余裕の割合です。1日の4分の1を待機しているサーバーから、系内に平均3人の人がいる状態が生み出されます。
  
  $L = n \geq 0 \sum n P_{n} = \frac{ρ}{1 - ρ} = \frac{0.750}{0.250} = 3.000$
3. 確率 ρ で存在する、サービス中の1人を引くと、2.25人が待っていることになります。
  
  $L_{q} = L - ρ = 3.000 - 0.750 = 2.250$
4. リトルの法則は人数を時間に変換するもので、分布の仮定を一切必要としません。系内の平均人数は、到着率と平均滞在時間の積です。15分で終わる仕事のために、系内に1時間滞在し、そのうち45分は列に並んでいることになります。
  
  $W = \frac{L}{λ} = \frac{3.000}{3} = 1.000, W_{q} = \frac{L _{q}}{λ} = 0.750$
5. ここで λ を 3.6 に上げます。利用率は 0.75 から 0.90 に上がり（仕事量が20%増え）、ρ/(1 − ρ) は 3 から 9 になります。
  
  $λ = 3.6 : ρ = 0.90, L = 9; λ = 3.96 : ρ = 0.99, L = 99$
解答

ツールは、利用率75%で L = 3.000、L_q = 2.250、W = 1.000、W_q = 0.750 を出力します。ここから得られる教訓は、ρ/(1 − ρ) の分母についてです。待ち行列を決めるのは、どれだけの空き容量があるかではなく、割合としてどれだけ残っているかであり、負荷を追加する際に消費されるのはその割合なのです。到着が20%増えると、行列は3倍になります。さらにその上から10%増えると、ρ = 0.99 となり、行列は 99 に達します。病院や高速道路、ディスクコントローラーが高利用率で緩やかに劣化するのではなく機能不全に陥るのも、「まだ能力の90%しか使っていません」という言葉が、響きほどには安心できないのも、これが理由です。

$L = \frac{ρ}{1 - ρ} blows up at ρ = 1 : + 20% λ ⟹ \times 3 queue$
ランダム性を排除した場合の同じペース 5 ステップ
λ = 1時間に3、μ = 1時間に4のまま、ランダム性を一切排除してください。 到着間隔は正確に20分、すべての仕事は正確に15分とします。利用率は 0.750 のままです。これによって生じる待ち行列を計算し、そこから ρ/(1 − ρ) がどれほど離れているかを求めてください。

この問題をツールで開く
1. 顧客 k は k/λ に到着し、サーバーが空いていれば k/λ + 1/μ に退出します。次の顧客は (k + 1)/λ に到着します。1/μ ≤ 1/λ のとき、つまり ρ ≤ 1 を書き換えた条件において、サーバーは常に間に合うように処理を終えています。
  
  $ρ = \frac{λ}{μ} = \frac{3}{4} = 0.750, \frac{1}{λ} = 0.3333 > \frac{1}{μ} = 0.250$
2. したがって、待ち行列が安定している限り、誰も全く待ちません。W_q = 0 であり、W はサービス時間のみの 1/μ = 0.250 時間となります。建物内にいる15分間、その1分1秒のすべてがサービスを受けている時間です。
  
  $\frac{k}{λ} + \frac{1}{μ} \leq \frac{k + 1}{λ} ⟺ \frac{1}{μ} \leq \frac{1}{λ} ⟺ ρ \leq 1 ⟹ W_{q} = 0$
3. リトルの法則はこれを人数に変換し、そこには分布も必要ありません。L = λW = 3 × 0.250 = 0.750 であり、L_q = 0 となります。4分の3人の顧客。これはサーバーが稼働している時間の割合そのものであり、それ以上の意味はありません。
  
  $W = \frac{1}{μ} = 0.250, L = λW = 3 \times 0.250 = 0.750, L_{q} = λ W_{q} = 0$
4. 一方、ρ/(1 − ρ) = 0.750/0.250 = 3.000 となり、真実の4倍になります。この倍率はこれらの数字による偶然ではありません。M/M/1 が ρ/(1 − ρ) を返すのに対し、規則的な場合は ρ となるため、どの利用率においても 1/(1 − ρ) の分だけ過大評価されるのです。
  
  $ρ 0.50 0.75 0.90 0.95 0.99 ρ / (1 - ρ) 1.000 3.000 9.000 19.000 99.000 ρ 0.500 0.750 0.900 0.950 0.990 1/ (1 - ρ) 241020100$
5. ρ = 0.99 ではその倍率は100になります。M/M/1 では系内に99人いることになりますが、完全に規則的なトラフィックであれば 0.99 人です。
  
  $\frac{ρ / ( 1 - ρ )}{ρ} = \frac{1}{1 - ρ}; ρ = 0.99 : 99.000 ⟷ 0.990$
解答

ツールは W = 0.250 と出力し、リトルの法則によってそれは L = 0.750 に変換されます。M/M/1 の予測 3.000 と比べると、+299.6% の誤差です。行列など最初から存在しなかったのです。最初の考察ブロックにあった ρ の崖はすべてばらつきによって作られており、ばらつきが全くない状態では、ρ = 0.99 にも崖はありません。これが現実世界において、予約制度を導入する根拠となります。処理能力を増やすことも、ばらつきを減らすことも、どちらも行列を短くしますが、1/(1 − ρ) という式は、前者を獲得するのが最も難しい状況において、後者が最大の効果を発揮することを教えてくれます。利用率75%のとき、完全に規則的なスケジュールは待ち行列を4分の1に減らす価値があり、99%では100分の1になります。現実のクリニックが時計仕掛けのように動くことはありませんし、同じペースでも到着が集中した場合には 21.482 という値になります。

$L_{D / D /1} = ρ = 0.750 ⟷ L_{M / M /1} = \frac{ρ}{1 - ρ} = 3.000, \frac{L _{M / M /1}}{L _{D / D /1}} = \frac{1}{1 - ρ} = 4$

参考文献 (1)

Insight block 3 — how little L = λW assumes: J. D. C. Little, "A Proof for the Queuing Formula: L = λW." Operations Research 9(3), 383–387, 1961.

42Math チーム · 公表された資料と照合しています。訂正のご指摘を歓迎します。