待ち行列モデル M/G/1のソースを表示

'''【まちぎょうれつもでるえむじーわん (queueing model M/G/1)】'''
=== 概要 ===

客の到着がポアソン過程にしたがい, サービス時間が, 一般分布にしたがう窓口1個(扱い者1人)の無限長の待ち行列を許す最も基本的な待ち行列モデルの1つ. M/G/1 型の待ち行列は, M/G/1モデルから派生する種々の待ち行列を指し, 例えば有限待合室モデル(M/G/1/<math>{\it m}\,</math>), 有限呼源モデル (M(<math>{\it n}\,</math>)/G/1), 休暇時間を伴う待ち行列(バケーションモデル M/G/1 +Vacation)などがある.
=== 詳説 ===
　[[待ち行列モデル M/G/1]] (queueing model M/G/1) は, 客の到着が到着率 <math>\lambda\, </math> の[[ポアソン過程]]に従い, サービス時間が一般分布 <math>H(t)\, </math> に従う, 窓口1個 (扱い者1人) の無限長の待ち行列を許す最も基本的なモデルである. 

　客の到着間隔 <math>A_r, r=1, 2, \cdots,\, </math>  およびサービス時間<math>B_r, r=1, 2, \cdots,\, </math>  は互いに独立で, <math>A_r\, </math> は平均 <math>1/\lambda\, </math> の指数分布, <math>B_r\, </math> はサービス時間分布 <math>H(t)\, </math> に従う. したがって任意の時間帯 <math>(\tau, \tau+t ]\, </math> における到着客数 <math>N_{\tau}(t)\, </math>は, 平均 <math>\lambda t\, </math> のポアソン分布に従う確率変数となる. 客の[[サービス規律]]として, 通常, [[先着順サービス|先着順]] (FCFS) を仮定するが, [[後着順サービス|後着順]] (LCFS), [[ランダム順サービス|ランダム順]] (ROS) などのサービス規律を考えることもある. 

　先着順サービスの M/G/1 モデルでは, 平均サービス時間を <math>1/\mu\, </math> とすると, 利用率 <math>\rho=\lambda/\mu < 1\, </math> のときにシステムは安定となり, 時間の経過とともに[[平衡状態]]へ近づく. 平衡状態における客の待ち時間分布 <math>W_q(t)\, </math> は[[ポラチェック・ヒンチンの公式]] (Pollaczek-Khintchine formula)


<center>
<math>
W_q^*(s) = (1-\rho)/ \{1-\lambda[1-H^*(s)]/s\}
\, </math>　　　　　<math>(1)\, </math>
</center>


によって与えられる. ここで <math>W_q^*(s), H^*(s)\, </math> はそれぞれ <math>W_q(t), H(t)\, </math>のラプラス・スチルチェス変換である. 


'''平均待ち時間'''　式 (1) から, 平衡状態における[[平均待ち時間]] <math>\mbox{E}(W_q)\, </math> は, <math>c^2= \mbox{Var}(B_r)/\{\mbox{E}(B_r)\}^2\, </math> をサービス時間分布の変動係数として, 


<center>
<math>
\mbox{E}(W_q) = \frac{\rho (1+c^2)}{2 \mu (1-\rho)}
\, </math>　　　　　<math>(2)\, </math>
</center>


で与えられることが分かる. この式から平均行列長, 平均系内人数, 平均系内滞在時間などは[[リトルの公式]]を用いて容易に導くことができる. 

　式 (2) は, 同じ <math>\lambda\, </math> と<math>\mu\, </math> をもった M/M/1 モデルの平均待ち時間を <math>\mbox{E}(W_q^{\rm M/M/1} )\, </math> とすれば


<center>
<math>
\mbox{E}(W_q^{\rm M/G/1}) = \frac{1}{2} (1+c^2) \mbox{E}(W_q^{\rm M/M/1})
\, </math>　　　　　<math>(3)\, </math>
</center>


と書ける. これは M/G/1 モデルではサービス時間分布のばらつきが大きいほど長く待たされることを示しており, 最も平均待ち時間が短いのはサービス時間が一定のときで, M/M/1 の 1/2 であることが確かめられる. 


'''M/G/1型待ち行列モデルの解析'''　以下, M/G/1 モデルとその類似モデルの解析について, いくつかコメントしておこう. 

