待ち行列について

# <i class='fa fa-magic' /> なにをするの？
待ち行列について簡単に説明し、Pythonのプログラムを通してシミュレーションし確認します。

# <i class='fa fa-magic' /> 待ち行列とは
    確率的に挙動するシステムの混雑現象を
    数理モデルを用いて解析するための理論。
    オペレーションズ・リサーチの1分野。

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

![image](https://qiita-image-store.s3.amazonaws.com/0/13955/f47ef9d8-4705-7174-3885-19b972174188.png)

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

# <i class='fa fa-magic' /> M/M/1 モデルとは
待ち行列では、(A)どのように到着するか、(B)どのようにサービスされるか、(C)サーバがいくつあるかが重要になります。
この3つの情報を、A/B/Cのように書く形式を[ケンドールの記号](https://ja.wikipedia.org/wiki/%E3%82%B1%E3%83%B3%E3%83%89%E3%83%BC%E3%83%AB%E3%81%AE%E8%A8%98%E5%8F%B7)とよびます。つまり、M/M/1とは、以下のシステムを指します。

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

Mは[マルコフ](https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%AB%E3%82%B3%E3%83%95%E9%81%8E%E7%A8%8B)(Markov)の略で、間隔が[指数分布](https://ja.wikipedia.org/wiki/%E6%8C%87%E6%95%B0%E5%88%86%E5%B8%83)だと到着数は[ポアソン分布](https://ja.wikipedia.org/wiki/%E3%83%9D%E3%82%A2%E3%82%BD%E3%83%B3%E5%88%86%E5%B8%83)になり、挙動はマルコフ過程になります。

## 待ち行列におけるパラメータ
- λ(ラムダ)：**平均到着率** = 単位時間[^1]に到着する顧客数の平均(平均到着間隔の逆数)
- μ(ミュー)：**平均サービス率** = 単位時間にサービスが終了する顧客数の平均(平均サービス時間の逆数)

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

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

- ρ(ロー)： = $ \frac{\lambda}{\mu} $

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

# <i class='fa fa-magic' /> 待ち行列における重要な式
## リトルの公式
[リトルの公式](https://ja.wikipedia.org/wiki/%E3%83%AA%E3%83%88%E3%83%AB%E3%81%AE%E6%B3%95%E5%89%87)とは、安定なシステムにおいて長時間平均化した顧客数$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人増えるとρ倍になる(マルコフ過程より導かれる)
- リトルの公式

まず、システム内に$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}$

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

```py3: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$で、おおよそ合っているのが確認できます。

以上