待ち行列５．M/M/1における待ち行列の基本方程式の導出 - 数学・物理・電気主任技術者試験、情報処理技術者試験等お勉強の記録

パラメーター $\lambda$ のポアソン到着、窓口が1人でパラメーター $\mu$ の指数サービスの待ち行列M/M/1において長さ $j$ であるとき、この待ち行列は状態 $E_j$ にあるという。したがって系は常に $E_0,E_1,\cdots$ のいずれか1つの状態をとる。時刻 $t$ で状態 $E_j$ にある確率を $P_j(t)$ で表す。時刻 $t$ における系の長さを $Q(t)$ とすれば、 $P_j(t)=P(Q(t)=j)$ である。

ある時刻 $t_0$ で状態 $E_j$ にあったとする。その時刻後の系の状態の分布の移り変わりは以下の要因によって決定される。

(1)時刻 $t_0$ における系の長さ。

(2)時刻 $t_0$ における客のサービス終了時刻。

(3)時刻 $t_0$ 以降の到着時刻の分布。

(4)時刻 $t_0$ 以降に到着する客のサービス時間。

ある時刻を0とし、系の長さ $Q(t),(t \lt 0)$ を考察する。任意の $t,t'\lt 0$ に対して

$P(Q(t+t')=k|Q(t)=j)=P(Q(t')=k|Q(0)=j)$ である。遷移確率を

\begin{equation}\left\{ \begin{array}{l} P_{i,j}(t)=P(Q(t)=j|Q(0)=i) \\ P_{i,j}(0)=\delta_{i,j} \left\{ \begin{array} {l} 1,(i=j) \\ 0,(i\ne j) \end{array} \right.\end{array} \right. \end{equation}

と表す。 $i,j$ のいずれかが負のときは $P_{ij}(t)=0$ とおく。微小な時間区間 $(t,t+dt)$ をとるとき1人到着する確率は $\lambda dt + o(dt^2)$ であり、サービス中の客がこの区間内で終了して立ち去る確率は同様に $\mu dt + o(dt^2)$ であるから

\begin{equation}\left\{ \begin{array}{l} P_{i,i+1}(dt)=\lambda dt + o(dt^2) \\P_{i,i-1}(dt)=\mu dt + o(dt^2) \\ P_{i,i}(dt)=1-\lambda(dt)-(1-\delta_{i0})\mu dt + o(dt^2) \\ P_{i,j}(dt)= o(dt^2),(|i-j|\geqq 2) \end{array}\right.\end{equation}

最初の式は時刻 $t$ で $i$ 人おり、それから微小時間 $dt$ 後1人増えて $i+1$ 人になる確率であるから、

$P(dt\mbox{内でサービスが終了せず1人到着する})$

$=(1-\mu dt + o(dt^2))(\lambda dt + o(dt^2))= \lambda dt + o(dt^2)$

と

$\displaystyle{ \sum_{n=1}^\infty P(dt\mbox{内でサービスが}n\mbox{人終了して}n+1\mbox{人到着する})}$

$\displaystyle{ \leqq \sum_{n=1}^\infty P(dt\mbox{内に}n+1\mbox{人到着する}) = P(dt \mbox{内に2人以上到着する})=o(dt^2)}$

の和で得られる。上から2式目も同様である。4式目は自明である。

上から3式目については $i=0$ のとき誰も来ない確率であるから

$P_{0,0}(t)=1-\lambda dt + o(dt^2)$

$i \gt 0$ のときは $dt$ 時間内に $n\geq 0$ として $n$ 人来て $n$ 人帰る確率の総和だから、0人来て0人帰る確率は

$(1-\lambda dt + o(dt^2))(1-\mu dt + o (dt^2))=1-\lambda dt -\mu dt + o(dt^2)$

1人来て1人帰る確率は

$(\lambda dt + o(dt^2))(\mu dt + o(dt^2))=o(dt^2)$

2人以上来て同じ人数帰る確率は無視できるから3式目も正しい。

時刻0で系の長さが $i$ なるとき、それから時刻 $t+dt$ で $j$ となる遷移確率 $P_{ij}(t+dt)$ は時刻 $t=0$ の状態 $E_i$ から時刻 $t$ で状態 $E_k$ に移り、それから時刻 $t+dt$ で状態 $E_j$ になる互いに排反な事象の確率を加え合わせたものである。さらに時刻 $t$ で状態 $E_k$ であるとき、時刻 $t+dt$ で状態 $E_j$ になる遷移確率は時刻 $t$ 以前の状態に独立であるから、

$\displaystyle{P_{i,j}(t+dt) =\sum_{k=0}^\infty P(Q(t+dt)=j,Q(t)=k|Q(0)=i) }$

$\displaystyle{= \sum_{k=0}^\infty P(Q(t)=k|Q(0)=i)P(Q(t+dt)=j|Q(t)=k)}$

$\displaystyle{= \sum_{k=0}^\infty P_{i,k}(t)P_{k,j}(dt)}$

\begin{equation} = \left\{ \begin{array}{ll} P_{i,j-1}(t) \lambda dt + P_{i,j}(t) \{1-(\lambda+\mu)dt\} +P_{i,j+1}(t) \mu dt + o(dt^2) & ,(j \gt 0)\\ P_{i,0}(t) (1-\lambda)dt +P_{i,1}(t) \mu dt + o(dt^2) & ,(j=0) \end{array} \right.\end{equation}

最後の変形は $P_{i,i}(dt),P_{i,i-1}(dt),P_{i,i+1}(dt),P_{i,j}(dt)$ の式を使った。したがって

\begin{equation} \frac{d P_{i,j}(t)}{dt}= \left\{ \begin{array}{ll} \lambda P_{i,j-1}(t)+ -(\lambda+\mu) P_{i,j}(t) +\mu P_{i,j+1}(t) & ,(j \gt 0) \\ -\lambda P_{i,0}(t) +\mu P_{i,1}(t) & ,(j=0)\end{array} \right.\end{equation}

以上で待ち行列の基本方程式の導出が終わった。微分方程式の各項の意味は $j-1$ 人いるところへ1人来る場合、 $j$ 人いるところへ1人の増減も無い場合、 $j+1$ 人いるところから1人減る場合となる。 $dt$ 時間内では2人以上の変化は無視できるということである。ちなみに $t\to \infty$ での極限は方程式の解がベッセル関数を使って解けることから、ベッセル関数の漸近表示を用いて示される。時間があれば後述しようと思います。

[商品価格に関しましては、リンクが作成された時点と現時点で情報が変更されている場合がございます。]

わかりやすい待ち行列システム理論と実践 [ 高橋敬隆 ]
価格：3080円（税込、送料無料) (2020/9/9時点)

楽天で購入