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

「待ち時間制約（２）」にならって、今度はＭ／Ｄ／１待ち行列におけるジョブの待ち時間分布を求めてみます。さて、ジョブがＭ／Ｄ／１待ち行列システムに到着した時、システム内にこのジョブを含めなくて $k$ 個のジョブがある確率は、「Ｍ／Ｄ／１の定常状態分布の近似式」の式(1)(40)から近似的に

$p(0)=1-u$ ・・・・(1)
の時
- $p(k){\approx}2(1-u)\left(\frac{u}{2-u}\right)^k$ ・・・・(2)

です。今、到着したジョブは $k$ 個のジョブが処理終了するのを待つことになります。 $k=0$ の場合も存在します。 $k{\ge}1$ の場合、 $k$ 個のジョブのうち１個は処理中であり、残りの $k-1$ 個のジョブは装置が空くのを待っている状態です。待っている $k-1$ 個のジョブは固定の時間 $t_e$ で装置で処理されるので、これらのジョブが全て処理される時間は固定値の $(k-1)t_e$ になります。さらに処理中のジョブの残り処理時間の分布について言えば、PASTAによって、到着したジョブは0から $t_e$ までの処理時間を均等な確率で見ることになります。よって、これは $(0,t_e]$ の一様分布になります。よって、待ち時間が $((k-1)t_e,kt_e]$ の範囲である場合の確率密度は一様分布になり、その積分が式(2)で与えられることになります。よって、ジョブの待ち時間の確率分布を $f_q(t)$ で表すと

- $f_q(t){\approx}\frac{2(1-u)}{t_e}\left(\frac{u}{2-u}\right)^k$ ・・・・(3)
- ただし
  - $k=ceil\left(\frac{t}{t_e}\right)$ ・・・・(4)

です。ここに $ceil(a)$ は天井関数で、 $a$ 以上の最小の整数を表します。

$k=0$ の場合は、装置は空いていますから、到着ジョブの待ち時間はゼロです。 $k=0$ になる確率は $1-u$ なのでジョブの待ち時間の分布は、待ち時間ゼロの時の確率が $1-u$ 、待ち時間がゼロより大きい場合の確率密度が式(3)で与えられる、ということになります。

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

$F_q(0)=1-u$ ・・・・(5)

です。一般の $t$ の時の $F_q(t)$ については

$F_q(t)=F_q(0)+\Bigint_0^{t}f_q(s)ds$ ・・・・(6)

を計算することで求めることが出来ます。ここからは図を描くと直感的に分かるのですが、積分の結果

$F_q(t){\approx}1-u+2(1-u)\Bigsum_{n=1}^{k-1}\left(\frac{u}{2-u}\right)^n+\frac{t-(k-1)t_e}{t_e}{\times}2(1-u)\left(\frac{u}{2-u}\right)^k$ ・・・・(7)

となります。式(7)の第２項は「よく使う式」の最初の式を利用すれば

- $=2(1-u)u\frac{1-\left(\frac{u}{2-u}\right)^{k-1}}{2-u-u}=2(1-u)u\frac{1-\left(\frac{u}{2-u}\right)^{k-1}}{2-2u}$
- $=u\left[1-\left(\frac{u}{2-u}\right)^{k-1}\right]$

なので式(7)は

- $=1-u+u-u\left(\frac{u}{2-u}\right)^{k-1}+2(1-u)\left(\frac{u}{2-u}\right)^k\left(\frac{t-(k-1)t_e}{t_e}\right)$
- $=1-u\left(\frac{u}{2-u}\right)^{k-1}+2(1-u)\left(\frac{u}{2-u}\right)^k\left(\frac{t-(k-1)t_e}{t_e}\right)$

よって

$F_q(t){\approx}1-u\left(\frac{u}{2-u}\right)^{k-1}+2(1-u)\left(\frac{u}{2-u}\right)^k\left(\frac{t-(k-1)t_e}{t_e}\right)$ ・・・・(8)
ただし
- $k=ceil\left(\frac{t}{t_e}\right)$ ・・・・(4)

となります。