待ち行列理論
待ち行列理論（まちぎょうれつりろん 英語: Queueing Theory）とは、顧客がサービスを受けるために行列に並ぶような確率的に挙動するシステムの混雑現象を数理モデルを用いて解析することを目的とした理論である。応用数学のオペレーションズ・リサーチにおける分野の一つに数えられる。
電話交換機や情報ネットワーク、生産システム、空港や病院などの設計や性能評価に応用される。性能評価指標としては、待ち行列長・待ち時間・スループットなどが用いられる。応用の場では、システムの性能がある設計目標を満たすために必要な設計パラメータを決定する際に、その逆問題を提供できる。
概要
待ち行列とは、資源に対する利用要求を抽象化した数理モデルである。このようなシステムの身近な例として、銀行のATMに並ぶ顧客の列が挙げられる。待ち行列モデルでは、サーバ (server) と待合室 (waiting room) からなるシステムと、そこに到着しある時間滞在する客 (customer) を考える。銀行のATMの例では、ATMをサーバ、銀行内の待ちスペースを待合室、ATMを利用する顧客を客と見なす。これらの対応はモデル化する現象によって一意である必要はない。このため世の中の広範なシステムに対して同一の理論的枠組みで議論できる。待ち行列の応用先としては、コールセンター、電話交換機、電話網、インターネット、サーバやルーターなどのバッファ設計、高度道路交通システム、生産システム、空港や病院などの施設設計などが存在する。
ケンドールの記号は、待ち行列モデルに対する理解を統一する目的から、D. G. ケンドールによって1953年に導入された。A/B/C/D（A：客の到着過程、B：サービス時間分布、C：サーバ数、D：待合室を含んだシステムの容量、無限大の場合は省略）の形でモデルの性質を表現する。この記法は、その後新たなモデルの登場に応じて拡張を施されながら、現在でも様々な文献で広く用いられている。例えばG/D/1は一般の到着過程を持ち、一定分布に従うサービス時間を持つ単一サーバ待ち行列を表している。