待ち行列理論

出典: フリー百科事典『ウィキペディア（Wikipedia）』

待ち行列理論（まちぎょうれつりろん　英訳：Queueing Theory）とは、顧客がサービスを受けるために行列に並ぶような確率的に挙動するシステムの混雑現象を数理モデルを用いて解析することを目的とした理論である。応用数学のオペレーションズ・リサーチにおける分野の1つに数えられる。

電話交換や情報ネットワーク、生産システム、空港や病院などの設計や性能評価に応用される。性能評価指標としては、待ち行列長や待ち時間、スループットなどが用いられる。応用の場では、システムの性能がある設計目標を満たすために必要な設計パラメータを決定する際に、その逆問題を提供することができる。

[編集] Overview

待ち行列とは、資源に対する利用要求を抽象化した数理モデルである。このようなシステムの身近な例として、銀行のATMに並ぶ顧客の列が挙げられる。待ち行列モデルでは、サーバ (server) と待合室 (waiting room) からなるシステムと、そこに到着しある時間滞在する客 (customer) を考える。銀行のATMの例では、ATMをサーバ、銀行内の待ちスペースを待合室、ATMを利用する顧客を客とみなすことができる。これらの対応は、モデル化する現象によって一意である必要はない。このため世の中の広範なシステムに対して同一の理論的枠組みで議論することができる。待ち行列の応用先としては、コールセンター、電話交換機、電話網、インターネット、サーバやルーターなどのバッファ設計、高度道路交通システム、生産システム、空港や病院などの施設設計などが存在する。

待ち行列モデルに対する理解を統一する目的から、D. G. Kendallによって1953年に導入されたのがケンドール記法である。A/B/C/Dの形でモデルの性質を表現するこの記法は、その後新たなモデルの登場に応じて拡張を施されながら、現在でもさまざまな文献で広く用いられている。ここでAは客の到着過程、Bはサービス時間分布、Cはサーバ数を表わしている。Dは待合室を含んだシステムの容量を表わしており、無限大の場合は省略される。たとえば、G/D/1は一般の到着過程を持ち、一定分布に従うサービス時間を持つ単一サーバ待ち行列を表わしている。