《待ち行列モデル M/G/1》 - 版の履歴

2007年8月9日 (木) 02:01にSakasegawaによる

2007-08-09T02:01:10Z

2007年8月8日 (水) 15:52にBassyによる

2007-08-08T15:52:02Z

2007年8月6日 (月) 18:18にKuwashimaによる

2007-08-06T18:18:54Z

2007年8月6日 (月) 15:08にBassyによる

2007-08-06T15:08:11Z

2007年8月6日 (月) 09:04にBassyによる

2007-08-06T09:04:07Z

2007年8月6日 (月) 05:08にOrsjwikiによる

2007-08-06T05:08:30Z

Orsjwiki: "《待ち行列モデル M/G/1》" を保護しました。 [edit=sysop:move=sysop]

2007-07-19T13:50:57Z

"《待ち行列モデル M/G/1》" を保護しました。 [edit=sysop:move=sysop]

2007年7月19日 (木) 04:27に122.17.2.240による

2007-07-19T04:27:34Z

2007年7月17日 (火) 04:54に122.17.2.240による

2007-07-17T04:54:25Z

2007年7月12日 (木) 13:25に122.17.2.240による

2007-07-12T13:25:38Z

差分を表示

@@ 181行目: / 181行目: @@
 [1] L. Kleinrock, ''Queueing Systems Vol. 1: Theory,'' John Wiley & Sons, 1975.
-[2] L. ak&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.
+[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.

@@ 120行目: / 120行目: @@
 <math>
 \frac{dV(x)}{dx}
-    =  \lambda \int_{0-}^x  [{1-H(x-y)}] \mathrm{d} V(y) \ \ \ \ ( x > 0 )
+    =  \lambda \int_{0-}^x  \left\{ 1-H(x-y)\right\} \mathrm{d} V(y) \ \ \ \ ( x > 0 )
 \, </math>　　　　　<math>(9)\, </math>
 </center>

← 古い版		2007年8月6日 (月) 18:18時点における版
188行目:		188行目:

	[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.		[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]]

@@ 99行目: / 99行目: @@
-のラプラス・スチルチェス変換で,  R^*(s) = \mu \left[ 1-H^*(s) \right]/ s で与えられる.
+のラプラス・スチルチェス変換で, <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].
@@ 120行目: / 120行目: @@
 <math>
 \frac{dV(x)}{dx}
-    =  \lambda \int_{0-}^x {1-H(x-y)} \mathrm{d} V(y) \ \ \ \ ( x > 0 )
+    =  \lambda \int_{0-}^x  [{1-H(x-y)}] \mathrm{d} V(y) \ \ \ \ ( x > 0 )
 \, </math>　　　　　<math>(9)\, </math>
 </center>

@@ 73行目: / 73行目: @@
 の関係が成立し, 式 (4), (5) より,  ポラチェック・ヒンチンの公式 (1) が得られる [1], [3].
-　<math>W^*(s)\, </math> の構造に確率的解釈を与え, 上記のように <math>\Pi(z)\, </math> を介さないで直接的に求める手法として, 全稼働期間解析法 (busy period analysis) がある. これは優先権のある待ち行列の解析に有効であり, 各種の全稼働期間中に到着する客の条件付き待ち時間分布のラプラス・スチルチェス変換<math>W^*(s| \mbox{busy period})\, </math> を基本として <math>W^*(s)\, </math> を構成するものである. これによれば
+　<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^*(s) \,\, </math></td>
+<tr><td rowspan="2"><math>W_q^*(s) \,\, </math></td>
-<td><math>= (1-\rho) W^*(s | \mbox{idle period}\, </math> に到着
+<td><math>= (1-\rho) W_q^*(s | \mbox{idle period}\, </math> に到着
-<math>\ ) + \rho W^*(s | \mbox{busy period}\, </math>に到着<math>\ ) \, </math></td></tr>
+<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)
@@ 94行目: / 94行目: @@
 R(t) = \frac{1}{\mathrm{E}(B_r)}
           \int_{0}^{t} \left[ 1-H(x) \right] \mathrm{d} x
-          \ \ \ \ t \geq 0
+          \ \ \ \ (t \geq 0)
 \, </math>　　　　　<math>(7)\, </math>
 </center>
