待ち行列理論(Queue Theory)

Blue Dreams　→　ソフトウェア開発の対策　→　待ち行列理論（ポイント重点対策）
Make:2001/03/09　Last-Update:2001/09/13

2001/09/13　「計算問題　１．平均到着率」でのミスを修正しました。

　>>はじめに（注意事項、問題の傾向）
　ここでは、ソフトウェア開発技術者試験だけでなく、ネットワーク試験（テクニカルエンジニア）の基礎にもなる待ち行列理論について解説します。待ち行列理論の範囲は広いため、ここですべてを取り上げる事は不可能（１冊の本を書ける量になりえませんし、大学教養範囲の数学の能力も必要とされる。）ですので、あくまで試験対策用として書いています。

　過去の試験から見て、問題の種類は次の２種類に分類されます。（下線付きの問題を下で解説しています）
　１．待ち行列（Ｍ／Ｍ／１）を考慮した計算問題、レスポンスタイムの算出など
　　　　　Ｈ８　問３４　　Ｈ９　問５６　　Ｈ12　問５２

　２．Ｍ／Ｍ／１など待ち行列に関する定義・特性
　　　　　Ｈ７　問４０　　Ｈ９　問８０　　Ｈ10　問５３
　　　　　Ｈ11　問５２　　Ｈ12　問５６

　ここ数年は毎年出題されていますし、得点できるところはできるだけ得点しましょう。また、待ち行列でもＭ／Ｍ／１がメインであり、狭い範囲に収束されていますので、対策も割と容易です。押さえるべきポイントを一つずつ着実に理解してください。


　>>待ち行列について
　私たちの普段の生活の中には、"待ち行列"がたくさん潜んでいます。
　例えば、スーパーマーケットへ買い物に行ったときのことをイメージしてください。食事の材料や生活用品等、買うものをカゴに入れていき、それを済ませたらレジに並ぶ事になります。そして、前の人が勘定を済ませるまで待ち、自分の番が来たら勘定を済ませることになります。この一連の流れが待ち行列を表しています。
　イメージ図を示します。それと共に、待ち行列理論で用いられる３つの用語も表記します。 　　
　母集団は、窓口でサービスを受けるもの全部を表しています。
　窓口は、母集団からの要求に対してサービスを提供します。
　そして待ち行列は、"窓口でのサービスの能力"などの要因により、母集団からの到着に対応しきれなくなった時発生する、待ちの状態です。


　>>ケンドール記号
　待ち行列の特徴を［到着分布／サービス時間分布／窓口数／（待ち行列の長さ）］で表します。到着分布、サービス時間分布については、以下のパラメータを用い（主に用いられるものをピックアップした）、窓口数には自然数を用います。待ち行列の長さは特に指定しなければ、∞（無限大、すなわち長さ制限無し）となります。
　また、窓口におけるサービスは先着順（FIFO:First In First Out）である、行列の途中からの抜け出しや割り込みはなしとする、ことをケンドール記号の前提条件としてあげています。
パラメータ到着分布の種類サービス時間分布の種類
Ｍポアソン分布
（ランダム到着）		指数分布サービス
Ｄ等間隔到着一定時間サービス
Ｇ一般分布到着一般分布サービス
Ｅkｋ次のアーラン分布到着−
例）
Ｍ／Ｍ／１
・客の到着分布はポアソン分布（ランダム到着）に従う
・窓口のサービス時間は指数分布に従う
・窓口は一つである
・待ち行列の長さに制限が無い
・サービスは先着順に受ける
・行列から、客が立ち去ったり割り込んだりしない

Ｍ／Ｄ／１
・客の到着分布は同上
・窓口のサービス時間は一定である
・以下、上記Ｍ／Ｍ／１モデルに同じ


　>>計算問題

１．平均到着率　 λ （ラムダ）　[件（人）／秒]
　単位時間（例えば１秒）あたりに到着する客の数

　１時間あたり平均９０人が到着するとすれば、λ＝９０／３６００＝０．０２５[人／秒]

　１秒あたり０．０２５人が訪れるということは、４０秒間隔で１人到着することを表す。
　これを平均到着間隔ｔａ（tはtime、aはarrival）で表し、ｔａ＝１／λ。
　この例の場合、ｔａ＝１／０．０２５＝４０[秒／人]
（←ｔａ＝１／０．２５＝４[秒／人]になってました！すいません。）

２．平均サービス時間　ｔｓ（tはtime、sはservice）　［秒／件（人）］
　窓口において、要求されたサービス１件を処理するのにかかる時間

　平均サービス時間は、窓口が何であるかを見きわめてｔｓを算出する必要がある。


　以下、Ｍ／Ｍ／１モデルについて解説します。窓口が２つ（Ｍ／Ｍ／２）になったり、サービス時間が一定（Ｍ／Ｄ／１）の場合では計算式が異なる事に留意してください。なお、Ｍ／Ｍ／１の式を理解しておけば、今挙げたモデルの基礎になります。
　（注：正式には窓口が２つ存在する場合必ずしもＭ／Ｍ／２になるとは限りません。関連事項を後述することにします。）


