工場統計力学（建設中！）

Ｍ／Ｍ／１／ｎ待ち行列（１）

待ち行列理論

では「勉強と研究の計画：ステーションに滞在出来るジョブ数に制限がある場合」の計画に沿って、まず、ステーションが１つ、ステーションを構成する装置が１台、ジョブの到着時間間隔の分布が指数分布、装置の処理時間の分布も指数分布、ステーション内にはジョブが $n$ 個までしか入らない場合の、この待ち行列の挙動を調べていきます。

ステーション内にジョブが $k$ 個ある確率を $p(k)$ で示します。また、ステーション内にジョブが $k$ 個ある状態を「状態 $k$ 」と呼ぶことにします。装置の処理時間の平均を $t_e$ で示します。ジョブの平均到着時間間隔を $t_a$ で示します。ここで

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

という数を考えます。すると

$t_a=\frac{t_e}{u}$ ・・・・(1)

になります。処理時間の分布は指数分布なので、任意のある時刻 $t$ から $t+dt$ の間に処理が完了する確率は

$\frac{1}{t_e}dt$ ・・・・(2)

となります。ジョブの到着時間間隔の分布も指数分布なので同様に、任意のある時刻 $t$ から $t+dt$ の間にジョブが到着する確率は

$\frac{u}{t_e}dt$ ・・・・(3)

となります。
状態0（つまり、ステーション内にジョブがまったくいない状態）を考えます。この状態から別の状態に変化する遷移は、ジョブの到着による、状態0→状態1、の遷移のみです。また、別の状態からこの状態に変化する遷移は、ジョブの処理完了による、状態1→状態0、の遷移のみです。

定常状態ではこの状態0から出て行く流れと状態0に入って行く流れが等しいはずです。出て行く流れ、つまり $t$ から $t+dt$ の間に状態0→状態1の遷移が発生する確率は式(3)から

$p(0)\frac{u}{t_e}dt$ ・・・・(4)

になります。一方、入って行く流れ、つまり $t$ から $t+dt$ の間に状態1→状態0の遷移が発生する確率は
式(2)から

$p(1)\frac{1}{t_e}dt$ ・・・・(5)

になります。式(4)と(5)が等しいわけですから

$p(0)\frac{u}{t_e}dt=p(1)\frac{1}{t_e}dt$

よって

$p(0)u=p(1)$

よって

$p(1)=up(0)$ ・・・・(6)

となります。

次に[tex:0

ジョブの到着による、状態 $k$ →状態 $k+1$ 、の遷移と、
ジョブの処理完了による、状態 $k$ →状態 $k-1$ 、の遷移

です。また、別の状態から状態 $k$ に変化する遷移は、

ジョブの処理完了による、状態 $k+1$ →状態 $k$ 、の遷移と、
ジョブの到着による、状態 $k-1$ →状態 $k$ 、の遷移

です。

定常状態ではこの状態 $k$ から出て行く流れと状態0に入って行く流れが等しいはずですので

$p(k)\frac{u}{t_e}dt+p(k)\frac{1}{t_e}dt=p(k+1)\frac{1}{t_e}dt+p(k-1)\frac{u}{t_e}$

が成り立ちます。上の式を整理すると

$p(k)u+p(k)=p(k+1)+p(k-1)u$

よって

$p(k+1)=(1+u)p(k)-up(k-1)$ ・・・・(7)

となります。

$k=1$ を式(7)に代入すると

$p(2)=(1+u)p(1)-up(0)$ ・・・・(8)

になります。ここで式(6)を代入すると

$p(2)=(1+u)p(1)-p(1)$

よって

$p(2)=up(1)$ ・・・・(9)

が成り立ちます。
次に $k=2$ を式(7)に代入すると

$p(3)=(1+u)p(2)-up(1)$ ・・・・(10)

になります。ここで式(9)を式(10)に代入すると

$p(3)=up(2)$ ・・・・(11)

が成り立ちます。以下、同様にして[tex:1{\le}k

$p(k+1)=up(k)$ ・・・・(12)

が成り立ちます。式(6)と(12)から、 $1{\le}k{\le}n$ について

$p(k)=u^kp(0)$ ・・・・(13)

が成り立ちます。

最後に状態 $n$ に関して、出て行く流れと入って行く流れを調べます。これは下の図のようになります。

この図から

$p(n)\frac{1}{t_e}dt=p(n-1)\frac{u}{t_e}dt$

が導かれます。これを整理すると

$p(n)=up(n-1)$

となります。これはすでに式(12)で得ていた結果ですので、結局、式(13)で問題がないことが分かります。

「Ｍ／Ｍ／１／ｎ待ち行列（２）」に続きます。