待ち行列理論(2016／09／24) 【1.待ち行列理論】 駅や銀行などの窓口では利用者が多くなり、処理が混んでくると待ち行列ができる。 このとき、窓口の処理時間や単位時間の利用者数によって、待たされる時間や自分の 前に何人が並んでいるかなどを考えるのが待ち行列理論である。 窓口が一つの場合で考える。 窓口で一件を処理する時間（以降、平均処理時間とする）をTprocess(秒)とする。 窓口には1Hrで X人がやってくるとしよう。 つまり、窓口1つの単位時間の処理件数を X とする。 1Hrに X人がやってきて一人当たり平均処理時間 Tprocess(秒)要するなら、 処理時間合計(秒)＝X・Tprocess となる。 従って、窓口の1Hrあたりの利用率ρ（以降、利用率とする）については 利用率ρ＝処理時間合計(秒)／3600＝X・Tprocess／3600秒 窓口の利用率ρが高い場合、利用者が待たされる時間は伸びることになる。 利用者の平均の待たされる率 Wwait(以降、平均待ち率 Wwait とする)が、利用率ρに比例し、不使用率 (＝1－ρ)に反比例するものと考えると 平均待ち率 Wwait＝ρ／(1－ρ) （※平均待ち率をもう少し分かりやすく言えば、一番最後に列に並んだ人から見て、サービスを 受けている人の未処理分の待ちと自分の前に並んでいる人の数である。 例えば 平均待ち率＝2.3のときは 窓口でサービスを受けている人は処理の7割が済み、未処理のサービスは3割(0.3人分)であり、 サービスをまだ受けていない人については自分の前に2名が並んでいることになる。 つまり2.3人分の待ちが生じている。） 利用者の平均待ち時間 Wは平均処理時間 Tprocessに平均待ち率 Wwaitをかけたものになるので 平均待ち時間 Wtime ＝平均処理時間 Tprocess・平均待ち率 Wwait ∴ 平均待ち時間 Wtime ＝Tprocess・ρ／(1－ρ) 一人当たりの待ち時間と窓口での平均処理時間の合計（以降、待ち含み平均処理時間Ttotalとする） ＝平均処理時間 Tprocess＋平均待ち時間 Wtime なので Ttotal＝ Tprocess＋Wtime＝ Tprocess＋Tprocess・ρ／(1－ρ) ＝ Tprocess／(1－ρ) さて、銀行にATMが1台しかなく一件あたり処理時間が2分で1時間で20人が利用している場合で 計算してみよう。 平均処理時間 Tprocess(秒)＝120秒 銀行を訪れる利用者は1時間で20名であり、ATMは1台なので、ATMの単位時間の処理件数 X は20件になる。 従って、X＝20である 利用率ρ＝X・Tprocess／3600＝20・120／3600＝2／3 平均待ち率 Wwait＝ρ／(1－ρ)＝(2／3)／(1－(2／3))＝2 (＝列の最後の人の前に2人が並んでいる） 平均待ち時間 Wtime ＝Tprocess・Wwait＝120・2＝240秒 待ち含み平均処理時間Ttotal＝ Tprocess／(1－ρ)＝120／(1－(2／3))＝360秒 つまり、まったく混んでいなくて、待ちなしですぐにATMが使える場合、平均処理時間 Tprocess＝120秒で済むが、 1Hrあたり20名の利用者がある場合は、平均待ち時間 Wtime は4分(＝240秒)であり、窓口処理時間(2分)を加えた 待ち含み平均処理時間Ttotalは360秒(6分)となる。 また、利用者がATMを利用するために訪れたとき、ATMが塞がっている確率は利用率ρ(＝2／3)と同じであり 66.7%であり、ATMが空いている確率は1－ρ＝1／3＝33.3%である。 ここで示した窓口一つの待ち行列モデルはケンドールの記号でMM1型と呼ばれるが、単位あたりの利用者が 増加してくると待ち時間が急速に大きくなる。このような場合は窓口を増やすことで待ち時間を大きく改善 できる。複数窓口の場合は別の機会に紹介する予定である。 【2．コンピュータ処理での待ち行列理論の応用】 ここまで述べてきた待ち行列理論の考え方は、ある処理装置で処理一件当たりの平均処理時間と1Hr当たりの処理 件数を元に待ちを含む処理時間を求める場合に応用できる。コンピュータのオンライン処理に関する1Hr当たりの 処理件数と応答時間の変化を計算する場合にも最適である。それでは以下の事例で応用してみよう。 ある特定処理専用のコンピュータ1台でまったく混んでないときの平均応答時間（＝平均処理時間）を0.5秒とする。 ある時間帯でその特定処理件数が6480件／Hrに達したとき、応答時間はどうなるか。コンピュータは特定処理以外は 実行しないものとする。 平均処理時間(＝平均応答時間）Tprocess＝0.5秒 利用率ρ＝単位時間当たり処理件数 X(6480件)・平均処理時間 Tprocess(0.5秒)／3600秒＝3240/3600＝0.9＝90% 待ち含み平均処理時間Ttotal＝ Tprocess／(1－ρ)＝0.5／(1－0.9)＝5 つまり、全く混んでない時点（利用率ρがほとんど0のとき)は0.5秒でコンピュータは処理結果を返してくるが 混雑度である利用率が90%のときは応答時間は10倍の5秒にも伸びてしまうのである。 尚、処理の限界は利用率=100%であり、それ以上の処理はできない。この例ではρ＝100%となるのは7200件／Hrの ときであり、ρ＝100%になった場合は後続の処理が同じペースで押し寄せる場合、計算上の待ち時間は無限大になる。 --------------------------------------------------------------- 窓口一つでの処理のときの待ち行列計算 (ホームへ) このページの無断引用を禁じます。