ネットワーク用語 > 待ち行列
待ち行列(まちぎょうれつ、英: queue)
・あるサービスの提供を受けるために待っている人の行列のこと。→待ち行列理論
・計算機科学でのデータ構造の一種。→キュー (コンピュータ)
待ち行列の計算モデル †
- 「M/M/1」という計算モデルが基本です。
「M/M/1」は、ケンドール記号と呼ばれています。
=ケンドールという数学者が考案した、待ち行列理論に由来。
(参考)
ネットワークの数学 - 待ち行列:ITpro
ネットワークの数学 - M/M/1:ITpro
待ち行列の計算方法 †
「M/M/1」モデルの公式。
- 理解すべき公式
- ρ=λ/μ
(利用率=平均到着率/平均サービス率) - L=ρ/(1-ρ)
(待ち行列の長さ=利用率/非利用率) - Tw=L×Ts
(平均待ち時間=待ち行列の長さ×平均サービス時間)
- 暗記すべき公式
L=ρ/(1-ρ)
具体例 †
- 待ち行列の計算は、自分がスーパーのレジに並んだときを思い出すと分かりやすいと思います。
行列に参加 | 待ち行列 | レジ | サッカー台 |
→◎ | →○○○○ | →● | →○ |
レジに向かう自分 | レジ待ちの先客 | レジで精算中の客 | レジを終えた客 |
A | B | C | D |
用語 †
到着率、サービス率 †
記号 | 内容 | 意味 |
λ(ラムダ) | 平均到着率 | 単位時間に、到着する客の平均値 |
μ(ミュー) | 平均サービス率 | 単位時間に、サービスを受ける客の平均値 |
- 単位時間は、一つに定める。(1時間でも、1分でもOK)
- λとμの逆数は、平均時間を表す。
1時間に、平均10人の客がレジに来る場合 → λ=10 (単位時間は、1時間)
1時間に、レジで平均20人の客をさばける場合 → μ=20 (単位時間は、1時間)
λとμの逆数は、時間を表しており、上記の例だと、
- 1/λ=平均到着時間=1/10時間=6分。 → 平均6分で1人、レジ待ちの客が増える。
- 1/μ=平均サービス時間=1/20時間=3分。 → レジで精算に要する時間は、客1人につき平均で3分。
利用率 †
記号 | 内容 | 意味 |
ρ(ロー) | 利用率 | サービスの稼働率 |
ρ=λ/μ
λ=10、μ=20なら、ρ=10/20=0.5 → 50%
つまり、レジの利用率は50%ということになる。
非利用率 †
- 利用率ρは、先客がいる確率=待たされる確率
- 1-ρは、先客がいない確率=待たされない確率
を表している。
確率という観点で見た場合、ρと1-ρは表裏一体ということ。
記号 | 内容 | 意味 |
ρ | 利用率 | サービスの稼働率 → レジ係が働いている割合 |
1-ρ | 非利用率 | サービスの非稼働率 → レジ係が暇な割合 |
来客が多すぎて、
λ>μ
の場合、レジで客をさばききれない。
λ>μ → ρ=λ/μ>1
になると、待ち行列が途切れることなく、どんどん伸びていく。
=発散して計算できなくなるので、待ち行列の問題では、たいてい0<ρ<1に設定されてます。
重要公式 †
待ち行列の計算で、肝となる公式は、
L=ρ/(1-ρ)
です。
Lは、上記の図(スーパーのレジ待ち)で、自分の前に並んでいる客の平均人数を表しています。
ポイントは、Lはレジ待ちのBだけではなく、B+Cの部分だということです。=レジで精算中のCも含む。
この公式の導出は、結構面倒くさくて、数学的な証明は、以下のサイトに詳しいです。
M/M/1型<待ち行列<オペレーションズ・リサーチ<Web教材<木暮
数学トレーニング講座 (待ち行列の講座あり)
まずは結論を覚えて、余裕があれば公式の証明も覚えよう!?
人数の計算例 †
平均到着率λ=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人の客がいる、ということ。
時間の計算例 †
平均到着率λ=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)の肝ですね?
ターンアラウンドタイム(平均応答時間) †
平均応答時間 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分です。
検算 †
計算問題で、
Twを問われているのか?
Tqを問われているのか?
を間違えないようにしましょう。
=Tqの場合、最後にTw+Tsの計算が必要。Twを求めただけで安心しないw
ネットワークの応答時間が問題だったら、Tqなんですよねー。
リンク †
ネットワークの数学 - 待ち行列:ITpro
ネットワークの数学 - M/M/1:ITpro
サルでもわかる待ち行列
M/M/1型<待ち行列<オペレーションズ・リサーチ<Web教材<木暮
数学トレーニング講座 (待ち行列の解説講座あり)