Ｍ／Ｍ／２→Ｍ／１待ち行列の解析 - 工場統計力学（建設中！）

先行エントリ：Ｍ／１一般ネットワークの場合の積形式解存在の証明

「Ｍ／１一般ネットワークの場合の積形式解存在の証明」では、ネットワークを構成するステーションは全て１台の装置からなるという制限がありました。しかしジャクソンネットワークは複数台の装置から成るステーションを許しています。今日は、一般的なジャクソンネットワークで積形式解の存在を証明する前段階として、下図のような待ち行列ネットワークを考え、その積形式解の存在を証明することを試みたいと思います。

装置１、２の利用率、処理時間をそれぞれ $u_1$ 、 $u_2$ 、 $T_{e1}$ 、 $t_{e2}$ とします。また装置１にロットが到着するスループットを $\lambda_1$ とします。この図に対応した局所平衡方程式を表す遷移図を下に書きます。

この図では、状態 $(k+1,m)$ →状態 $(k,m+1)$ の遷移の量を書き込んでいません。それはk+1の値が１の時と２以上の時では（つまりkの値がゼロの時と１以上の時では）遷移の量が異なるからです。kの値がゼロの時は、遷移の量が

$\frac{1}{t_{e1}}$

ですが、kの値が１以上の時は遷移の量が

$\frac{2}{t_{e1}}$

になります。つまり

となります。よって、

$p(1,m)\frac{1}{t_{e1}}=p(0,m)\lambda_1$ ・・・・・・（１）
$p(0,m+1)\frac{1}{t_{e2}}=p(1,m)\frac{1}{t_{e1}}$ ・・・・・・（２）

また、 $k{\ge}1$ の場合は

$p(k+1,m)\frac{2}{t_{e1}}=p(k,m)\lambda_1$ ・・・・・・（３）
$p(k,m+1)\frac{1}{t_{e2}}=p(k+1,m)\frac{2}{t_{e1}}$ ・・・・・・（４）

また

$\lambda_1=\frac{2u_1}{t_{e1}}=\frac{u_2}{t_{e2}}$ ・・・・・・（５）

が成り立ちます。まず、式（１）に式（５）を用いて

$p(1,m)\frac{\lambda_1}{2u_1}=p(0,m)\lambda_1$

よって

$p(1,m)=p(0,m)2u_1$ ・・・・・・（６）

次に式（３）に式（５）を用いて同様に変形すると

$k{\ge}1$ の時、 $p(k+1,m)=p(k,m)u_1$ ・・・・・・（７）

これは、「Ｍ／Ｍ／ｍにおける待ち時間の式の導出（２）」における式（８）と式（９）と本質的に同じなので、同様の考察から以下のように言えます。利用率が $u_1$ に等しいＭ／Ｍ／２待ち行列における状態 $k$ の発生確率を $p\left{M/M/2,u_1\right}(k)$ で表します。すると $p(k,m)$ は、

$p(k,m)=c_1p\left{M/M/2,u_1\right}(k)p(0,m)$ ・・・・・・（８）

と表すことが出来ます。ただし、 $c_1$ は規格化定数です。（「Ｍ／Ｍ／２→Ｍ／１待ち行列の解析（補足）」参照）。一方、式（２）の右辺に式（１）を代入して

$p(0,m+1)\frac{1}{t_{e2}}=p(0,m)\lambda_1$

式（４）の右辺に式（３）を代入して

$k{\ge}1$ の時、 $p(k,m+1)\frac{1}{t_{e2}}=p(k,m)\lambda_1$

よって全ての $k$ について

$p(k,m+1)\frac{1}{t_{e2}}=p(k,m)\lambda_1$ ・・・・・・（９）

式（９）に式（５）を用いて

$p(k,m+1)\frac{\lambda_1}{u_2}=p(k,m)\lambda_1$

よって

$p(k,m+1)=p(k,m)u_2$ ・・・・・・（１０）

これも上と同様に考えて、利用率が $u_2$ に等しいＭ／Ｍ／１待ち行列における状態 $m$ の発生確率を $p\left{M/M/1,u_2\right}(m)$ で表すと

$p(k,m)=c_2p\left{M/M/1,u_2\right}(m)p(k,0)$ ・・・・・・（１１）

になることが分かります。ただし、 $c_2$ も規格化定数です。式（１１）から

$p(0,m)=c_2p\left{M/M/1,u_2\right}(m)p(0,0)$ ・・・・・・（１２）

式（８）に式（１２）を代入して

$p(k,m)=c_1c_2p\left{M/M/2,u_1\right}(k)p\left{M/M/1,u_2\right}(m)p(0,0)$ ・・・・・・（１３）

よって、Ｍ／Ｍ／２→Ｍ／１待ち行列においても積形式解が存在することが明らかになりました。
さらに規格化定数を求めておきます。

$\Bigsum_{k=1}^{\infty}\Bigsum_{m=1}^{\infty}p(k,m)=1$ ・・・・・・（１４）

でなければならないので、式（１４）に式（１３）を代入して

$\Bigsum_{k=1}^{\infty}\Bigsum_{m=1}^{\infty}c_1c_2p\left{M/M/2,u_1\right}(k)p\left{M/M/1,u_2\right}(m)p(0,0)=1$
$c_1c_2p(0,0)\Bigsum_{k=1}^{\infty}p\left{M/M/2,u_1\right}(k)\Bigsum_{m=1}^{\infty}p\left{M/M/1,u_2\right}(m)=1$ ・・・・・・（１５）