待ち行列理論
待ち行列理論(Queueing theory)
確率モデルに基づいた理論
顧客がサービスを受けるために行列に並ぶような確率的に挙動するシステムの混雑現象を数理モデルを用いて解析することを目的とした理論 処理(サービス)を待つ「順番待ち行列」の例
銀行のATMに並ぶ顧客の列
レジに並ぶ顧客の列
トランザクションがサーバ処理を待つケース
何のために使われるか
システムの性能を評価するために使用する
待ち時間予測
処理が遅い場合にどこを改善するべきかを見る
サービスに掛ける時間を短くするか
窓口を増やすべきか
それによってどれだけのコストかかかりそうかの目安を出すため
https://gyazo.com/229289c48d61acfb79b7d8b7ae352910
A/B/Cというやつ
最近はA/S/c/K/N/Dという書き方が考えられていて、こっちの方がわかりやすい
具体例
詳しくはM/M/1モデルのページへ
A: 到着の過程
到着の過程・分布
トランザクションの到着の分布を表す
単位時間に到着するトランザクション数
ポアソン分布は離散的な分布
平均到着間隔$ \frac{1}{\lambda} : 指数分布 トランザクションの到着から、次のトランザクションの到着までの平均時間
指数分布は連続的な分布
S: サービス時間の分布
サービスの分布を表す
平均サービス率$ μ : ポアソン分布
単位時間あたりのサービス数
平均サービス時間$ \frac{1}{μ} : 指数分布
c: サービスの数
窓口の数
到着の確率分布
到着間隔(指数分布)
到着個数(ポアソン分布)
サービスの確率分布
サービス時間(指数分布)
サービス数(ポアソン分布)
平均到着率: $ λ
例:
平均2件/秒の割合で発生するトランザクション→$ λ = 2[件/s]
平均到着間隔
あるトランザクションの到着から、次のトランザクションの到着までの平均時間
$ 平均到着間隔 = \frac{1}{平均到着率} = \frac{1}{\lambda}
例:
コンビニで会計が終わった後に次のお客が会計にくるまでの平均が5分に1人の場合、平均到着間隔は$ 5[分]
平均サービス率: $ μ
単位時間あたりにサービス可能なトランザクション数
例:
1件あたり平均0.3秒で処理する→$ μ = 0.3[件/s]
平均サービス時間
ひとつのトランザクションがサービスを受ける平均時間
$ 平均サービス時間 = \frac{1}{μ}
利用率: $ ρ
単位時間に窓口を利用している割合。トラフィック密度。
$ ρ = \frac{λ}{μ}
$ λ : 平均到着率
$ μ : 平均サービス率
$ 利用率(ρ) = \frac{平均サービス時間}{平均到着間隔}
$ = (\frac{1}{μ}) \div (\frac{1}{λ})
$ = (\frac{1}{μ}) \times λ
$ = \frac{λ}{μ}
例:
5分ごとに客が到着し、1人の客に対して3分でサービスする場合の利用率
$ 平均サービス時間 = 3 [分/人]
$ 平均到着間隔 = 5分
$ 利用率ρ = \frac{平均サービス時間}{平均到着間隔}= \frac{3}{5} = 0.6
待ち時間の計算
例:
1分間に5人の客がレジに到着する場合
$ 平均到着率 = 5[人/\rm{分}]
$ 平均到着間隔 = \frac{1[分]}{5[人/\rm{分}]}
待ち時間(平均応答時間$ W_w 、平均待ち時間$ W_q )
待ち時間、トランザクションが待ち行列内にいる時間
サービスを受けている時間を含めたもの 平均応答時間: $ W_w
サービスを受けている時間を除いたもの 平均待ち時間: $ W_q
平均応答時間$ W_w
ひとつのトランザクションが待ち行列内にいる時間と、平均サービス時間を足したもの
$ W_q = \frac{ρ}{1 - ρ} \times \frac{1}{μ} + \frac{1}{μ}
$ ρ : 利用率
$ \frac{1}{μ} : 平均サービス時間
平均待ち時間$ W_q
ひとつのトランザクションが待ち行列内にいて待っている時間
$ W_q = \frac{ρ}{1 - ρ} \times \frac{1}{μ}
$ ρ : 利用率
$ \frac{1}{μ} : 平均サービス時間
待ち行列の長さ(平均滞留数$ L_W 、平均待ち行列数$ L_q )
平均滞留数: $ L_W
サービス中のトランザクションを含めた待ち行列の長さ
待ち行列の長さ + サービス中のトランザクション
平均待ち行列数: $ L_q
サービス中のトランザクションを除いた待ち行列の長さ
待ち行列中の長さ
問題
例:
平均2件/秒の割合で発生するトランザクションを、1件あたり平均0.3秒で処理するシステムがある。トランザクション発生及び処理がM/M/1待ち行列モデルに従うものとすると、システムの平均応答時間は何ミリ秒か。
$ 平均到着率λ = 2[件/s]
$ 平均サービス時間 = 0.3[s/件], 平均サービス率μ = \frac{1}{0.3}[件/s]
利用率$ ρ は、
$ ρ = \frac{λ}{μ} = \frac{2}{\frac{1}{0.3}} = \frac{0.6}{1} = 0.6
平均応答時間$ W_w は
$ W_w = \frac{ρ}{1 - ρ} \times \frac{1}{μ} + \frac{1}{μ}
$ = \frac{0.6}{1 - 0.6} \times 0.3 + 0.3
$ = \frac{0.18}{0.4} + 0.3
$ = 0.45 + 0.3
$ = 0.75
確認用
Q. 待ち行列とは
Q. 待ち行列理論とは
Q. 待ち行列理論は何のために使うのか
Q. どう言う面で評価をするのか
Q. ケンドールの記号とは
Q. ケンドールの記号のA/S/cのそれぞれ
Aは何か
Sは何か
cは何か
Q. M/M/1モデル
客は[]1に到着し([]2)、一人の客がサービスをうける時間は[]3で([]4)、窓口は[]5つ([]6)という状況のモデル化
Q. M/M/1モデルの例
Q. M/M/1モデルの式
平均到着率
平均到着率とは
$ []
平均到着間隔
平均到着間隔とは
$ \frac{[]}{[]}
平均サービス率
平均サービス率とは
$ []
平均サービス間隔
平均サービス間隔とは
$ \frac{[]}{[]}
利用率
利用率とは
$ ρ = \frac{平均[]}{平均[]} = \frac{[]}{[]}
Q. 平均応答時間
Q. 平均待ち時間
Q. 平均滞留数
Q. 平均待ち行列数
関連
参考