待ち行列システムGI/G/1における待ちについての近似公式（２）

「待ち行列システムGI/G/1における待ちについての近似公式（１）」の続きです。

1.2　記法

$T_A$ ＝要求の到着間隔時間

$T_W$ ＝要求の待ち時間（サービスを除く）

$T_H$ ＝要求のサービス時間

$T_F$ ＝要求の滞在時間（ $=T_W+T_H$ ）

$T_{IP}$ ＝空きの期間

$T_{BP}$ ＝稼働の期間

$T_D$ ＝要求の出発間隔時間

とする。さて、与えられたトラフィック $A$ は

$A=\frac{E(T_H)}{E(T_A)}=\lambda\cdot{E}(T_H)=\lambda\cdot{h}$ ・・・・(1.1)

であり、 $E(T_H)=h$ は平均サービス時間で $\lambda$ は要求の到着レートである。
ここで与えられた $A$ は、損失がないので（純粋な待ちシステムなので）サーバの稼働率と同一である。キューの方針はサービス時間と独立である限り、任意である。
到着間隔とサービスの時間の分布関数は $F_A(t)$ と $F_H(t)$ で、対応する変動係数は

$c_A=\sqrt{Var(T_A)}/E(T_A)$ 、 $c_H=\sqrt{Var(T_H)}/E(T_H)$ ・・・・(1.2)

である。

1.3　得られた主要な結果
この論文の主要な結果は、GI/G/1システムの平均待ち時間 $E(T_W)$ と待ちの確率 $W$ についての単純で明快な近似公式
$E(T_W)=\frac{A\cdot{h}}{2(1-A)}\cdot(c_A^2+c_H^2)\left\{{\exp\left(-\frac{2(1-A)}{3A}\cdot\frac{(1-c_A^2)^2}{c_A^2+c_H^2}\right)\text{ c_A^2{\le}1}\atop{{\exp\left(-(1-A)\cdot\frac{c_A^2-1}{c_A^2+4c_H^2}\right)}\text{ c_A^2{\ge}1}}$ ・・・・(1.3)
と
$W=A+(c_A^2-1)\cdot{A}(1-A)\left\{{\frac{1+c_A^2+A{\cdot}c_H^2}{1+A(c_H^2-1)+A^2{\cdot}(4c_A^2+c_H^2)}\text{ c_A^2{\le}1}\atop{\frac{4A}{c_A^2+A^2{\cdot}(4c_A^2+c_H^2)}}\text{ c_A^2{\ge}1}}$ ・・・・(1.4)
である。
これらの公式の精度は、D、E4、E2、M、H2分布関数の全ての組合せを持つシステムを含む、大量の正確な結果とシミュレーション結果との比較によりテストされてきた。
これらの結果から、さらに他のトラフィックの特性（例、平均待ち行列長）を得ることが出来、さらにバッチ到着システムについても得ることが出来る。

1.4　各章の概説
第２章では文献にすでにある明快な結果について述べ、第３章では公式(1.3)と(1.4)のヒューリスティックな開発に特別な興味を置いている。そこには妥当性確認結果も含まれている。
第４章では、バッチ到着システムが等価な単一到着システムを考慮することにより簡単に近似的に計算出来ることが示される。第５章は最後に、既知の関係を用いて他のトラフィックの特性（例、対応する出発過程の変動）についての単純な公式がいまや使用可能であることを示す。

２　既存の明快な結果
一般待ち行列システムGI/G/1に関する相当な量の出版物が待ち行列理論の最先端を示しているが、それらはそれでもなお、正確な数学的結果と迅速な工学への適用との間のギャップを明らかに出来ていない。GI/G/1問題を解くためにいくつかの計算方法が開発されてきた。それらは以下を含む。

Erlangのフェーズの方法。例えば*1 *2 *3

Lindleyの積分の方法*4

Kendallの隠れマルコフチェーンの方法*5

これらの方法とその他の方法は理論的深みに浸透するのに、そして多くの正確な結果を生み出すのに十分なくらい協力であることが証明されてきた。しかし実地への適用においては厄介な欠点が存在する。

1)

これらの方法hは適用可能であるためには特殊なトラフィックの仮定を必要とする。

2)

既存の正確な結果の大部分はラプラス変換と母関数と部分的に非常に精緻な方程式の根を含む。

3)

