スライド

平成27年12月2日
＜学習内容＞
1. 待ち行列理論
2. 待ち行列理論の応用
＜目的＞
待ち行列理論の中のM/M/1モデルを用いて、平均到着率、平
均サービス率、平均利用率、平均待ち時間そして平均応答時
間の意味と定義を学習し、それらの間の関係を理解する。そ
して、実際の問題に待ち行列理論を応用できるようになる。
平均すると3分に一人だが、1
どのような理論？
分間隔で来ることもあれば、
 次のような問題を考える。
6分間隔で来る事もある。
 チケットの販売窓口が一つある。
 顧客は、平均して1時間に20人来る。
1分で終了することもあれば、
 一人当たりの発券業務に平均2分かかる。3分かかることもある。
 このとき、売り場に着いてから券を買えるまで平均何分待つ
か？
 これに答を与えるのが待ち行列理論
ポアソン分布
0.25
λ=3
 お客の到着の仕方
 単位時間に平均λ人とする。
平均到着率
 実際に何人来るかの分布
⇒ポアソン分布
e   x
P( x) 
x!
λ=5
λ=10
0.2
0.15
0.1
0.05
0
0
5
x
10
 意味は･･･
 単位時間に平均λ回ランダムに起こる事象が（単位時間内に）x回起こ
る確率を与える。
15
指数分布
1.2
1
 窓口の処理時間
0.8
 単位時間に平均μ人処理できる。
平均サービス率
 t時間以内に一つのサービスが
終了する確率 ⇒指数分布
P(t )  1  e  t
0.6
μ=3
0.4
μ=5
μ=10
0.2
0
0
0.5
t
1
 単位時間にμ人処理できる事象がランダムに起きると仮定して導出。
1.5
客の到着がランダム
窓口が一つ
【基礎課題8-1】
サービス時間がランダム
＜仮定（前提条件）＞
1. サービスが提供される窓口は１つ。
2. 窓口でサービスを同時に受けることができるのは１人だけ。
3. 順番待ちをする客の列は１つ。
4. 客は待ち行列に加わったら、途中で抜け出さない。
5. 客の到着の仕方がポアソン分布にしたがう。
6. 窓口でのサービス（処理）時間の分布が指数分布にしたがう。
この仮定が成り立つ時、平均待ち時間等を計算できる。
【基礎課題8-1
①】
 平均到着率
λ
単位時間に平均何人窓口に来るか
 平均サービス率
μ
例）窓口に30分で6人来て、10分
で4人処理できる場合
単位時間を1時間とすると
窓口で単位時間に何名処理できるか。 λ=6×(60/30)=12
 平均サービス時間
Ts=1/μ
1名当たりの処理にかかる時間
 平均利用率
ρ=λ/μ
窓口が利用されている割合
μ=4×(60/10)=24
Ts=1/24(時間)=2.5(分)
ρ=λ/μ=12/24=0.5
【基礎課題8-2
Tw
 平均待ち時間
列に並んでからサービスを受けるまでの時間
Tw 

1 
②、③】

Ts
1 
列の長さ（並んでいる人数）
T
 平均応答時間
列に並んでからサービスを終了するまでの時間

M/M/1モデル
1
T  Tw  Ts 
Ts  Ts 
Ts
1 
1 
【基礎課題8-3】、【基礎課題8-4】
★平均到着率
★平均待ち時間 Tw
λ
窓口に単位時間に来る客の人数
列に並んでからサービスを受けるまでの時間
窓口で単位時間に処理できる人数
Tw 
★平均サービス率 μ
★平均サービス時間
Ts=1/μ
1名当たりの処理にかかる時間
★平均利用率 ρ=λ/μ
窓口が利用されている割合

1 
Ts
★平均応答時間 T
列に並んでからサービスを終了するまでの時間
Tw 
1
Ts
1 
例）窓口に30分で6人来て、10分で4人処理できる場合
単位時間を1時間とすると, λ=12, μ=24, ρ=λ/μ=0.5
Ts=1/24(時間)=2.5(分), Tw=0.5/(1-0.5)×2.5=2.5(分),
T=5.0(分)
【基礎課題8-5】、
【基礎課題8-6】
例１）１台のレジがある。客の到着が１時間あたり平均12人で，レジ
での所要時間は平均３分である。このとき、平均待ち時間は何分か？
 平均到着率：
λ=12 (人/時間)
 平均サービス時間：
Ts=3 (分)
μ=60/3 = 20 (人/時間)
 平均利用率： ρ=λ/μ = 12/20 = 0.6
 平均サービス率：
 平均待ち時間：Tw=ρ/(1-ρ)×Ts=(0.6/0.4)×3=4.5(分)
 平均応答時間：T=Tw+Ts=7.5(分)
【基礎課題8-7】
例２）今度は、客の到着が１時間あたり平均24人と2倍になった。この
とき、平均応答時間を変えないためには、レジでの平均サービス時間を
何分にしなければならないか？
 平均到着率：
λ=24 (人/時間) = 0.4(人/分)
 平均利用率：
ρ=λ/μ = λ×Ts = 0.4Ts ･･･ ①
 平均応答時間：T=1/(1-ρ)×Ts=7.5(分)
Ts=7.5(1-ρ)
 ②より
 ③に①を代入すると
･･･
③
Ts=7.5(1-0.4Ts) ･･･ ④
 ④より(1+7.5×0.4)Ts=7.5
3
･･･ ②
∴ Ts=7.5/4=1.875 (分)
最初の
62.5%
行列の長さのρ依存性
行列の長さ=ρ/(1-ρ)
10
9
行列の長さ
8
急激に待ち時間が
増える！
7
6
5
4
3
2
1
0
0
0.2
0.4
ρ
0.6
0.8
 【応用課題8-1】～【応用課題8-3】
12月3日 18:00まで

Download Report