工場統計力学（建設中！）

Ｍ／Ｇ／１／３待ち行列（１）

待ち行列理論

「Ｍ／Ｇ／１／２待ち行列（１）」の内容をＭ／Ｇ／１／３の場合に拡張します。

まず、サービス終了時のシステム内のジョブ数に注目します。この時、サービスを終了したジョブはジョブ数に含めません。そうするとジョブ数は２の時と１の時とゼロの時があります。それぞれの確率を $p'(2)$ 、 $p'(1)$ 、 $p'(0)$ で表わします。

あるサービス後にジョブが０個の場合、以下の２つの場合が考えられます。

前のサービス後にジョブが０個で、しばらくサーバが空いており、その後次にジョブが到着してサービス時間の間、ジョブの到着がなかった。
前のサービス後にジョブが１個で、そのジョブのサービス時間の間、ジョブの到着がなかった。

サービス時間の間、ジョブが到着しない確率を $A(0)$ とします。定常状態であることを考えると上の考察から

$p'(0)=p'(0)A(0)+p'(1)A(0)$

となります。よって

$p'(1)=\frac{1-A(0)}{A(0)}p'(0)$ ・・・・(1)

あるサービス後にジョブが１個の場合、以下の３つの場合が考えられます。

前のサービス後にジョブが０個で、しばらくサーバが空いており、その後次にジョブが到着してサービス時間の間、ジョブが１個到着した。
前のサービス後にジョブが１個で、そのジョブのサービス時間の間、ジョブが１個到着した。
前のサービス後にジョブが２個で、そのうちの１つのジョブのサービスの間、ジョブの到着がなかった。

サービス時間の間、ジョブが１個到着する確率を $A(1)$ とします。定常状態であることを考えると上の考察から

$p'(1)=p'(0)A(1)+p'(1)A(1)+p'(2)A(0)$

よって

$p'(2)A(0)=[1-A(1)]p'(1)-p'(0)A(1)$
$p'(2)=\frac{[1-A(1)]p'(1)-p'(0)A(1)}{A(0)}$ ・・・・(2)

Ｍ／Ｇ／１／３の場合、サービス終了時のシステム内のジョブ数はゼロか１か２のどれかしかないので

$1=p'(0)+p'(1)+p'(2)$ ・・・・(3)

式(3)の右辺に(1)(2)を代入して

