重負荷極限定理（１） - 工場統計力学（建設中！）

ＧＩ／Ｇ／ｓ待ち行列で成り立つ重負荷極限定理を導出します。重負荷極限定理は次のような内容です。

$\lim_{u\rightar{1}}(1-u)L_q=\frac{c_a^2+c_e^2}{2}$ ・・・・(1)

ここで $u$ は装置の稼働率、 $L_q$ は平均待ち行列長、 $c_a$ はジョブの到着間隔の変動係数、 $c_e$ は処理時間の変動係数、です。ところでＧＩ／Ｇ／ｓ待ち行列で成り立つ数式はめったにありません。その意味でこの定理はＧＩ／Ｇ／ｓ待ち行列の平均待ち行列長を推定するための大きな手掛かりになる重要な定理です。

では、証明を（厳密な証明ではありませんが）以下に示します。
$u\rightar{1}$ になると一般的な傾向として平均待ちジョブが急速に増えます。そして待ちジョブがまったくない確率はゼロに近づいてきます。今、待ちジョブが１よりかなり多くある状態が続く期間が時刻0から $t$ まであったとします。時刻0からその期間内の任意の時刻 $r$ までに到着したジョブの数を $A(r)$ で表すことにします。また、時刻0からその期間内の任意の時刻 $r$ までに処理が開始されたジョブの数を $D(r)$ で表すことにします。 $u\rightar{1}$ になると $t$ がどんどん長くなります。その場合 $A(t)$ と $D(t)$ の分布はそれぞれどうなるでしょうか？

ジョブの到着は繰り返し発生する現象です。到着分布はＧＩであって、これは広く一般の（General）分布を仮定していますが、それだけでなく各間隔の確率が独立である（Indepent）であることも仮定しているという意味です。この到着という現象は、前に起きた時刻からある確率分布に従う時間後に次の発生があり、かつ、その確率分布は変わらないので、「確率変数の和の個数の分布について」で述べたことが適用出来て、 $A(t)$ は正規分布に近づくことが言えます。そして $A(t)$ の平均 $m_A$ は、ジョブの到着間隔の平均を $t_a$ とすると「確率変数の和の個数の分布について」の最後に述べたことから

$m_A=n_a$ ・・・・(2)

となり、「確率変数の和の個数の分布について」の式(9)により $n_a=t/t_a$ となるので

$m_A=\frac{t}{t_a}$ ・・・・(3)

となります。 $A(t)$ の標準偏差 $\sigma_A$ は、ジョブの到着間隔の標準偏差を $\sigma_a$ で表すと「確率変数の和の個数の分布について」の最後に述べたことから

$\sigma_A=\sqrt{n_a}\frac{\sigma_a}{t_a}$

よって

$\sigma_A=\frac{\sigma_a}{t_a}\sqrt{\frac{t}{t_a}}$ ・・・・(4)

となります。

一方処理開始回数 $D(t)$ については次のように考えます。 $s$ 台ある装置のうち $k$ 番目の装置についての処理開始回数を $D_k(t)$ で表すことにします。すると

$D(t)=\Bigsum_{k=1}^sD_k(t)$ ・・・・(5)

が言えます。さて、 $D_k(t)$ についてですが、時刻ゼロから $t$ まで、どの装置も空くことはないので、装置 $k$ は常に処理中です。よってジョブの処理開始という現象も、前に処理開始が起きた時刻からある確率分布に従う時間後に次の処理開始があり、かつ、その確率分布は変わらない、ということが言えます。よって、「確率変数の和の個数の分布について」で述べたことが適用出来て、 $D_k(t)$ は正規分布に近づくことが言えます。 $D(t)$ は極限では正規分布に従う確率変数 $D_k(t)$ の和ですから、これもまた正規分布に近づくことが分かります。さて $D_k(t)$ の平均 $m_D(k)$ は、処理時間の平均を $t_e$ とすると「確率変数の和の個数の分布について」の最後に述べたことから

$m_D(k)=\frac{t}{t_e}$ ・・・・(6)

となります。 $D_k(t)$ の標準偏差 $\sigma_D(k)$ は、処理時間の標準偏差を $\sigma_e$ で表すと「確率変数の和の個数の分布について」の最後に述べたことから

$\sigma_D(k)=\frac{\sigma_e}{t_e}\sqrt{\frac{t}{t_e}}$ ・・・・(7)

となります。 $D(t)$ は式(5)にあるように $s$ 個の $D_k(t)$ の和であるので、 $D(t)$ の平均 $m_D$ は、

$m_D=sm_D(k)$

よって

$m_D=\frac{st}{t_e}$ ・・・・(8)

となります。また、 $D(t)$ の標準偏差 $\sigma_D$ は、

$\sigma_D=\sqrt{s}\cdot\sigma_D(k)$

よって

$\sigma_D=\frac{\sigma_e}{t_e}\sqrt{\frac{st}{t_e}}$ ・・・・(9)

となります。 $u\rightar{1}$ で $D(t)$ は式(8)で与えられる平均と式(9)で与えられる標準偏差を持つ正規分布に近づきます。

さて、時刻ゼロの時の待ちジョブ数、つまり待ち行列長を $Q(0)$ で表し、時刻 $t$ の時の待ち行列長を $Q(t)$ で表します。すると

$Q(t)=Q(0)+A(t)-D(t)$ ・・・・(10)

となります。では、 $u\rightar{1}$ になった時の $Q(t)$ の分布はどうなるでしょうか？　 $Q(0)$ は定数であり、 $A(t)$ 、 $D(t)$ はそれぞれ正規分布に従う確率変数でした。さらに、待ちジョブがある限りジョブの到着とジョブの処理開始は独立に発生するので、 $A(t)$ と $D(t)$ は独立です。よって $Q(t)$ もまた $u\rightar{1}$ で正規分布に近づきます。では $u\rightar{1}$ の時の $Q(t)$ の平均 $m_Q$ と標準偏差 $\sigma_Q$ はどうなるでしょうか？　式(10)(3)(8)から

$m_Q=Q(0)+m_A-m_D=Q(0)+\left(\frac{1}{t_a}-\frac{s}{t_e}\right)t=Q(0)+\left(\frac{t_e}{st_a}-1\right)\frac{st}{t_a}$

ここで

$u=\frac{t_e}{st_a}$

なので

$m_Q=Q(0)-(1-u)\frac{st}{t_e}$ ・・・・(10)

また式(10)(4)(9)から

$\sigma_Q^2=\sigma_A^2+\sigma_D^2=\frac{\sigma_a^2}{t_a^2}\cdot\frac{t}{t_a}+\frac{\sigma_e^2}{t_e^2}\cdot\frac{st}{t_e}=c_a^2\frac{t}{t_a}+c_e^2\frac{st}{t_e}=\left(c_a^2\frac{t_e}{st_a}+c_e^2\right)\frac{st}{t_e}$

よって

$\sigma_Q^2=(uc_a^2+c_e^2)\frac{st}{t_e}$ ・・・・(11)

となります。

「重負荷極限定理（２）」につづきます。