待ち行列理論

2024年5月14日 14:09

待ち行列理論とは？

待ち行列理論（Queueing Theory）は、待ち行列（キュー）やサービスプロセスを数学的に分析する理論です。主に、人々、物、または情報が何らかのサービスを受けるために待つ場面に適用されます。この理論は、システムの性能を評価し改善するために用いられ、コールセンター、ネットワークトラフィック、製造ラインなど多岐にわたる分野で応用されています。

シミュレーションとして以下の問題を考えてみたいと思います。

ある銀行に顧客が平均15分間隔でランダムに訪れます。窓口は1つのみで、一人の顧客の取引処理時間は平均12分であるとします。このとき、顧客が窓口での取引を開始するまでの平均待ち時間は？

ここで待ち行列をモデル化する上で、2つの主要なパラメーターがあります。

到着率 (λ): 単位時間あたりにシステムに到着する顧客の数
サービス率 (μ): 単位時間あたりにサービスを完了できる平均顧客数

今回のシミュレーション設定に対するパラメーターは下記の通りになります。

lambda_ = 1/15
mu = 1/12

待ち行列の一般的なモデルとしてM/M/1というのがあります。
「M」はマルコフ性（指数分布）を意味します。このモデルでは、到着とサービスが指数分布に従い、1台のサーバー（窓口）が存在します。

到着とサービス時間について、指数分布に従うランダムな値を生成します。

import numpy as np

num_customers = 100000 

interarrival_times = np.random.exponential(1/lambda_, num_customers)
service_times = np.random.exponential(1/mu, num_customers)

それでは平均待ち時間を計算してみます。

arrival_times = np.cumsum(interarrival_times)
start_service_times = np.zeros(num_customers)
finish_service_times = np.zeros(num_customers)

start_service_times[0] = arrival_times[0]
finish_service_times[0] = start_service_times[0] + service_times[0]

for i in range(1, num_customers):
    start_service_times[i] = max(arrival_times[i], finish_service_times[i-1])
    finish_service_times[i] = start_service_times[i] + service_times[i]

waiting_times = start_service_times - arrival_times

average_waiting_time = np.mean(waiting_times)

この結果得られた平均待ち時間は約48分でした。