待ち行列モデル M/M/cとは? わかりやすく解説

Weblio 辞書 > 学問 > OR事典 > 待ち行列モデル M/M/cの意味・解説 

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

読み方まちぎょうれつもでるえむえむしー
【英】: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) という.

 到着率\lambda\, , 平均サービス時間1/\mu\, とすると, 定常状態確率(3)用いて (4)与えられる. ただし, 今度場合, とりうる状態は k=0, 1, 2, \ldots , c\, だけであるので, p_0\,



p_0 = \left[\, \sum_{k=0}^{c}
\frac{1}{k!}\left(\frac{\lambda}{\mu}\right)^k \right]^{-1}
\,      (8)\,


与えられ, たとえ \rho=\lambda/c \mu<1\, でなくてもシステム安定的である. PASTA性質により, 呼損率は系内にちょうc\, 人の客がいる確率



p_c=\frac{1}{c!} \left(\frac{\lambda}{\mu}\right)^c p_0
\,      (9)\,


等しい. この式はアーランの損失式 (Erlang's loss formula) と呼ばれ, 損失系の性能評価で最も重要な特性量のひとつである. なお, この式は M/G/c\, /c\, モデル, すなわち一般サービスのときでも成り立つことが知られている.



参考文献

[1] L. Kleinrock, Queueing Systems Vol. 1 Theory, Wiley, New York, 1975.

[2] 森村英典, 大前義次, 『応用待ち行列理論』, 日科技連, 1975.

[3] 尾崎俊治, 『確率モデル入門』, 朝倉書店, 1996.

[4] S. M. Ross, Stocastic Processes, Wiley, New York, 1980.




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「待ち行列モデル M/M/c」の関連用語

待ち行列モデル M/M/cのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



待ち行列モデル M/M/cのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2024 (社)日本オペレーションズ・リサーチ学会 All rights reserved.

©2024 GRAS Group, Inc.RSS