特別なGI/G/1システムの個々のタイプについて、数値結果を得る方法は多かれ少なかれ異なっている。

要するに、平均待ち時間と待ちの確率についての単純で明確手、かつ正確な公式はポアソン到着の場合（M/G/1）についてのみ存在する。よく知られたポラツェク＝ヒンチンの公式(1930/32)（*6参照）は

$E(T_W)=\frac{A(1+c_H^2)}{2(1-A)}\cdot{h}$ ・・・・(2.1)

であり、ここでは待ち時間の１次モーメントだけが与えられる。
対応する待ちの確率は単純に

$W=A$ ・・・・(2.2)

である。上述のギャップを橋渡しする必要性はさまざまに認識され、例えば下記をもたらしてきた。

ラプラス変換の数値変換テクニックの適用

観測された分布のステップ関数*7あるいはフェーズタイプ関数による適合

さまざまなタイプの待ち行列システムについての表。例えば*8参照。

平均待ち時間についての上限と下限の導出*9 *10 *11

Kingman *12はGI/G/1の平均待ち時間の上限

$E(T_W){\le}\frac{A[(c_A^2/A^2)+c_H^2]}{2(1-A)}\cdot{h}$ ・・・・(2.3)

を導出したが、これは重負荷（ $A\rightar{1}$ ）においてよい近似である
何名かの著者は単一到着G1/G/1待ち行列について下限や軽負荷近似を導出した。
また、過渡状態についてさえ重負荷公式を得るために拡散近似法が適用されてきた*13。定常状態における平均仮想待ちは最近*14において

$E(T_W)_{\rm{virtual}}=\frac{A(c_A^2+c_H^2)}{2(1-A)}\cdot{h}$ ・・・・(2.4)

と近似された。あいにく実際の平均待ち時間の上限と下限は稼働率の主要な興味のある範囲についてはあまり有用ではない。例えば、 $A=0.7$ に適用した重負荷公式(2.3)は平均待ち時間を100%まで過大に見積もってしまう。
よって、目標は、到着間隔とサービス時間の分布関数の１次と２次のモーメントに制限されているが、迅速な答を妥当な精度で可能にするような、ポラツェク＝ヒンチンの公式の拡張を純粋にヒューリスティックに導出することに設定された。

W. Kraemer and M. Langenbach-Belz,「Approximate Formulae for the Delay in the Queueing System GI/G/1」より

*1:SYSKI,R. Introduction to Congestion Theory in Telephone Systems. Oliver & Boyd, London/ Edinburgh, 1960

*2:COHEN,J.W. The Single Server Queue. North Holland, Amsterdam/London, 1969

*3:KLEINROCK,L. Queueing Systems, Vol I: Theory JWS,NY,London, 1975

*4:LINDLEY, D.V. The Theory of Queues with a Single server. Proc. Camb. Phil. Soc. 48 (1952), 277-289

*5:KENDALL, D.G. Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain Ann. Math. Stat. 24(1953), 338-354

*6:KLEINROCK,L. Queueing Systems, Vol I: Theory JWS,NY,London, 1975

*7:GREENBERG, I. Distribution-Free Analysis of M/G/1 and G/M/1 Queues. J. Op. Res. 21(1973), 629-635

*8:KUIHN, P. Tables of Delay Systems. Institute of Switching and Data Technics, University of Stuttgart, 1976

*9:MARSHALL, K.T. Some Inequalities in Queueing J. Op. Res. 16(1968), 651-668

*10: MARSHALL, K.T. Bounds for Some Generalizations of the GI/G/1 Queue. J. Op. Res. 16(1968), 841-848

*11:KOBAYASHI, H. Bounds for the Waiting Time in Queueing Systems. IBM Research Rpt RC4718, Yorktown Heights, February 1974

*12:KINGMAN, J.F.C. Some Inequalities for the GI/G/1 Queue. Biometrica, 49(1962), 315-324

*13:HEYMAN, D.P. A Diffusion Mocdel Approximation for the GI/G/1 Queue in Heavy Traffic. BSTJ 54(1975), 1637-1646

*14:HEYMAN, D.P. A Diffusion Mocdel Approximation for the GI/G/1 Queue in Heavy Traffic. BSTJ 54(1975), 1637-1646