QNA読解：4.5 出発（１）

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

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


「QNA読解：4.4 分岐」の続きです。
正直に言いましてこのセクションも私はあまり理解出来ていません。


セクションの目的と結論は明白です。目的はノードから出て行くジョブの出発間隔の２乗変動係数c_d^2を求めることです。

そして結論は以下の近似式です。

	c_d^2=1+(1-\rho^2)(c_a^2-1)+\frac{\rho^2}{\sqrt{m}}(max\{c_s^2, 0.2\}-1)	(42)

ここに


上記式(42)を導出するためにまず論文はGI/G/1待ち行列についてのMarshallの公式というものを持ち出してきています。

　単一サーバ・ノードの定常間隔法について、我々はGI/G/1待ち行列*1 *2における出発間隔時間の２乗変動係数、つまりc_d^2、についてMarshallの公式

	c_d^2=c_a^2+2\rho^2c_s^2-2\rho(1-\rho){\mu}EW		(37)

を適用する。ただしEWは平均待ち時間である。

このMarshallの公式は「近似式」とは書かれていませんからどうやら厳密に成り立つ式のようです。なお、\muは処理時間\tauの逆数です。つまり

  • \mu=\frac{1}{\tau}

さて、この式の導出の仕方ですが、この論文には書かれていません。どうも

  • K. T. Marshall,「待ち行列におけるいくつかの不等式」Oper. Res., 16, No. 3 (May-June 1968), pp. 651-65.

を読まないといけないようです。
この式(37)のEWに、EWの近似式（これは、「Word Whitt: The Queueing Network Analyzer（１３）」で登場する式(44)です。）

  • EW=\tau\rho(c_a^2+c_s^2)g/2(1-\rho)・・・・（ア）

を代入します。すると\mu=1/\tauに注意して

  • c_d^2=c_a^2+2\rho^2c_s^2-\rho^2(c_a^2+c_s^2)g・・・・（イ）

ここでWhittは、他の論文で述べてある考察から

  • g=1

とおいても近似として十分であるとしています。

（イ）は

  • c_d^2=c_a^2+2\rho^2c_s^2-\rho^2(c_a^2+c_s^2)
  • c_d^2=\rho^2c_s^2+(1-\rho^2)c_a^2・・・・(38)

となります。これはGI/G/1のための式です。これをGI/G/m待ち行列に拡張するのに、この論文では次の式を提案しています。論文では

QNAの現在のバージョンで使用されているGI/G/m待ち行列のための(38)の単純な拡張は

と書かれていますが、私はこれがどうして単純な拡張なのかよく分かりません。拡張された式は

  • c_d^2=1+(1-\rho^2)(c_a^2-1)+\frac{\rho^2}{\sqrt{m}}(c_s^2-1)・・・・(39)

です。確かにm=1を(39)に代入すれば、式(38)に一致します。しかし、それだけでは式(39)の形を決める理由にはなりません。GI/G/mの出発過程の２乗変動係数の近似式に要請される条件の１つにM/M/m待ち行列の出発過程の２乗変動係数は１である（つまりポアソン到着の指数処理時間の待ち行列の出発過程はポアソン分布になる）というものがあります。
確かに式(39)で

  • c_a^2=1
  • c_s^2=1

を代入すると

  • c_d^2=1

になります。しかし、だからといって式(38)から式(39)が思いつく、というのは飛躍だと思います。
もうひとつ、M/G/\infty待ち行列の場合も

  • c_d^2=1

になるという条件があるそうです。式(39)はこの条件も満たしていることは簡単に確かめられます。とはいえ、どのようにして式(39)を得たのか、私には分かりません。上の２つの条件を満たすのであれば、たとえば

  • c_d^2=1+(1-\rho^2)(c_a^2-1)+\frac{\rho^2}{m}(c_s^2-1)

でも

  • c_d^2=1+(1-\rho^2)(c_a^2-1)+\frac{\rho^2}{m^2}(c_s^2-1)

でもよいわけです。式(39)でなければならない理由が分かりません。ヒントになりそうなのは論文の

(39)の３番目の項はmが増加するにつれて０に近づき、複数サーバが重ね合わせオペレーションのように振舞う傾向を反映している。

ですが、今の私にはここから(39)の理由を見つけるには到っていません。


論文は式(39)を提示したあと、この式は処理時間が確定的な場合、つまり

  • c_s^2=0

の場合

  • c_d^2

を過少に見積る傾向がある、と述べて、最終的に

  • c_d^2=1+(1-\rho^2)(c_a^2-1)+\frac{\rho^2}{\sqrt{m}}(max\{c_s^2, 0.2\}-1)・・・・(42)

を提案しています。


「QNA読解：4.5 出発（２）」に続きます。

*1:K. T. Marshall,「待ち行列におけるいくつかの不等式」Oper. Res., 16, No. 3 (May-June 1968), pp. 651-65.

*2:W. Whitt,「出発過程の近似と直列になった待ち行列」Nav. Res. Log Qtr., to be published.