待ち行列モデル
【英】：queueing model
目次 |
概要
混雑現象を解析するための代表的なモデル群の1つ．単一の待ち行列モデルは，客の到着，窓口における客のサービス，サービスを待つ客が成す待ち行列，などから構成され，平均待ち時間などによって混雑の程度が評価される．近年，待ち行列がネットワーク状につながった"待ち行列ネットワーク"が積極的に解析され，コンピュータシステムや通信システムなどの性能評価に利用されている．
応用分野については，次の各項目を参照のこと：待ち行列の通信への応用，待ち行列のコンピュータへの応用，待ち行列の生産システムへの応用．
詳説
混雑現象
われわれの身の回りには，混雑現象が主因となっている問題がたくさん存在する[5]．たとえば，通勤電車，繁華街，行楽地，イベント会場などにおける混雑，高速道路や幹線道路の渋滞， スーパーのレジや銀行の ATM における行列，病院での待ち，携帯電話の不接続，などなど．また，人間が待たされるわけではないが，商品の在庫，仕事の滞貨，注文残，考えようによっては洪水などというのもある．コンピュータの中では複数のジョブが CPU や I/O (Disk など) で待ち行列を作って処理されているし，情報通信ネットワークでも，情報があちこちのノードで少しずつ待たされながら目的地に運ばれる．
このような混雑現象は，需要つまりサービス要求量が一時的にサービス能力を超えることから生じており，次のようにいろいろな方法で処理されている．
a. サービス処理能力を需要にあわせて変動させる (電力会社は，火力発電や水力発電で発電量を細かく調整している)．
b. サービス品質を落として処理能力を一時的に上げる (通勤電車では客が多くなると尻押しをしてでも詰め込む)．
c. バッファで一時的な超過分を吸収する (行列で待たせる)．
d. サービスを拒否する (携帯電話では当然のように行われる)．
混雑現象のためのモデル
a．の追随型とb．の品質低下型は，混雑に対する対応がリアルタイムであるため，需要の変動パターンがわかれば，混雑の程度の解析は比較的容易である．これに対してc．のバッファ型とd．の拒絶型，とくにc. は，システムの挙動がサービスの仕方とも関連して複雑であり，モデルによる検討が必要になることが多い．そのモデルも，需要の変動パターンによって使い分けが必要である．
i) サービス要求量の増大が一定時間続くラッシュアワー型の場合
ii) 偶然変動による比較的短時間の増大が繰り返し生じる確率型の場合
である．むろんそれらが複合していることもある．
流体近似モデル
i) のラッシュアワー型の解析は，流体近似 (fluid approximation) を使ってなされることが多い．これは水道の水のように，サービス要求がある率でバッファに入ってきて，ある率で流れ出ていく，と考えるものである (図1)．このとき，時刻 
における入力率を 
，出力率 (バッファに貯まっているときに出力する率) を 
とすると，時刻 におけるバッファの内容量 
は，微分方程式
|
または
のとき
で記述される．ただしこの微分方程式を使わなくても，時間区間 ![(0, t]\,](http://cdn.weblio.jp/e7/img/dict/orjtn/179ee8fc1f9677f3cd15beefafbc6472.png)
における累積入力量
のグラフから累積出力量 
のグラフを描くことができ，それらの差 
から時刻 におけるバッファーの内容量を求めることができる [2,5]．
 |
| 図１：流体近似 : 水道のイメージ |
待ち行列モデル
サービス要求量の変動が ii) の確率型の場合は，待ち行列モデル (queueing model) や 在庫モデル (inventory model)，ダムモデル (dam model) などを使って解析される [1，2]．ここでは待ち行列モデルを主に説明しよう．
 |
