閉鎖型ジャクソンネットワークの積形式解（１）

待ち行列ネットワークへの助走

閉鎖型ジャクソンネットワークが積形式解を持つことを見ておきます。
「閉鎖型待ち行列ネットワークの到着定理（７）」の式（４２）から証明を進めていきます。ここではその式の番号を降りなおして（１）とします。

  • p(\vec~k(j:+1))=a\frac{m_ju_j}{\min(k_j+1,m_j)}・・・・・（１）

この式の前提条件は以下の通りでした。

  • ネットワーク全体にあるジョブ数はS-1個
  • \vec~kは、そのネットワークの任意の状態を表す。ただし\vec~kはk_iからなるベクトルで、k_iはステーションiでのジョブ数である。
  • \vec~k(j:+1)は状態\vec~kに比べてステーションjだけが１個ジョブ数が多い状態。

（１）を変形して

  • a=\frac{\min(k_j+1,m_j)}{m_ju_j}p(\vec~k(j:+1))・・・・・（２）

一方、ステーションjとは異なるステーションiを考えて式（１）に対応する式を作ると

  • p(\vec~k(i:+1))=a\frac{m_iu_i}{\min(k_i+1,m_i)}・・・・・（３）

式（３）に（２）を代入すると

  • p(\vec~k(i:+1))= \frac{\min(k_j+1,m_j)}{m_ju_j}\frac{m_iu_i}{\min(k_i+1,m_i)} p(\vec~k(j:+1))・・・・・（４）

式（４）において状態\vec~k(j:+1)を改めて状態\vec~kと定義しなおすと、この状態はネットワークにジョブがS個ある場合の状態の１つを表します。すると式（４）の右辺の状態\vec~k(i:+1)は状態\vec~k(i:+1,j:-1)と再定義されます。これは状態\vec~kと比べてステーションiのジョブ数が１つ多くて、その代わりステーションjのジョブ数が１つ少ない状態です。このように状態を定義しなおすと式（４）は

  • p(\vec~k(i:+1,j:-1))= \frac{\min(k_j,m_j)}{m_ju_j}\frac{m_iu_i}{\min(k_i+1,m_i)} p(\vec~k)・・・・・（５）

となります。


ここで状態\vec~wを、w_1=S、w_i=0（ただしi\neq{1}）であるような状態であるとします。任意の状態\vec~kは、状態\vec~wに、ステーション１からジョブを１つ減らして他のステーションに１増やすという操作を繰り返し適宜回、適用することによって実現することが出来ますから、p(\vec~k)は、p(\vec~w)に式（５）を繰り返し適用することによって以下のように求めることが出来ます。

  • p(\vec~k)=\frac{\min(S,m_1)}{m_1u_1}\frac{\min(S-1,m_1)}{m_1u_1}\:\cdots\:\frac{\min(k_1+2,m_1)}{m_1u_1}\frac{\min(k_1+1,m_1)}{m_1u_1}
    • \times\frac{m_2u_2}{\min(1,m_2)} \frac{m_2u_2}{\min(2,m_2)}\:\cdots\:\frac{m_2u_2}{\min(k_2-1,m_2)}\frac{m_2u_2}{\min(k_2,m_2)}\times\:\cdots
    • \times\frac{m_Nu_N}{\min(1,m_N)}\frac{m_Nu_N}{\min(N,m_N)}\:\cdots\:\frac{m_Nu_N}{\min(k_N-1,m_N)}\frac{m_Nu_N}{\min(k_N,m_N)}{\times}p(\vec~w)・・・・・（６）

式（６）の形がすでに積形式の形になっています。


ここで

  • \frac{m_2u_2}{\min(1,m_2)}\frac{m_2u_2}{\min(2,m_2)}\:\cdots\:\frac{m_2u_2}{\min(k_2-1,m_2)}\frac{m_2u_2}{\min(k_2,m_2)}

についてもう少し調べると、k_2{\le}m_2の時

  • \frac{m_2u_2}{\min(1,m_2)}\frac{m_2u_2}{\min(2,m_2)}\:\cdots\:\frac{m_2u_2}{\min(k_2-1,m_2)}\frac{m_2u_2}{\min(k_2,m_2)}=\frac{(m_2u_2)^{k_2}}{k_2!}

k_2>m_2の時

  • \frac{m_2u_2}{\min(1,m_2)} \frac{m_2u_2}{\min(2,m_2)}\:\cdots\:\frac{m_2u_2}{\min(k_2-1,m_2)}\frac{m_2u_2}{\min(k_2,m_2)}=\frac{(m_2u_2)^{m_2}}{m_2!}u_2^{k_2-m_2}

Ｍ／Ｍ／ｍにおける待ち時間の式の導出（２）の（１１）（１２）と比較すれば

  • \frac{m_2u_2}{\min(1,m_2)}\frac{m_2u_2}{\min(2,m_2)}\:\cdots\:\frac{m_2u_2}{\min(k_2-1,m_2)}\frac{m_2u_2}{\min(k_2,m_2)}=\frac{1}{p_{02}}p\{M/M/m_2,u_2\}(k_2)・・・・・（７）

と書くことが出来ることが分かります。ただし、

  • p_{02}=p\{M/M/m_2,u_2\}(0)

であり、

  • p\{M/M/m_2,u_2\}(k_2)

は、装置台数m_2のＭ／Ｍ／ｍ待ち行列で装置の利用率がu_2である場合に、システム内にジョブがk_2個ある確率を表します。


「閉鎖型ジャクソンネットワークの積形式解（２）」に続きます。