Kingmanの近似式の根拠が明らかになるか？（２）

待ち行列理論

「Kingmanの近似式の根拠が明らかになるか？（１）」の続きです。


まず、「Page, E. S. (1972), Queueing Theory in OR」によれば、ＧＩ／Ｇ／ｍ待ち行列の平均待ち時間CT_qは、ジョブの到着間隔の変動係数c_aと装置処理時間の変動係数c_eが１より小さい場合には、Ｍ／Ｍ／ｍ、Ｍ／Ｄ／ｍ、Ｄ／Ｍ／ｍの平均待ち時間の一時結合

  • CT_q{\approx}c_a^2c_b^2CT_{q(M/M/m)}+c_a^2(1-c_b^2)CT_{q(M/D/m)}+c_b^2(1-c_a^2)CT_{q(D/M/m)}・・・・（２）

で近似出来るということです。ここで

  • CT_{q(M/M/m)}

は、今CT_qを求めようとしているＧＩ／Ｇ／ｍ待ち行列と同じ装置台数、同じ利用率を持つＭ／Ｍ／ｍ待ち行列における平均待ち時間を表します。同様に

  • CT_{q(M/D/m)}

はＭ／Ｄ／ｍの平均待ち時間

  • CT_{q(D/M/m)}

はＤ／Ｍ／ｍの平均待ち時間を表します。この式の正当性を私は完全に示すことは出来ませんが、部分的には示すことが出来ます。まず、式（２）をＭ／Ｍ／ｍの場合に適用すると、Ｍ／Ｍ／ｍの場合にはc_a=1、c_b=1なので、これらを式（２）に代入すると

  • CT_q{\approx}CT_{q(M/M/m)}

になるので、確かにＭ／Ｍ／ｍの場合は式（２）が成り立ちます。次にＭ／Ｄ／ｍの場合に適用すると、この場合はc_a=1、c_e=1なので、これらを式（２）に代入すると

  • CT_q{\approx}CT_{q(M/D/m)}

になります。やはりこの場合も式（２）が成り立っています。最後にＤ／Ｍ／ｍの場合に適用すると、この場合はc_a=0、c_e=1なので、式（２）は

  • CT_q{\approx}CT_{q(D/M/m)}

になって、成り立つことがわかります。
この３つが成り立つだけであれば別に式（２）の形とは限らず、たとえば

  • CT_q{\approx}c_ac_bCT_{q(M/M/m)}+c_a(1-c_b)CT_{q(M/D/m)}+c_b(1-c_a)CT_{q(D/M/m)}・・・・（２’）

でも

  • CT_q{\approx}c_a^3c_b^3CT_{q(M/M/m)}+c_a^3(1-c_b^3)CT_{q(M/D/m)}+c_b^3(1-c_a^3)CT_{q(D/M/m)}・・・・（２”）

でもかまわないのですが、式（２）になった理由は、「アーラン分布を使ったいくつかの例で確かめた（「待ち行列における近似モデル(特集 モデルの複雑さのへのアプローチ)」による）ということが根拠のようです。k次のアーラン分布の変動係数は

なので、いろいろな値の変動係数のアーラン分布が存在します。これらの分布を用いて計算あるいはシミュレーションをしたのでしょう。これは計算したのかもしれません。そう思う理由は、森雅夫氏・宮沢政清氏(1976)による「待ち行列システムの半順序関係」に以下の記事があり、これはＭ／Ｇ／ｍの場合ですが、同様のことがＧＩ／Ｇ／ｍの場合でもあり得ると推測するからです。

最近のTakahashi & Takami*1、*2の仕事があげられよう。彼らは、M/E_k/c型の状態確率をうまく集約して　Lumped Markov Chainとしてあつかいガウス・ザイデル法により効率よく計算する方法を案出し数多くの計算を実施している。さらにこの多量の結果を整理し、M/E_k/cの平均および分散がM/D/cとM/M/cのそれらの値の簡単な線形結合で近似されることを見いだしている。いわば、膨大なデータから１つの実験式を与えているのだが、その誤差はきわめて小さい。

文中のE_kとはk次のアーラン分布を意味します。


以上のように私にとって式（２）の根拠付けは未解決の問題ですが、ここではこれを認めて次に行きます。
次の問題は、Ｍ／Ｄ／ｍとＤ／Ｍ／ｍの平均待ち時間をどのように近似するかです。これは

  • CT_{q(D/M/m)}{\approx}\frac{1}{2}CT_{q(M/M/m)}・・・・（３）
  • CT_{q(M/D/m)}{\approx}\frac{1}{2}CT_{q(M/M/m)}・・・・（４）

と近似出来るそうです。（４）については「リー・ロントンの近似式」

  • CT_{q(M/G/m)}{\approx}\frac{1+c_e^2}{2}CT_{q(M/M/m)}・・・・（５）

を用いて導くことが出来ます。すなわち処理時間の分布がＤ（＝一定時間）なのでc_e=0。これを（５）に代入すれば（４）になります。しかし、私はまだリー・ロントンの近似式の正当化も出来ていません。ここではこの近似式を認めて進みます。（３）についても私は正当化出来ていません。しかし（３）（４）を認めてこれを（２）に代入すると

  • CT_q{\approx}c_a^2c_b^2CT_{q(M/M/m)}+c_a^2(1-c_b^2)\frac{1}{2}CT_{q(M/M/m)}+c_b^2(1-c_a^2)\frac{1}{2}CT_{q(M/M/m)}
    • =\frac{1}{2}[2c_a^2c_b^2+c_a^2(1-c_b^2)+c_b^2(1-c_a^2)]CT_{q(M/M/m)}
    • =\frac{1}{2}[2c_a^2c_b^2+c_a^2-c_a^2c_b^2+c_b^2-c_a^2c_b^2]CT_{q(M/M/m)}
    • =\frac{c_a^2+c_b^2}{2}CT_{q(M/M/m)}

よって

  • CT_q{\approx}\frac{c_a^2+c_b^2}{2}CT_{q(M/M/m)}・・・・（１）

を導くことが出来ます。


しかし、本当に根拠をしっかりと示すことが出来るようになるにはまだまだ勉強しなければならないことがありそうです。「Kingmanの近似式の根拠が明らかになるか？（３）」に続きます。

*1:Takahashi, Y. and Takami, Y., A Numerical Method for the Steady-State Probabilities of a GI/G/c Queueing System in a General Class, J. Opns, Res, Soc. Japan, (to appera in 1976).

*2:高橋、（私信）.