M/M/1 待ち行列

M/M/1待ち行列の概要

M/M/1待ち行列とは、確率論の分野で用いられる待ち行列モデルの一つであり、特に顧客や要求が一列に並び、一つの窓口またはサーバーによって処理されるシステムを説明するものです。このモデルには、到着事象がポアソン過程に従い、各要求の処理時間が指数分布に従うという特徴があります。このようにして、M/M/1待ち行列は、簡潔でありながら多くの実用的なシナリオに適用可能なフレームワークを提供します。

モデルの基礎

M/M/1待ち行列の「M」はメモリーレスな性質を示しており、到着プロセスやサービスプロセスがそれぞれポアソン過程と指数分布の特性を持っています。具体的には、顧客の到着が無作為に発生し、新たに到着した顧客は待ち行列の最後に追加される仕組みです。また、サーバーは待ち行列の最前列から順次顧客を処理していきます。

このモデルは、待ち行列の長さが常に非負で無限に存在可能な状態を想定しています。即ち、待っている顧客の数に上限がなく、過剰な顧客が到着しても対応可能です。

確率過程としての説明

M/M/1待ち行列は、待ち行列の長さによって状態空間が形成されています。状態空間は{0, 1, 2, 3, ...}の集合であり、モデルの確率過程として表現できます。到着率とサービス率のそれぞれをλおよびμとし、待ち行列の長さが増加する時間、即ち新たな到着があるまでに要する時間は次のような確率密度関数に従います:

$$P(T = t) = λ e^{-λt} \\ (t ≥ 0)$$

同様にサービスが完了し、長さが減る時間も指数分布に従います:

$$P(T = t) = μ e^{-μt} \\ (t ≥ 0)$$

これにより、待ち行列の長さの変化が指数分布に基づく確率過程であることが分かります。このプロセスをさらに進めると、状態遷移図を描くことができ、待ち行列の振る舞いを視覚的に理解する助けとなります。

定常状態と解析

M/M/1待ち行列では、時間が経過するにつれてどのように機能するかも解析可能です。時間t → ∞の際の挙動は、特に平均利用率ρ（λ/μ）によって決定されます。利用率ρが1以上の場合、待ち行列は無限に伸びる傾向があり、定常分布を持たなくなります。一方、ρが1未満であれば、システムは安定しており、定常過程を持つことが示されています。

この安定した状態においては、待ち行列の長さに関する確率も明確に定義でき、次のように表現されます:

$$π_i = (1 - ρ) ρ^i$$

この結果から、待ち行列の長さが持つ確率分布が幾何的な性質を持つことが確認できます。

サーバーのビジー時間と応答時間

M/M/1待ち行列の動作時には、サーバーがビジーである時間の解析も重要です。ビジー時間は、最初の要求が来てから全ての要求が処理されるまでの時間として定義され、この時間は特定の確率密度関数に従います。また、平均応答時間はリトルの法則を用いて基本的に1/(μ - λ)で計算でき、待ち時間やサービス時間の合算として得られます。

結論

M/M/1待ち行列は、その基本性質や挙動を理解する上で良い概要を提供します。様々なサービス状況に応じた適用が可能で、待ち行列理論における基礎的なモデルとして、より複雑な構造への拡張を行う上での出発点ともなります。例えば、M/M/c待ち行列では、複数のサーバーを考慮に入れることで、さらに実際のシステムに近いモデルを構築可能です。

もう一度検索