ＧＩ／Ｍ／１待ち行列の待ち時間分布

待ち行列理論

「Ｍ／Ｇ／１待ち行列の待ち時間分布の近似（２）」の続きです。今度はＧＩ／Ｍ／１待ち行列の待ち時間分布を求めてみます。これは「待ち時間制約（２）」で展開した考察をなぞっていきます。


さて、ジョブがＧＩ／Ｍ／１待ち行列システムに到着した時、システム内にこのジョブを含めなくてk個のジョブがある確率\pi(k)は、「ＧＩ／Ｍ／１待ち行列の特性」の式（ここでは番号を振って式(1)とします）

  • \pi(k)=(1-b)b^k・・・・(1)
  • ただしbは
    • b=\Bigint_0^{\infty}\exp\left(-\frac{(1-b)t}{t_e}\right)g(t)dt・・・・(2)
    • ただしg(t)は到着間隔の確率密度関数。t_eは装置の処理時間の平均。
  • を満たすもの

で求めることが出来ます。今、到着したジョブはk個のジョブが処理終了するのを待つことになります。k=0の場合も存在します。k{\ge}1の場合、k個のジョブのうち１個は処理中であり、残りのk-1個のジョブは装置が空くのを待っている状態です。待っているk-1個のジョブは平均時間t_eの指数分布で装置で処理されるので、これらのジョブが全て処理される時間は、k-1個の同一分布の指数分布を持つ確率変数を足し合わせた確率変数になります。さらに処理中のジョブの残り処理時間の分布について言えば、指数分布の記憶なし特性のために、やはり平均時間t_eの指数分布になります。よって、到着したジョブの待ち時間時間はk個の平均時間t_eの指数分布を持つ確率変数和になります。
「アーラン分布」の「アーラン分布は指数分布の和」のセクションで述べたように、平均1/\lambdaのk個の指数分布の和はアーラン分布

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

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

  • f(t;k)=\frac{1}{t_e^k}\frac{t^{k-1}}{(k-1)!}\exp\left(-\frac{t}{t_e}\right)・・・・(4)

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

  • f_q(t)=\Bigsum_{k=1}^{\infty}f(t;k)b^k(1-b)=\Bigsum_{k=1}^{\infty}\frac{1}{t_e^k}\frac{t^{k-1}}{(k-1)!}\exp\left(-\frac{t}{t_e}\right)b^k(1-b)
    • =(1-b)\exp\left(-\frac{t}{t_e}\right)\Bigsum_{k=1}^{\infty}\frac{1}{t_e^k}\frac{t^{k-1}}{(k-1)!}b^k=(1-b)\exp\left(-\frac{t}{t_e}\right)\frac{b}{t_e}\Bigsum_{k=1}^{\infty}\frac{1}{(k-1)!}\left(\frac{bt}{t_e}\right)^{k-1}
    • =(1-b)\exp\left(-\frac{t}{t_e}\right)\frac{b}{t_e}\Bigsum_{k=0}^{\infty}\frac{1}{k!}\left(\frac{bt}{t_e}\right)^k
    • =\frac{(1-b)b}{t_e}\exp\left(-\frac{t}{t_e}\right)\exp\left(\frac{bt}{t_e}\right)=\frac{(1-b)b}{t_e}\exp\left(-\frac{(1-b)t}{t_e}\right)

よってk{\ge}1の場合

  • f_q(t)=\frac{(1-b)b}{t_e}\exp\left(-\frac{(1-b)t}{t_e}\right)・・・・(5)

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


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

  • F_q(0)=1-b・・・・(6)

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

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

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

  • \Bigint_0^{t}f_q(s)ds=\frac{(1-b)b}{t_e}\Bigint_0^t\exp\left(-\frac{(1-b)s}{t_e}\right)ds
    • =\left(\frac{(1-b)b}{t_e}\right)\left(\frac{-t_e}{1-b}\right)\left[\exp\left(-\frac{(1-b)s}{t_e}\right)\right]_0^t=-b\left[\exp\left(-\frac{(1-b)s}{t_e}\right)\right]_0^t
    • =b\left[1-\exp\left(-\frac{(1-b)t}{t_e}\right)\right]

となりますので、これを式(7)に代入すると

  • F_q(t)=F_q(0)+b\left[1-\exp\left(-\frac{(1-b)t}{t_e}\right)\right]

これに式(6)を代入すると

  • F_q(t)=1-b+b\left[1-\exp\left(-\frac{(1-b)t}{t_e}\right)\right]

よって

  • F_q(t)=1-b\exp\left(-\frac{(1-b)t}{t_e}\right)・・・・(8)

式(8)から、F_q(0)=1-bであること、t\rightar{\infty}でF_q(t)\rightar{1}になることを確かめることが出来ます。式(8)はＭ／Ｇ／１の場合（「[Ｍ／Ｇ／１待ち行列の待ち時間分布の近似（１）]」の式(4)参照）と異なり

  • F_q(t){\approx}1-u\exp\left(-\frac{at}{t_e}\right)・・・・(9)

という形になっていないことに注意しましょう。
また、「ＧＩ／Ｍ／１待ち行列の特性」にあるようにbについては式(2)を計算しなくても、近似的には

  • b{\approx}\frac{(2c_a^2+[1-c_a^2]u)u}{2-(2-\{2c_a^2+[1-c_a^2]u\})u}

で求めることが出来ます。