サービスを受けるまでの待ち行列を表現するための手法【ケンドールの記号】

目次（まとめ）

◾️ 待ち行列理論とは、サービスを受けるための行列についての理論

◾️ ケンドールの記号をつかって待ち行列を表現する

◾️ M/M/1の待ち行列モデルは情報処理試験に頻繁に出題されます

こんにちは、みっちゃんです。

今回の記事では、いろいろなサービスを受けるために待っている人（やデータ）の行列を表現するための手法である「ケンドールの記号」について紹介します。

待ち行列理論とは、サービスを受けるための行列についての理論

わたしたちの身近では、ATMの前や、スーパーの安売り日、新しい商品の発売日などに、多くの人が行列を作っている光景がみられます（最近では、距離を保って並ぶ感じになってきました）。

ここでは、この「行列」がどのように生じているのか考えてみます。

例えば、ATMの周辺には、「ATMという機械」と「ATMを利用している人」、「待っている人」という3者関係によって行列が生じています。

「ATMという機械」が多ければ多いほど行列は解消され、「ATMを利用している人」が長く滞在すればするほど行列が長くなり、「待っている人」が多ければ多いほど行列が長くなります。

このような行列を理論的に解析するために「待ち行列理論」というものが存在します（名前が意味するままですね）。

面白いのは、待ち行列というのは、人だけでなく、コンピュータ内のデータについても考えることができます。

つまり、何らかのシステムがあって、そこにデータを入力していくとき、ある程度の「待ち時間」が生じるため、データが「待ち行列」を作ることになります。

ケンドールの記号をつかって待ち行列を表現する

イギリスの統計学者であるデービッド・ケンドール（David George Kendall）さんは、待ち行列を表現するための記号を導入しました。

ケンドール記号は「A/B/C/D」という形式で、待ち行列を表現します。

A: データが到着する過程
例えば、マルコフ過程（Markov process）にしたがってデータが到着する場合には、頭文字をとって「M」と表現する。

B: サービスを提供する時間の分布
例えば、マルコフ過程（Markov process）にしたがってサービスを提供する場合には、頭文字をとって「M」と表現する。

C: サービスの数
例えば、ATMの例で考えると、ATMの台数に対応する。数に応じて「1」などと表現する。

D: システムの容量
無限にあると考える場合には、書かなくてよい。


ここで、マルコフ過程とは、未来のことは現在が決めて、過去には依存しないことを意味します。データ到着（A）とサービス提供（B）がともにマルコフ過程にしたがう場合、待ち行列が伸びていく時間と待ち行列が短くなっていく時間が「指数分布」にしたがうことになります（指数分布については、こちらの記事をご覧ください）。

M/M/1の待ち行列モデルは情報処理試験に頻繁に出題されます

情報処理試験では、例えば「平均待ち時間」に関連する問題が出題されています。

「平均待ち時間」は、以下の式で計算することができます。
$$(平均待ち時間) = (平均サービス時間) \times \frac{(利用率)}{1-(利用率)}$$

必要に応じて、公式を覚えていきましょう。