待ち行列モデル 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 _{0-}^{\infty }C(t-x)\mathrm {d} W_{q}(x)&(t\geq 0)\\0&(t<0)\end{array}}\right.\,$　　　　　$(10)\,$

$C(t)=\int _{x=0}^{\infty }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(\geq 1)\,$ 回のたたみこみを表す[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.