《待ち行列》

【まちぎょうれつ (queues) 】

混雑現象　 われわれの身の回りには, 混雑現象が主因となっている問題がたくさん存在する. たとえば, 通勤電車, 繁華街, 行楽地, イベント会場などにおける混雑, 高速道路や幹線道路の渋滞, スーパーのレジや銀行の ATM における行列, 病院での待ち, 携帯電話の不接続, などなど. また, 人間が待たされるわけではないが, 商品の在庫, 仕事の滞貨, 注文残, 考えようによっては洪水などというのもある. コンピュータの中では複数のジョブが CPU や I/O (Disk など) で待ち行列を作って処理されているし, 情報通信ネットワークでも, 情報があちこちのノードで少しずつ待たされながら目的地に運ばれる.

　このような混雑現象は, 需要つまりサービス要求量が一時的にサービス能力を超えることから生じており, 次のようにいろいろな方法で処理されている.

a.　サービス処理能力を需要にあわせて変動させる (電力会社は, 火力発電や水力発電で発電量を細かく調整している).

b.　サービス品質を落として処理能力を一時的に上げる (通勤電車では客が多くなると尻押しをしてでも詰め込む).

c.　バッファで一時的な超過分を吸収する (行列で待たせる).

d.　サービスを拒否する (携帯電話では当然のように行われる).

混雑現象のためのモデル　 a. の追随型とb. の品質低下型は, 混雑に対する対応がリアルタイムであるため, 需要の変動パターンがわかれば, 混雑の程度の解析は比較的容易である. これに対してc. のバッファ型とd. の拒絶型, とくにc.　は, システムの挙動がサービスの仕方とも関連して複雑であり, モデルによる検討が必要になることが多い. そのモデルも, 需要の変動パターンによって使い分けが必要である.

　i)　サービス要求量の増大が一定時間続くラッシュアワー型の場合

　ii)　偶然変動による比較的短時間の増大が繰り返し生じる確率型の場合

である. むろんそれらが複合していることもある.

流体近似モデル　i) のラッシュアワー型の解析は, 流体近似 (fluid approximation) を使ってなされることが多い. これは水道の水のように, サービス要求がある率でバッファに入ってきて, ある率で流れ出ていく, と考えるものである (図1). このとき, 時刻 $t\,$ における入力率を $\lambda _{t}\,$, 出力率 (バッファに貯まっているときに出力する率) を $\mu _{t}\,$ とすると, 時刻 $t\,$ におけるバッファの内容量 $Q_{t}\,$ は, 微分方程式

${\frac {{\mbox{d}}Q_{t}}{{\mbox{d}}t}}={\Biggl \{}{\Biggr .}\,\,$

$\lambda _{t}-\mu _{t}\,\,$ 　　 $\lambda _{t}>\mu _{t}\,\,$または$Q_{t}>0\,\,$　のとき $0\,\,$ その他

で記述される. ただしこの微分方程式を使わなくても, 時間区間 $(0,t]\,$ における累積入力量$\textstyle A_{t}=\int _{0}^{\infty }\lambda _{t}\,dt\,$ のグラフから累積出力量 $D_{t}\,$ のグラフを描くことができ, それらの差 $Q_{t}=A_{t}-D_{t}\,$ から時刻 $t\,$ におけるバッファーの内容量を求めることができる [2].

図１：流体近似 : 水道のイメージ スタイル検討

待ち行列モデル　サービス要求量の変動が ii) の確率型の場合は, 待ち行列モデル (queueing model) や 在庫モデル (inventory model), ダムモデル (dam model) などを使って解析される [1, 2]. ここでは待ち行列モデルを主に説明しよう.

図２：待ち行列のイメージ図 スタイル検討