　M/G/1 モデルから派生する種々の待ち行列モデルを, M/G/1 型待ち行列モデルと呼ぶ. 例えば, 有限待合室モデル (M/G/1/<math>m\, </math>), 有限呼源モデル (M<math>({\it n}) \, </math>/G/1), 集団到着個別処理モデル (M<math>^{[X]}\, </math>/G/1), 休暇時間 (準備時間) を伴う待ち行列([[バケーション|バケーションモデル]]) などはM/G/1 型待ち行列モデルである. また複数個の待ち行列をもつモデル, たとえば多重待ち行列([[ポーリングモデル]]), 優先権のある待ち行列, 移動扱い者によって処理される直列型(網型)の待ち行列などもM/G/1 型待ち行列モデルと考えることができる. M/G/1 モデルの双対的な待ち行列モデルとして, GI/M/1 モデルを考えることもある. 

　M/G/1 モデルやM/G/1 型モデルの常套的な解析法として, 客のサービス終了直後における系内人数に着目する[[隠れマルコフ連鎖法]]や, 系内人数の他に残りサービス時間 (あるいはサービス経過時間)を状態変数として取り入れる[[補助変数法]]が知られている. また, [[PASTA]]が成立するのも特徴の一つである. 

　待ち行列モデル M/G/1 において, 非割り込みのサービス規律 (先着順, ランダム順など) の下で, 客の退去時点 (サービス終了時点) 直後における系内客数の定常分布 <math>\{\pi_j\}\, </math> の母関数 <math>\Pi(z)\, </math> は


<center>
<math>
\Pi(z) = \frac{\pi_0  (1-z)}{1-z/H^*(\lambda(1-z))}, \ \ \ \pi_0 = 1
-\rho
\, </math>　　　　　<math>(4)\, </math>
</center>


で与えられる. 先着順サービスの下では, ある客 C の系内滞在時間 <math>\Theta\, </math>内に到着する客数と C の退去時点の系内客数は等しく, かつ C の系内時間<math>\Theta\, </math> と C の到着以降の到着過程 <math>\{ N_{\tau}(t)\}\, </math> は独立であるから, <math>\Theta\, </math> の定常分布 <math>\Theta(x)\, </math> のラプラス・スチルチェス変換を <math>\Theta^*(s)\, </math> と表せば, 


<center>
<math>
\Pi(z) = \Theta^*(\lambda(1-z))
       = W_q^*(\lambda(1-z)) H^*(\lambda(1-z))
\, </math>　　　　　<math>(5)\, </math>
</center>


の関係が成立し, 式 (4), (5) より,  ポラチェック・ヒンチンの公式 (1) が得られる [1], [3]. 

　<math>W_q^*(s)\, </math> の構造に確率的解釈を与え, 上記のように <math>\Pi(z)\, </math> を介さないで直接的に求める手法として, 全稼働期間解析法 (busy period analysis) がある. これは優先権のある待ち行列の解析に有効であり, 各種の全稼働期間中に到着する客の条件付き待ち時間分布のラプラス・スチルチェス変換<math>W_q^*(s| \mbox{busy period})\, </math> を基本として <math>W_q^*(s)\, </math> を構成するものである. これによれば


<center>
<table>
<tr><td rowspan="2"><math>W_q^*(s) \,\, </math></td>
<td><math>= (1-\rho) W_q^*(s | \mbox{idle period}\, </math> に到着 
<math>\ ) + \rho W_q^*(s | \mbox{busy period}\, </math>に到着<math>\ ) \, </math></td></tr>
<tr><td><math>= (1-\rho) \cdot 1 + \rho \cdot R^*(s) 
\cdot s(1-\rho)/ \left[ s-\lambda+\lambda H^*(s)
\right]\, </math>　　　　　<math>(6)\, </math></td></tr></table>
</center>


となる [1], [3]. ただし <math>R^*(s)\, </math> は, 残余サービス時間分布


<center>
<math>
R(t) = \frac{1}{\mathrm{E}(B_r)}
         \int_{0}^{t} \left[ 1-H(x) \right] \mathrm{d} x
         \ \ \ \ (t \geq 0)
\, </math>　　　　　<math>(7)\, </math>
</center>


のラプラス・スチルチェス変換で, <math> R^*(s) = \mu \left[ 1-H^*(s) \right]/ s \,</math>で与えられる. 

　時刻 <math>t\, </math> に仮に客が到着したとすればその客が待たなければならない時間 <math>v(t)\, </math> は, 仮り待ち時間 (virtual waiting time) と呼ばれる. 時刻<math>t\, </math> における仮り待ち時間の分布関数 <math>V(t, x)\, </math>, <math>x, t \geq 0\, </math> に関して, 次のタカッチの積分-微分方程式 (Tak\'{a}cs' integro-differential equation) が成立する [1]. 


