待ち行列(M/M/1)

/ tau / コメントする

前提

時刻t～t + Δtの間に以下のいずれかの状態遷移が発生するとする。希少性の仮定から、2つ以上の事象が同時に起こることはなく、いずれか1つが発生するとする。

  • 確率λΔtで1つのトランザクションが到着する
  • 確率μΔtで1つのサービスが完了する
  • 確率(1 – λΔt – μΔt)でトランザクションの到着もなくサービスも完了しない
    • 本来は(1 – λΔt)(1  – μΔt)で表されるところ、これを展開してΔt2の項を無視してこの形になる
    • あるいは指数分布の密度関数をMaclaurin展開して2時以上の項をo(Δt2)として消していってもよい

なお、M/M/1待ち行列のイベント制御による再現をR言語で試している。

状態方程式

システムの状態を、システム内のトランザクション数nで表す。nには、サービスを受けているトランザクションとサービスを待機しているトランザクションの数の和。

時刻tにおいてトランザクション数がnである状態確率をpn(t)とすると、状態方程式は以下のようになる。

(1)   \begin{eqnarray*} p_n (t + \Delta t) &=& p_{n-1} \lambda \Delta t + p_n (t) (1 - \lambda \Delta t - \mu \Delta t) + p_{n+1} \mu \Delta t \\ p_{0}(t + \Delta t) &=& p_{0}(1 - \lambda \Delta t) + p_{1} \mu \Delta t \end{eqnarray*}

まず式(1)の第1式について、

(2)   \begin{eqnarray*} \frac{dp_n (t)}{dt} &=& \lim_{\Delta t \rightarrow 0} \frac{p_n(t + \Delta t) - p_n (t)}{\Delta t} \\ &=& p_{n-1} \lambda - p_n (\lambda + \mu) + p_{n+1} \mu \end{eqnarray*}

また第2式については、

(3)   \begin{eqnarray*} \frac{dp_0 (t)}{dt} &=& \lim_{\Delta t \rightarrow 0} \frac{p_0(t + \Delta t) - p_0 (t)}{\Delta t} \\ &=& - p_0 \lambda + p_1 \mu \end{eqnarray*}

式(2)と式(3)を改めてまとめて書くと、

(4)   \begin{eqnarray*} \frac{dp_n (t)}{dt} &=& \lambda p_{n-1} - (\lambda + \mu) p_n + \mu p_{n+1} \\ \frac{dp_0 (t)}{dt} &=& - \lambda p_0 + \mu p_1 \end{eqnarray*}

定常問題化と状態方程式の解

状態方程式においてt → ∞でトランザクション数の変化がなく一定値に収束するとして、次式を得る。

(5)   \begin{eqnarray*} \lambda p_{n-1} - (\lambda + \mu) p_n + \mu p_{n+1} &=& 0 \quad (n > 0) \\ - \lambda p_0 + \mu p_1 &=& 0 \end{eqnarray*}

ここでρ = λ/μ < 0とおいて、

(6)   \begin{eqnarray*} \rho p_{n-1} - (1 + \rho) p_n + p_{n+1} &=& 0 \quad (n > 0) \\ - \rho p_0 + p_1 &=& 0 \end{eqnarray*}

これは階差数列の式に変形できて、

(7)   \begin{eqnarray*} p_n - p_{n-1} &=& \rho (p_n - p_{n-1}) \\ p_1 &=& \rho p_0 \end{eqnarray*}

上式から順次各項を求めると、

(8)   \begin{eqnarray*} p_1 &=& \rho p_0 \\ p_2 &=& \rho (p_1 - p_0) + p_1 = \rho p_1 = \rho ^2 p_0 \\ p_3 &=& \rho(p_2 - p_1) + p_2 = \rho p_2 = \rho ^3 p_0 \\ &\cdots& \\ p_n &=& \rho ^n p_0 \end{eqnarray*}

全事象の和が1という条件から、以下の結果を得る。

(9)   \begin{eqnarray*} \sum_{i=0}^\infty p_n &=& p_0 (1 + \rho + \rho ^2 + \cdots ) = p_0 \frac{1}{1 - \rho} = 1 \\ \therefore \quad p_0 &=& 1 - \rho \end{eqnarray*}