３．平均利用率　 ρ （ロー）　[単位無し]
　窓口がどれだけ利用されているかの尺度

　 ρ ＝ λ ・ｔｓ

　Ｍ／Ｍ／１モデルを採用するものとし、１時間あたり平均９０人が到着して、平均サービス時間が３０秒の場合を考えてみます。
　λ ＝９０／３６００＝０．０２５[人／秒]　　ｔｓ＝３０[秒／人]
　よって、ρ ＝ λ ・ｔｓ＝０．０２５×３０＝０．７５

　また、ρ は必ず１より小さくなければならない。 ρ ≧１の場合、到着間隔より処理時間が長い、すなわち待ち行列がどんどん長くなることを意味し、いつまで経っても処理がされない状態を指します。

４．平均待ち時間　ｔｗ（tはtime、wはwait）　[秒]
　待ち行列に並んで、サービス処理が開始されるまでの待ち時間

　ｔｗ＝ ρ ／（１− ρ ）・ｔｓ

　３．の例で算出すると、
　ｔｗ＝０．７５／（１−０．７５）×３０＝９０[秒]

　また、待ち行列に並んで、サービス処理が終了するまでの時間Ｔを求めます。
　この場合は時間の流れ（並んで待ったあと、サービスを受ける）に沿って、単に平均待ち時間＋平均サービス時間を算出すれば良いです。
　Ｔ＝ｔｗ＋ｔｓ
　３．の例では、Ｔ＝９０＋３０＝１２０[秒]となる。


　>>過去問題
簡単な部類の問題として、４問を解説します。

Ｈ８　問３４

　通信回線を使用したデータ伝送システムにＭ／Ｍ／１モデルの待ち行列理論を適用すると、平均待ち時間、平均伝送時間、回線利用率の関係は図の式で表される。
　平均回線待ち時間が平均伝送時間よりも長くなるのは、回線利用率（％）がどの値を超える場合か。

ア　４０　　イ　５０　　ウ　６０　　エ　７０　　オ　８０

--------
待ち時間ｔｗは、ｔｗ＝ρ／（１−ρ）×ｔｓで求められました。
式を見てのとおりｔｗがｔｓよりも長くなる条件は、ρ／（１−ρ）が１より大きくなるときですね。
ρ／（１−ρ）≧１
ρ≧１−ρ
２ρ≧１
∴　ρ≧０．５
答えは百分率に直すと５０％以上となります。
--------


Ｈ９　問５６

　単一処理を行うオンラインシステムがある。トランザクションは１秒当たり平均０．６件到着し、このトランザクションに対する平均サービス時間は７５０ミリ秒／件である。このときの平均応答時間は何秒か。

ア　０．４５　　イ　０．６１　　ウ　１．２５　　エ　１．３６

-------
平均応答時間とあるが、これは平均待ち時間＋平均サービス時間を表す。

１．問題文から平均到着率λと平均サービス時間ｔｓを見つける
「トランザクションは１秒当たり平均０．６件到着」→λ（平均到着率）＝０．６件／秒
「平均サービス時間は７５０ミリ秒／件」→ｔｓ（平均サービス時間）＝０．７５秒／件

２．回線利用率の計算
ρ＝λ×ｔｓ＝０．６×０．７５＝０．４５

３．前の結果を用いて平均待ち時間と平均応答時間を計算
ｔｗ＝０．４５／（１−０．４５）×０．７５≒０．６１
Ｔ＝ｔｓ＋ｔｗ＝０．７５＋０．６１＝１．３６
-------


Ｈ１２　問５２

　Ｍ／Ｍ／１待ち行列における、平均待ち時間（Ｗ）と窓口利用率（ρ）の関係で、ρが０．２５から０．７５になったとき、Ｗは何倍になるか。

ア　１／３　　イ　３　　ウ　４．５　　エ　９

-------
ρが０．２５のときと、０．７５のときの平均待ち時間Ｗを求める。
・ρ＝０．２５のとき
Ｗ１＝０．２５／０．７５×ｔｓ＝ｔｓ／３

・ρ＝０．７５のとき
Ｗ２＝０．７５／０．２５×ｔｓ＝ｔｓ×３

Ｗ２／Ｗ１＝（ｔｓ×３）／（ｔｓ／３）＝９
-------


Ｈ７　問４０

　Ｍ／Ｍ／１の待ち行列モデルに関して、正しい記述はどれか。

ア．一定時間に到着する客の数は指数分布に従う。
イ．客が立ち去ることがある。
ウ．サービス時間は指数分布に従う。
エ．待ち行列の長さに制限がある。
オ．窓口は複数個のことがある

-------
Ｍ／Ｍ／１の待ち行列、ケンドール記号について思い出してみましょう。

ア／到着率はポアソン分布（ランダム到着）であるので×
イ／ケンドール記号の前提で「立ち去る事はないこととする」としているので×
ウ／正解
エ／Ｍ／Ｍ／１／∞と表現されるところを省略してＭ／Ｍ／１としている。∞は待ち行列に制限がないことを表すので×
オ／窓口数は１個であるので×
-------