ジャクソンネットワークの積形式解の存在（２）

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

「ジャクソンネットワークの積形式解の存在（１）」の続きです。
「ジャクソンネットワークの積形式解の存在（１）」で登場した局所平衡方程式（６）

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

が大域平衡方程式を満足することを確認します。

まず、上の図のように考えれば、大域平衡方程式を作るのに考慮すべき遷移は以下のようなものです。
まず状態\vec~kに入る遷移から

ただし、状態状態\vec~k(-j)はステーションjのジョブ数だけを−１した状態を表すものとします。また、上記の遷移はiとjについて合計をとるものとします。さらに、k_j=0の場合は、状態\vec~k(-j)や状態\vec~k(+i,-j)は存在しないので、それらからの遷移はないものと考えます。
次に状態\vec~kから出る遷移は

これについても上記の遷移はjについて合計をとるものとします。さらに、k_j=0の場合は、状態\vec~k(-j)や状態\vec~k(+i,-j)は存在しないので、それらからの遷移はないものと考えます。
すると大域平衡方程式は（出て行くほうを左辺に入ってくるほうを右辺に書くと）以下のようになります。

  • \Bigsum_{j=1}^Np(\vec~k)\lambda_j+\Bigsum_{j=1}^Np(\vec~k)\frac{min(k_j,m_j)}{t_{ej}}
    • =\Bigsum_{j=1}^Np(\vec~k(-j))\lambda_j+\Bigsum_{j=1}^N\Bigsum_{i=1}^Np(\vec~k(+i,-j))\frac{min(k_i+1,m_i)}{t_{ei}}r_{ij}
    • +\Bigsum_{j=1}^Np(\vec~k(+j))\frac{min(k_j+1,m_j)}{t_{ej}}r_{j0}・・・・・・（７）

ただしr_{j0}はジョブがステーションjでの処理終了後、ネットワークの外に出て行く確率を表します。この定義から

  • r_{j0}=1-\Bigsum_{i=1}^Nr_{ji}・・・・・・（８）

であることが分かります。また式（７）においてk_j=0の時のp(\vec~k(-j))とp(\vec~k(+i,-j))はゼロであると考えます。


では、局所平衡方程式（６）が大域平衡方程式（７）を満たすことを確認します。
式（６）から、もしk_j>0ならば

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

k_j=0の時は、式（９）の左辺は０になります。そこでk_j=0の時はp(\vec~k(-j))=0、p(\vec~k(+i,-j))=0であると考えれば、k_j{\ge}0の時に式（９）が成り立つと言う事が出来ます。
また、（６）から

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

（９）と（１０）を足すと

  • p(\vec~k)\lambda_j+p(\vec~k)\frac{min(k_j,m_j)}{t_{ej}}=p(\vec~k(-j))\lambda_j
    • +\Bigsum_{i=1}^Np(\vec~k(+i,-j))\frac{min(k_i+1,m_i)}{t_{ei}}r_{ij}
    • +p(\vec~k(+j))\frac{min(k_j+1,m_j)}{t_{ej}}-\Bigsum_{i=1}^Np(\vec~k(+i))\frac{min(k_i+1,m_i)}{t_{ei}}r_{ij}

この両辺をjについて合計すると

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

（１１）の左辺は

  • \Bigsum_{j=1}^Np(\vec~k(-j))\lambda_j+\Bigsum_{j=1}^N\Bigsum_{i=1}^Np(\vec~k(+i,-j))\frac{min(k_i+1,m_i)}{t_{ei}}r_{ij}
    • +\Bigsum_{j=1}^Np(\vec~k(+j))\frac{min(k_j+1,m_j)}{t_{ej}}-\Bigsum_{j=1}^N\Bigsum_{i=1}^Np(\vec~k(+i))\frac{min(k_i+1,m_i)}{t_{ei}}r_{ij}
  • =\Bigsum_{j=1}^Np(\vec~k(-j))\lambda_j+\Bigsum_{j=1}^N\Bigsum_{i=1}^Np(\vec~k(+i,-j))\frac{min(k_i+1,m_i)}{t_{ei}}r_{ij}
    • +\Bigsum_{j=1}^Np(\vec~k(+j))\frac{min(k_j+1,m_j)}{t_{ej}}-\Bigsum_{i=1}^N\Bigsum_{j=1}^Np(\vec~k(+j))\frac{min(k_j+1,m_i)}{t_{ei}}r_{ji}
  • =\Bigsum_{j=1}^Np(\vec~k(-j))\lambda_j+\Bigsum_{j=1}^N\Bigsum_{i=1}^Np(\vec~k(+i,-j))\frac{min(k_i+1,m_i)}{t_{ei}}r_{ij}
    • +\Bigsum_{j=1}^Np(\vec~k(+j))\frac{min(k_j+1,m_j)}{t_{ej}}\left[1-\Bigsum_{i=1}^Nr_{ji}\right]

ここで最後の項について式（８）を適用すれば

  • \Bigsum_{j=1}^Np(\vec~k(-j))\lambda_j+\Bigsum_{j=1}^N\Bigsum_{i=1}^Np(\vec~k(+i,-j))\frac{min(k_i+1,m_i)}{t_{ei}}r_{ij}
    • +\Bigsum_{j=1}^Np(\vec~k(+j))\frac{min(k_j+1,m_j)}{t_{ej}}\left[1-\Bigsum_{i=1}^Nr_{ji}\right]
  • =\Bigsum_{j=1}^Np(\vec~k(-j))\lambda_j+\Bigsum_{j=1}^N\Bigsum_{i=1}^Np(\vec~k(+i,-j))\frac{min(k_i+1,m_i)}{t_{ei}}r_{ij}
    • +\Bigsum_{j=1}^Np(\vec~k(+j))\frac{min(k_j+1,m_j)}{t_{ej}}r_{j0}

よって式（１１）は

  • \Bigsum_{j=1}^Np(\vec~k)\lambda_j+\Bigsum_{j=1}^Np(\vec~k)\frac{min(k_j,m_j)}{t_{ej}}
    • =\Bigsum_{j=1}^Np(\vec~k(-j))\lambda_j+\Bigsum_{j=1}^N\Bigsum_{i=1}^Np(\vec~k(+i,-j))\frac{min(k_i+1,m_i)}{t_{ei}}r_{ij}
    • +\Bigsum_{j=1}^Np(\vec~k(+j))\frac{min(k_j+1,m_j)}{t_{ej}}r_{j0}

となり、これは大域平衡方程式（７）に一致します。よって局所平衡方程式（６）が大域方程式（７）を満たすことを示すことが出来ました。


「ジャクソンネットワークの積形式解の存在（３）」に続きます。