これより、システムの状態がnである確率は以下で表せる。

(10)   \begin{equation*} p _n &=& (1 - \rho) \rho ^n \end{equation*}

ρの意味

ρ = λ / μは、単位時間当たりのサービス提供数に対する単位時間当たりのトラフィック到達数で、サービスの混み具合を表している。また、どの程度サービスが稼働しているか／利用されているか、とも言えるので、混雑度、平均稼働率／利用率、平均到達率、平均トラフィック密度などと呼ばれている。

平均トランザクション数と平均待ち行列長

システム内の平均トランザクション数Lは、

(11)   \begin{eqnarray*} L &=& \sum_{n=0}^\infty n p_n = (1 - \rho) \sum_{n=0}^\infty n \rho ^n \\ &=& (1 - \rho) \left(0 \cdot \rho^0 + 1 \cdot \rho^1 + 2 \cdot \rho^2 + \cdots \right) \end{eqnarray*}

これを以下のように解く。

(12)   \begin{eqnarray*} & &\begin{array}{rrrrrrrrrrr} \displaystyle \frac{1}{1 - \rho} L_n &= &1 \cdot \rho ^1 &+ &2 \cdot \rho ^2 &+ &\cdots &+ &\n \rho^n \\ \displaystyle \frac{\rho}{1 - \rho} L_n &= & & &1 \cdot \rho^2 &+ &\cdots &+ &(n - 1) \rho^n &+ &n \rho^{n + 1} \\ \hline L_n &= &\rho &+ &\rho^2 &+ &\cdots &+ &\rho^n &- &n \rho^{n+1} \end{array} \\ \\ & &L_n = \rho \frac{1 - \rho^n}{1 - \rho} - n \rho^{n+1} \end{eqnarray*}

よって、

(13)   \begin{equation*} L = \lim_{n \rightarrow \infty} L_n = \frac{\rho}{1 - \rho} \end{equation*}

また平均待ち行列長については、サービス中のトランザクションを除いて考えて、

(14)   \begin{eqnarray*} L_q &=& 0 \cdot p_0 + 0 \cdot p_1 + 1 \cdot p_2 + 2 \cdot p_3 + \cdots\\ &=& (1 - \rho) \left( 1 \cdot \rho^2 + 2 \cdot \rho^3 + \cdots \right) \end{eqnarray*}

これも以下のように解く。

(15)   \begin{eqnarray*} & &\begin{array}{rrrrrrrrrrr} \displaystyle \frac{1}{1 - \rho} L_qn &= &1 \cdot \rho ^2 &+ &2 \cdot \rho ^3 &+ &\cdots &+ &\n \rho^{n+1} \\ \displaystyle \frac{\rho}{1 - \rho} L_qn &= & & &1 \cdot \rho^3 &+ &\cdots &+ &(n - 1) \rho^{n + 1} &+ &n \rho^{n + 2} \\ \hline L_n &= &\rho^2 &+ &\rho^3 &+ &\cdots &+ &\rho^{n+1} &- &n \rho^{n+2} \end{array} \\ \\ & &L_n = \rho^2 \frac{1 - \rho^n}{1 - \rho} - n \rho^{n+2} \end{eqnarray*}

よって、

(16)   \begin{equation*} L_q = \lim_{n \rightarrow \infty} L_qn = \frac{\rho^2}{1 - \rho} \end{equation*}

リトルの法則(Litter’s law)

定常状態にある待ち行列において、トランザクションがシステムに到着してからサービスを終えるまでの時間の平均(平均応答時間)をTとすると、その間に平均してλTのトランザクションが到着することから、次式が成り立つ。

(17)   \begin{equation*} L = \lambda T \end{equation*}

また、同じことが待ち行列長Lqと平均待ち時間Tqにも言えるので、

(18)   \begin{equation*} L_q = \lambda T_q \end{equation*}

リトルの公式を使うと、待ち行列の長さと到着率から、平均待ち時間が計算できる。

(19)   \begin{eqnarray*} T &=& \frac{L}{\lambda} \\ T_q &=& \frac{L_q}{\lambda} \end{eqnarray*}

たとえば客の列に到着したときの行列の人数を数え、その後到着する客の数や出ていく客の数から到着率を推定することで、待ち時間を推定できる。

 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です