Kingmanの近似式の導出メモ（１） - 工場統計力学（建設中！）

さて、「Ｅ２／Ｍ／１待ち行列の平均待ち時間とその近似式」において、ＧＩ／Ｍ／１の平均待ち時間の近似式として

$CT_q{\approx}(1-c_a^2)CT_{q,D/M/1}(u,t_e)+c_a^2CT_{q,M/M/1}$ ・・・・・（１）

が登場しました。この中の $CT_{q,D/M/1}(u,t_e)$ については、「Ｄ／Ｍ／１における待ち時間の近似式」の式（５）に従って

$CT_{q,D/M/1}(u,t_e){\approx}\frac{u}{2(1-u)}t_e$ ・・・・・（２）

と近似することにします。そして $CT_{q,M/M/1}(u,t_e)$ については

$CT_{q,M/M/1}(u,t_e)=\frac{u}{1-u}t_e$ ・・・・・（３）

ですから、式（１）に（２）と（３）を代入して

$CT_q{\approx}(1-c_a^2)\frac{u}{2(1-u)}t_e+c_a^2\frac{u}{1-u}t_e=\frac{(1-c_a^2)+2c_a^2}{2}\frac{u}{1-u}t_e$

つまり、ＧＩ／Ｍ／１の平均待ち時間の近似式として

$CT_q{\approx}\frac{1+c_a^2}{2}\frac{u}{1-u}t_e$ ・・・・・（４）

を得ることが出来ます。
一方、「Ｍ／Ｇ／１における待ち時間の式の導出（１）」にありますように、Ｍ／Ｇ／１の平均待ち時間の式は（こちらは近似式ではありません）

$CT_q=\frac{1+c_e^2}{2}\frac{u}{1-u}t_e$ ・・・・・（５）

です。（４）と（５）からＧＩ／Ｇ／１のための待ち時間の近似式

$CT_q{\approx}\frac{c_a^2+c_e^2}{2}\frac{u}{1-u}t_e$ ・・・・・（６）

つまりKingmanの近似式、が成り立つことを主張したいところですが、これだけで式（６）を主張するのは、ちょっと飛躍ですね。
もう少し、式（６）を正当化する理由がないか探してみることにします。

平均待ち時間について今まで分かったことを下図にまとめました。

この図は横軸に $c_e^2$ を縦軸に $c_a^2$ をとっています。
Ｍ／Ｍ／１については平均待ち時間が分かっています。Ｍ／Ｍ／１とＭ／Ｄ／１を結ぶ直線、つまり上図の赤の横線、はＭ／Ｇ／１を表しますが、その平均待ち時間は式（５）で与えられることが分かっています。次に、Ｍ／Ｍ／１とＤ／Ｍ／１を結ぶ直線、つまり上図の青の縦線はＧＩ／Ｍ／１を表しますが、その平均待ち時間は近似的に式（４）で表すことが出来ます。そして式（６）は式（４）と式（５）を自分の中に含んでいます。しかし、これら２本の直線以外の場所で本当に、近似的にも式（６）が成り立つのか、証拠がありません。そこで証拠を探してみます。

まず、 $E_2/E_2/1$ を検討してみます。 $E_2$ は２次のアーラン分布を表します。
まず、平均処理時間 $t_e/2$ のＭ／Ｍ／１待ち行列を考えます。この時の装置の利用率を $u$ とすると、ジョブの平均待ち時間 $CT_{q1}$ は

$CT_{q1}=\frac{u}{1-u}\frac{t_e}{2}$ ・・・・・（７）

になります。この待ち行列に到着するジョブを１つおきに印をつけることにします。そうすると、印の付いたジョブの到着の間隔に注目すれば、これは指数分布の到着間隔を２つ足したものになりますから「アーラン分布」の「アーラン分布は指数分布の和」の箇所を参照すれば分かるように、この到着間隔は２次のアーラン分布（ $E_2$ ）になります。一方、印の付いたジョブとその直後の印の付いていないジョブの処理時間をひとまとめにして、その全体を印のついているジョブの処理時間と見なすと、これも同じ理由から２次のアーラン分布（ $E_2$ ）になり、その平均処理時間は

$t_e/2{\times}2=t_e$

になります。ただし、このような見方が崩れる場合があります。それは、印のついているジョブの処理時間とその直後にある、印のついていないジョブの処理時間が連続していない場合です。今は、このことを考慮しないでおきます。

すると、印のついたジョブに注目する限り、この待ち行列は $E_2/E_2/1$ の待ち行列と擬似的に考えることが出来ます。その時の印のついたジョブの平均待ち時間はどれだけでしょうか？　これは最初に考えたＭ／Ｍ／１におけるジョブの平均待ち時間に等しいことになります。つまり式（７）で与えられることになります。そこで、（擬似的でない）本当の $E_2/E_2/1$ における平均待ち時間を $CT_q$ で表すと