[[ネットワーク用語]] ＞ 待ち行列
[[待ち行列 - Wikipedia>http://ja.wikipedia.org/wiki/%E5%BE%85%E3%81%A1%E8%A1%8C%E5%88%97]]
>待ち行列（まちぎょうれつ、英: queue）
・あるサービスの提供を受けるために待っている人の行列のこと。→[[待ち行列理論>http://ja.wikipedia.org/wiki/%E5%BE%85%E3%81%A1%E8%A1%8C%E5%88%97%E7%90%86%E8%AB%96]]
・計算機科学でのデータ構造の一種。→[[キュー (コンピュータ)>http://ja.wikipedia.org/wiki/%E3%82%AD%E3%83%A5%E3%83%BC_(%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF)]]
* 待ち行列の計算モデル [#e19fa8e6]
-「M/M/1」という計算モデルが基本です。
&ref(zu1.jpg);
「M/M/1」は、ケンドール記号と呼ばれています。
＝ケンドールという数学者が考案した、待ち行列理論に由来。
&ref(zu3.jpg);
（参考）
[[ネットワークの数学 - 待ち行列：ITpro>http://itpro.nikkeibp.co.jp/article/COLUMN/20060920/248523/]]
[[ネットワークの数学 - Ｍ／Ｍ／１：ITpro>http://itpro.nikkeibp.co.jp/article/COLUMN/20060920/248528/]]
* 待ち行列の計算方法 [#l9da19ee]
「M/M/1」モデルの公式。
- 理解すべき公式
+ ρ＝λ／μ
（利用率＝平均到着率／平均サービス率）
+ L＝ρ／（１－ρ）
（待ち行列の長さ＝利用率／非利用率）
+ Tw＝L×Ts
（平均待ち時間＝待ち行列の長さ×平均サービス時間）
- 暗記すべき公式
L＝&color(red){ρ／（１－ρ）};
** 具体例 [#k39caf22]
- 待ち行列の計算は、自分がスーパーのレジに並んだときを思い出すと分かりやすいと思います。
CENTER:図：スーパーのレジ待ち
|行列に参加|待ち行列|レジ|サッカー台|h
|→◎|→○○○○|→●|→○|
|レジに向かう自分|レジ待ちの先客|レジで精算中の客|レジを終えた客|
|A|B|C|D|
~
CENTER:（人の流れは、左から右へ流れていく。）
CENTER:（行列の長さL＝B+Cの部分。AとDは、Lに含まない。）
* 用語 [#tdd2939c]
** 到着率、サービス率 [#xf8feff5]
|記号|内容|意味|h
|λ（ラムダ）|平均到着率|単位時間に、到着する客の平均値|
|μ（ミュー）|平均サービス率|単位時間に、サービスを受ける客の平均値|
- 単位時間は、一つに定める。（1時間でも、1分でもOK）
- λとμの逆数は、平均時間を表す。
1時間に、平均10人の客がレジに来る場合 → λ＝10 （単位時間は、1時間）
1時間に、レジで平均20人の客をさばける場合 → μ＝20 （単位時間は、1時間）
λとμの逆数は、時間を表しており、上記の例だと、
- 1/λ＝平均到着時間＝1/10時間＝6分。 → 平均6分で1人、レジ待ちの客が増える。
- 1/μ＝平均サービス時間＝1/20時間＝3分。 → レジで精算に要する時間は、客1人につき平均で3分。
** 利用率 [#i0aec06e]
|記号|内容|意味|h
|ρ（ロー）|利用率|サービスの稼働率|
ρ＝λ／μ
&ref(zu2.jpg);
λ＝10、μ＝20なら、ρ＝10/20＝0.5 → 50％
つまり、レジの利用率は50％ということになる。
*** 非利用率 [#z6cf4d14]
- 利用率ρは、先客がいる確率＝待たされる確率
- 1-ρは、先客がいない確率＝待たされない確率
を表している。
確率という観点で見た場合、ρと１－ρは表裏一体ということ。
|記号|内容|意味|h
|ρ|利用率|サービスの稼働率 → レジ係が働いている割合|
|１－ρ|非利用率|サービスの非稼働率 → レジ係が暇な割合|
来客が多すぎて、
λ＞μ
の場合、レジで客をさばききれない。
λ＞μ → ρ＝λ／μ＞1
になると、待ち行列が途切れることなく、どんどん伸びていく。
＝発散して計算できなくなるので、待ち行列の問題では、たいてい0＜ρ＜1に設定されてます。
** 重要公式 [#xc8881aa]
待ち行列の計算で、肝となる公式は、
>L＝&color(red){ρ／（１－ρ）};
です。
Lは、上記の図（スーパーのレジ待ち）で、自分の前に並んでいる客の平均人数を表しています。
ポイントは、Lはレジ待ちのBだけではなく、B＋Cの部分だということです。＝レジで精算中のCも含む。
この公式の導出は、結構面倒くさくて、数学的な証明は、以下のサイトに詳しいです。
[[Ｍ／Ｍ／１型＜待ち行列＜オペレーションズ・リサーチ＜Ｗｅｂ教材＜木暮>http://www.kogures.com/hitoshi/webtext/or-que-mm1/index.html]]
[[数学トレーニング講座>http://www.geocities.co.jp/Technopolis-Mars/5427/mathtrtop.html]] （待ち行列の講座あり）
まずは結論を覚えて、余裕があれば公式の証明も覚えよう！？
*** 人数の計算例 [#u843afad]
平均到着率λ＝16 （平均で、1時間に16人の客がレジに到着する）
平均サービス率μ＝20 （平均で、1時間に20人の客をレジで精算できる）
の場合、
利用率ρ＝16／20＝0.8
待ち行列の長さ（待ち人数）L＝ρ／（１－ρ）＝0.8／（１－0.8）＝0.8／0.2＝4
→自分がレジに行ったら、自分の前に（1時間あたり平均で) 4人の先客がいる、ということ。
→上記の図では、L＝B＋Cの部分が4。つまり、レジ待ちのBが3人で、レジで精算中のCが1人で、合計4人の客がいる、ということ。
*** 時間の計算例 [#bde0ff1d]
平均到着率λ＝16 （平均で、1時間に16人の客がレジに到着する）
平均サービス率μ＝20 （平均で、1時間に20人の客をレジで精算できる）
の場合、
平均到着(arrival)時間 Ta＝1／λ＝1／16＝0.0625時間（＝3.75分＝3分45秒）
平均サービス(service)時間 Ts＝1／μ＝1／20＝0.05時間（＝3分）
+ Tw＝L×Ts
（平均待ち時間＝平均待ち人数×平均サービス時間）
L＝4人なので、
平均待ち時間Tw＝L×Ts＝4×0.05＝0.2時間（＝12分）
自分が待ち行列の最後尾に到着して、レジにたどり着くまでには、12分かかります。
→自分の前に4人の先客がいて、1人当たりレジを通過するのに3分かかります。
→だから、4×3分（4×0.05時間）で、12分（0.2時間）待たされることになります。
このLを計算するのに、1／（1－ρ）を使うところが、待ち行列（M/M/1）の肝ですね？
***ターンアラウンドタイム（平均応答時間） [#r9c106dc]
平均応答時間 Tq＝Tw＋Ts
（Tqのqは、queのq）
平均応答時間Tqは、[[ターンアラウンドタイム]]とも言います。
待ち行列の計算問題では、平均待ち時間Twだけではなく、平均応答時間Tqも問われる場合があります。
→待ち行列は、TwかTqを求める2パターンしかない？
平均到着率λ＝16 （平均で、1時間に16人の客がレジに到着する）
平均サービス率μ＝20 （平均で、1時間に20人の客をレジで精算できる）
の場合、
平均サービス時間 Ts＝1／μ＝1／20＝0.05時間（＝3分）
平均待ち時間 Tw＝L×Ts＝4×0.05＝0.2時間（＝12分）
なので、
平均応答時間Tqは、自分が行列に並び始めて、レジで精算を完了して、サッカー台（レジの後ろにある、商品を袋詰めする作業台）に着くまでの時間です。
つまり、待っている時間Twに加えて、自分自身がサービスを受ける時間Ts（自分がレジを通過するときにかかる時間）を足した時間となります。
平均応答時間Tq＝Tw＋Ts＝0.2時間（12分）＋0.05時間（3分）＝0.25時間（15分）
つまり、買物が完了するまでの所要時間は、15分です。
*** 検算 [#xf2a5d62]
計算問題で、
Twを問われているのか？
Tqを問われているのか？
を間違えないようにしましょう。
＝Tqの場合、最後にTw＋Tsの計算が必要。Twを求めただけで安心しないｗ
ネットワークの応答時間が問題だったら、Tqなんですよねー。
* リンク [#k873275e]
[[ターンアラウンドタイム]]
[[レスポンスタイム]]
[[ネットワークの数学 - 待ち行列：ITpro>http://itpro.nikkeibp.co.jp/article/COLUMN/20060920/248523/]]
[[ネットワークの数学 - Ｍ／Ｍ／１：ITpro>http://itpro.nikkeibp.co.jp/article/COLUMN/20060920/248528/]]
[[サルでもわかる待ち行列>http://objectclub.jp/technicaldoc/monkey/s_wait]]
[[Ｍ／Ｍ／１型＜待ち行列＜オペレーションズ・リサーチ＜Ｗｅｂ教材＜木暮>http://www.kogures.com/hitoshi/webtext/or-que-mm1/index.html]]
[[数学トレーニング講座>http://www.geocities.co.jp/Technopolis-Mars/5427/mathtrtop.html]] （待ち行列の解説講座あり）
[[待ち行列 - 末広ページ>http://www.yscon.co.jp/j/am/kihonyougo/queuingtheory.htm]]
[[待ち行列の計算>http://tomari.org/main/java/machi.html]]
