Kingmanの近似式の導出

待ち行列理論

ＧＩ／Ｇ／１待ち行列の平均待ち時間を与えるKingmanの近似式

の根拠付けについて私が知っていることを以下に記します。

Pageによる大量の数値計算によってc_a{\le}1かつc_a{\le}1の時に、以下の近似式が成り立っていることが分かっています*1。

  • CT_{q(GI/G/s)}{\approx}c_a^2c_e^2CT_{q(M/M/s)}+c_a^2(1-c_e^2)CT_{q(M/D/s)}+c_e^2(1-c_a^2)CT_{q(D/M/s)}・・・・（２）
    • ただし
    • CT_{q(GI/G/s)：ＧＩ／Ｇ／ｓの待ち行列の平均待ち時間
    • CT_{q(M/M/s)：上のＧＩ／Ｇ／ｓと同じ利用率で同じ平均処理時間であるようなＭ／Ｍ／ｓの待ち行列の平均待ち時間
    • CT_{q(M/D/s)：上のＧＩ／Ｇ／ｓと同じ利用率で同じ平均処理時間であるようなＭ／Ｄ／ｓの待ち行列の平均待ち時間
    • CT_{q(D/M/s)：上のＧＩ／Ｇ／ｓと同じ利用率で同じ平均処理時間であるようなＤ／Ｍ／ｓの待ち行列の平均待ち時間


式（２）でs=1と置くと

  • CT_{q(GI/G/1)}{\approx}c_a^2c_e^2CT_{q(M/M/1)}+c_a^2(1-c_e^2)CT_{q(M/D/1)}+c_e^2(1-c_a^2)CT_{q(D/M/1)}・・・・（３）

ここでCT_{q(M/M/1)}は

であり、CT_{q(M/D/1)}は

です。CT_{q(D/M/1)}については「Ｄ／Ｍ／１における待ち時間の近似式」で示したグラフ

が表しているように

  • CT_{q(D/M/1)}{\approx}CT_{q(M/D/1)}・・・・（６）

と近似できます。式（４）（５）（６）を式（３）に代入すると

  • CT_{q(GI/G/1)}{\approx}c_a^2c_e^2\frac{u}{1-u}t_e+\frac{c_a^2(1-c_e^2)}{2}\frac{u}{1-u}t_e+\frac{c_e^2(1-c_a^2)}{2}\frac{u}{1-u}t_e
    • =\frac{2c_a^2c_e^2+c_a^2(1-c_e^2)+c_e^2(1-c_a^2)}{2}\frac{u}{1-u}t_e
    • =\frac{2c_a^2c_e^2+c_a^2-c_a^2c_e^2+c_e^2-c_a^2c_e^2}{2}\frac{u}{1-u}t_e
    • =\frac{c_a^2+c_e^2}{2}\frac{u}{1-u}t_e

よって

  • CT_{q(GI/G/1)}=\frac{c_a^2+c_e^2}{2}\frac{u}{1-u}t_e

となります。CT_{q(GI/G/1)}は式（１）におけるCT_qと同じ意味ですから、この式によって式（１）が証明されたことになります。

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