ケリーネットワークの積形式解の存在証明の試み（再挑戦）（１）

「ケリーネットワーク」が積形式解を持つことの証明に再挑戦します。

待ち行列ネットワークのステーションの数を $N$ とします。ステーションを区別するために1から順番に番号をつけていきます。 $i$ 番目のステーションは $m_i$ 台の装置から成り、装置の処理時間は指数分布であるとします。ジョブのクラスの数を $Q$ とします。クラスに1から順番に番号をつけていきます。外から各ステーションへの各クラスのジョブの到着の時刻の間隔も指数分布であるとします。
$i$ 番目のステーションを通るクラス $k$ のジョブのスループットを $\theta_{ik}$ で表します。また、 $i$ 番目のステーションに外から入ってくるクラス $k$ のジョブのスループットを $\lambda_{ik}$ で表します。ステーション $i$ を終えたクラス $k$ のジョブがクラス $s$ になってステーション $j$ に進む確率を $r_{ikjs}$ で表します。そうすると、ステーション $j$ にクラス $s$ のジョブの入ってくる量 $\theta_{js}$ は

$\theta_{js}=\lambda_{js}+\Bigsum_{i=1}^N\Bigsum_{k=1}^Q\theta_{ik}r_{ikjs}$ ・・・・・・（１）

で表すことが出来ます。式（１）は $\theta$ についての連立一次方程式になっています。これが $\theta$ について解けると仮定します。これを、

$\theta_{js}=f_{js}(\Lambda,R)$ ・・・・・・（２）

と表わすことにします。ただし $\Lambda$ は $\lambda_{ik}$ を簡略的に表わしたものであり、 $R$ は $(r_{ikjs})$ を簡略的に表わしたものとします。さて $a$ を任意の定数として、式（１）で

$\theta_{ik}$ → $a\theta_{ik}$
$\lambda_{ik}$ → $a\lambda_{ik}$

で置き換えると、やはり式（１）が成り立つので式（２）について

$f_{js}(a\Lambda,R)=af_{js}(\Lambda,R)$ ・・・・・・（３）

が成り立つことが分かります。一方、定義から

$\Bigsum_{s=1}^Q\theta_{js}=\frac{m_ju_j}{t_{ej}}$ ・・・・・・（４）

です。ここでステーション $i$ のクラス $s$ による利用率 $u_{js}$ を

$u_{js}=\frac{\theta_{js}t_{ej}}{m_j}$ ・・・・・・（５）

で定義します。このようにすると

$\Bigsum_{s=1}^Qu_{js}=\Bigsum_{s=1}^Q\frac{\theta_{js}t_{ej}}{m_j}=\frac{t_{ej}}{m_j}\Bigsum_{s=1}^Q\theta_{js}=\frac{t_{ej}}{m_j}\frac{m_ju_j}{t_{ej}}=u_j$

つまり

$\Bigsum_{s=1}^Qu_{js}=u_j$ ・・・・・・（５’）

となり、 $u_{js}$ が $u_j$ のうちのクラス $s$ による部分であることが分かります。
式（５）を変形して

$\frac{1}{t_{ej}}=\frac{\theta_{js}}{m_ju_{js}}$ ・・・・・・（６）

ネットワークの「状態」は各ステーションでの「状態」を列記したものとし、各ステーションでの「状態」は「複数クラスを持つＭ／Ｍ／ｍ待ち行列（４）」で定義したのと同じように、ジョブが現実にどの装置上にあるかにかかわらず、位置１から順に詰めていくが、クラスでソートしない並びを１つの状態とします。また、処理中のどれかのジョブが終了して出て行った場合は、そのジョブの位置より右側の全てのジョブが１つずつズレるものと考えることも同様です。

ネットワークの状態 $S$ を考え、状態 $S$ の時にステーション $j$ にクラス $s$ のジョブが到着して出来た状態を $S(+(j,s))$ と表すことにします。局所平衡方程式を組立てるのに、まず状態 $S$ の時にステーション $j$ にクラス $s$ のジョブが到着して状態 $S(+(j,s))$ に遷移することが考えられます。次に、ステーション $i$ からクラス $k$ のジョブが出発し、それが確率 $r_{ikjs}$ でクラス $s$ に変わってステーション $j$ に到着し状態 $S(+(j,s))$ に遷移することが考えられます。
ここで問題になるのがその遷移前の状態がどのような状態であるか、です。たとえば $s=2$ としましょう。そして現在のネットワークの状態が $S(+(j,2))$ であるとしましょう。今、ある状態からステーション $i$ で終了したクラス $k$ のジョブが確率 $r_{ikj2}$ に従ってクラス2に代わりステーション $j$ に向かった結果ネットワークの状態が $S(+(j,2))$ としましょう。ここで問題を簡単にするために $k$ もまた2であるとしましょう。すなわちステーション $i$ で終了したクラス2のジョブがクラスを変えることなくステーション $j$ に到着するとしましょう。このジョブがステーション $j$ に到着した時のステーション $i$ の状態は $\{(1,2)\}$ であり、ステーション $i$ の装置台数は３台（すなわち $m_i=3$ ）であるとしましょう。ではこのジョブが到着する前のステーション $i$ の状態は何だったでしょうか？
その状態としては

$\{(2,1,2)\}$

の場合と

$\{(1,2,2)\}$

の場合が考えられます。

「ケリーネットワークの積形式解の存在証明の試み（再挑戦）（２）」に続きます。