Ｍ／Ｍ／ｓ待ち行列の待ち時間分布 - 工場統計力学（建設中！）

「待ち時間制約（３）」の続きです。「待ち時間制約（２）」でＭ／Ｍ／１について行った考察をそのままＭ／Ｍ／ｓに拡張していきましょう。
ジョブがＭ／Ｍ／１待ち行列システムに到着した時、システム内にこのジョブを含めなくて $k$ 個のジョブがある確率（ただし $k{\ge}s$ とします）は、「Ｍ／Ｍ／ｓ待ち行列の特性」から

$p(k)=u^{k-s}(1-u)\Pi$ ・・・・(1)

です。[tex:k $k{\ge}s$ の場合について考察します。この場合、 $k$ 個のジョブのうち $s$ 個は処理中であり、残りの $k-s$ 個のジョブは装置が空くのを待っている状態です。 $s$ 台の装置のうちどれか１台が処理終了になるまでの時間は、処理時間の分布が指数分布なので、指数分布のにより、任意の時点から測っても同一の分布を持ちます。１台の装置が任意の $dt$ の間に処理終了する確率は

$\frac{dt}{t_e}$ ・・・・(2)

なので、 $s$ 台の装置のうちどれかが任意の $dt$ の間に処理終了する確率は

$\frac{sdt}{t_e}$ ・・・・(3)

このことから、 $s$ 台の装置のうちどれか１台が処理終了になるまでの時間 $T$ の分布は

$\frac{t_e}{s}\exp\left(-\frac{s}{t_e}t\right)$ ・・・・(4)

になります。つまり、平均時間

$frac{t_e}{s}$ ・・・・(5)

の指数分布になります。現在（先ほどのジョブが到着した時点）から、その時点で待っている $k-s$ 個のジョブのうち先頭のジョブが処理開始するまでの時間は平均 $t_e/s$ の指数分布を持ちます。次に、２番目のジョブが待つ時間も指数分布の記憶なし特性によりやはり平均 $t_e/s$ の指数分布を持つことになります。結局、到着したジョブの前に並んで待っている $k-s$ 個のジョブが全て処理開始するまでの時間は、平均 $t_e/s$ の指数分布を持つ確率変数の $k-s$ 個の和で表されることになります。まだ、この状態では到着したジョブの待ち時間は終わっていません。到着したジョブが待ち時間を終了するためには、つまり、処理を開始するためには、さらに平均 $t_e/s$ の指数分布を持つ時間だけ待たなければなりません。結局のところ、平均 $t_e/s$ の指数分布を持つ $k-s+1$ 個の確率変数の和がジョブの待ち時間になります。
ところで、「アーラン分布」の「アーラン分布は指数分布の和」のセクションで述べたように、平均 $1/\lambda$ の $k$ 個の指数分布の和はアーラン分布

$\frac{\lambda^kt^{k-1}}{(k-1)!}\exp(-\lambda{t})$ ・・・・(6)

となります。よって、ジョブが到着した時にシステム内に自分を含めなくて $k$ 個のジョブがある場合（ただし $k{\ge}s$ とします）の、到着したジョブが待つ時間の分布を $f(t;k)$ とすると、

$f(t;k)=\left(\frac{s}{t_e}\right)^{k-s+1}\frac{t^{k-s}}{(k-s)!}\exp\left(-\frac{st}{t_e}\right)$ ・・・・(7)

となります。到着時にシステム内に $k$ 個のジョブが存在する確率は式(1)で与えられるので、ジョブの待ち時間の確率分布 $f_q(t)$ は

- $=(1-u)\Pi\exp\left(-\frac{st}{t_e}\right)\Bigsum_{k=s}^{\infty}\left(\frac{s}{t_e}\right)^{k-s+1}\frac{t^{k-s}}{(k-s)!}u^{k-s}=(1-u)\exp\left(-\frac{st}{t_e}\right)\frac{s\Pi}{t_e}\Bigsum_{k=s}^{\infty}\frac{1}{(k-s)!}\left(\frac{ust}{t_e}\right)^{k-s}$
- $=(1-u)\exp\left(-\frac{st}{t_e}\right)\frac{s\Pi}{t_e}\Bigsum_{k=0}^{\infty}\frac{1}{k!}\left(\frac{ust}{t_e}\right)^k$
- $=\frac{(1-u)s\Pi}{t_e}\exp\left(-\frac{st}{t_e}\right)\exp\left(\frac{ust}{t_e}\right)=\frac{(1-u)s\Pi}{t_e}\exp\left(-\frac{(1-u)st}{t_e}\right)$

よって $k{\ge}s$ の場合

$f_q(t)=\frac{(1-u)s\Pi}{t_e}\exp\left(-\frac{(1-u)st}{t_e}\right)$ ・・・・(7)

となります。[tex:k $k<s$ になる確率は $1-\pi$ なのでジョブの待ち時間の分布は、待ち時間ゼロの時の」」が $1-\Pi$ 、待ち時間がゼロより大きい場合の確率密度が式(7)で与えられる、ということになります。

上の確率分布を累積確率分布の形で表してみましょう。累積確率分布を $F_q(t)$ で表すことにします。 $t$ の最低値は0であり、 $t=0$ である確率が $1-\Pi$ なので

$F_q(0)=1-\Pi$ ・・・・(8)

です。 $t>0$ の時の $F_q(t)$ については

$F_q(t)=F_q(0)+\Bigint_0^{t}f_q(\tau)d\tau$ ・・・・(9)

を計算することで求めることが出来ます。式(9)の右辺の第２項は

- $=\frac{(1-u)s\Pi}{t_e}\frac{-t_e}{(1-u)s}\left[\exp\left(-\frac{(1-u)s\tau}{t_e}\right)\right]_0^t=-\Pi\left[\exp\left(-\frac{(1-u)s\tau}{t_e}\right)\right]_0^t$
- $=\Pi\left[1-\exp\left(-\frac{(1-u)st}{t_e}\right)\right]$