改訂新版 世界大百科事典 「待ち行列」の意味・わかりやすい解説
待ち行列 (まちぎょうれつ)
queue
たとえばスーパーマーケットのレジの前で順番を待っている買物客のように，順番待ちの行列ができることがある。この種の渋滞は通信をはじめさまざまな分野に多数存在し，数学的に研究する必要が生じた。この行列は数学用語のマトリックスとの混同を避けるため，待ち行列と呼ばれている。待ち行列に代表される混雑に関する理論を待ち行列論queuing theoryと呼び，歴史的には，電話交換システムの回線数決定の理論として1910年ころに始められた。最初の著しい成果は，17年にアーランA.K.Erlangによって得られた呼損率の公式であって，全世界の電話事業の発展に大きく貢献した。その後，30年代から40年代にかけての先駆的な研究を経て，50年以降になると飛躍的に研究が進み，オペレーションズリサーチの中心的手法とみなされるにいたった。
スーパーマーケットの買物客は〈代金を支払う〉ために勘定台の前で行列を作るが，これと同じ状況はいたるところに見いだされる。たとえば，航空機は〈着陸〉や〈離陸〉のために滑走路使用の順番を待つし，工場で生産される製品は，各工程で〈加工〉される際暫時ためておかれる。もしこれらの待ち行列が長くなりすぎると，重大な事故や生産費の高騰につながりかねないので，待ち行列がどの程度になるかを知ることは大切である。このため待ち行列理論が広く応用されるようになってきた。特に近年は，衛星通信やLAN（ラン）（local area networkの略）などの各種通信網あるいは計算機システム等の発達に伴い，それらの性能評価が重要な問題となっているが，待ち行列はこの分野で主力的な役割を果たしている。
上例の代金支払いや離着陸，加工工程などを一般に〈サービス〉と呼び，それを提供する機構を〈窓口〉もしくは〈扱い者〉と称する。窓口は1個の場合も複数個の場合もある。またサービスを受けるために窓口に到着するものを〈客〉と呼ぶ。航空機の例では，航空機が客，滑走路が窓口，離着陸の許可を管制官に求めることが到着，滑走路を占有している間がサービス時間に当たる。客が到着したとき窓口が空いていれば彼はただちにサービスを受けるが，先客のサービス中であれば，待ち行列に並んで待たなければならない。待ち行列発生の原因は，たまたま到着間隔が短くなったり，サービス時間が長くなったりする確率的な変動に求められるので，待ち行列の解析は確率論的方法によることになる。到着間隔やサービス時間が指数分布に従うときはマルコフ連鎖の理論を用いて比較的容易に取り扱うことができ実用上も大切な場合になるので，特に単純待ち行列とよび，基本的なタイプと考える。ここでは，到着数の制限はなく，到着やサービス時間の確率分布はそのパラメーターを含めて時間が経っても変わらず，しかも先着順にサービスされると仮定している。また，窓口が複数個の場合には，待ち行列はそれらに共通して1本だけでき，どの窓口のサービスが終わったときでも，その次の客は待ち行列の先頭の客であると考える。
しかし，現実に存在する待ち行列はもっと多様であり，そのためさまざまなタイプの待ち行列が取り扱われる。たとえば，客の総数に限りのある〈有限待ち行列〉は計算機システムなどの重要なモデルであるし，待ち行列の長さに制限のある場合は通信システムにその例が多い。特に待ち行列を作ることを許さず，窓口がすべてふさがっているときに到着した客はそのまま立ち去るとみなす場合は，普通の電話交換システムに相当する。われわれが電話をかけたとき，もし回線がふさがっていれば〈話中音〉が聞こえて接続不能を知らされる。これが並ばずに立ち去る客に相当している。いつも話中音が頻繁に聞こえるようでは苦情が殺到するであろう。逆に，相手が話中のとき以外は絶対に話中音が出ないような状況は，局間の回線数がきわめて多くほとんどの回線が遊んでいる場合に限られる。これは過剰投資となり電話料金の高騰を招く。途中回線の不足のため話中に出会う確率を〈呼損率〉と呼ぶが，それがたとえば1/100程度以下になる範囲で回線数を少なくするのが合理的である。アーランの公式はこの呼損率を計算するものであった。アーランの公式は，サービス時間分布を指数分布に限らなくても成立するが，それを示すのは簡単ではない。一般に，到着間隔やサービス時間の分布が指数分布以外のときは解析も結果も複雑になることが多いので，最近は精度のよい近似式を求める努力が多くされている。
さらに，基本的なタイプ以外で代表的な待ち行列には次のようなタイプがある。一つはサービスの順番に先着順以外のものを考えるもので，優先権を特定の客に与えたり，サービス時間の短い客のサービスを優先したり，あるいは待ち行列の最後尾からサービスを行ったりする。また，ある窓口のサービスを終えた客が他の窓口の待ち行列に並ぶという多段階の待ち行列や，それがさらに複雑に結ばれた〈待ち行列網〉も近年盛んに研究されている重要なタイプである。
執筆者：森村 英典
出典 株式会社平凡社「改訂新版 世界大百科事典」改訂新版 世界大百科事典について 情報