待ち行列理論

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

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

概要

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

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

関連項目

• 確率論
• 確率分布
• ランダム初期検知
• リトルの法則
• 渋滞
• フォーク並び
• ケンドールの記号
  • M/M/1 待ち行列
• アグナー・アーラン

参考文献

• 高橋幸雄, 森村英典：「混雑と待ち」、朝倉書店、ISBN 978-4254275179（2001年7月1日）。
• 牧本直樹：「待ち行列アルゴリズム―行列解析アプローチ」、朝倉書店、ISBN 978-4254275131（2001年3月）。
• 紀一誠：「待ち行列ネットワーク」 、朝倉書店、ISBN 978-4254275230（2002年11月）。
• 吉岡良雄：「待ち行列と確率分布―情報システム解析への応用」、森北出版、ISBN 978-4627828216（2004年2月）。
• 大石進一：「待ち行列理論」、コロナ社、ISBN 978-4339060737（2003年4月）。
• 高橋敬隆, 吉野秀明, 山本尚生, 戸田彰, 電気情報通信学会（編）：「わかりやすい待ち行列システム―理論と実践」、電子情報通信学会、ISBN 978-4885521928（2003年4月）。
• 北岡正敏：「例題でわかる待ち行列理論入門」、日本理工出版会、ISBN 978-4890195176（2010年6月）。
• 鈴木武次：「待ち行列」［復刊］、裳華房; 第2版、ISBN 978-4785311087（2011年7月21日）。
• 宮沢政清：「待ち行列の数理とその応用」、牧野書店、ISBN 978-4434076978（2006年4月）。
• 牧野都治：「待ち行列の応用」 POD版、森北出版、ISBN 978-4627001299（2011年3月31日）。

外部リンク

• 日本大百科全書(ニッポニカ)『待ち行列理論』 - コトバンク
• 待ち行列モデル