待ち行列は英語でQueue|例題や理論モデルシミュレーションをエクセルでできる

未分類

待ち行列の計算がなぜ必要なのか

情報処理技術者試験を受けたことがある人は、一度は「待ち行列問題」で悩んだことがあると思う。

例題を上げるならば↓こんな感じ↓になる。

  • レジが1台しかないコンビニがある
  • レジで精算するまでに要する時間は平均4分
  • お客さんは1時間に平均12人が来店し必ず何かを購入する
  • このコンビニの平均待ち時間と平均応答時間を求めよ

情報システムに対して、クリックする、コマンドを打ち込むなど、何らかの「要求」をすると、情報システムから「応答」が帰って来る。要求を十分にさばききれればすぐに応答が帰って来るけれど、要求が集中するような場面では、要求を「キュー(Queue)」と呼ばれるメモリに貯めて、先頭から順に処理していく。

この要求がどれだけあって、情報システムがどれだけ応えられるかを計算するのに、待ち行列理論に基づく計算が必要になる。身近な所では、ルーターと呼ばれる通信機器も、パケットを待ち行列理論に基づき処理している。

情報処理技術者ならば必須の知識と言える。

待ち行列は英語で何と言う?

待ち行列は英語でQueue。

母音が4つも続く単語はそうそうない。他に知っているのは、Hawaiian位かな。でもこれは地名が入っているからギリ反則。~iousで終わる単語があれば、もしかして母音が5つ以上続く単語があるかもね。

待ち行列の例題

窓口利用率ρとは

待ち行列問題の「窓口利用率ρ(ロー)」は、レジが一つしかないコンビニをイメージしてもらうと良い。

レジ打ち時間は平均して40秒、お客さんは平均して50秒ごとにレジに並ぶ。この場合、窓口利用率ρは40/50=0.8となる。

窓口利用率ρが1より小さいとは

ρが1より小さいならば、お客さんが何人並んでいても、レジ打ちの方が早いので、お客さんの列はやがてゼロになる。

窓口利用率ρ=1とは

レジ打ち時間が平均して40秒、お客さんは平均して40秒ごとにレジに並ぶ場合、お客さんの列は増減しない。10人並んでいたとして、先頭のお客さんがレジから離れた瞬間に一番後ろに人が並ぶから、10人が減ることはない。

窓口利用率ρが1より大きいとは

レジ打ち時間が平均して40秒、お客さんは平均して20秒ごとにレジに並ぶ場合、窓口利用率は1を超える。こうなると、お客さんの列は際限なく増え続ける。レジ打ちのアルバイトはパニックだろう。

並んでいるお客さんの数

並んでいるお客さんの数はρ/(1-ρ)で求める。この例だと0.8/0.2となり、4人となる。

平均待ち時間

目の前に4人並んでいる状態で自分が並ぶ。レジが4人のレジ打ちを終えるのに要する時間は、並んでいるお客さんの人数×レジ打ち時間なので、4人×40秒=160秒(2分40秒)となる。

平均応答時間

平均待ち時間が終われば、自分の精算が始まる。自分の清算にもやはり40秒かかるので、先ほどの160秒に40秒を足して200秒(3分20秒)となる。

待ち行列問題は難しくない

待ち行列問題の基本的なところはさして難しくはない。ρだの、λだの、μだの、普段馴染みのない記号を使うからややこしくなる。学問的厳密さはさておいて、身近な例で教えてもらえれば、もっと勉強は楽になるだろう。

待ち行列をエクセル(Excel)でシミュレートできる?

まずは窓口利用率ρを求める

窓口利用率ρを求めるのに必要なパラメータは、レジ打ち時間と来店間隔の2つ。分母が来店間隔で、分子がレジ打ち時間である。

レジ待ち人数を求める

窓口利用率ρを使ってρ/(1-ρ)で計算できる。

平均待ち時間を求める

平均待ち時間はレジ待ち人数×レジ打ち時間で計算できる。

平均応答時間を求める

平均応答時間は平均待ち時間に自分のレジ打ち時間を加算して計算する。

上記をワークシート関数で実現するだけである。

 

仙台の中学受験応援ブログ〜二華中、青陵中、宮教大付属中〜
~二華中を始めとする中学受験生とその親御さんを応援~

コメント

タイトルとURLをコピーしました