Ｍ／Ｍ／１→Ｍ／１→Ｍ／１待ち行列の解析

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

先行エントリ：積形式解、ジャクソン・ネットワーク


今度は、下図のような３段直列待ち行列でも（処理時間が指数分布で到着間隔も指数分布ならば）積形式解になるかどうか調べます。

１台目の装置の平均処理時間をt_{e1}、２台目の装置の平均処理時間をt_{e2}、３台目の装置の平均処理時間をt_{e3}とします。さらに、１台目の装置の利用率をu_1、２台目の装置の利用率をu_2、３台目の装置の利用率をu_3とします。
２段直列のときと同じように、スループットがこの３つのステーションで等しいことから

  • \lambda=\frac{u_1}{t_{e1}}=\frac{u_2}{t_{e2}}=\frac{u_3}{t_{e3}}・・・・・・（１）

が成り立ちます。次に、２段直列のときと同じように状態遷移図を書こうとしたのですが、下図のようになってしまい、うまく書けませんでした。

しかし２段直列のときに下図のような

関係の状態間の遷移の流れの量を等しいと仮定して積形式解を導き出したように、３段直列でも下図のような関係の状態間の遷移の流れの量を等しいと仮定してみます。

  • 図１

もし、この仮定が成り立つならば、全体の状態遷移の間でも平衡が成り立つことになります（下図）。

図１から数式を作ると、平衡状態が成り立つための式は

  • p(k,m,n)\lambda=p(k+1,m,n)\frac{1}{t_{e1}}=p(k,m+1,n)\frac{1}{t_{e2}}=p(k,m,n+1)\frac{1}{t_{e3}}

となります。ここにp(k,m,n)は状態(k,m,n)の発生確率です。この式は以下の３つの式に分解出来ます。

  • p(k,m,n)\lambda=p(k+1,m,n)\frac{1}{t_{e1}}
  • p(k,m,n)\lambda=p(k,m+1,n)\frac{1}{t_{e2}}
  • p(k,m,n)\lambda=p(k,m,n+1)\frac{1}{t_{e3}}

これらの式のそれぞれに式（１）を代入して少々変形すると、以下のようになります。

  • p(k+1,m,n)=p(k,m,n)u_1・・・・・・（２）
  • p(k,m+1,n)=p(k,m,n)u_2・・・・・・（３）
  • p(k,m,n+1)=p(k,m,n)u_3・・・・・・（４）

式（２）からは

  • p(k,m,n)=p(0,m,n)u_1^k・・・・・・（５）

式（３）からは

  • p(k,m,n)=p(k,0,n)u_2^m・・・・・・（６）

式（４）からは

  • p(k,m,n)=p(k,m,0)u_3^n・・・・・・（７）


式（６）からは

  • p(0,m,n)=p(0,0,n)u_2^m・・・・・・（８）

が導かれます。式（８）を式（５）に代入して

  • p(k,m,n)=p(0,0,n)u_1^ku_2^m・・・・・・（９）

となります。式（７）からは

  • p(0,0,n)=p(0,0,0)u_3^n・・・・・・（１０）

が導かれます。式（１０）を式（９）に代入して

  • p(k,m,n)=p(0,0,0)u_1^ku_2^mu_3^n・・・・・・（１１）

となります。式（１１）は積形式解です。
このようにＭ／Ｍ／１→Ｍ／１→Ｍ／１待ち行列でも積形式解になることが分かりました。