Ｍ／Ｇ／ｍの待ちジョブ数と待ち時間

待ち行列理論

Ｍ／Ｇ／ｍ待ち行列の待ち行列にk個のジョブがある定常状態確率をq(k)で表すことにします。ジョブが処理開始する（つまり待ち行列から抜ける）時点での残りの待ち行列内ジョブ数は、このジョブが到着してから到着したジョブ数に等しいです（ＦＩＦＯなので）。
ジョブの待ち時間の確率変数をWとします。するとこのジョブが処理開始する時に待ち行列内にあるジョブはWの間に到着したことになります。Wの確率密度関数をw(t)とします。時間tの間にジョブがk個到着する確率はポアソン分布の式（「ポアソン分布」参照）

  • p(k,t)=\frac{({\lambda}t)^k}{k!}\exp(-{\lambda}t)・・・・(17)

なので、ジョブ処理開始時に待ち行列にk個のジョブがある確率は

  • \Bigint_0^{\infty}\frac{({\lambda}t)^k}{k!}\exp(-{\lambda}t)w(t)dt・・・・(1)

で計算出来ます。ところで「Ｍ／Ｇ／ｓの定常状態の待ちジョブ数分布について」によれば処理開始時の待ちジョブ数の分布は時間平均で見た待ちジョブ数の分布に等しいのでした。よって

  • q(k)=\Bigint_0^{\infty}\frac{({\lambda}t)^k}{k!}\exp(-{\lambda}t)w(t)dt・・・・(2)

となります。ここでq(k)の確率母関数Q^*(z)を考えます。つまり

  • Q^*(z)=\Bigsum_{k=0}^{\infty}q(k)z^k・・・・(3)

です。式(3)に式(2)を代入すると

  • Q^*(z)=\Bigsum_{k=0}^{\infty}\left[\Bigint_0^{\infty}\frac{({\lambda}t)^k}{k!}\exp(-{\lambda}t)w(t)dtz^k\right]
    • =\Bigint_0^{\infty}\exp(-{\lambda}t)w(t)\Bigsum_{k=0}^{\infty}\frac{({\lambda}t)^k}{k!}z^kdt
    • =\Bigint_0^{\infty}\exp(-{\lambda}t)w(t)\Bigsum_{k=0}^{\infty}\frac{({\lambda}zt)^k}{k!}dt
    • =\Bigint_0^{\infty}\exp(-{\lambda}t)w(t)\exp({\lambda}zt)dt

よって

  • Q^*(z)=\Bigint_0^{\infty}\exp(-({\lambda}-{\lambda}z)t)w(t)dt・・・・(4)

となります。ところでw(t)のラプラス変換をW^*(s)で表すと

  • W^*(s)=\Bigint_0^{\infty}\exp(-st)w(t)dt・・・・(5)

ですから、式(4)は

  • Q^*(z)=W^*({\lambda}-{\lambda}z)・・・・(6)

と書けます。式(6)の両辺をzで微分すると

  • Q^{*(1)}(z)=-\lambda{W}^{*(1)}({\lambda}-{\lambda}z)・・・・(7)

式(7)の両辺をさらにzで微分すると

  • Q^{*(2)}(z)=\lambda^2W^{*(2)}({\lambda}-{\lambda}z)・・・・(8)

式(8)でz=1と置くと

  • Q^{*(2)}(1)=\lambda^2W^{*(2)}(0)・・・・(9)

「確率密度関数のラプラス変換」の式(3)から

  • W^{*(2)}(0)=E(W^2)・・・・(10)

一方、式(3)の両辺をzで微分すると

  • Q^{*(1)}(z)=\Bigsum_{k=1}^{\infty}kq(k)z^{k-1}・・・・(11)

式(11)の両辺をさらにzで微分すると

  • Q^{*(2)}(z)=\Bigsum_{k=2}^{\infty}k(k-1)q(k)z^{k-1}・・・・(12)

式(12)でz=1とすると

  • Q^{*(2)}(1)=\Bigsum_{k=2}^{\infty}k(k-1)q(k)=\Bigsum_{k=0}^{\infty}k(k-1)q(k)

よって

  • Q^{*(2)}(1)=E(Q(Q-1))・・・・(13)

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

  • E(Q(Q-1))=\lambda^2E(W^2)

よって

  • E(Q^2)-E(Q)=\lambda^2E(W^2)・・・・(14)

となります。これで、「Whitt教授の「Approxomations for the GI/G/m queue」の翻訳（３２） 」に登場する公式(4.2)

  • E(Q^2)-EQ=\lambda^2E(W^2)・・・・(5.5)

を証明することが出来ました。