M/M/1 モデルを理解する [応用情報技術者試験]

はじめに

応用情報技術者試験の勉強していると,  "待ち行列理論" や "M/M/1 モデル" は必ず目にする内容だと思います。
実際, 応用情報技術者試験ではおよそ２回に１回は出題されるほど頻出で, 試験を受ける上では押さえておきたい内容です。

多くの参考書や問題集の解説では, システムの利用率を $${\rho}$$ として

$$
平均待ち時間 = \frac{\rho}{1 - \rho}\times 平均サービス時間
$$

という数式が解説されていると思います。
本稿では, この式の意味について詳しく見ていきます。
先に断っておきますが, 応用情報技術者試験の点数取ることを目的とするならば, 本稿の内容を理解することよりも, 上の式を暗記して使うほうがよろしいかと思います。

基礎概念

待ち行列理論

待ち行列とは, 例えば, 駅の券売機の並び列, 飲食店の待ち列, 交差点の車の信号待ち, 混雑した回線内のルータ内部でのパケット待ち行列などにみられる。

待ち行列は, 本質的には確率的な現象である。例えば

• ATM に３分に１人の割合で人が立ち寄る (入力)

• １人あたりの平均利用時間は２分 (処理能力)

を仮定すると, 平均的には 処理能力 $${>}$$ 入力 より待ち行列は発生しないが, 実際には確率的な "ゆらぎ" によって待ち行列が発生することもある。

確率論的には, 人の到着間隔や処理能力の期待値のみならず, ２次以上のモーメントも待ち行列の特性を支配している。

このような特性を数理的に解析する手段を与えているものが待ち行列理論 (Queueing Theory)である。

待ち行列モデル

数理的に待ち行列モデルを解析するために, 関連用語を定義し, 待ち行列の特徴を抽象化して表現したモデルを構築する。

用語の定義 (ATM にできる待ち行列を例に定義する)

• 到着 (arrival)：ATM に人が訪れる動作

• 窓口 (server)：ATM 自体

• 客 (customer)：窓口を訪れる人

• サービス (service)：窓口で行う業務

• 待ち室 (waiting room)：行列を作って待つ場所

• 退去 (departure)：窓口でサービスを受けた客が ATM から離れる動作

• 待ち行列システム：待ち室と窓口を含む全体

待ち行列システム

待ち行列モデルと Kendall の記法

待ち行列モデルは

• 客の到着過程

• サービス時間分布：サービス時間 ($${=}$$ サービス量) を確率変数とした分布関数

• 窓口の数

• (待ち室容量：待ち室に収容可能な最大客数)

• (呼源数：システムに訪れる可能性のある客数の最大値)

• (サービス規律：先着順, 後着順など, サービスの順番に関する規律)

により特徴づけられる。

待ち行列理論では, これらの特徴を Kendall の記法により表現する：

$$
\mathrm{A}(N)/\mathrm{S}/c(K)\quad \mathrm{O}
$$

ただし, $${\mathrm{A}}$$ は客の到着過程, $${\mathrm{S}}$$ はサービス時間分布の種類, $${\mathrm{O}}$$ はサービス規律の種類を表す記号, $${N}$$ は呼源数, $${c}$$ は窓口数, $${K}$$ は待ち室容量を表す値である。

$$
\begin{array}{lll} \hline
記号 & 到着過程 & サービス時間分布 \\ \hline
\mathrm{M} & \text{Poisson 過程} & \text{指数分布} \\
\mathrm{D} & \text{到着間隔一定} & \text{サービス時間一定} \\
\mathrm{GI} & \text{再生過程} & \text{一般分布 (客のサービス時間が互いに独立)} \\
\mathrm{G} & \text{一般の到着過程} & \text{一般分布 (独立性を必ずしも考慮しない)} \\
\mathrm{MAP} & \text{Markov 過程} & \text{---}\\ \hline
\end{array}
$$

一般に, サービス規律では先着順を仮定することが多いため, その場合は記載が省略される。
また, $${N}$$ や $${K}$$ が無限大の場合もそれぞれ記載が省略される。

例えば, "$${\mathrm{M}/\mathrm{M}/1}$$" は, 客が Poisson 過程に従って到着し, サービス時間が指数分布に従い, 窓口が１つ (, 待ち室容量と呼源数が無限大で, サービス規律が先着順) である待ち行列モデルを表す。

出生死滅過程

時刻 $${t\geq 0}$$ における, ある生物の個体数を $${X(t)\in \mathbb{N}_{0} = \{0, 1, \dots\}}$$ と表す。
この生物の個体数は確率的に増減する, すなわち, $${\{X(t); t\geq 0\}}$$ は確率過程として捉えられると仮定する。
さらに, $${\{X(t); t\geq 0\}}$$ は, 現在の個体数 $${i}$$ が与えられれば, 過去の個体数とは無関係に将来の個体数が決まると仮定する。

すなわち, $${\{X(t); t\geq 0\}}$$ は Markov 性を満足し, 時刻 $${t}$$ は連続的に変化するから, $${\{X(t); t\geq 0\}}$$ は連続時間 Markov 連鎖である。

この生物の個体数については, １度に高々１つだけ増えるか, あるいは減るかのどちらかであるとする。
すなわち, 個体数が $${i> 0}$$ のとき, 微笑時間 $${\Delta t}$$ に個体数が変化するならば, 個体数は $${i + 1}$$ または $${i - 1}$$ に推移することのみが可能であるとする。
また, 個体数が $${0}$$ の場合は, 個体数がそれ以上減ることは考えず, 個体数が $${1}$$ に推移することのみが可能であるとする。

このような推移構造をもつ連続時間 Markov 連鎖 $${\{X(t); t\geq 0\}}$$ を出生死滅過程 (Birth-and-Death Process) と呼ぶ。
出生死滅過程で待ち行列システムを解析するためには, 待ち行列システムへ同時に２人以上客が到着, 退去しないことが前提となる。

M/M/1 モデル