　待ち行列モデルは, 図2のように, あるサービスステーションに客(customer)が到着し, そこである種のサービス (service) をうけ, 系外に立ち去る, というサービスシステム (servicing system) のモデルである. サービスステーションは, 通常, サービスが行われる窓口 (channel) と, 到着した客がサービスを受けるために待つ待ち行列 (queue) とから成る. この待ち行列がバッファ (buffer) の役割を果たす. 待つことのできる客の数に制限がある場合, 待合室という概念を導入することもある. このとき待合室の容量が, 待つことのできる客の数の上限となる.

　客, 窓口, 待合室などは, モデルによってさまざまなものに対応する. ある種の生産システムでは, 客は製品や部品であり, 窓口は加工機, 検査機, 組立台など, そして待合室は仮置き台などである. コンピュータの性能評価では, 客はジョブであり, 窓口は CPU や DISK, 待合室は各所のメモリである. また情報通信ネットワークの性能評価では, セルやパケットといった情報の塊が客であり, 各種のスイッチ類やチャネルが窓口, バッファメモリが待合室として扱われる.

性能評価指標, 混雑指標　図2のような標準的なモデルでは, 利用率 (traffic intensity), $\rho \,$ というのが重要なシステムパラメータである. これは

スタイル検討

という形で定義される. たとえば客が平均 $\lambda ^{-1}\,$ の間隔で到着し, $c\,$ 個の窓口で平均 $\mu ^{-1}\,$ のサービスが行われるようなシステムでは, $\rho =\lambda /c\mu \,$ である. 多くの場合, $\rho <1\,$ であれば, システムは平衡状態(stationary) とよばれる安定な状態へ向かい, 確率論的な解析が可能となる.

　一般に, $\rho \,$ が 0に近いときは混雑はほとんどなく, 1に近づくにつれて混雑がひどくなる. このような混雑を評価する指標としては, 待ち時間 (waiting time) (客が待ち行列で待たされる時間), 滞在時間 (sojourn time) (客が到着してからサービスが終了するまでの時間), 待ち行列長 (queue length) (待ち行列で待っている客の数), 系内人数 (number of customers in the system) (待ち行列と窓口にいる客の数) などの平均や分散, または分布などが用いられる.

　待合室の容量 (capacity of waiting room) が有限で, システムに入れる客の数に制限がある場合, 呼損率 (loss probability) も重要な指標である. これは到着した客のうち待合室が一杯でサービスを受けられずに退去する客の割合である. ここで "呼 (こ, よび)" という耳慣れない言葉が使われているが, これは電話をかけるときの接続要求のことで, 待ち行列理論がデンマークの電話技術者アーランアグナー・K}{アーラン} (A. K. Erlang) によって20世紀の初頭に始められ以来, 電話の交換機の適正数を評価するのに有限待合室のモデル (finite-buffer model) がずっと使われてきたという経緯からきている [4].

　近年, 待ち行列理論の分野では, 情報通信技術の発達などと歩調を合わせて, より複雑でより一般的な状況の下でのモデル解析が進められている. これらについては他の項目ならびに文献 [2, 4] を参照されたい. また関連書籍は [3] にサーベイが載っている. 応用分野も多岐にわたっている. 次の各項目を参照してほしい. 待ち行列の通信への応用, 待ち行列のコンピュータへの応用, 待ち行列の生産システムへの応用.

---

参考文献

[1] 森村英典, 大前義次, 『応用待ち行列理論』, 日科技連出版社, 1975.

[2] 高橋幸雄, 「入門講座, やさしい待ち行列(1)～(4)」, 『オペレーションズ・リサーチ』, 40 (1995), 649-654, 716-721, 41 (1996), 35-40, 100-105.

[3] 高橋敬隆, 高橋幸雄, 牧本直樹, 「入門講座, やさしい待ち行列 (補遺) ― 待ち行列の本」, 『オペレーションズ・リサーチ』, 41 (1996), 106-107.

[4] 高橋幸雄, 「講座, 待ち行列研究の新しい潮流 (1)― 待ち行列研究の変遷」, 『オペレーションズ・リサーチ』, 43 (1998), 495-499.