待ち行列理論についてまとめてみる
さて、あかわらずイマイチしっくりきてないんだけども、自分なりにまとめてみた。
同じ様な感じで、まとめている人がいて、すごく参考になった。
理解してないことを自分なりにまとめてみると、勉強になると同時に「まとめる作業」は難しいなあって思う。
また、「勉強の仕方」も勉強したい。
待ち行列理論について
待ち行列理論は、行列の時間やサービス等を導きだす理論である(と思う)
応用情報レベルでは、主にM/M/1モデル(エムエムワン)に基づいて考えられる。
この記事とかで、現実でも応用できそうな事が書いてあるけれども、実際の所、結構な前提条件によって成り立っている。
前提条件(M/M/1)
1.常に窓口(サービスを受ける場所)は1つである。
2.当然、サービスを受けるのは一人ずつである。
3.当然、列は一列。
4.並んでいる人は途中で抜ける事はない(!)
5.客の到着はポアソン分布に従う
6.サービス時間は指数分布に従う
■ポアソン分布：到着の仕方■
定常性...どの時間でも客の到着の仕方は一定
(時間辺りに多くなったり、少なくなったりはしない。実際にはありえん)
独立性...客は周りの影響されない
(混んでるから止めたとかはない)
希少性...同時には来ない
(数学の理論的には同時にくるとマズいのだ)
■指数分布：サービスの時間■
マルコス性...サービスの時間は常に一定
(これも基本ありえん)
んで、上記の前提を考慮した上で、
待ち行列の基本要素
(ここは覚えるしか無い)
①利用率(ρ)[ロー]...単位時間に窓口を利用している割合
公式:平均到着率/平均サービス率
覚え方:「1より少ない場合空いている」ということを覚えておけば、自ずとサービス率が分母になるということがわかる
②平均到着率(λ)[ラムダ]...1時間(分)あたりに到着する人数
③平均到着時間...１人が到着する時間
当然ながら、②と③は逆数で求められる
例)1時間に10人来客がある場合、一人は6分間隔で現れる。これらはお互いに逆数である。
④平均サービス率(μ)[ミュー]...1時間あたりにサービスを受ける人数
⑤平均サービス時間...1人がサービスを受ける時間
※②③と同じ考え方
さらに、こっからが覚えづらい
⑥平均滞留数(Lw)...待ち数+サービスを受けている人
⑦平均待ち行列長(Lq)...待ち数(つまりLw - 1)
⑧平均応答時間(Ww)...並んだ時間+サービスを受ける時間
⑨ 平均待ち時間(Wq)...並んだ時間(つまりWw - 1)
→ρ/1-ρ * 平均サービス時間
この公式がミソ。しかしながら、なぜこう成るのかは、難しい。
簡単に分解するなら、待っている時間は当然、
待ってる人数 * １人当たりのサービス時間
よって、ρ/1-ρ = 待ってる人数
なぜ、「ρ/1-ρ = 待ってる人数」なのか?
これは覚えるのだ....
全体を通じていろんな記号が出て来てややこしく感じるが、応用レベルならこんだけ覚えとけば、大抵の問題は解ける!
■応用情報技術者 平成22年春期_午前問3
多数のクライアントが，LANに接続された1台のプリンタを共同利用するときの印刷要求から印刷完了までの所要時間を，待ち行列理論を適用して見積もる場合について考える。プリンタの運用方法や利用状況に関する記述のうち，M/M/1の待ち行列モデルの条件に反しないものはどれか。
1.一部のクライアントは，プリンタの空き具合をみながら印刷要求する。
クライアント毎の差はないはずなので×
2.印刷の緊急性や印刷量の多少にかかわらず，先着順に印刷する。
常に一定で、先着順。正しい
3.印刷待ちの文書データがプリンタのバッファサイズを越えるときは，一時的に受付を中断する
前提条件を知ってればありえん答え、よって×
4.一つの印刷要求にかかる時間は，印刷の準備に要する一定時間と，印刷量に比例する時間の合計である。
一つの印刷要求にかかる時間=平均滞留数Lw
印刷の準備に要する時間=Lq
Lw = Lq + サービス時間
印刷量に比例する時間の合計 ≠ サービス時間
よって違う。
平成14年度春期 午前_問33
自動支払機が1台ずつ設置してあった二つの支店を統合し，統合後の支店には自動支払機を1台設置する。統合後の自動支払機の平均待ち時間を求める式はどれか。ここで，待ち時間はM/M/1の待ち行列モデルに従い，平均待ち時間にはサービス時間を含まないものとする。
〔条件〕
（1）平均サービス時間：TS
（2）統合前のシステムの利用率：両支店ともρ
めんどくさいので、答えの候補は書かないけど、
上記の公式を使って平均待ち時間を求めるとすれば、
平均待ち時間 = ρ/1-ρ * 平均サービス時間
問題の場合、利用率は(2)(3)より2ρ。よって、答えは明確!
てな感じッス！
(あ、もっと綺麗にまとめれればよかったけど、記事書くの途中でちょっとめんどくさくなった。
