Ｄ／Ｍ／１における待ち時間の式の導出

待ち行列理論

「Ｄ／Ｍ／１待ち行列の到着時刻状態分布（３）」の続きです。
ここまでくると、Ｄ／Ｍ／１におけるジョブの平均待ち時間も計算できそうです。ジョブがシステムに到着した時に、システム内にk個のジョブが存在するとした場合、この到着したジョブは処理開始までどれだけ待つでしょうか？　システム内にk個のジョブが存在する場合k-1個が待ちジョブで１個が処理中です。k-1個の待ちジョブはそれぞれ平均t_eの処理時間で処理されるので、これらが全て処理完了する時間の平均は(k-1)t_eとなります。


では、処理中のジョブはあと平均どれだけで処理が完了するでしょうか？　これは処理時間がＭ、つまり指数分布なので、指数分布の「記憶なし」性質を利用することが出来ます。そうすると、残り処理時間も平均t_eであることが分かります。よって、今、到着したジョブが待つ時間の平均は(k-1)t_e+t_e=kt_eとなります。


ジョブが到着した時にシステム内にジョブがk個存在する確率p(k)は「Ｄ／Ｍ／１待ち行列の到着時刻状態分布（２）」の式（１４）

  • p(k)=(1-b)b^k・・・・・（１４）

で与えられるので、ジョブの待ち時間の平均CT_qは

  • CT_q=\Bigsum_{k=0}^{\infty}p(k)kt_e=\Bigsum_{k=0}^{\infty}(1-b)b^kkt_e=(1-b)t_e\Bigsum_{k=0}^{\infty}kb^k
    • =(1-b)t_e\Bigsum_{k=1}^{\infty}kb^k=(1-b)bt_e\Bigsum_{k=1}^{\infty}kb^{k-1}

ここで「補足」の式（２）を参照すれば

  • CT_q=(1-b)bt_e\frac{1}{(1-b)^2}

よって

  • CT_q=\frac{b}{1-b}t_e・・・・・（１７）
    • ただしbは
    • \frac{1}{b}\exp\left(\frac{b}{u}\right)=\exp\left(\frac{1}{u}\right)・・・・・（１６）
    • を満足するb<1である解

となります。これを

  • \frac{CT_q}{t_e}=\frac{b}{1-b}・・・・・（１８）

と変形してグラフに書くと、以下のようになります。比較のためにＭ／Ｍ／１の場合も一緒に示しました。

「Ｄ／Ｍ／１における待ち時間の近似式」に続きます。