待ち行列モデル M/M/c

出典: ORWiki

【まちぎょうれつもでるえむえむしー (queueing model M/M/ $c$ )】

概要

ポアソン到着, 指数サービス, 窓口が $c\,$ 個の待ち行列モデル. 最も基本的な待ち行列モデルの1つ. 待ち行列モデルを指して "マルコフモデル" というときは, このモデルを指していることが多い.

詳説

　待ち行列モデル M/M/c (queueing model M/M/ $c\,$ )は, 客の到着がパラメータ $\lambda\,$ のポアソン過程に従い, サービス時間が平均 $1/\mu\,$ の指数分布に従う, 窓口 $c\,$ 個の最も基本的な待ち行列モデルである. 待ち行列理論がA. K. Erlangによって20世紀初頭に誕生したときに, 真っ先に研究の対象となったのがこのタイプのモデルであった. それ以来, モデルの簡潔さ, 公式のわかりやすさから, 代表的な待ち行列モデルとして, 常に待ち行列理論のよりどころとなり, また多方面で実際問題の解決に応用されてきている. 近年研究が進められている待ち行列ネットワークでも, その中心となっているのはこの M/M/ $c\,$ モデルをネットワーク状につないだジャクソン型ネットワークとそれを拡張したBCMP型ネットワークであることからも, その重要性が理解できよう.

ポアソン到着と指数サービス　M/M/ $c\,$ モデルに関連して, いくつかの用語が慣用的に用いられている. 客の到着がポアソン過程にしたがうとき, つまり客の到着間隔が独立で同一の指数分布に従うとき, その到着の仕方をポアソン到着 (Poisson arrival) という. この場合, 到着過程のパラメータを $\lambda\,$ とすると, 長さ $t\,$ の時間に到着する人数は平均 $\lambda t\,$ のポアソン分布に従う. この $\lambda\,$ のことを到着率 (arrival rate) と呼ぶ. また, サービス時間の分布が指数分布に従うとき, サービスの仕方は指数サービス (exponential service) であるという. このとき平均サービス時間の逆数 $\mu\,$ のことをサービス率 (service rate) と呼ぶ.

マルコフ性　M/M/ $c\,$ モデルが容易に解析できるのは, 指数分布がつぎの"無記憶性"をもつことによる. 確率変数 $X\,$ がパラメータ $\lambda\,$ の指数分布に従っているものとしよう. すると, 任意の $s, t>0\,$ に対して

$\mbox{P}\{ X>s+t\mid X>s \} = \mathrm{e}^{-\lambda t} = \mbox{P}\{ X>t \}\, \,$

が成り立つ. これは, 現在の状況 ( $X>s\,$ ということ) がわかると, 今後の確率的挙動は過去の履歴とは無関係, ということであり, この性質を無記憶性 (memoryless property) またはマルコフ性 (Markov property) と呼ぶ. M/M/ $c\,$ などのケンドールの記号において, ポアソン到着と指数サービスを M で表現するのは, このマルコフ性に由来する.

　M/M/ $c\,$ モデルでは, ポアソン到着と指数サービスの仮定から, 系内人数を状態とするマルコフ連鎖を導くことができる. このマルコフ連鎖は出生死滅過程と呼ばれる特殊な型をしており, その解析は容易である. マルコフ連鎖の一般論から, 適当な条件の下でこの出生死滅過程は時間の経過とともに平衡状態に近づく. そのため M/M/ $c\,$ モデルでは, 平衡状態における状態確率 (これを定常状態確率 (stationary state probability) とか極限状態確率と呼ぶ) を解析的に求め, それらから待ち確率, 平均待ち時間, 待ち時間分布}, 平均系内人数, 系内人数分布などの混雑の尺度を計算して, 実際のシステムの性能評価に役立てている.

M/M/1 モデル　待ち行列モデル M/M/1 (queueing model M/M/1) は, $c=1\,$ の場合で, ポアソン到着, 指数サービス, 単一窓口をもつ待ち行列として定義される. 定常状態確率が存在するための必要十分条件は, $\rho = \lambda/\mu<1\,$ を満たすことである. そのときシステム内に $k\,$ 人の客がいる定常状態確率は

$p_k=(1-\rho)\rho^k, \qquad k=0, 1, 2, \cdots \, \,$ 　　　　　 $(1)\,$

