Help us understand the problem. What is going on with this article?

待ち行列について

More than 3 years have passed since last update.

なにをするの?

待ち行列について簡単に説明し、Pythonのプログラムを通してシミュレーションし確認します。

待ち行列とは

確率的に挙動するシステムの混雑現象を
数理モデルを用いて解析するための理論。
オペレーションズ・リサーチの1分野。

待ち行列では、サービスを提供するものをサーバ、サービスを提供されるものを顧客(クライアント)とよぶことにします。
顧客は、確率的(または確定的)に発生し、FIFO(First In First Out:先入れ先出し)の行列に並びます。
そして、先頭から確率的(または確定的)な時間をかけてサービスを受け、サービス終了後に抜けていきます。
このようなしくみを系またはシステムとよびます。

image

待ち行列における最も簡単なモデルは、M/M/1 モデルになります。

M/M/1 モデルとは

待ち行列では、(A)どのように到着するか、(B)どのようにサービスされるか、(C)サーバがいくつあるかが重要になります。
この3つの情報を、A/B/Cのように書く形式をケンドールの記号とよびます。つまり、M/M/1とは、以下のシステムを指します。

  • 到着過程 = M :ポアソン到着(おおざっぱに言えばランダムに到着すること)
  • サービス = M :サービス時間が指数分布
  • サーバ数 = 1 :サーバが1台

Mはマルコフ(Markov)の略で、間隔が指数分布だと到着数はポアソン分布になり、挙動はマルコフ過程になります。

待ち行列におけるパラメータ

  • λ(ラムダ):平均到着率 = 単位時間1に到着する顧客数の平均(平均到着間隔の逆数)
  • μ(ミュー):平均サービス率 = 単位時間にサービスが終了する顧客数の平均(平均サービス時間の逆数)

これらのパラメータを使って以下のように計算したρは、サーバの平均稼働率になることが計算できます(後述)。

  • ρ(ロー): = $ \frac{\lambda}{\mu} $

待ち行列における統計値

  • 平均システム内人数($L$):システム内にいる人数の期待値
  • 平均待ち行列長($L_q$):待ち行列に並んでいる人数の期待値
  • 平均システム内時間($W$):システム内に滞在している時間の期待値
  • 平均待ち時間($W_q$):待ち行列に並んでいる時間の期待値

待ち行列における重要な式

リトルの公式

リトルの公式とは、安定なシステムにおいて長時間平均化した顧客数$L$は、長時間平均化した到着率$λ$と、長時間平均化したシステム内時間$W$の積に等しいという法則です。(システムを待ち行列にしても同じ)

$$L = \lambda W$$
$$L_q = \lambda W_q$$

この公式は、到着分布やサービス分布がどのようなものであっても成り立ちます。
また、この式は、直感的にもわかりやすいです。すなわち、

総合病院は、経験的に、1時間に3人やってくる。また、待合室には平均6人待っていることが分かっている。
平均待ち時間は、2時間と考えられる。

これは、$W_q = L_q / \lambda = 6 / 3 = 2$ を計算したことになります。この計算は、平均について成り立ちます。
「自分が到着したとき6人並んでいた」場合の待ち時間の期待値は、(サービスがMの場合)6×平均サービス時間になります。

統計値の理論値

M/M/1では、比較的簡単に統計値の理論値を求めることができます。理論値を丸暗記しなくても、次の2つを覚えれば計算できます。

  1. システム内人数の確率は、1人増えるとρ倍になる(マルコフ過程より導かれる)
  2. リトルの公式

まず、システム内に$i$人いる確率$P_i$は(1)から$\alpha \rho^i$となります。確率を全て足すと1なので、下記のように計算できます。

$$ \alpha(1 + \rho + \rho^2 + \rho^3 + \cdots) = \frac{\alpha}{1 - \rho} = 1 から \alpha = 1-\rho$$
$$ システム内にi人いる確率P_i = (1-\rho) \rho^i $$

これを使うと、サーバの平均稼働率=$\sum_{i=1}{P_i} = 1 - P_0 = 1 - (1-\rho) = \rho$ということもわかります。

また、リトルの公式も使って以下のように計算できます。

平均システム内人数($L$) = $\sum_{i=0}{i P_i} = (1-\rho)(\rho+2 \rho^2 + 3 \rho^3 + \cdots) = \frac{\rho}{1-\rho}$
平均待ち行列長($L_q$) = $平均システム内人数 - サーバの平均稼働率 = L - \rho = \frac{\rho^2}{1-\rho}$
平均システム内時間($W$) = $L / \lambda = \frac{1}{\mu - \lambda}$
平均待ち時間($W_q$) = $L_q / \lambda = \frac{\rho}{\mu - \lambda}$

Pythonで確認

待ち行列シミュレーションは、Pythonの$\mbox{simpy}$を使うと便利です。インストールは、"pip install simpy"でできます。
到着率λ=1/5、サービス率μ=1/3とします。

python3
import simpy, random, numpy as np
random.seed(1)
env = simpy.Environment() # シミュレーション環境
queue, intime = [], [] # 待ち行列(到着時間のリスト) と システム内時間のリスト

# 到着イベント
def arrive():
    while True:
        yield env.timeout(random.expovariate(1.0 / 5)) # 平均到着率 1/5
        env.process(into_queue())

# 待ち行列に並ぶ
def into_queue():
    global queue
    queue.append(env.now)
    if len(queue) > 1:
        return
    while len(queue) > 0:
        yield env.timeout(random.expovariate(1.0 / 3)) # 平均サービス率 1/3
        tm, queue = queue[0], queue[1:]
        intime.append(env.now - tm)

# 実行
env.process(arrive())
env.run(1000000)
print('total = %d clients, W = %.2f' % (len(intime), np.average(intime)))
>>>
total = 199962 clients, W = 7.53

理論値は、$W = \frac{1}{\mu - \lambda} = \frac{1}{\frac{1}{3} - \frac{1}{5}} = 7.5$で、おおよそ合っているのが確認できます。

以上


  1. 単位時間とは、基準となる時間で1時間でも1分でも、モデル作成者が好きなものを決めることができます。 

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした