閉鎖型待ち行列ネットワークの到着定理（７）

「閉鎖型待ち行列ネットワークの到着定理（６）」の続きです。

待ち行列ネットワークのステーションの数を $N$ とします。ステーション $i$ のスループットを $\theta_i$ で表します。ステーション $i$ を終えたジョブがステーション $j$ に進む確率を $r_{ij}$ で表します。そうすると、ステーション $j$ に入ってくる量 $\theta_j$ は

$\theta_j=\Bigsum_{i=1}^N\theta_ir_{ij}$ ・・・・・・（３７）

で表すことが出来ます。式（３７）は $\theta$ についての連立一次方程式になっています。これを満足する $\theta$ を

$\theta_j=f_j(R)$ ・・・・・・（３８）

と表わすことにします。ただし $R$ は $(r_{ij})$ を簡略的に表わしたものとします。さて $a$ を任意の定数として、式（３７）で

$\theta_i$ → $a\theta_i$

で置き換えると、やはり式（３７）が成り立ちます。つまり式（３７）では $\theta$ は一意には決まらず、定数 $a$ が不定になります。

一方、定義から

$\theta_j=\frac{m_ju_j}{t_{ej}}$ ・・・・・・（３９）

です。ただし $u_j$ はステーション $j$ の装置の利用率です。式（３９）を変形すると

$\frac{1}{t_{ej}}=\frac{\theta_j}{m_ju_j}$ ・・・・・・（４０）

となります。さて、状態 $\vec~k(j:+1)$ についての局所平衡方程式は以下のように書くことが出来ます。

$p(\vec~k(j:+1))\frac{\min(k_j+1,m_j)}{t_{ej}}=\Bigsum_{i=1}^Np(\vec~k(i:+1))\frac{\min(k_i+1,m_i)}{t_{ei}}r_{ij}$ ・・・・・・（４１）

これの意味するところは、

状態 $\vec~k(j:+1)$ の時にステーション $j$ からジョブの処理が完了して別の状態に遷移する確率のレート（つまり $dt$ あたりの確率）

は

状態 $\vec~k(i:+1)$ の時にジョブがステーション $i$ での処理を終えてステーション $j$ に向かい状態 $\vec~k(j:+1)$ に遷移する確率レートを全ての $i$ について合計したもの

に等しい、ということです。

式（４１）を式（３７）と比較すると、（３７）で

$\theta_j{\rightar}p(\vec~k(j:+1))\frac{\min(k_j+1,m_j)\theta_j}{m_ju_j}$

と置き換えると（４１）になることが分かるので、

$p(\vec~k(j:+1))\frac{\min(k_j+1,m_j)\theta_j}{m_ju_j}=a\theta_j$

つまり

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

これを用いると

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

式（４２）と（４３）から

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

状態 $\vec~k(j:+1)$ と $\vec~k(i:+1)$ を比べれば、状態 $\vec~k(i:+1)$ でステーション $i$ のジョブ数を１減らし、ステーション $j$ のジョブ数を１増やしたのが状態 $\vec~k(j:+1)$ になりますが、状態 $\vec~k$ と $\vec~k(i:-1,q:+1)$ についても、状態 $\vec~k$ でステーション $i$ のジョブ数を１減らし、ステーション $q$ のジョブ数を１増やしたのが状態 $\vec~k(i:-1,q:+1)$ になるので、これらの状態の関係は並行しています。そこで、状態 $\vec~k$ と $\vec~k(i:-1,q:+1)$ について（４４）を適用すれば

$\frac{P(\vec~k(i:-1,q:+1))}{P(\vec~k)}=\frac{\min(k_i,m_i)m_qu_q}{\min(k_q+1,m_q)m_iu_i}$ ・・・・・（４５）

となります。

一方、遷移確率（３５）と（３６）の比は

$\frac{\frac{\min(k_q+2,m_q)}{t_{eq}}p(\vec~k(i:-1,q:+2))dt}{\frac{\min(k_q+1,m_q)}{t_{eq}}p(\vec~k(q:+1))dt}=\frac{\min(k_q+2,m_q)p(\vec~k(i:-1,q:+2))}{\min(k_q+1,m_q)p(\vec~k(q:+1))}$ ・・・・・（４６）

ここで（４４）を状態 $\vec~k(i:-1,q:+2)$ と $\vec~k(q:+1)$ について適用すると

$\frac{p(\vec~k(i:-1,q:+2))}{p(\vec~k(q:+1))}=\frac{\min(k_i,m_i)m_qu_q}{\min(k_q+2,m_q)m_iu_i}$ ・・・・・（４６-１）

（４６-１）を（４６）に代入して

- $=\frac{\min(k_q+2,m_q)}{\min(k_q+1,m_q)}\frac{\min(k_i,m_i)m_qu_q}{\min(k_q+2,m_q)m_iu_i}=\frac{\min(k_i,m_i)m_qu_q}{\min(k_q+1,m_q)m_iu_i}$ ・・・・・（４７）

式（４５）と（４７）より

$\frac{\frac{\min(k_q+2,m_q)}{t_{eq}}p(\vec~k(i:-1,q:+2))dt}{\frac{\min(k_q+1,m_q)}{t_{eq}}p(\vec~k(q:+1))dt}=\frac{P(\vec~k(i:-1,q:+1))}{P(\vec~k)}$ ・・・・・（４８）

これで、以下の補題が証明出来ました。この補題を補題２とします。

補題２
- ネットワーク全体でジョブがＳ個ある場合に、ステーション１にジョブが到着する際、そのジョブが見る状態が $\vec~k$ である確率と $\vec~k(i:-1,q:+1)$ である確率の比は、ネットワーク全体でジョブがＳ−１個ある場合の $P(\vec~k)$ と $P(\vec~k(i:-1,q:+1))$ の比に等しい。

「閉鎖型待ち行列ネットワークの到着定理（８）」に続きます。