で与えられ, 幾何分布に従う. 窓口がサービス中である確率は $1-p_0=\rho\,$ であるので, $\rho\,$ を利用率と呼ぶ. これは到着した客が待たされる確率, すなわち待ち確率, でもある (PASTA参照). (1) 式より, 平均系内人数は $L=\rho/(1-\rho)\,$ であり, 平均待ち行列長は $L_q=\rho^2/(1-\rho)\,$ である.

　待ち時間分布は $t=0\,$ に $1-\rho\,$ のマスをもち, $t>0\,$ では指数分布型の密度をもつ

$F(t)=\mbox{P}\{ \boldsymbol{W_q} \leq t \} =\left\{ \begin{array}{ll} 0, & t<0 \\ 1-\rho \mathrm{e}^{-(\mu-\lambda)t}, \qquad & t \geq 0 \end{array} \right. \,$ 　　　　　 $(2)\,$

で与えられる. この分布関数から, またはリトルの公式から, 平均待ち時間は $W_q=L_q/\lambda=\rho/\mu(1-\rho)\,$ , 平均系内滞在時間は $W=L/\lambda=1/\mu (1-\rho)\,$ であることがわかる.

M/M/ $\boldsymbol {c}\,$ モデル　待ち行列モデル M/M/c は, ポアソン到着で $c\,$ 個 (通常は複数) の指数サービス窓口をもつモデルである. これも出生死滅過程を用いて解析できる. 客の到着率を $\lambda\,$ , 平均サービス時間を $1/\mu\,$ とすると, 平衡状態が存在するための条件は $\rho=\lambda/c \mu < 1\,$ である. 系内に $c\,$ 人以上の客がいるときはすべての窓口がサービス中なので, 短い時間 $dt\,$ の間にいずれかのサービスが終了する確率は $c \mu \, dt\,$ であり, 系内にいる客の数が $k\,$ 人 ( $k<c\,$ ) のときは, $k\,$ 個の窓口でサービスを行っているだけなので, この確率は $k\mu \, dt\,$ である. そこで

$\mu_k=\left\{ \begin{array}{ll} k\mu, & \qquad k=0, 1, \cdots, c-1 \\ c\mu, & \qquad k=c, c+1, \cdots \end{array} \right. \,$ 　　　　　 $(3)\,$

とおけば, $dt\,$ の間に一人の客が到着する確率が $\lambda \, dt\,$ であることから, 平衡状態において $k\,$ 人の客がいる確率は

$p_k=p_0 \prod_{i=1}^k \frac{\lambda}{\mu_i}, \qquad k=1, 2, \cdots \,$ 　　　　　 $(4)\,$

で与えられる. ここで $p_0\,$ は, (4) の $p_k\,$ の和が 1 となるよう

$p_0 = \left[\sum_{k=0}^{c-1} \frac{c^k \rho^k}{k!} +\frac{c^c \rho^c}{c! \, (1-\rho)}\right]^{-1} \,$ 　　　　　 $(5)\,$

で与えられる. 安定性の条件 $\rho<1\,$ は, (4) の $p_k\,$ の和が有限の値に収束するための条件となっていることに注意しよう. この $\rho\,$ は各窓口がサービス中の時間の割合になっており, やはり利用率と呼ばれる. すべての窓口がふさがっている確率は,

$\Pi=\sum_{k=c}^\infty p_k = \frac{c^c \rho^c}{c! \, (1-\rho)} p_0 \,$ 　　　　　 $(6)\,$

であり, PASTA よりこれが待ち確率でもある. 待ち時間分布は

$\mbox{P}\{ \boldsymbol{W_q} \leq t\} = \left\{ \begin{array}{ll} 0 , & t <0 \\ 1 - \Pi \, \mathrm{e}^{-c \mu(1-\rho)t}, \quad & t \geq 0 \end{array} \right. \,$ 　　　　　 $(7)\,$

で与えられ, 平均待ち時間は $W_q= \Pi / c \mu (1 - \rho)\,$ である.

M/M/ $\boldsymbol {c/c}\,$ モデル　待ち行列モデル M/M/c/c (queueing model M/M/ $c\,$ / $c\,$ ) は, ポアソン到着で, $c\,$ 個の指数サービス窓口があるが, 待合室が無く, 客が待つことができない待ち行列である. 客が到着したときに, 空いた窓口がある場合には直ちにサービスを受けるが, すべての窓口が塞がっている場合にはサービスを受けることなく立ち去る. このようにサービスを受けずに立ち去る客がある待ち行列モデルは損失系と呼ばれ, 電話回線などのトラフィック理論でしばしば利用される. このときサービスを受けずに立ち去る客の割合を呼損率 (loss probability) という.