Ｍ／E2／１／２待ち行列

待ち行列理論

最近ジョブ数有限の待ち行列を取り上げているのは、一般的なジョブ数有限の待ち行列の定常状態確率分布の近似式はないか知りたいからです。まず、Ｍ／Ｇ／１／１については正確に定常状態確率分布を求めることが出来ました（「Ｍ／Ｇ／１／１待ち行列（４）」参照）。Ｍ／Ｇ／ｓ／ｓについてもおそらくＭ／Ｍ／ｓ／ｓと同じ定常状態確率分布であろうという推測も出来ました。もしこの推測が正しければＭ／Ｍ／ｓ／ｓ待ち行列についてはすでに定常状態確率分布はよく知られているので、Ｍ／Ｇ／ｓ／ｓ待ち行列についても定常状態確率分布が計算できることになります。一方、ジョブ数の上限値が大きくなれば分布がＭ／Ｇ／１の分布に近づいてくることは容易に想像出来ます。Ｍ／Ｇ／１の定常状態確率分布については近似式をすでに求めておりました（「Ｍ／Ｇ／１定常状態分布の近似式」参照）。これを元にして近似式を作ることも考えられます。
しかし近似式を作るには、まず正確な値がどのくらいか調べる必要があります。全ての場合について正確な値を求めることが出来ればそれが理想なのですが、それが出来なくても代表的な場合についての値を求めておく必要があります。そこで、ここではM/E_2/1/2待ち行列について定常状態確率分布を求めてみようと思います。

  • 図１


M/E_2/1/2待ち行列の状態遷移図を書くと左の図のようになります。丸の中の数字が状態を示します。状態０はジョブが０個の状態、ジョブ１：１はジョブが１個でサービスのフェーズが１の状態、ジョブ１：２はジョブが２個でサービスのフェーズが２の状態、ジョブ２：１はジョブが２個で、（そのうち１個はサービスを受けていて）サービスのフェーズが１の状態、ジョブ２：２はジョブが２個で、（そのうち１個はサービスを受けていて）サービスのフェーズが２の状態、です。


この状態遷移図から平衡方程式を作成すると以下のようになります。まず、状態０に出入りする流量に注目すると

  • up(0)=2p(1:2)

ここから

  • p(1:2)=\frac{u}{2}p(0)・・・・(1)

次に状態１：１を出入りする流量に注目すると

  • (u+2)p(1:1)=up(0)+2p(2:2)・・・・(2)

次に状態１：２を出入りする流量に注目すると

  • (u+2)p(1:2)=2p(1:1)・・・・(3)

式(3)に(1)を代入して

  • \frac{u(u+2)}{2}p(0)=2p(1:1)

よって

  • p(1:1)=\frac{u(u+2)}{4}p(0)・・・・(4)

サービスのフェーズに関わらずジョブが１個の状態の定常状態確率をp(1)とすると式(1)(4)を用いて

  • p(1)=p(1:1)+p(1:2)=\left[\frac{u(u+2)}{4}+\frac{u}{2}\right]p(0)=\frac{u}{4}(u+2+2)p(0)

よって

  • p(1)=\frac{u(u+4)}{4}p(0)・・・・(5)

式(4)を(2)に代入して

  • \frac{u(u+2)^2}{4}p(0)=up(0)+2p(2:2)

よって

  • 2p(2:2)=\frac{u(u+2)^2}{4}p(0)-up(0)=\frac{u}{4}[(u+2)^2-4]p(0)=\frac{u}{4}(u^2+4u)p(0)

よって

  • p(2:2)=\frac{u^2(u+4)}{8}p(0)・・・・(6)

次に状態２：１を出入りする流量に注目すると

  • up(1:1)=2p(2:1)

よって

  • p(2:1)=\frac{u}{2}p(1:1)・・・・(7)

式(7)に(4)を代入して

  • p(2:1)=\frac{u^2(u+2)}{8}p(0)・・・・(8)

サービスを受けているジョブのサービスのフェーズに関わらずジョブが２個の状態の定常状態確率をp(2)とすると式(6)(8)を用いて

  • p(2)=p(2:1)+p(2:2)=\frac{u^2(u+2)}{8}p(0)+\frac{u^2(u+4)}{8}p(0)=\frac{u^2(2u+6)}{8}p(0)

よって

  • p(2)=\frac{u^2(u+3)}{4}p(0)・・・・(9)

全ての状態の確率の和は１でなければならないので

  • p(0)+p(1)+p(2)=1

よって

  • \frac{4+u(u+4)+u^2(u+3)}{4}p(0)=1
  • \frac{4+u^2+4u+u^3+3u^2}{4}p(0)=1
  • \frac{u^3+4u^2+4u+4}{4}p(0)=1
  • p(0)=\frac{4}{u^3+4u^2+4u+4}・・・・(10)

式(10)を(5)に代入して

  • p(1)=\frac{u(u+4)}{u^3+4u^2+4u+4}・・・・(11)

式(10)を(9)に代入して

  • p(2)=\frac{u^2(u+3)}{u^3+4u^2+4u+4}・・・・(12)


以上でM/E_2/1/2待ち行列の定常状態確率分布を求めることが出来ました。