ようこそ!逆襲のニートブログへ

ブログ内検索

最近の記事

はてなブックマーク数

この日記のはてなブックマーク数

カテゴリー

月別アーカイブ

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

待ち行列の計算方法

情報処理試験の過去問で、待ち行列の問題があった。
この機会に理解しておきたい。

●待ち行列とは?
待ち行列 - Wikipedia

待ち行列(まちぎょうれつ、英: queue)
あるサービスの提供を受けるために待っている人の行列のこと。→待ち行列理論
計算機科学でのデータ構造の一種。→キュー (コンピュータ)



待ち行列がわかる本―情報処理試験もバッチリ
桐山 光弘
日刊工業新聞社
1997-09


検索すると、いろんな解説記事がヒットするが、
自分としては、スーパーのレジの例え話が、一番分かりやすいモデルだった。

ネットワークの数学 - 待ち行列:ITpro
ケンドールの記法



ネットワークの数学 - M/M/1:ITpro
M/M/1の待ち行列モデル

利用率、到着率、サービス率

M/M/1の公式



- サルでもわかる待ち行列
ρ/(1-ρ)のグラフ
この記事では、病院の例え話で説明してあった。

λ ..... とぼとぼ歩く患者...とぼとぼとぼ


μ ..... さらさら書く医者のカルテ...さらさらさら


μμμμμ           λλλλλλ
診る医者  ← 受け付け ←  来る患者
さらさら            とぼとぼ


ρ = λ/μ (混み具合) ... 利用の回転... くるくる


擬態語が面白い!(・∀・)
だけども、だっけっど…





ん~、ここの説明、基本分かりやすくていいんだけど、ちょっとだけ分かりづらい部分があった。
(他のサイトと併せて読んだら、やっと理解できた。)

・分かりづらかった点

いきなり結論

さて,一気に結論を言ってしまいます.「混み具合」を「ρ」(ロー)というギリシャ文字で表すと,あなたが医者に行くと,あなたの待つ時間は,

待ち時間 = ρ/(1-ρ) [人分]

です.

ここで,[人分]と書いたのは,あなたの前にはすでにρ/(1-ρ)人が並んで待っているということです.



「待ち時間」という表現が、困惑を生む原因だった。
→正確には、「待ち時間」ではなくて、「待っている人数」に相当すると思う。

Tw[待ち時間] = ρ/(1-ρ)[待ち人数] × Ts[サービス時間]

つまり、自分の前に5人待っているとして、1人当たりのサービス時間(処理にかかる時間)が3分だった場合、
5人×3分=15分待たされるということ。

よく読めば、単位が「人分」となっているし、「並んで待っている」という説明が付記されているから、待ち人数であることは、理解できるのだろうが、やはり「待ち時間=」という表現にとらわれてしまって、なかなかスッキリと理解できなかった。orz

この点を除けば、サルでもわかる待ち行列の説明が、一番分かりやすかったです。

窓口が1個の場合と、窓口が2個の場合を比較して、計算できれば、一応待ち行列の基本は理解できているといえるかな?



・その他、参考になったサイト
待ち行列 - 末広ページ
→ρ/1-ρ
=利用率/(1-利用率)
=利用時間/非利用時間
=「発揮指数」と命名。

ρ=λ/μは、μがゼロにならない限り、有限の値。
μ<λになると、処理が追いつかなくなって、行列が途切れなくなる?
→ 1<ρになっちゃう。

客が殺到=銀行の取り付け騒ぎとかですねw
取り付け騒ぎ - Wikipedia

取り付け騒ぎ(とりつけさわぎ)とは、特定の金融機関や金融制度に対する信用不安などから、預金者が預金・貯金・掛け金等を取り戻そうとして(=取り付け)、急激に金融機関の店頭に殺到し、混乱をきたす現象のこと。


銀行の取り付け騒ぎ

情報処理試験で出てくる待ち行列は、たいてい処理がオーバーフローしない範囲で設定されている。
だから、0≦ρ≦1で考えればOK。
分母も、0≦1-ρ≦1となり、計算しやすい。

末広ページの説明は、自分がスーパーの買い物客になったつもりで、レジ待ちの場合で例えてある。
具体的にイメージしやすくて、各値の意味が理解できた。

待ち行列の計算
計算のシミュレーター
→具体的に、待ち時間を計算できて、分かりやすくなる。

待ち行列の長さ(人数)について、違いを注意。
M/M/1型<待ち行列<オペレーションズ・リサーチ<Web教材<木暮

公式のまとめ(これは覚えてください)

  客の平均到着率:    λ[人/時] ⇔ 平均到着間隔:  1/λ[時/人]
  窓口の平均サービス率: μ[人/時] ⇔ 平均サービス時間:1/μ[時/人]
    ρ=λ/μ 窓口の稼働率,客が到着したとき待ちが生じる確率

  系の中に人がいない確率: P0=1-ρ (待たないでよい確率)
  系の中にn人がいる確率: Pn=ρnP0=ρn/(1-ρ)
  
  サービスを待っている人の平均人数:Lq=ρ2/(1-ρ)
  サービス中も含む系内の平均人数: L=Lq+λ/μ=ρ/(1-ρ)

  到着してからサービスを受けるまでの平均待ち時間: Wq=Lq/λ=λ/μ(μ-λ)
  到着してからサービスを受けて去るまでの平均時間: W=Wq+1/μ=1/(μ-λ)
   (上の赤い部分リトルの公式です。)



>サービスを待っている人の平均人数:Lq=ρ2/(1-ρ)
>サービス中も含む系内の平均人数: L=Lq+λ/μ=ρ/(1-ρ)

あれ~?
サービスを待っている人の平均人数=待ち行列の長さが、ρ/(1-ρ)だと思ったけど、サービス中も含んでいるんだな?

意味が深く理解できていないけど、計算するときに、微妙な違いがあったら、注意しよう!
=設問の罠に注意!

連載の詳しい解説もあり。
数学トレーニング講座
待ち行列(1) http://www.geocities.co.jp/Technopolis-Mars/5427/math/sw_waitque1.html
待ち行列(2) http://www.geocities.co.jp/Technopolis-Mars/5427/math/sw_waitque2.html
待ち行列(3) http://www.geocities.co.jp/Technopolis-Mars/5427/math/sw_waitque3.html
待ち行列(4) http://www.geocities.co.jp/Technopolis-Mars/5427/math/sw_waitque4.html
待ち行列(5) http://www.geocities.co.jp/Technopolis-Mars/5427/math/sw_waitque5.html
待ち行列(6) http://www.geocities.co.jp/Technopolis-Mars/5427/math/sw_waitque6.html
待ち行列(7) http://www.geocities.co.jp/Technopolis-Mars/5427/math/sw_waitque7.html
待ち行列(8) http://www.geocities.co.jp/Technopolis-Mars/5427/math/sw_waitque8.html

あとは、計算問題で練習して、各値の出し方を体得するだけだな!
関連記事

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバックURL:
http://gooddays1.blog37.fc2.com/tb.php/900-9b049d87

FC2Ad

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。