定常状態分布

待ち行列理論

「平均待ち時間」では、任意のジョブ到着間隔分布と、任意の処理時間分布を持つ待ち行列について、ジョブの平均待ち時間を推定する近似式を紹介しました。ここでは、さらに進んで、そのような待ち行列の定常状態分布、すなわち、この待ち行列のシステムにジョブがk個存在する確率p(k)を推定する近似式を紹介します。正直なところ、指数分布ではない任意の到着間隔分布の場合、この近似の根拠はあまりありません。しかし、他によい近似も見つからなかったので、この近似を提示する次第です。

  • [tex:k
    • p(k)\approx\frac{(su)^k}{k!}p(0)・・・・(4)
  • k{\ge}sの場合
    • p(k){\approx}b^{k-s}(1-b)\frac{(su)^s}{s!(1-u)}p(0)・・・・(5)
  • ただし
    • p(0)=\frac{1}{\Bigsum_{k=0}^{s-1}\frac{(su)^k}{k!}+\frac{(su)^s}{s!(1-u)}}・・・・(6)
    • b=\frac{(c_a^2+c_e^2[c_a^2(1-u)+u])u}{2-(2-c_a^2-c_e^2[c_a^2(1-u)+u])u}・・・・(7)

上の諸式において、c_aは到着間隔の変動係数（＝標準偏差を平均値で割ったもの）、c_eは処理時間の変動係数、t_eは処理時間の平均値、sは装置の台数、uは装置の利用率、です。


これらの式がどの程度、信頼おけるものなのかを示すために、上記で推定されたp(k)に関するいくつかの性質を示しておきます。まず、p(k)が確率として満たさなければならない

  • \Bigsum_{k=0}^{\infty}p(k)=1・・・・(8)

を本当に満たしているということです。まず式(4)を用いて

  • \Bigsum_{k=0}^{s-1}p(k)=p(0)\Bigsum_{k=0}^{s-1}\frac{(su)^k}{k!}・・・・(9)

です。次に式(5)を用いて

  • \Bigsum_{k=s}^{\infty}p(k)=(1-b)\frac{(su)^s}{s!(1-u)}p(0)\Bigsum_{k=s}^{\infty}b^{k-s}
    • =(1-b)\frac{(su)^s}{s!(1-u)}p(0)\Bigsum_{k=0}^{\infty}b^k=(1-b)\frac{(su)^s}{s!(1-u)}p(0)\frac{1}{1-b}
    • =\frac{(su)^s}{s!(1-u)}p(0)

よって

  • \Bigsum_{k=s}^{\infty}p(k)=\frac{(su)^s}{s!(1-u)}p(0)・・・・(10)

式(9)(10)から

  • \Bigsum_{k=0}^{\infty}p(k)=p(0)\left[\Bigsum_{k=0}^{s-1}\frac{(su)^k}{k!}+\frac{(su)^s}{s!(1-u)}\right]

ここで式(6)を用いると式(8)

  • \Bigsum_{k=0}^{\infty}p(k)=1・・・・(8)

が成り立つことが分かります。


次に、式((5)と「平均待ち時間」の式(2)との整合性を示したいと思いますが、その前にこの待ち行列の平均待ち行列長を示しておきたいと思います。