- $=\frac{A(0)p'(0)+[1-A(0)]p'(0)+[1-A(1)]p'(1)-A(1)p'(0)}{A(0)}$
- $=\frac{p'(0)+[1-A(1)]p'(1)-A(1)p'(0)}{A(0)}=\frac{[1-A(1)]p'(0)+[1-A(1)]p'(1)}{A(0)}$
- $\frac{[1-A(1)][p'(0)+p'(1)]}{A(0)}$

よって

$\frac{[1-A(1)][p'(0)+p'(1)]}{A(0)}=1$ ・・・・(4)

ここで式(4)の右辺の $p'(0)+p'(1)$ については式(1)を用いると

$p'(0)+p'(1)=\frac{A(0)+1-A(0)}{A(0)}p'(0)$

よって

$p'(0)+p'(1)=\frac{p'(0)}{A(0)}$ ・・・・(5)

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

$\frac{[1-A(1)]p'(0)}{A(0)^2}=1$

よって

$p'(0)=\frac{A(0)^2}{1-A(1)}$ ・・・・(6)

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

$p'(1)=\frac{1-A(0)}{A(0)}\times\frac{A(0)^2}{1-A(1)}$
$p'(1)=\frac{[1-A(0)]A(0)}{1-A(1)}$ ・・・・(7)

式(6)(7)を(2)に代入して

$p'(2)=\frac{[1-A(0)]A(0)-A(1)\frac{A(0)^2}{1-A(1)}}{A(0)}=[1-A(0)]-A(1)\frac{A(0)}{1-A(1)}=\frac{[1-A(0)][1-A(1)]-A(1)A(0)}{1-A(1)}$

よって

$p'(2)=\frac{1-A(0)-A(1)}{1-A(1)}$ ・・・・(8)

「Ｍ／Ｇ／ｓ／ｎの定常状態のジョブ数分布について」で述べたことから

$p(0)=p'(0)[1-p(3)]$
$p(1)=p'(1)[1-p(3)]$
$p(2)=p'(2)\1-p(3)]$

なので、式(1)(7)(8)から

$p(0)=\frac{A(0)^2}{1-A(1)}[1-p(3)]$ ・・・・(9)
$p(1)=\frac{[1-A(0)]A(0)}{1-A(1)}[1-p(3)]$ ・・・・(10)
$p(2)=\frac{1-A(0)-A(1)}{1-A(1)}[1-p(3)]$ ・・・・(11)

が成り立ちます。ここで「Ｍ／Ｇ／１／ｎ待ち行列のp(0)とp(n)の関係」で述べたことから

$u[1-p(3)]=1-p(0)$ ・・・・(12)

が成り立ちます。式(12)から

$1-p(3)=\frac{1-p(0)}{u}$ ・・・・(13)

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

$p(0)=\frac{A(0)^2}{[1-A(1)]u}[1-p(0)]$
$[1-A(1)]up(0)=A(0)^2[1-p(0)]$
$\{[1-A(1)]u+A(0)^2\}p(0)=A(0)^2$
$p(0)=\frac{A(0)^2}{[1-A(1)]u+A(0)^2}$ ・・・・(14)

次に式(14)を(13)に代入して

$1-p(3)=\frac{1-\frac{A(0)^2}{[1-A(1)]u+A(0)^2}}{u}=\frac{[1-A(1)]u+A(0)^2-A(0)^2}{u\{[1-A(1)]u+A(0)^2\}}=\frac{[1-A(1)]u}{u\{[1-A(1)]u+A(0)^2\}}$
$1-p(3)=\frac{1-A(1)}{[1-A(1)]u+A(0)^2}$ ・・・・(15)

よって

$p(3)=1-\frac{1-A(1)}{[1-A(1)]u+A(0)^2}=\frac{[1-A(1)]u+A(0)^2-[1-A(1)]}{[1-A(1)]u+A(0)^2}$
$p(3)=\frac{-[1-A(1)](1-u)+A(0)^2}{[1-A(1)]u+A(0)^2}$ ・・・・(16)

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

$p(1)=\frac{[1-A(0)]A(0)}{1-A(1)}\times\frac{1-A(1)}{[1-A(1)]u+A(0)^2}$
$p(1)=\frac{[1-A(0)]A(0)}{[1-A(1)]u+A(0)^2}$ ・・・・(17)

式(15)を(11)に代入して

$p(2)=\frac{1-A(0)-A(1)}{1-A(1)}\times\frac{1-A(1)}{[1-A(1)]u+A(0)^2}$
$p(2)=\frac{1-A(0)-A(1)}{[1-A(1)]u+A(0)^2}$ ・・・・(18)

結局

$p(0)=\frac{A(0)^2}{[1-A(1)]u+A(0)^2}$ ・・・・(14)
$p(1)=\frac{[1-A(0)]A(0)}{[1-A(1)]u+A(0)^2}$ ・・・・(17)
$p(2)=\frac{1-A(0)-A(1)}{[1-A(1)]u+A(0)^2}$ ・・・・(18)
$p(3)=\frac{-[1-A(1)](1-u)+A(0)^2}{[1-A(1)]u+A(0)^2}$ ・・・・(16)

あとは $A(0)$ 、 $A(1)$ を求めることが出来れば $p(0)$ 、 $p(1)$ 、 $p(2)$ の値を求めることが出来ます。

「Ｍ／Ｇ／１の定常状態分布」の式(5)（ここでは番号を振り直して式(19)とします。）

$A(k)=\Bigint_0^{\infty}\frac{({\lambda}t)^k}{k!}\exp(-{\lambda}t)g(t)dt$ ・・・・(19)

ここで

$\lambda=\frac{1}{t_a}$

なので

$A(k)=\Bigint_0^{\infty}\frac{t^k}{t_a^kk!}\exp\left(-\frac{t}{t_a}\right)g(t)dt$ ・・・・(20)

となります。式(20)を用いて $A(0)$ 、 $A(1)$ を求め、それを式(14)(17)(18)(16)に代入することにより、Ｍ／Ｇ／１／３待ち行列の定常状態確率分布を求めることが出来ます。