待ち行列理論

待ち行列理論

 待ち行列理論は、キュー(queue)と呼ばれるシステムに対して、到着する要求(顧客、ジョブ、トランザクションなど)が待ち行列に溜まることで、要求が処理されるまでの待ち時間やシステムの負荷などを予測するための理論です。

待ち行列理論では、以下のような仮定が置かれます。

  • 到着する要求はランダムに分布しており、ポアソン分布に従う。
  • サービス時間(要求を処理する時間)は指数分布に従う。
  • 待ち行列には無限のキャパシティがある。
  • サービスは先入先出(FIFO)の方式で行われる。

このような仮定に基づいて、待ち行列理論は、システムの負荷や待ち時間、処理能力などを評価するための数学モデルを構築します。

具体的には、以下のような指標が用いられます。

  • 平均待ち時間(average waiting time)
    要求が待ち行列に入ってから処理されるまでの平均時間。
  • 平均滞在時間(average sojourn time)
    要求がシステム内に滞在する総時間の平均。
  • 平均待ち人数(average number in queue)
    待ち行列に溜まっている要求の平均数。
  • サービスレベル(service level)
    一定時間内に要求が処理される割合。

これらの指標を計算することで、システムの効率性や改善点を把握することができます。

 待ち行列理論は、様々な分野で応用されています。例えば、コールセンターや銀行の窓口、製造工程の生産ライン、インターネットのネットワークなど、さまざまなシステムの設計や改善に活用されています。

 待ち行列理論において、単純な待ち行列モデルは、複数の客が一つのサービス施設を共有する場合を表します。これには、以下の仮定が含まれます。

  1. 客はランダムに到着し、一定の平均到着率λで到着する。
  2. サービス施設には一定数のサーバがあり、それぞれ平均サービス率μで処理を行う。
  3. 客は一定の平均サービス時間1/μの指数分布に従ってサービスを受ける。
  4. 待ち行列にある客は、先に到着した客から順番にサービスを受ける(FIFO方式)。

このモデルを用いることで、以下のような性能評価が行えます。

  1. 平均客数
    システム内に平均でいくつの客がいるか。
  2. 平均待ち時間
    客が待たされる平均時間はどの程度か。
  3. サービス利用率
    サービス施設がどの程度使用されているか。
  4. 進行中のサービスがある客の確率
    待ち行列に客がいるとき、サービスを受けている客がいる確率はどの程度か。

 また、このモデルを拡張することで、複数のサービス施設、優先度付き客、非同期サービス時間などを考慮したより現実的なシステムをモデル化することができます。