待ち行列理論について

 待ち行列という言葉は誰でも知っている言葉だと思います。スーパのレジやテーマパークの順番待ちなどが考えられると思います。この日常的な待ち行列に、理論があるのを知っているでしょうか？この理論は待ち行列理論といい、1900年代から始まった理論で、電話交換機の評価を行うためのものでした。僕が考える待ち行列理論の面白さは、次のようなものがあります。

・人間の行動やシステムを、いくつかの仮定の下で、数式で表現できる

・数式から解析解を求めることができる

・待ち行列を評価する特性量(平均系内人数など)を求めることができる

・特性量を用いて、システムを最適化することもできる

・数学的にきれい

・確率論、確率過程をふんだんに使う

(1) 待ち行列理論の構成

待ち行列理論にはケンドール記号というものがり、「M/M/1」のような形で表現されます。最初のMですが、到着過程を表し、MはMarkovian(マルコビアン)の略です。これがMのときは、到着過程がポアソン過程での到着を示しています。ポアソン過程は、単位時間あたりの到着人数がポアソン分布に従い、到着間隔は指数分布に従う過程のことです。最初はポアソン分布とポアソン過程の違いがわからずに、同じものと考えてしまっていました。次のMはサービスを表しています。到着がMのときはポアソン過程でしたが、サービスがMのときはサービスが指数分布に従うことを表します。最後の1は窓口数を表します。さらに、「M/M/1/K」のように、窓口数の後にさらにバッファーの大きさ指定する場合があります。このKの大きさまで待ち行列を作れて、K人既に並んでいる場合、新規で到着した客は待ち行列に並ぶことができず、退去することになります。これを故損と言います。またMだけでなくGなどの他の記号も用います。Gの場合は一般分布に(名前が定まっていないような確率分布)に従うことを意味していて、表現を広げています。このように待ち行列理論は、到着過程、サービス分布、窓口数で基本的な構成がされています。

(2) 待ち行列理論を解く

待ち行列理論の面白いところは、このような人間の行動をシステムとして評価できるところです。M/M/1は解析的に解くモデルの代表例ですが、M/M/のモデルは複数窓口の場合も、バッファーが有限の場合も解析的に解くことができます。M/G/1のサービスが一般分布になったモデルも解析解が得られます。これをポラチックヒンチンの公式と言います。ところが、M/G/s (sは2以上)のような複数窓口になった場合、解析的に解くことが困難になります。窓口数が1なら解析的に解けるのですが、複数になると、途端に難しくなるところが待ち行列理論の特徴です。

待ち行列理論にはネットワーク型もあります。M/M/1がネットワーク型に繋がったものがジャクソンネットワークといい、積形式解という形で解析解が求まります。このジャクソンネットワークは外部からの到着、外部への退去もあり、開放型と言います。このジャクソンネットワークを開放型、閉鎖型両方のネットワークに対応し、さらに複数窓口、客クラス、4つのサービスタイプに拡張したBCMP待ち行列ネットワークというものも解析的に特性量を求めることができます。僕はこのBCMP待ち行列ネットワークが適用範囲が広く、この応用例をよく扱っています。

待ち行列理論の背景を簡単に述べましたが、日常的にみられる待ち行列を、数式で表現でき、さらにそれを解いて特性量からシステム的に評価できるような待ち行列理論は、いろんな奥深さがあると考えています。