待ち行列
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
[[ネットワーク用語]] ＞ 待ち行列
[[待ち行列 - Wikipedia>http://ja.wikipedia.org/wiki/%E5%B...
>待ち行列（まちぎょうれつ、英: queue）
・あるサービスの提供を受けるために待っている人の行列のこ...
・計算機科学でのデータ構造の一種。→[[キュー (コンピュータ...
* 待ち行列の計算モデル [#e19fa8e6]
-「M/M/1」という計算モデルが基本です。
&ref(zu1.jpg);
「M/M/1」は、ケンドール記号と呼ばれています。
＝ケンドールという数学者が考案した、待ち行列理論に由来。
&ref(zu3.jpg);
（参考）
[[ネットワークの数学 - 待ち行列：ITpro>http://itpro.nikke...
[[ネットワークの数学 - Ｍ／Ｍ／１：ITpro>http://itpro.nik...
* 待ち行列の計算方法 [#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時間に、レジで平均20人の客をさばける場合 → μ＝20 （単位...
λとμの逆数は、時間を表しており、上記の例だと、
- 1/λ＝平均到着時間＝1/10時間＝6分。 → 平均6分で1人、レジ...
- 1/μ＝平均サービス時間＝1/20時間＝3分。 → レジで精算に要...
** 利用率 [#i0aec06e]
|記号|内容|意味|h
|ρ（ロー）|利用率|サービスの稼働率|
ρ＝λ／μ
&ref(zu2.jpg);
λ＝10、μ＝20なら、ρ＝10/20＝0.5 → 50％
つまり、レジの利用率は50％ということになる。
*** 非利用率 [#z6cf4d14]
- 利用率ρは、先客がいる確率＝待たされる確率
- 1-ρは、先客がいない確率＝待たされない確率
を表している。
確率という観点で見た場合、ρと１－ρは表裏一体ということ。
|記号|内容|意味|h
|ρ|利用率|サービスの稼働率 → レジ係が働いている割合|
|１－ρ|非利用率|サービスの非稼働率 → レジ係が暇な割合|
来客が多すぎて、
λ＞μ
の場合、レジで客をさばききれない。
λ＞μ → ρ＝λ／μ＞1
になると、待ち行列が途切れることなく、どんどん伸びていく。
＝発散して計算できなくなるので、待ち行列の問題では、たい...
** 重要公式 [#xc8881aa]
待ち行列の計算で、肝となる公式は、
>L＝&color(red){ρ／（１－ρ）};
です。
Lは、上記の図（スーパーのレジ待ち）で、自分の前に並んでい...
ポイントは、Lはレジ待ちのBだけではなく、B＋Cの部分だとい...
この公式の導出は、結構面倒くさくて、数学的な証明は、以下...
[[Ｍ／Ｍ／１型＜待ち行列＜オペレーションズ・リサーチ＜Ｗ...
[[数学トレーニング講座>http://www.geocities.co.jp/Technop...
まずは結論を覚えて、余裕があれば公式の証明も覚えよう！？
*** 人数の計算例 [#u843afad]
平均到着率λ＝16 （平均で、1時間に16人の客がレジに到着す...
平均サービス率μ＝20 （平均で、1時間に20人の客をレジで精...
の場合、
利用率ρ＝16／20＝0.8
待ち行列の長さ（待ち人数）L＝ρ／（１－ρ）＝0.8／（１－0.8...
→自分がレジに行ったら、自分の前に（1時間あたり平均で) 4人...
→上記の図では、L＝B＋Cの部分が4。つまり、レジ待ちのBが3人...
*** 時間の計算例 [#bde0ff1d]
平均到着率λ＝16 （平均で、1時間に16人の客がレジに到着す...
平均サービス率μ＝20 （平均で、1時間に20人の客をレジで精...
の場合、
平均到着(arrival)時間 Ta＝1／λ＝1／16＝0.0625時間（＝3.75...
平均サービス(service)時間 Ts＝1／μ＝1／20＝0.05時間（＝3...
+ Tw＝L×Ts
（平均待ち時間＝平均待ち人数×平均サービス時間）
L＝4人なので、
平均待ち時間Tw＝L×Ts＝4×0.05＝0.2時間（＝12分）
自分が待ち行列の最後尾に到着して、レジにたどり着くまでに...
→自分の前に4人の先客がいて、1人当たりレジを通過するのに3...
→だから、4×3分（4×0.05時間）で、12分（0.2時間）待たされる...
このLを計算するのに、1／（1－ρ）を使うところが、待ち行列...
***ターンアラウンドタイム（平均応答時間） [#r9c106dc]
平均応答時間 Tq＝Tw＋Ts
（Tqのqは、queのq）
平均応答時間Tqは、[[ターンアラウンドタイム]]とも言います。
待ち行列の計算問題では、平均待ち時間Twだけではなく、平均...
→待ち行列は、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に加えて、自分自身がサービスを受...
平均応答時間Tq＝Tw＋Ts＝0.2時間（12分）＋0.05時間（3分）...
つまり、買物が完了するまでの所要時間は、15分です。
*** 検算 [#xf2a5d62]
計算問題で、
Twを問われているのか？
Tqを問われているのか？
を間違えないようにしましょう。
＝Tqの場合、最後にTw＋Tsの計算が必要。Twを求めただけで安...
ネットワークの応答時間が問題だったら、Tqなんですよねー。
* リンク [#k873275e]
[[ターンアラウンドタイム]]
[[レスポンスタイム]]
[[ネットワークの数学 - 待ち行列：ITpro>http://itpro.nikke...
[[ネットワークの数学 - Ｍ／Ｍ／１：ITpro>http://itpro.nik...
[[サルでもわかる待ち行列>http://objectclub.jp/technicaldo...
[[Ｍ／Ｍ／１型＜待ち行列＜オペレーションズ・リサーチ＜Ｗ...
[[数学トレーニング講座>http://www.geocities.co.jp/Technop...
[[待ち行列 - 末広ページ>http://www.yscon.co.jp/j/am/kihon...
[[待ち行列の計算>http://tomari.org/main/java/machi.html]]
終了行:
[[ネットワーク用語]] ＞ 待ち行列
[[待ち行列 - Wikipedia>http://ja.wikipedia.org/wiki/%E5%B...
>待ち行列（まちぎょうれつ、英: queue）
・あるサービスの提供を受けるために待っている人の行列のこ...
・計算機科学でのデータ構造の一種。→[[キュー (コンピュータ...
* 待ち行列の計算モデル [#e19fa8e6]
-「M/M/1」という計算モデルが基本です。
&ref(zu1.jpg);
「M/M/1」は、ケンドール記号と呼ばれています。
＝ケンドールという数学者が考案した、待ち行列理論に由来。
&ref(zu3.jpg);
（参考）
[[ネットワークの数学 - 待ち行列：ITpro>http://itpro.nikke...
[[ネットワークの数学 - Ｍ／Ｍ／１：ITpro>http://itpro.nik...
* 待ち行列の計算方法 [#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時間に、レジで平均20人の客をさばける場合 → μ＝20 （単位...
λとμの逆数は、時間を表しており、上記の例だと、
- 1/λ＝平均到着時間＝1/10時間＝6分。 → 平均6分で1人、レジ...
- 1/μ＝平均サービス時間＝1/20時間＝3分。 → レジで精算に要...
** 利用率 [#i0aec06e]
|記号|内容|意味|h
|ρ（ロー）|利用率|サービスの稼働率|
ρ＝λ／μ
&ref(zu2.jpg);
λ＝10、μ＝20なら、ρ＝10/20＝0.5 → 50％
つまり、レジの利用率は50％ということになる。
*** 非利用率 [#z6cf4d14]
- 利用率ρは、先客がいる確率＝待たされる確率
- 1-ρは、先客がいない確率＝待たされない確率
を表している。
確率という観点で見た場合、ρと１－ρは表裏一体ということ。
|記号|内容|意味|h
|ρ|利用率|サービスの稼働率 → レジ係が働いている割合|
|１－ρ|非利用率|サービスの非稼働率 → レジ係が暇な割合|
来客が多すぎて、
λ＞μ
の場合、レジで客をさばききれない。
λ＞μ → ρ＝λ／μ＞1
になると、待ち行列が途切れることなく、どんどん伸びていく。
＝発散して計算できなくなるので、待ち行列の問題では、たい...
** 重要公式 [#xc8881aa]
待ち行列の計算で、肝となる公式は、
>L＝&color(red){ρ／（１－ρ）};
です。
Lは、上記の図（スーパーのレジ待ち）で、自分の前に並んでい...
ポイントは、Lはレジ待ちのBだけではなく、B＋Cの部分だとい...
この公式の導出は、結構面倒くさくて、数学的な証明は、以下...
[[Ｍ／Ｍ／１型＜待ち行列＜オペレーションズ・リサーチ＜Ｗ...
[[数学トレーニング講座>http://www.geocities.co.jp/Technop...
まずは結論を覚えて、余裕があれば公式の証明も覚えよう！？
*** 人数の計算例 [#u843afad]
平均到着率λ＝16 （平均で、1時間に16人の客がレジに到着す...
平均サービス率μ＝20 （平均で、1時間に20人の客をレジで精...
の場合、
利用率ρ＝16／20＝0.8
待ち行列の長さ（待ち人数）L＝ρ／（１－ρ）＝0.8／（１－0.8...
→自分がレジに行ったら、自分の前に（1時間あたり平均で) 4人...
→上記の図では、L＝B＋Cの部分が4。つまり、レジ待ちのBが3人...
*** 時間の計算例 [#bde0ff1d]
平均到着率λ＝16 （平均で、1時間に16人の客がレジに到着す...
平均サービス率μ＝20 （平均で、1時間に20人の客をレジで精...
の場合、
平均到着(arrival)時間 Ta＝1／λ＝1／16＝0.0625時間（＝3.75...
平均サービス(service)時間 Ts＝1／μ＝1／20＝0.05時間（＝3...
+ Tw＝L×Ts
（平均待ち時間＝平均待ち人数×平均サービス時間）
L＝4人なので、
平均待ち時間Tw＝L×Ts＝4×0.05＝0.2時間（＝12分）
自分が待ち行列の最後尾に到着して、レジにたどり着くまでに...
→自分の前に4人の先客がいて、1人当たりレジを通過するのに3...
→だから、4×3分（4×0.05時間）で、12分（0.2時間）待たされる...
このLを計算するのに、1／（1－ρ）を使うところが、待ち行列...
***ターンアラウンドタイム（平均応答時間） [#r9c106dc]
平均応答時間 Tq＝Tw＋Ts
（Tqのqは、queのq）
平均応答時間Tqは、[[ターンアラウンドタイム]]とも言います。
待ち行列の計算問題では、平均待ち時間Twだけではなく、平均...
→待ち行列は、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に加えて、自分自身がサービスを受...
平均応答時間Tq＝Tw＋Ts＝0.2時間（12分）＋0.05時間（3分）...
つまり、買物が完了するまでの所要時間は、15分です。
*** 検算 [#xf2a5d62]
計算問題で、
Twを問われているのか？
Tqを問われているのか？
を間違えないようにしましょう。
＝Tqの場合、最後にTw＋Tsの計算が必要。Twを求めただけで安...
ネットワークの応答時間が問題だったら、Tqなんですよねー。
* リンク [#k873275e]
[[ターンアラウンドタイム]]
[[レスポンスタイム]]
[[ネットワークの数学 - 待ち行列：ITpro>http://itpro.nikke...
[[ネットワークの数学 - Ｍ／Ｍ／１：ITpro>http://itpro.nik...
[[サルでもわかる待ち行列>http://objectclub.jp/technicaldo...
[[Ｍ／Ｍ／１型＜待ち行列＜オペレーションズ・リサーチ＜Ｗ...
[[数学トレーニング講座>http://www.geocities.co.jp/Technop...
[[待ち行列 - 末広ページ>http://www.yscon.co.jp/j/am/kihon...
[[待ち行列の計算>http://tomari.org/main/java/machi.html]]
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
