- 追加された行はこの色です。
- 削除された行はこの色です。
[[ネットワーク用語]] > 待ち行列 [[待ち行列>http://ja.wikipedia.org/wiki/%E5%BE%85%E3%81%A1%E8%A1%8C%E5%88%97]] [[待ち行列 - 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/]] [[ネットワークの数学 - M/M/1:ITpro>http://itpro.nikkeibp.co.jp/article/COLUMN/20060920/248528/]] * 待ち行列の計算方法 [#l9da19ee] 「M/M/1」モデルの公式。 - 理解すべき公式 + ρ=λ/μ (利用率=平均到着率/平均サービス率) + L=ρ/(1-ρ) (待ち行列の長さ=利用率/非利用率) + Tw=L×Ts (平均待ち時間=待ち行列の長さ×平均サービス時間) - 暗記すべき公式 L=&color(red){ρ/(1-ρ)}; ** 具体例 [#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-ρは、先客がいない確率=待たされない確率 を表している。 確率という観点で見た場合、ρと1-ρは表裏一体ということ。 |記号|内容|意味|h |ρ|利用率|サービスの稼働率 → レジ係が働いている割合| |1-ρ|非利用率|サービスの非稼働率 → レジ係が暇な割合| 来客が多すぎて、 λ>μ の場合、レジで客をさばききれない。 λ>μ → ρ=λ/μ>1 になると、待ち行列が途切れることなく、どんどん伸びていく。 =発散して計算できなくなるので、待ち行列の問題では、たいてい0<ρ<1に設定されてます。 ** 重要公式 [#xc8881aa] 待ち行列の計算で、肝となる公式は、 >L=&color(red){ρ/(1-ρ)}; です。 Lは、上記の図(スーパーのレジ待ち)で、自分の前に並んでいる客の平均人数を表しています。 ポイントは、Lはレジ待ちのBだけではなく、B+Cの部分だということです。=レジで精算中のCも含む。 この公式の導出は、結構面倒くさくて、数学的な証明は、以下のサイトに詳しいです。 [[M/M/1型<待ち行列<オペレーションズ・リサーチ<Web教材<木暮>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=ρ/(1-ρ)=0.8/(1-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を求めただけで安心しないw ネットワークの応答時間が問題だったら、Tqなんですよねー。 * リンク [#k873275e] [[ターンアラウンドタイム]] [[レスポンスタイム]] [[ネットワークの数学 - 待ち行列:ITpro>http://itpro.nikkeibp.co.jp/article/COLUMN/20060920/248523/]] [[ネットワークの数学 - M/M/1:ITpro>http://itpro.nikkeibp.co.jp/article/COLUMN/20060920/248528/]] [[サルでもわかる待ち行列>http://objectclub.jp/technicaldoc/monkey/s_wait]] [[M/M/1型<待ち行列<オペレーションズ・リサーチ<Web教材<木暮>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]]