待ち行列でキャパシティプランニング

システムのキャパシティを計測するために 待ち行列 の考え方が役に立ちます。

待ち行列

待ち行列とは、窓口に列が出来ているときにどれくらい待つことになるかの話です。
スーパーのレジに並ぶような状況を想像すると分かりやすいかと思います。

どれくらい待つかを計算するには次の2つを考えます。

1回の会計に平均3分かかって、5分に1人のペースで新たに列に並ぶとします。
つまり、1分あたり1/5人並んで、1分あたり1/3人分の処理ができます。

混み具合を (1分あたりに並ぶ人数) / (1分あたりに処理できる人数) とすると
(1分あたりに並ぶ人数) / (1分あたりに処理できる人数) = 3/5 = 0.6 なので混雑率60% となります。

この状況のとき、どれくらいの人が並んでいるかは混雑率 / (1- 混雑率) と計算できます。
つまり 0.6 / (1 – 0.6) = 1.5 人が並んでいる状態に落ち着きます。

1回の会計に3分かかるので、待ち時間は 1.5 * 3 = 4.5 分です。
自分の会計が終わるのはさらに会計の時間を足して 7.5 分後になります。

なんとなくイメージできたでしょうか。

式で定義すると次のようになります

最初の例で言うと

となります。

ここまで説明したものは M/M/1 モデルと呼ばれる待ち行列です。

A/B/C という書き方はケンドール記号と呼ばれる表現で、Aは到着する人の分布、Bはサービス時間分布、Cは窓口の数を表しています。

最初のMは到着の分布がポアソン分布に従うことを意味していて、2つ目のMはサービス時間が指数分布に従うことを意味しています。最後の1は窓口が1つであるという意味です。分布の説明は省略しますがざっくり言うとランダムということです。

これまでは窓口を増やす場合を考えましたが、窓口を増やす場合はM/M/Sモデルを考えます。ここで S は窓口の数です。