待ち行列 の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• 待ち行列 へ行く。

[[ネットワーク用語]] ＞ 待ち行列

[[待ち行列 - 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]]