| 図２：待ち行列のイメージ図 |
待ち行列モデルは，図2のように，あるサービスステーションに客(customer)が到着し， そこである種のサービス (service) をうけ，系外に立ち去る，というサービスシステム (servicing system) のモデルである．サービスステーションは，通常，サービスが行われる窓口 (channel) と，到着した客がサービスを受けるために待つ待ち行列 (queue) とから成る．この待ち行列がバッファ (buffer) の役割を果たす．待つことのできる客の数に制限がある場合，待合室という概念を導入することもある．このとき待合室の容量が，待つことのできる客の数の上限となる．
客，窓口，待合室などは，モデルによってさまざまなものに対応する．ある種の生産システムでは，客は製品や部品であり，窓口は加工機，検査機，組立台など，そして待合室は仮置き台などである．コンピュータの性能評価では，客はジョブであり，窓口は CPU や DISK，待合室は各所のメモリである．また情報通信ネットワークの性能評価では，セルやパケットといった情報の塊が客であり，各種のスイッチ類やチャネルが窓口，バッファメモリが待合室として扱われる．
性能評価指標，混雑指標
図2のような標準的なモデルでは，利用率 (traffic intensity)，
というのが重要なシステムパラメータである．これは
という形で定義される．たとえば客が平均 
の間隔で到着し，
個の窓口で平均 
のサービスが行われるようなシステムでは，
である．多くの場合，
であれば，システムは平衡状態(stationary) とよばれる安定な状態へ向かい，確率論的な解析が可能となる．
一般に， が 0に近いときは混雑はほとんどなく，1に近づくにつれて混雑がひどくなる．このような混雑を評価する指標としては，待ち時間 (waiting time) (客が待ち行列で待たされる時間)，滞在時間 (sojourn time) (客が到着してからサービスが終了するまでの時間)，待ち行列長 (queue length) (待ち行列で待っている客の数)，系内人数 (number of customers in the system) (待ち行列と窓口にいる客の数) などの平均や分散，または分布などが用いられる．
待合室の容量 (capacity of waiting room) が有限で，システムに入れる客の数に制限がある場合，呼損率 (loss probability) も重要な指標である．これは到着した客のうち待合室が一杯でサービスを受けられずに退去する客の割合である．ここで "呼 (こ，よび)" という耳慣れない言葉が使われているが，これは電話をかけるときの接続要求のことで，待ち行列理論がデンマークの電話技術者アーラン(A. K. Erlang) によって20世紀の初頭に始められ以来，電話の交換機の適正数を評価するのに有限待合室のモデル (finite-buffer model) がずっと使われてきたという経緯からきている [4]．
読書案内
近年，待ち行列理論の分野では，情報通信技術の発達などと歩調を合わせて，より複雑でより一般的な状況の下でのモデル解析が進められている．待ち行列理論関係の参考書は，日本オペレーションズリサーチ学会待ち行列研究部会のホームページに「待ち行列関係書籍（和書）」としてまとめられている．[7] 中でも [5] は混雑現象全般にわたって解説されているので，初学者には参考になるだろう．[6] は初学者から専門の研究者まで幅広い読者層を想定して，待ち行列理論の基本的な項目が解説されている．英語の書籍の紹介は [3,4] にある．
参考文献
[1] 森村英典，大前義次，『応用待ち行列理論』，日科技連出版社，1975．ISBN 481715313X
[2] 高橋幸雄，「入門講座，やさしい待ち行列(1)～(4)」，『オペレーションズ・リサーチ』，40 (1995)，649-654，716-721，41 (1996)，35-40，100-105．http://www.orsj.or.jp/~archive/pdf/bul/Vol.41_01_035.pdf
[3] 高橋敬隆，高橋幸雄，牧本直樹，「入門講座，やさしい待ち行列 (補遺) ― 待ち行列の本」，『オペレーションズ・リサーチ』，41 (1996)，106-107．http://www.orsj.or.jp/~archive/pdf/bul/Vol.41_02_106.pdf
[4] 高橋幸雄，「講座，待ち行列研究の新しい潮流 (1)― 待ち行列研究の変遷」，『オペレーションズ・リサーチ』，43 (1998)，495-499.
[5] 高橋幸雄，森村英典，『混雑と待ち』，朝倉書店，2001．ISBN: 425427517X
[6] 宮沢 政清，『待ち行列の数理とその応用』，牧野書店，2006．ISBN-13: 978-4434076978
[7] 日本オペレーションズリサーチ学会待ち行列研究部会 http://www.orsj.or.jp/queue/
| 待ち行列： | 待ち行列モデル M/M/1 待ち行列モデル M/M/c/c 待ち行列モデル M/M/c 待ち行列モデル 待ち行列長 待合室の容量 後着順サービス |
| 確率と確率過程： | 強マルコフ性 待ち行列モデル M/M/1 待ち行列モデル M/M/c 待ち行列モデル 拡散方程式 拡散過程 指数分布 |
待ち行列理論
 |
待ち行列理論（まちぎょうれつりろん 英語: Queueing Theory）とは、顧客がサービスを受けるために行列に並ぶような確率的に挙動するシステムの混雑現象を数理モデルを用いて解析することを目的とした理論である。応用数学のオペレーションズ・リサーチにおける分野の一つに数えられる。
電話交換機や情報ネットワーク[要曖昧さ回避]、生産システム、空港や病院などの設計や性能評価に応用される。性能評価指標としては、待ち行列長・待ち時間・スループットなどが用いられる。応用の場では、システムの性能がある設計目標を満たすために必要な設計パラメータを決定する際に、その逆問題を提供できる。
概要
待ち行列とは、資源に対する利用要求を抽象化した数理モデルである。このようなシステムの身近な例として、銀行のATMに並ぶ顧客の列が挙げられる。待ち行列モデルでは、サーバ (server) と待合室 (waiting room) からなるシステムと、そこに到着しある時間滞在する客 (customer) を考える。銀行のATMの例では、ATMをサーバ、銀行内の待ちスペースを待合室、ATMを利用する顧客を客と見なす。これらの対応はモデル化する現象によって一意である必要はない。このため世の中の広範なシステムに対して同一の理論的枠組みで議論できる。待ち行列の応用先としては、コールセンター、電話交換機、電話網、インターネット、サーバやルーターなどのバッファ設計、高度道路交通システム、生産システム、空港や病院などの施設設計などが存在する。
ケンドールの記号は、待ち行列モデルに対する理解を統一する目的から、D. G. ケンドールによって1953年に導入された。A/B/C/D（A：客の到着過程、B：サービス時間分布、C：サーバ数、D：待合室を含んだシステムの容量、無限大の場合は省略）の形でモデルの性質を表現する。この記法は、その後新たなモデルの登場に応じて拡張を施されながら、現在でも様々な文献で広く用いられている。例えばG/D/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日）。
 | この節の加筆が望まれています。 |
外部リンク
- 待ち行列モデルのページへのリンク