<center>
<math>
\frac{\partial V(t, x)}{\partial t}
   =  \frac{\partial V(t, x)}{\partial x}
     -\lambda \left[
            V(t, x) -\int_{0-}^{x} H(x-y) \mathrm{d}_y V(t, y)
              \right]
\, </math>　　　　　<math>(8)\, </math>
</center>


平衡状態 (<math>t \rightarrow \infty\, </math>) における仮り待ち時間の分布関数<math>V(x)\, </math>のラプラス・スチルチェス変換 <math>V^*(s)\, </math> と表わし, 式(8)の左辺を零とおけば、次のレベルクロッシング法[5]の公式 (level-crossing formula) が得られる. これを,<math>V^*(0)=1\, </math>の下に解いて<math>V^*(s)\, </math>が決定される. 

<center>
<math>
\frac{dV(x)}{dx}
   =  \lambda \int_{0-}^x  \left\{ 1-H(x-y)\right\} \mathrm{d} V(y) \ \ \ \ ( x > 0 )
\, </math>　　　　　<math>(9)\, </math>
</center>


　M/G/1 モデルでは PASTA が成立するので <math>W_q^*(s) = V^*(s)\, </math> であり, このようにしても式(1) の<math>W_q^*(s)\, </math> が求められる. さらに, 客の到着が一般分布 <math>F(t)\, </math> に従う GI/G/1モデルにおける[[リンドレーの方程式|リンドレーの積分方程式]] (Lindley's equation)

<center>
<math>
W_q(t) = \left\{
\begin{array}{ll}
\displaystyle\int^{\infty}_{0-} C(t-x) \mathrm{d} W_q(x) & (t \geq 0) \\
 0                                                        & (t < 0)
\end{array}
\right. 
\, </math>　　　　　<math>(10)\, </math>
</center>


<center>
<math>
        C(t)=\int^{\infty}_{x=0} H(t+x) \mathrm{d} F(x)
            \ \ \ -\infty < t < +\infty
\, </math>　　　　　<math>(11)\, </math>
</center>


やタカッチの公式 (Tak&aacute;cs' formula)


<center>
<math>\begin{array}{lll}
V^*(s) & = &(1-\rho) V^*(s | \mbox{idle period} )
              + \rho V^*(s | \mbox{busy period} ) \\
       & = & 1-\rho + \rho R^*(s) W_q^*(s)
\end{array}\, </math>　　　　　<math>(12)\, </math>
</center>


を利用しても <math>W_q^*(s)\, </math> が直接的に求められる [1], [2]. 式 (12) は, M/G/1 における式 (6) の GI/G/1 への一般化であり, さらに一般的な到着過程として定常性のみを仮定した G/G/1 においても成立することが示されている. 本式と <math>W_q^*(s) = V^*(s)\, </math> より直ちにポラチェック・ヒンチンの公式を得る. 

　なお, 式 (1) の<math>W_q^*(s)\, </math> の逆変換形 <math>W_q(t)\, </math> の一つとして次式が知られている. 


<center>
<math>
W_q(t) = (1-\rho) \sum_{k=0}^{\infty} \rho^k R_k(t) \ \ \ \ ( t\geq 0 )
\, </math>　　　　　<math>(13)\, </math>
</center>


ただし <math>R_0(t) = 1\, </math> で, <math>R_k(t)\, </math> は式 (7) の残余サービス時間分布 <math>R(t)\, </math> 自身の<math>k(\geq1)\, </math> 回のたたみこみを表す[1], [4]. 



----

'''参考文献'''

[1] L. Kleinrock, ''Queueing Systems Vol. 1: Theory,'' John Wiley & Sons, 1975. 

[2] L. Tak&aacute;cs, "The Limiting Distribution of the Virtual Waiting Time and the Queue Size for a Single-Server Queue with Recurrent Input and General Service Times," ''Sankhya'', Series '''A25''' (1963), 91-100. 

[3] H. Takagi, ''Queueing Analysis :A Foundation of Performance Evaluation Vol. 1, Vacation and Priority Systems, Part I,'' Elsevier Science Publisher B. V., North-Holland, 1991. 

[4] N. U. Prabhu, ''Foundation of Queueing Theory,'' Kluwer Academic Publishers, 1997.

[5] B. Doshi: Level-crossing Analysis of Queues, ''Queueing and related models'', edited by U. N. Bhat and I. V. Basawa, Oxford University Press (1992), 3-33.

[[category:待ち行列|まちぎょうれつもでるM/G/1]]