QNA読解：5.1 GI/G/1待ち行列（３）

待ち行列ネットワークへの助走

上位エントリー：Word Whitt: The Queueing Network Analyzerの構成


「QNA読解：5.1 GI/G/1待ち行列（２）」の続きです。
今回はD（つまりW=0の場合を除いたW）の２乗変動係数c_D^2の近似について論文を読解していきます。Dを持ち出してきた理由は、DはWよりも処理時間分布の依存が強い（到着間隔時間分布への依存が弱い）という事実があるからということです。残念ながら今の私はそれを示すことが出来ません。そしてc_D^2をまず求め、次にそれを用いてc_W^2を求めようとするのがこの論文の戦略です。c_D^2を求めるには、M/G/1におけるc_D^2の以下の式を利用しています。

  • c_D^2=2\rho-1+4(1-\rho)d_s^3/3(c_s^2+1)^2・・・・(50)
  • ただし
    • d_s^3=E(v^3)/(Ev)^3
  • でvは処理時間を表す確率変数です。

これがGI/G/1の時も近似的に成り立つかどうかは検討の余地があります。しかし、この論文ではそこを説明していません。さて、今度は

  • d_s^3

を求める必要があります。処理時間分布はさまざまである可能性がありますが、ここでは

  • c_s^2{\ge}1の場合（ケース１）は処理時間分布として超指数分布を
  • c_s^2<1の場合（ケース２）は処理時間分布としてアーラン分布を

代表させてd_s^3を求めています。はたして、一般的な分布をこのように特殊な分布で代表させてよいものかどうか疑問が残るところです。

ケース１：c_s^2{\ge}1の場合

処理時間の分布として「バランスのとれた平均を持つ超指数分布」H_2^bを仮定します。この分布の確率密度関数は

  • f(t)=q\gamma_1\exp(-\gamma_1t)+(1-q)\gamma_2\exp(-\gamma_2t)、t{\ge}0・・・・（ア）
  • ただし
    • q=\left[1+\sqrt{(c_s^2-1)/(c_s^2+1)}\right]/2・・・・（イ）
    • \gamma_1=2q/Ev・・・・（ウ）
    • \gamma_2=2(1-q)/Ev・・・・（エ）

です。この（イ）（ウ）（エ）の導出については「バランスのとれた平均を持つ超指数分布」を参照して下さい。

  • ところで論文では（イ）の代わりに以下の式
    • q=\left[1+\sqrt{4(c_s^2-1)/(c_s^2+1)}\right]/2
  • が登場していますが、これは誤植でしょう。

（ア）を用いてd_s^3を求めます。まず、E(v^3)を求めます。

  • E(v^3)=\Bigint_0^{\infty}t^3f(t)dt=q\Bigint_0^{\infty}t^3\gamma_1\exp(-\gamma_1t)dt+(1-q)\Bigint_0^{\infty}t^3\gamma_2\exp(-\gamma_2t)dt

ここで、「アーラン分布」の式(4)

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

を用いれば

  • E(v^3)=q\gamma_1\frac{3!}{\gamma_1^4}+(1-q)\gamma_2\frac{3!}{\gamma_2^4}
  • E(v^3)=q\frac{6}{\gamma_1^3}+(1-q)\frac{6}{\gamma_2^3}

この式に（ウ）（エ）を代入すると

  • E(v^3)=q\frac{6(Ev)^3}{8q^3}+(1-q)\frac{6(Ev)^3}{8(1-q)^3}=\frac{3}{4}(Ev)^3\left[\frac{1}{q^2}+\frac{1}{(1-q)^2}\right]

よって

  • d_s^3=E(v^3)/(Ev)^3=\frac{3}{4}\left[\frac{1}{q^2}+\frac{1}{(1-q)^2}\right]
  • d_s^3=\frac{3}{4}\left[\frac{1}{q^2}+\frac{1}{(1-q)^2}\right]・・・・（オ）

（イ）から

  • q=\frac{sqrt{c_s^2+1}+\sqrt{c_s^2-1}}{2sqrt{c_s^2+1}}
  • q^2=\frac{c_s^2+1+2sqrt{(c_s^2+1)(c_s^2-1)}+c_s^2-1}{4(c_s^2+1)}=\frac{2c_s^2+2sqrt{c_s^4-1}}{4(c_s^2+1)}=\frac{c_s^2+sqrt{c_s^4-1}}{2(c_s^2+1)}
  • \frac{1}{q^2}=\frac{2(c_s^2+1)}{c_s^2+sqrt{c_s^4-1}}・・・・（カ）

同じく（イ）から

  • 1-q=1-\frac{sqrt{c_s^2+1}+\sqrt{c_s^2-1}}{2sqrt{c_s^2+1}}=\frac{2sqrt{c_s^2+1}-sqrt{c_s^2+1}-\sqrt{c_s^2-1}}{2sqrt{c_s^2+1}}=\frac{sqrt{c_s^2+1}-\sqrt{c_s^2-1}}{2sqrt{c_s^2+1}}
  • q^2=\frac{c_s^2+1-2sqrt{(c_s^2+1)(c_s^2-1)}+c_s^2-1}{4(c_s^2+1)}=\frac{2c_s^2-2sqrt{c_s^4-1}}{4(c_s^2+1)}=\frac{c_s^2-sqrt{c_s^4-1}}{2(c_s^2+1)}
  • \frac{1}{(1-q)^2}=\frac{2(c_s^2+1)}{c_s^2-sqrt{c_s^4-1}}・・・・（キ）

（オ）に（カ）と（キ）を代入して

  • d_s^3=\frac{3}{4}\left[\frac{2(c_s^2+1)}{c_s^2+sqrt{c_s^4-1}}+\frac{2(c_s^2+1)}{c_s^2-sqrt{c_s^4-1}}\right]=\frac{3(c_s^2+1)}{2}\left[\frac{1}{c_s^2+sqrt{c_s^4-1}}+\frac{1}{c_s^2-sqrt{c_s^4-1}}\right]
    • =\frac{3(c_s^2+1)}{2}\left[\frac{c_s^2-sqrt{c_s^4-1}+c_s^2+sqrt{c_s^4-1}}{c_s^4-(c_s^4-1)}\right]=\frac{3(c_s^2+1)}{2}(2c_s^2)=3c_s^2(c_s^2+1)

よって

  • d_s^3=3c_s^2(1+c_s^2)・・・・(51)

が求まります。


「QNA読解：5.1 GI/G/1待ち行列（４）」に続きます。