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

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

4　バッチ到着のシステム
この章では平均待ち時間と待ちの確率の公式は、等価な単一到着システムを定義することによってバッチ到着のシステムにも適用出来ることが示される。

4.1　概論
通信システムでは、例えば、しばしば集中したユニットへの到着がバッチで、つまり任意のサイズ $K$ のグループで発生する。ただし $K$ は独立な確率変数であると仮定する。 $P_K$ 、（ $K=0,1,...$ ）が（バッチの到着間隔時間 $T_{AB}$ の分布関数によって特徴を定められた）バッチの可能な到着事象でサイズ $K$ のバッチが到着する確率であるとする。一般性のために、サイズ $K=0$ のバッチもまた含まれるとしよう。一般性のために、サイズ $K=0$ の「バッチ」もまた含まれるとしよう。これは特にいわゆるサンプルされたシステムにおいて有用である。そこではバッチは等距離に分布した時刻にだけ到着する（例えば*1参照）。
さて、標準の計算によりバッチの最初の要求の特性値（追加の１で示される）とバッチの任意のメンバの特性値の間の一般的な関係を確立することが出来る。平均待ち時間については

$E(T_W)=E(T_{W1})+\left(\frac{Var(K)}{E(K)}+E(K)-1\right)\cdot\frac{h}{2}$ ・・・・(4.1)

この公式は例えば*2、*3、*4で見つけることが出来る。

待ちの確率については、任意の要求がそのバッチ内の最初の要求である確率 $q$

$q=\frac{1}{E(K|K>0)}=\frac{1-p_0}{E(K)}$ ・・・・(4.2)

を用いて、

$W=q\cdot{W}_1+(1-q)\cdot{1}$ ・・・・(4.3)

であると単純に言うことが出来る。これは

$W=1-\frac{(1-p_0)}{E(K)}\cdot(1-W_1)$ ・・・・(4.4)

ということである。
この２つの公式(4.1)と(4.4)は、単一の要求の値は、もしそれに対応するバッチの最初の要求が知られるならば、決定することを可能にしている。4.2を参照のこと。

4.2　単一到着の等価システム
バッチの最初の要求も待ち時間は、全ての（>0の）バッチを「大要求」として定義した等価システムを考察することによって計算出来る*5。次に新しい到着間隔時間は、>0のバッチの到着と到着の間の時間であり、サービス時間は全ての（>0の）バッチを処理するための合計の時間である。
もし等価システムの諸特性をアスタリスク＊を追加して示すならば、

$E(T_H*)=E(K|K>0)\cdot{E}(T_H)$ ・・・・(4.5)

である。

$Var(T_H*)=E(T_H)^2\cdot{Var}(K|K>0)+E(K|K>0)\cdot{Var}(T_H)$ ・・・・(4.6)

により等価なサービス時間の（二乗）変動係数が

$C_H*^2=\frac{1-p_0}{E(K)}\cdot\left[\frac{Var(K)}{E(K)}+c_H^2\right]-p_0$ ・・・・(4.7)

であることを示すことが出来る。さて、到着過程が

バッチの到着間隔時間 $T_{AB}$ （サイズ $K{\ge}0$ の。つまり平均 $E(T_{AB})$ と変動係数 $c_{AB}$ を持つ「入力スイッチ」の連続終了の間の時間）

バッチサイズ確率 $P_K$ （ $K{\ge}0$ ）

で特徴づけられるとしよう。等価システムがサイズ>0のバッチに基づくので

$E(T_A*)=\frac{E(T_{AB})}{1-p_0}$ ・・・・(4.8)

と

$c_A*^2=(1-P_0)\cdot{c}_{AB}^2+p_0$ ・・・・(4.9)

が成り立つ。まとめると、等価システムは以下によって特徴付けられる。

平均サービス時間

$E(T_H*)=\frac{E(K)}{1-p_0}\cdot{E}(T_H)$ ・・・・(4.10)

元のバッチ到着システムと同じ、与えられたトラフィック

$A*=\frac{E(T_H*)}{E(T_A*)}=\frac{E(K)\cdot{E}(T_H)}{E(T_{AB})}=A$ ・・・・(4.11)

(4.9)と(4.7)による変動係数 $c_A*$ と $c_H*$

これらの値は等価単一到着システムのGI/G/1近似公式を用いる前に計算しておかなければならない。

4.3　バッチ到着システムの例
M/G/1システムについて公式(1.3)と(1.4)は正確なので、等価M/G/1システムに変換される全てのバッチ到着システムは正確に計算される。
これは、任意のサイズ $K>0$ と任意の分布を持つバッチ間の到着間隔時間がマイナスの指数分布である場合（つまり、 $c_{AB}^2=1$ 、 $p_0$ が任意の場合）について成立する。もし $p_0>0$ ならば、これはサイス $K>0$ のバッチ間の到着間隔時間がマイナスの指数分布である場合となり、平均が $1/(1-p_0)$ だけ増加する。（複合ポアソン到着過程）。

(4.1)を(1.3)と(4.7)から(4.11)までと組み合わせると、任意のサイズ $K{\ge}0$ のバッチ間の到着間隔時間がマイナスの指数分布である場合について

$E(T_W)=\frac{h}{2(1-A)}\cdot\left[A(1+c_H^2)+\frac{Var(K)}{E(K)}+E(K)-1\right]$ ・・・・(4.12)

という結果になる。待ちの確率については、(4.4)で $W_1=A$ として

$W=1-\frac{1-p_0}{E(K)}\cdot(1-A)$ ・・・・(4.13)

式(4.12)はGAVER*6の結果と同一である。彼は複合ポアソン到着過程を持つシステムの状態確率の母関数を導き出した。

これらの公式が複合ポアソン到着過程について正確なので、妥当性確認のため、２つのバッチ到着の間の時間がマイナスの指数分布ではない例も示すことにする。
極端な、しかしそれでも重要な場合を選ぶために、等距離に分布した到着間隔時間が，つまり、いわゆるサンプルされたシステムが選択された。これらのシステムは到着スイッチが周期的に終了するものとして認識される。

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

*1:LANGENBACH-BELZ, M. Sampled Queueing Systems Proc. Symp. on Computer Communications Networks & Teletraffic, Polytechnic Press, Brooklyn, New York, 1972.

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

*3:LANGENBACH-BELZ, M. Sampled Queueing Systems Proc. Symp. on Computer Communications Networks & Teletraffic, Polytechnic Press, Brooklyn, New York, 1972.

*4:BURKE, P.J. Delays in Single Server Queues with Batch Input. J.Op.Res. 23(1975), 830-833

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

*6:GAVER, D.P.Jr. Imbedded Markov Chain Analysis of a Waiting-Line Process in Continuous Time. Ann. Math. Stat, 30(1959), 698-720