1. No category

アルゴリズム論 b (2014)
[第5回] 指数乱数と待ち行列

窓口に並ぶ行列
客の到着
待ち行列の発生
窓口
サービス対応
サービス終了
退出

スーパーやコンビニレジの行列

チケット売り場

高速道路料金所(ETCなし)

ATMなどのオンラインシステム

インターネットサーバーのアクセス処理
客の到着状況
 客の行列人数
 窓口の数、サービスにかかる時間


「行列ができる」状態



→待ち時間大
→コスト増加
サービス低下
「行列ができない」状態



商売繁盛？
窓口数を増やす
窓口が空いている状態
窓口数を減らす
→サービス過剰
適度の待ち行列人数を維持することが必要

予測不能の状況
 顧客の到着の不規則さ
 サービス対応時間の不規則さ

各窓口への振り分け方法

先着順、ランダム、空いている窓口へ

平均待ち時間・平均行列の人数の評価

サービス時間とコスト(窓口数調整など)の最適化

客の到着



1分間あたりの客の到着人数 ポアソン分布
客の到着時間間隔
指数分布
サービス時間 確率的な現象



確率的な現象
経過した時間に依存しないランダムな時間
1人あたりのサービス時間
指数分布
窓口数 １～ n

M／M／n モデル → ポアソン／指数／窓口数


窓口１つ
M/M/1
モデル
窓口が複数 n 個
M/M/n モデル

平均到着率
λ 1分あたり到着する客数
平均サービス量
μ 1分あたり処理できる客数
平均サービス時間 t s=1/ μ 1人あたりの処理時間

平均待ち行列長さ

平均システム内客数 Lq 平均滞在客数
（サービスを受けている客を除く）


L 平均の行列人数

平均窓口利用率

平均の行列人数
L＝

ρ
ρ＝ λ / μ
Lq ＝
1ー ρ
ρ2
1ー ρ
平均待ち時間 リトルの法則
Wq ＝
ρ
1ー ρ
ts =
Lq
λ

１人目



到着 すぐサービス開始
サービス時間発生
２人目



到着→ １人目がサービス時間内なら待ち時間
行列の人数 +1
１人目のサービスが終了していたらサービス開始
待ち時間途中からサービス開始

n人目

到着→ 直前の客がサービス時間内なら待ち時間
行列数 +1
直前の客のサービスが終了したらサービス開始

待ち時間経過後、サービス開始


各人の待ち時間、待ち行列人数などを計算

ポアソン分布
 1分間あたりの人数

指数分布
 次の事象が起きるまでの時間間隔（分）

ポアソン分布と指数分布は表裏の関係

客の単位時間あたりの到着人数


客の到着間隔


ポアソン分布に従う乱数
指数分布に従う乱数
サービス時間

指数分布に従う乱数
ポアソン分布と指数分布は
表裏の関係

ポアソン乱数 (平均 λ) 1分間に来るお客の数
一様乱数を複数個を掛ける
=RAND（）*・・・* RAND（） ＞exp(－λ)
exp(－λ)よりも小さくなる直前の 積の個数（整数）
Excelの乱数機能にも用意

指数乱数
(平均 m)
お客が来る時間間隔
窓口サービスにかかる時間
＝ － LOG（ RAND（） ）＊ m
1. ポアソン到着・指数サービスの乱数を生成
2. 各ステップで待ち時間・待ち行列人数を算定
3. 平均の待ち行列人数・平均システム内人数を、
シミュレーションの平均として求める
4. 窓口２つの場合のシミュレーション
到着した客がどちらの窓口に入るか