リー・ロントンの近似式を根拠づける試み（５）

待ち行列理論

「リー・ロントンの近似式を根拠づける試み（４）」の続きです。
「リー・ロントンの近似式を根拠づける試み（２）」の考察は間違っていなかったと思うのですが、結果はあまり思わしくありませんでした。おそらくKingmanの近似式をc_a=1以外の待ち行列に使う場合には精度が落ちるのでしょう（よく分かりませんが・・・）。そこで、別な方向から考えてみました。


Ｍ／Ｇ／ｓ待ち行列を考えます。Ｍ／Ｇ／１待ち行列の平均待ち時間を求めた時（ポラツェク・ヒンチンの式。「Ｍ／Ｇ／１における待ち時間の式の導出（１）」「（２）」参照）の推論をＭ／Ｇ／ｓの場合についてなぞっていきます。


ジョブが到着した時に待ち行列で待っているジョブの個数（到着したジョブは個数に含めない）を考え、その平均値を考えます。到着過程はポアソン過程なのでＰＡＳＴＡを用いることが出来ます。ＰＡＳＴＡによってこの個数の平均は、待ち行列の（時間）平均の長さL_{q(M/G/s)}になります。
次に、ジョブが到着した時にs台の装置が全て処理中であるとして、そのうちのどれかが最初に空く（＝処理完了になる）までの時間を考えます。これは確率変数なのでRで表します。その平均値をE(R)で表します。
また、s台の装置が全て処理中である場合の待ち行列の平均の長さを\hat{L}_{q(M/G/s)}で表します。また、s台の装置が全て処理中である確率を\Pi_{(M/G/s)}で表します。そうすると\hat{L}_{q(M/G/s)}とL_{q(M/G/s)}の定義から

  • L_{q(M/G/s)}=\Pi_{(M/G/s)}{\times}\hat{L}_{q(M/G/s)}+(1-\Pi_{(M/G/s)}){\times}0

つまり

  • L_{q(M/G/s)}=\Pi_{(M/G/s)}{\times}\hat{L}_{q(M/G/s)}・・・・(1)

が成り立ちます。


今到着したジョブが待ち行列で待つ時間の平均値を考えます。到着した時点でもしs台の装置が全て処理中であるならば、平均\hat{L}_{q(M/G/s)}個のジョブが待っているはずです。１個のジョブの処理にt_eだけ時間がかかりますが、装置はs台あるので、\hat{L}_{q(M/G/s)}個のジョブが全て処理されるのに平均

  • \hat{L}_{q(M/G/s)}{\times}\frac{t_e}{s}

だけ時間がかかることになります。さらに現在処理中の装置のどれかが空いてから、これらのジョブの処理が始まるので、今到着したジョブが待ち行列で待つ平均時間は

  • \hat{L}_{q(M/G/s)}{\times}\frac{t_e}{s}+E(R)・・・・(2)

になるように思われます（あとで考えるとそうとも言えないことが分かりました）。
もし、１台でも空いている装置があれば、もちろん待ち時間はゼロです。
s台の装置が全て処理中である確率は\Pi_{(M/G/s)}ですから、ジョブが待ち行列で待つ時間の平均CT_{q(M/G/s)}は

  • CT_{q(M/G/s)}=\Pi_{(M/G/s)}\hat{L}_q\frac{t_e}{s}+{\Pi_{(M/G/s)}}E(R)・・・・(3)

となります。式(1)を考えると式(3)は

  • CT_{q(M/G/s)}=L_{q(M/G/s)}\frac{t_e}{s}+{\Pi_{(M/G/s)}}E(R)・・・・(4)

と書けます。ここでL_{q(M/G/s)}についてリトルの法則を適用すれば、

  • L_{q(M/G/s)}=CT_{q(M/G/s)}{\times}\frac{su}{t_e}

なので式(4)は

  • CT_{q(M/G/s)}=CT_{q(M/G/s)}u+{\Pi_{(M/G/s)}}E(R)

となり

  • CT_{q(M/G/s)}(1-u)={\Pi_{(M/G/s)}}E(R)

よって

  • CT_{q(M/G/s)}=\frac{{\Pi_{(M/G/s)}}E(R)}{1-u}・・・・(5)

となります。


「リー・ロントンの近似式を根拠づける試み（６）」に続きます。