Ｍ／Ｍ／１待ち行列のジョブのサイクルタイム分布

待ち行列理論

いつものように一番簡単な待ち行列としてＭ／Ｍ／１（「ケンドールの記号」参照）を取り上げて考察を進めます。今回の考察の目標は
「ジョブのサイクルタイムの平均は

ということは「待ち行列理論の私的総論」で分かったが、ではそのサイクルタイムはどのくらいバラついているの？　もっと言えば、その分布はどうなっているの？」
という疑問に答えることです。


すでに定常状態におけるＭ／Ｍ／１待ち行列におけるジョブ数毎の発生確率は「Ｍ／Ｍ／１における待ち時間の式の導出（２）」の式（９）

  • p_k=u^k(1-u)・・・・・・（１）

で明らかになっております。
もしあるジョブがこの待ち行列（＝システム）に到着する時に（自分を含めなくて）k個のジョブが存在するとすれば、その発生確率は「Ｍ／Ｇ／ｍの定常状態のジョブ数分布について」に述べたように定常状態での時間平均での発生確率に等しいので結局式（１）で与えられることが分かります。


さて、ジョブがシステムに到着した時、システム内に自分を含めなくてk個のジョブがあったとします。するとこのジョブは自分の前にk個のジョブを持つことになります。このうち１個のジョブは処理中であり、残りのk-1個のジョブは装置が空くのを待っている状態です。待っているk-1個のジョブは平均時間t_eの指数分布で装置で処理されるので、これらのジョブが全て処理される時間の分布はk-1個の同一分布の指数分布を足し合わせた分布になります。さらに処理中のジョブの残り処理時間の分布について言えば、指数分布の「記憶なし」特性のために、やはり平均、時間t_eの指数分布になります。さらに到着したジョブ自身の処理時間も同じく平均時間t_eの指数分布になります。結局のところ、到着したジョブが作業完了するための時間はk+1個の平均時間t_eの指数分布の和になります。
「アーラン分布」の「アーラン分布は指数分布の和」のセクションで述べたように、平均1/\lambdaのk個の指数分布の和はアーラン分布

  • \frac{\lambda^kt^{k-1}}{(k-1)!}\exp(-\lambda{t})・・・・・・（２）

となります。よって、ジョブが到着した時にシステム内に自分を含めなくてk個のジョブがある場合の、到着したジョブが到着から作業完了までの時間の分布f(t;k)は

  • f(t;k)=\frac{1}{t_e^{k+1}}\frac{t^k}{k!}\exp\left(-\frac{t}{t_e}\right)・・・・・・（３）

となります。システム内にk個のジョブがある確率は式（１）で与えられるので、ジョブのサイクルタイムの確率分布f_{ct}(t)は

  • f_{ct}(t)=\Bigsum_{k=0}^{\infty}f(t;k)u^k(1-u)=\Bigsum_{k=0}^{\infty}\frac{1}{t_e^{k+1}}\frac{t^k}{k!}\exp\left(-\frac{t}{t_e}\right)u^k(1-u)
    • =(1-u)\exp\left(-\frac{t}{t_e}\right)\Bigsum_{k=0}^{\infty}\frac{1}{t_e^{k+1}}\frac{t^k}{k!}u^k=(1-u)\exp\left(-\frac{t}{t_e}\right)\frac{1}{t_e}\Bigsum_{k=0}^{\infty}\frac{1}{k!}\left(\frac{ut}{t_e}\right)^k
    • =\frac{1-u}{t_e}\exp\left(-\frac{t}{t_e}\right)\exp\left(\frac{ut}{t_e}\right)=\frac{1-u}{t_e}\exp\left(-\frac{(1-u)t}{t_e}\right)

よって

  • f_{ct}(t)=\frac{1-u}{t_e}\exp\left(-\frac{(1-u)t}{t_e}\right)・・・・・・（４）

つまり、Ｍ／Ｍ／１におけるジョブのサイクルタイムの確率分布は平均

  • \frac{1}{1-u}t_e

の指数分布になります。指数分布であることから、サイクルタイムの標準偏差も

  • \frac{1}{1-u}t_e

であることが分かります。