日: 2018年3月26日

待ち行列理論について

待ち行列理論とは、スーパーやコンビニのレジに並ぶ客の待ち時間を統計的に算出するものであり、他の何らかの処理系がありそれを利用する待ち行列があるときに応用される。各種性能の問題などで、平均待ち時間などを算出する理論である。

平均待ち時間を計算するには、処理系が処理する性能の分布（レジの数）と客の数などの待ち行列の分布が必要になる。それを記号で表記する、M/M/1モデルであれば、ランダム分布の客に、ランダム分布の処理系が１つある場合である。これをケンドール記法という。次にケンドール記法に使われる記号を示す。

M ランダム分布あるいは指数分布
G 一般分布
D 一定値

サービス要求の発生額度分布/サービス処理時間分布/サービス窓口数

単位時間あたりの平均到着数 λ
単位時間あたりの平均処理件数 μ
窓口の利用率 ρ
処理中のトランザクションを含めたシステム内に帯留するトランザクション数の平均 L
平均到着数 λ = 1 / ts
平均サービス率 μ = 1 / t

M/M/1の待ち行列モデル

M 単位時間あたりのトランザクションの到着数 ランダム到着としてポアソン分布に従う。
M 1件あたりのサービス時間 指数分布に従う。
1 サービス窓口の数 1つ
窓口の利用率(ρ)
待たされる確率
= 処理時間の割合
= 単位時間あたりの処理時間
= 単位時間あたりの平均到着数(λ) * 1件の平均処理時間(1 / μ)
= 単位時間あたりの平均到着数(λ) / 単位時間あたりの処理できる件数(μ)
=λ / μ

系内にだれもいない確率 = 1 – ρ

系内の平均客数
=処理中のトランザクションを含めたシステム内に帯留するトランザクション数の平均( L )
= ρ/(1－ρ)
この式は、数列を使用して算出されたものであり、必ず覚えること。

待ち行列内の平均客数
=サービス待ち行列の客数の平均( Lq )
= L-ρ
=ρ2/(1－ρ)