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

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

待ち行列モデル M/G/1

読み方まちぎょうれつもでるえむじーわん
【英】:queueing model M/G/1

概要

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

詳説

 待ち行列モデル M/G/1 (queueing model M/G/1) は, 客の到着到着率 \lambda\, ポアソン過程従い, サービス時間一般分布 H(t)\, に従う, 窓口1個 (扱い1人) の無限長の待ち行列を許す最も基本的なモデルである.

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

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



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


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


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



\mbox{E}(W_q) = \frac{\rho (1+c^2)}{2 \mu (1-\rho)}
\,      (2)\,


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

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



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


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


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

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

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

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



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


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



\Pi(z) = \Theta^*(\lambda(1-z))
       = W_q^*(\lambda(1-z)) H^*(\lambda(1-z))
\,      (5)\,


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

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


W_q^*(s) \,\, = (1-\rho) W_q^*(s | \mbox{idle period}\, 到着 \ ) + \rho W_q^*(s | \mbox{busy period}\, 到着\ ) \,
= (1-\rho) \cdot 1 + \rho \cdot R^*(s) 
\cdot s(1-\rho)/ \left[ s-\lambda+\lambda H^*(s)
\right]\,      (6)\,


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



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


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

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



\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]
\,      (8)\,


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


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


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


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. 
\,      (10)\,



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


やタカッチの公式 (Takács' formula)


\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}\,      (12)\,


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

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



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


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



参考文献

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

[2] L. Taká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.




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

辞書ショートカット

すべての辞書の索引

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

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

   

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



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

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

©2025 GRAS Group, Inc.RSS