@@ 115行目: / 115行目: @@
-平衡状態 (<math>t \rightarrow \infty\, </math>) における仮り待ち時間の分布関数<math>V(x)\, </math>のラプラス・スチルチェス変換 <math>V^*(s)\, </math> は, 式(8)の左辺を零としてこれを解いて求められる. M/G/1 モデルでは PASTA が成立するので <math>W^*(s) = V^*(s)\, </math> であり, このようにしても式(1) の<math>W^*(s)\, </math> が求められる. さらに, 客の到着が一般分布 <math>F(t)\, </math> に従う GI/G/1モデルにおける[[リンドレーの方程式|リンドレーの積分方程式]] (Lindley's equation)
+平衡状態 (<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>
-W(t) = \left\{
+\frac{dV(x)}{dx}
 \begin{array}{ll}
-\displaystyle\int^{\infty}_{0-} C(t-x) \mathrm{d} W(x) & (t \geq 0) \\
+\displaystyle\int^{\infty}_{0-} C(t-x) \mathrm{d} W_q(x) & (t \geq 0) \\
                                                         & (t < 0)
 \end{array}
 \right.
-\, </math>　　　　　<math>(9)\, </math>
+\, </math>　　　　　<math>(10)\, </math>
 </center>
@@ 133行目: / 143行目: @@
          C(t)=\int^{\infty}_{x=0} H(t+x) \mathrm{d} F(x)
              \ \ \ -\infty < t < +\infty
-\, </math>　　　　　<math>(10)\, </math>
+\, </math>　　　　　<math>(11)\, </math>
 </center>
@@ 144行目: / 154行目: @@
 V^*(s) & = &(1-\rho) V^*(s | \mbox{idle period} )
                + \rho V^*(s | \mbox{busy period} ) \\
-        & = & 1-\rho + \rho R^*(s) W^*(s)
+        & = & 1-\rho + \rho R^*(s) W_q^*(s)
-\end{array}\, </math>　　　　　<math>(11)\, </math>
+\end{array}\, </math>　　　　　<math>(12)\, </math>
 </center>
-を利用しても <math>W^*(s)\, </math> が直接的に求められる [1], [2]. 式 (11) は, M/G/1 における式 (6) の GI/G/1 への一般化であり, さらに一般的な到着過程として定常性のみを仮定した G/G/1 においても成立することが示されている. 本式と <math>W^*(s) = V^*(s)\, </math> より直ちにポラチェック・ヒンチンの公式を得る.
+を利用しても <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^*(s)\, </math> の逆変換形 <math>W(t)\, </math> の一つとして次式が知られている.
+　なお, 式 (1) の<math>W_q^*(s)\, </math> の逆変換形 <math>W_q(t)\, </math> の一つとして次式が知られている.
 <center>
 <math>
-W(t) = (1-\rho) \sum_{k=0}^{\infty} \rho^k R_k(t) \ \ \ \ t \geq 0
+W_q(t) = (1-\rho) \sum_{k=0}^{\infty} \rho^k R_k(t) \ \ \ \ ( t\geq 0 )
-\, </math>　　　　　<math>(12)\, </math>
+\, </math>　　　　　<math>(13)\, </math>
 </center>
@@ 176行目: / 186行目: @@
 [4] N. U. Prabhu, ''Foundation of Queueing Theory,'' Kluwer Academic Publishers, 1997.

@@ 66行目: / 66行目: @@
 <math>
 \Pi(z) = \Theta^*(\lambda(1-z))
-        = W^*(\lambda(1-z)) H^*(\lambda(1-z))
+        = W_q^*(\lambda(1-z)) H^*(\lambda(1-z))
 \, </math>　　　　　<math>(5)\, </math>
 </center>

← 古い版	2007年7月19日 (木) 13:50時点における版
(相違点なし)

@@ 3行目: / 3行目: @@
 　[[待ち行列モデル 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) などのサービス規律を考えることもある.
+　客の到着間隔 <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)
+　先着順サービスの M/G/1 モデルでは, 平均サービス時間を <math>1/\mu\, </math> とすると, 利用率 <math>\rho=\lambda/\mu < 1\, </math> のときにシステムは安定となり, 時間の経過とともに[[平衡状態]]へ近づく. 平衡状態における客の待ち時間分布 <math>W_q(t)\, </math> は[[ポラチェック・ヒンチンの公式]] (Pollaczek-Khintchine formula)
@@ 45行目: / 45行目: @@
 '''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 型待ち行列モデルと呼ぶ. 例えば, 有限待合室モデル (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]]が成立するのも特徴の一つである.
@@ 115行目: / 115行目: @@
-平衡状態 (<math>t \rightarrow \infty\, </math>) における仮り待ち時間の分布関数<math>V(x)\, </math>のラプラス・スチルチェス変換 <math>V^*(s)\, </math> は, 式(8)の左辺を零としてこれを解いて求められる. M/G/1 モデルでは PASTA が成立するので <math>W^*(s) = V^*(s)\, </math> であり, このようにしても式(1) の<math>W^*(s)\, </math> が求められる. さらに, 客の到着が一般分布 <math>F(t)\, </math> に従う GI/G/1モデルにおける[[リンドレーの積分方程式]] (Lindley's equation)
+平衡状態 (<math>t \rightarrow \infty\, </math>) における仮り待ち時間の分布関数<math>V(x)\, </math>のラプラス・スチルチェス変換 <math>V^*(s)\, </math> は, 式(8)の左辺を零としてこれを解いて求められる. M/G/1 モデルでは PASTA が成立するので <math>W^*(s) = V^*(s)\, </math> であり, このようにしても式(1) の<math>W^*(s)\, </math> が求められる. さらに, 客の到着が一般分布 <math>F(t)\, </math> に従う GI/G/1モデルにおける[[リンドレーの方程式|リンドレーの積分方程式]] (Lindley's equation)
 <center>

@@ 8行目: / 8行目: @@
-:<math>
+<center>
 W_q^*(s) = (1-\rho)/ \{1-\lambda[1-H^*(s)]/s\}
 \, </math>　　　　　<math>(1)\, </math>
@@ 19行目: / 21行目: @@
-:<math>
+<center>
 \mbox{E}(W_q) = \frac{\rho (1+c^2)}{2 \mu (1-\rho)}
 \, </math>　　　　　<math>(2)\, </math>
@@ 29行目: / 33行目: @@
-:<math>
+<center>
 \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>
@@ 46行目: / 52行目: @@
-:<math>
+<center>
 \Pi(z) = \frac{\pi_0  (1-z)}{1-z/H^*(\lambda(1-z))}, \ \ \ \pi_0 = 1
 -\rho
 \, </math>　　　　　<math>(4)\, </math>
@@ 55行目: / 63行目: @@
-:<math>
+<center>
 \Pi(z) = \Theta^*(\lambda(1-z))
         = W^*(\lambda(1-z)) H^*(\lambda(1-z))
 \, </math>　　　　　<math>(5)\, </math>
@@ 66行目: / 76行目: @@
-:<table>
+<center>
 <tr><td rowspan="2"><math>W^*(s) \,\, </math></td>
 <td><math>= (1-\rho) W^*(s | \mbox{idle period}\, </math> に到着
@@ 73行目: / 84行目: @@
 \cdot s(1-\rho)/ \left[ s-\lambda+\lambda H^*(s)
 \right]\, </math>　　　　　<math>(6)\, </math></td></tr></table>
@@ 78行目: / 90行目: @@
-:<math>
+<center>
 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>
@@ 90行目: / 104行目: @@
-:<math>
+<center>
 \frac{\partial V(t, x)}{\partial t}
     =  \frac{\partial V(t, x)}{\partial x}
@@ 97行目: / 112行目: @@
                \right]
 \, </math>　　　　　<math>(8)\, </math>
 平衡状態 (<math>t \rightarrow \infty\, </math>) における仮り待ち時間の分布関数<math>V(x)\, </math>のラプラス・スチルチェス変換 <math>V^*(s)\, </math> は, 式(8)の左辺を零としてこれを解いて求められる. M/G/1 モデルでは PASTA が成立するので <math>W^*(s) = V^*(s)\, </math> であり, このようにしても式(1) の<math>W^*(s)\, </math> が求められる. さらに, 客の到着が一般分布 <math>F(t)\, </math> に従う GI/G/1モデルにおける[[リンドレーの積分方程式]] (Lindley's equation)
-:<math>
+<center>
 W(t) = \left\{
 \begin{array}{ll}
@@ 109行目: / 126行目: @@
 \right.
 \, </math>　　　　　<math>(9)\, </math>
-:<math>
+<center>
          C(t)=\int^{\infty}_{x=0} H(t+x) \mathrm{d} F(x)
              \ \ \ -\infty < t < +\infty
 \, </math>　　　　　<math>(10)\, </math>
@@ 120行目: / 140行目: @@
-:<math>\begin{array}{lll}
+<center>
 V^*(s) & = &(1-\rho) V^*(s | \mbox{idle period} )
                + \rho V^*(s | \mbox{busy period} ) \\
         & = & 1-\rho + \rho R^*(s) W^*(s)
 \end{array}\, </math>　　　　　<math>(11)\, </math>
@@ 132行目: / 154行目: @@
-:<math>
+<center>
 W(t) = (1-\rho) \sum_{k=0}^{\infty} \rho^k R_k(t) \ \ \ \ t \geq 0
 \, </math>　　　　　<math>(12)\, </math>