Kingmanの近似式の根拠が明らかになるか?(1)

G/G/m待ち行列の平均待ち時間を与える近似式

  • CT_q\appro\left(\frac{c_a^2+c_e^2}{2}\right)CT_{q(M/M/m)}・・・・(1)
    • ただし
    • CT_q:キューでの待ち時間
    • c_aジョブの到着間隔の変動係数。(変動係数とは、標準偏差/平均 のこと)
    • c_e:装置処理時間の変動係数
    • CT_{q(M/M/m)}:M/M/mにおけるキューでの待ち時間
    • m:装置台数

の根拠を知ることはここ2年、私の懸案事項の一つでありましたが、ようやくネット上でそれに関する有望そうな情報を得ました。逆瀬川浩孝氏による「待ち行列における近似モデル(特集 モデルの複雑さのへのアプローチ)」のpdf版のp.5の終わりからp.6にかけての部分です。その部分を引用します。

M/M/sD/M/sM/D/sE_k/E_l/sのように計算のできるモデルで値を求め、それらの結果から、もっと複雑なモデルの特性量の期待値を予測しようとするデータ解析的なアプローチの仕方がある。・・・・・
 一般の複数窓口モデルGI/G/sのうち、到着分布もサービス分布も、その変動係数が1よりも小さい場合には、M/M/sM/D/sD/M/sの平均待ち時間の1次結合として近似的に、

  • EW_{(GI/G/s)}{\approx}c_a^2c_b^2EW_{M/M/s}+c_a^2(1-c_b^2)EW_{M/D/s}+c_b^2(1-c_a^2)EW_{D/M/s}・・・・(5)

で与えられるようだ、ということがアーラン分布を使ったいくつかの例で確かめられている*1

ここでc_bとあるのは上でのc_eと同じ意味です。

 一方、M/M/sの平衡解は解析的に求まっており、平均行列長は分布のパラメータと窓口の数sとの関数で与えられているが階乗を含む面倒な式になっている。これを

  • EL_{q(M/M/s)}{\approx}\frac{\rho^{sqrt{2(s+1)}}}{1-\rho}

・・・・・・
という簡単な式におきかえても、比較的精度よく近似できることが確かめられている。

これは逆瀬川の近似式です。これについては「逆瀬川の近似式の精度」で扱いました。ただしここで登場するのは平均行列長L_qについての式ではなく平均待ち時間CT_qについての式です。リトルの法則を用いれば、互いに他の式に変換することが出来ます。

近似式というのは、最終的な結果を出すのが目的ではなく、大雑把な比較のために用いられるのだから、あまり高い精度は要求されないだろう、ということから、この式と(5)式および

  • EW_{(D/M/s)},EW_{(M/D/s)}{\approx}\frac{1}{2}EW_{(M/M/s)}・・・・(6)

とから、次の近似式が導かれる。

  • EL_{q(GI/G/s)}{\approx}\frac{c_a^2+c_b^2}{2}\frac{\rho^{sqrt{2(s+1)}}}{1-\rho}

これは(6)式を使った影響で、ほとんどの範囲で過大評価を与えるが、実用的にみて許容範囲にあることが数値的に確かめられている*2

これでだいたい大筋は明らかになっていますが、今まで私が用いてきた記号を用いて式(1)の根拠付けを行います。


Kingmanの近似式の根拠が明らかになるか?(2)」に続きます。

*1:Page, E. S. (1972), Queueing Theory in OR

*2:Sakasegawa, H.(1977), An approximation formula L_q{\approx}\alpha{\cdot}\rho^\beta/(1-\rho)、Annals ISM, 29.1, 67-75.