「《待ち行列における関係式》」の版間の差分

2008年8月5日 (火) 19:08時点における最新版

【まちぎょうれつにおけるかんけいしき (qualitative relations in queuing theory)】

リトルの公式　待ち行列における関係式の中で, 最も基本的なものひとつに, リトルの公式 (Little's formula) がある [5] この公式は, 任意の待ち行列システムに対して, 平衡状態における平均系内人数 ${\mbox{E}}(L)\,$ と平衡状態における平均系内滞在時間 ${\mbox{E}}(W)\,$ とを関係づけるものである. $\lambda \,$ をシステムへの到着率とすると, ${\mbox{E}}(W\,$ ) か ${\mbox{E}}(L)\,$ のどちらか一方が存在するならば, 他方も存在し,

${\mbox{E}}(L)=\lambda {\mbox{E}}(W)\,\,$ 　　　　　 $(1)\,$

となる.

　この公式はシステムが平衡状態にあることを除けば, 客の到着, サービス時間, サーバ数, サービス規律等に特に何の仮定もおいていない. システムが単一ノードである必要もない. たとえばシステムとして単一窓口待ち行列の窓口部分だけを考えれば, ${\mbox{P}}\,$ (窓口が塞がっている確率) $=\lambda {\mbox{E}}(S)=\rho \,$ が得られる. ここで ${\mbox{E}}(S)\,$ は平均サービス時間である. また, システムとして窓口を除いた待ち行列の部分を考えれば, (1) は, 平均待ち人数 ${\mbox{E}}(L_{q})\,$ と平均待ち時間 ${\mbox{E}}(W_{q})\,$ に対して

${\mbox{E}}(L_{q})=\lambda {\mbox{E}}(W_{q})\,\,$ 　　　　　 $(2)\,$

となる. 通常, ${\mbox{E}}(W)={\mbox{E}}(W_{q})+{\mbox{E}}(S)\,$ であり, システムへの到着率 $\lambda \,$ は既知であるので, (1) と (2) から, ${\mbox{E}}(L)\,$ , ${\mbox{E}}(L_{q})\,$ , ${\mbox{E}}(W)\,$ , E $(W_{q})\,$ の4つの特性量のうちひとつがわかれば, 他のものはこれらの関係式から求められる. これは待ち行列モデルを解析するときに大変便利である.

　リトルの公式は待ち行列解析のいろいろな場面で頻繁に出現し, たとえば閉ジャクソンネットワークを解析するときに用いられる平均値解析法は, このリトルの公式を様々な形で利用することによって導かれる.

PASTA　リトルの公式と並んで, 待ち行列の解析に重要な役割を果たす関係にPASTA (パスタ) がある [9]. PASTAは Poisson Arrivals See Time Averagesの略で, ポアソン到着を仮定した待ち行列システムにおいて, 到着時点でシステムがある状態にいる割合は長い時間の中で過程がその状態にいる割合と等しい, という関係である. すなわち, ポアソン到着ならば, 到着時点分布と任意時点分布が等しいことを意味している. PASTAを用いれば, 例えば客の呼損率を求める場合, 客の到着時点のシステムの状態を求めなくても, 任意時点の状態から計算することができ, 非常に有効である.

クラインロックの保存則　任意の複数クラス, 単一サーバ待ち行列G/GI/1システムを考える. クラスの数を $C\,$ とし, クラス $c\,$ の到着率が $\lambda _{c}\,$ , サービス時間 $S_{c}\,$ は独立で同一分布に従うならば, 平均残余仕事量( ${\mbox{E}}V\,$ ) (時間平均) は次式で与えられる.

${\mbox{E}}(V)=\sum _{c=1}^{C}\left[{\mbox{E}}(L_{qc}){\mbox{E}}(S_{c})+\rho _{c}\,{\mbox{E}}(S_{c}^{2})/2{\mbox{E}}(S_{c})\right]\,$ 　　　　　 $(3)\,$

ここで, クラス $c\,$ に対しE $(L_{qc})\,$ は平均待ち行列長 (時間平均), E $(S_{c})\,$ , E $(S_{c}^{2})\,$ はサービス時間の1, 2次積率, $\rho _{c}\ (=\lambda _{c}{\mbox{E}}(S_{c}))\,$ はトラヒック密度である. この関係式はクラインロックの保存則 (Kleinrock's conservation law) と呼ばれる [3].

　(3) にリトルの公式 (2) を適用すると　

$\sum _{c=1}^{C}\rho _{c}\,{\mbox{E}}(W_{qc})=\,$ 一定　　　　　 $(4)\,$

という関係式が得られる. ここで ${\mbox{E}}(W_{qc})\,$ はクラスc の客の平均待ち時間, $\rho _{c}=\lambda _{c}\,{\mbox{E}}(S_{c})\,$ はクラス $c\,$ の客の利用率である. この (4) は, 優先権などを用いてあるクラスの客の平均待ち時間を小さくしようとすると, かならず他のいずれかのクラスの客の平均待ち時間が長くなってしまうことを示している.

その他の関係式　リトルの公式やPASTAのように待ち行列システムの性能尺度や関連する確率過程の関係を表す式には, 他にもバークの定理, フィンチの定理等がある.

　このような関係式は特性量の間の関係を議論しているだけであり, 具体的に特性量の値そのものを導出するのには力不足, と見られたこともあったが, 点過程論 (point process theory) を用いると, 非マルコフシステムや複雑なシステムの解析において, 特性量の近似値を求めたりすることもできる. 例えば, 通常の GI/GI/1 待ち行列システムに対して, ブルメルの公式 (残余仕事量と待ち時間の関係式) と拡散近似を適用すると, 平均待ち時間の近似式が得られるが, これはポアソン入力 (M/GI/1 システム) の場合には厳密解に一致する. また, 多重待ち行列システムに対して擬保存則(歩行時間のあるサーバ巡回型システムに対する保存則)を用いると, 精度の良い平均待ち時間近似式が得られる.

　これらの関係式の研究は, 従来, 個別に行われていたが, 宮沢の率保存則 (rate conservation law) [8] の発見以降, それらは統一的に扱うことが可能になってきた. 従来の率保存則は, たとえばKönigら [4] のように複雑な積分表現になっており, 扱いにくかった. 宮沢 [6] はKönigらの結果と等価な微分型の率保存則を見出した. 宮沢の率保存則により前述の関係式を初めとする待ち行列理論における殆ど全ての諸関係式が容易に求められることが分かって来た [2]. 率保存則の証明自体も最近では工夫されている. 当初はパルムの逆変換公式を用いた幾分難解なものだったが, その後, 宮沢 [7], Brémaud [1]により簡単化され, その理解には必ずしも実関数論を必要としないことが明らかにされている.

参考文献

[1] P. Brémaud, "An Elemantary Proof of Sengupta's Invariance Relation and a Remark on Miyazawa's Rate Conservation Principle," Journal of Applied Probability, 28 (1991), 950-954.

[2] 川島幸之助, 町原文明, 高橋敬隆, 斎藤洋, 『通信トラヒック理論の基礎とマルチメディア通信網』, 電子情報通信学会編, 1995.

[3] L. Kleinrock, Queueing Systems, Vol. II, John Wiley & Sons, 1976.

[4] D. König, T. Rolski, V. Schmidt and D. Stoyan, "Stochastic Processes with Imbedded Marked Point Processes (PMP) and Their Application in Queueing," Mathematische Operationsforschung und Statistik, Ser. Optimization, 9 (1978), 125-141.

[5] J. D. C. Little, "A Proof of the Queueing Formula L= \lambda W," Operations Research, 9 (1961), 383-387.

[6] M. Miyazawa, "The Derivation of Invariance Relations in Complex Queueing System with Stationary Input," Advanced Applied Probability, 15 (1983), 874-855.

[7] M. Miyazawa, "The Intensity Conservation Law for Queues with Randomly Changed Service Rate," Journal Applied Probability, 22 (1985), 408-418.

[8] 宮沢政清, 『待ち行列の数理とその応用』, 牧野書店, 2006.

[9] R. W. Wolff, "Poisson Arrivals See Time Averages,"Operations Research, 30 (1982), 223-231.

@@ 1行目: / 1行目: @@
 '''【まちぎょうれつにおけるかんけいしき (qualitative relations in queuing theory)】'''
-'''リトルの公式'''　待ち行列における関係式の中で, 最も基本的なものひとつに, [[リトルの公式]] (Little's formula) がある [5] この公式は, 任意の待ち行列システムに対して, 平衡状態における平均系内人数 E$<math>(L)</math>$ と平衡状態における平均系内滞在時間 $<math>\mbox{E}(W)</math>$ とを関係づけるものである. $<math>\lambda</math>$ をシステムへの到着率とすると, $<math>\mbox{E}(W</math>)$ か $<math>\mbox{E}(L)</math>$ のどちらか一方が存在するならば, 他方も存在し,
+'''リトルの公式'''　待ち行列における関係式の中で, 最も基本的なものひとつに, [[リトルの公式]] (Little's formula) がある [5] この公式は, 任意の待ち行列システムに対して, 平衡状態における平均系内人数 <math>\mbox{E}(L)\, </math> と平衡状態における平均系内滞在時間 <math>\mbox{E}(W)\, </math> とを関係づけるものである. <math>\lambda\, </math> をシステムへの到着率とすると, <math>\mbox{E}(W\, </math>) か <math>\mbox{E}(L)\, </math> のどちらか一方が存在するならば, 他方も存在し,
-:<math>
+<center>
+<math>
 \mbox{E}(L) = \lambda \mbox{E}(W) \,
-</math>　　　　　<math>(1)\, </math>
+\, </math>　　　　　<math>(1)\, </math>
+</center>
 となる.
-　この公式はシステムが平衡状態にあることを除けば, 客の到着, サービス時間, サーバ数, サービス規律等に特に何の仮定もおいていない. システムが単一ノードである必要もない. たとえばシステムとして単一窓口待ち行列の窓口部分だけを考えれば, $<math>\mbox{P}(窓口が塞がっている確率)=\lambda \mbox{E}(S)=\rho</math>$ が得られる. ここで $<math>\mbox{E}(S)</math>$ は平均サービス時間である. また, システムとして窓口を除いた待ち行列の部分を考えれば, (1) は, 平均待ち人数 E$<math>(L_q)</math>$ と平均待ち時間 $<math>\mbox{E}(W_q)</math>$ に対して
+　この公式はシステムが平衡状態にあることを除けば, 客の到着, サービス時間, サーバ数, サービス規律等に特に何の仮定もおいていない. システムが単一ノードである必要もない. たとえばシステムとして単一窓口待ち行列の窓口部分だけを考えれば, <math>\mbox{P}\, </math>(窓口が塞がっている確率)<math>=\lambda \mbox{E}(S)=\rho\, </math> が得られる. ここで <math>\mbox{E}(S)\, </math> は平均サービス時間である. また, システムとして窓口を除いた待ち行列の部分を考えれば, (1) は, 平均待ち人数 <math>\mbox{E}(L_q)\, </math> と平均待ち時間 <math>\mbox{E}(W_q)\, </math> に対して
-:<math>
+<center>
+<math>
 \mbox{E}(L_q) = \lambda \mbox{E}(W_q) \,
-</math>　　　　　<math>(2)\, </math>
+\, </math>　　　　　<math>(2)\, </math>
+</center>
-となる. 通常, $<math>\mbox{E}(W)=\mbox{E}(W_q)+\mbox{E}(S)</math>$であり, システムへの到着率$<math>\lambda</math>$は既知であるので, (1) と (2) から, E$<math>(L)</math>$, E$<math>(L_q)</math>$, E$<math>(W)</math>$, E<math>$(W_q)</math>$の4つの特性量のうちひとつがわかれば, 他のものはこれらの関係式から求められる. これは待ち行列モデルを解析するときに大変便利である.
+となる. 通常, <math>\mbox{E}(W)=\mbox{E}(W_q)+\mbox{E}(S)\, </math>であり, システムへの到着率<math>\lambda\, </math>は既知であるので, (1) と (2) から, <math>\mbox{E}(L)\, </math>, <math>\mbox{E}(L_q)\, </math>, <math>\mbox{E}(W)\, </math>, E<math>(W_q)\, </math>の4つの特性量のうちひとつがわかれば, 他のものはこれらの関係式から求められる. これは待ち行列モデルを解析するときに大変便利である.
-　リトルの公式は待ち行列解析のいろいろな場面で頻繁に出現し, たとえば[[閉ジャクソンネットワーク]]を解析するときに用いられる[[平均値解析法]]は, このリトルの公式を様々な形で利用することによって導かれる.
+　リトルの公式は待ち行列解析のいろいろな場面で頻繁に出現し, たとえば[[ジャクソンネットワーク|閉ジャクソンネットワーク]]を解析するときに用いられる[[平均値解析法]]は, このリトルの公式を様々な形で利用することによって導かれる.
-'''PASTA'''　リトルの公式と並んで, 待ち行列の解析に重要な役割を果たす関係に[[PASTA]] (パスタ) がある [8]. PASTAは Poisson Arrivals See Time Averagesの略で, ポアソン到着を仮定した待ち行列システムにおいて, 到着時点でシステムがある状態にいる割合は長い時間の中で過程がその状態にいる割合と等しい, という関係である. すなわち, ポアソン到着ならば, 到着時点分布と任意時点分布が等しいことを意味している. PASTAを用いれば, 例えば客の呼損率を求める場合, 客の到着時点のシステムの状態を求めなくても, 任意時点の状態から計算することができ, 非常に有効である.
+'''PASTA'''　リトルの公式と並んで, 待ち行列の解析に重要な役割を果たす関係に[[PASTA]] (パスタ) がある [9]. PASTAは Poisson Arrivals See Time Averagesの略で, ポアソン到着を仮定した待ち行列システムにおいて, 到着時点でシステムがある状態にいる割合は長い時間の中で過程がその状態にいる割合と等しい, という関係である. すなわち, ポアソン到着ならば, 到着時点分布と任意時点分布が等しいことを意味している. PASTAを用いれば, 例えば客の呼損率を求める場合, 客の到着時点のシステムの状態を求めなくても, 任意時点の状態から計算することができ, 非常に有効である.
-'''クラインロックの保存則'''　任意の複数クラス, 単一サーバ待ち行列G/GI/1システムを考える. クラスの数を$<math>C</math>$とし, クラス$<math>c</math>$ の到着率が $<math>\lambda_c</math>$, サービス時間$<math>S_c</math>$は独立で同一分布に従うならば, 平均残余仕事量E($<math>V</math>$) (時間平均) は次式で与えられる.
+'''クラインロックの保存則'''　任意の複数クラス, 単一サーバ待ち行列G/GI/1システムを考える. クラスの数を<math>C\, </math>とし, クラス<math>c\, </math> の到着率が <math>\lambda_c\, </math>, サービス時間<math>S_c\, </math>は独立で同一分布に従うならば, 平均残余仕事量(<math>\mbox{E}V\, </math>) (時間平均) は次式で与えられる.
-:<math>
+<center>
+<math>
 \mbox{E}(V) = \sum_{c = 1}^C \left[ \mbox{E}(L_{qc}) \mbox{E}(S_c) +
 \rho_c \, \mbox{E}(S_c^2) / 2 \mbox{E}(S_c)\right]
-</math>　　　　　<math>(3)\, </math>
+\, </math>　　　　　<math>(3)\, </math>
+</center>
-ここで, クラス$<math>c</math>$に対しE$<math>(L_{qc})</math>$は平均待ち行列長 (時間平均), E$<math>(S_c)</math>$, E$<math>(S_c^2)</math>$ はサービス時間の1, 2次積率, $<math>\rho_c \ (= \lambda_c \mbox{E} (S_c))</math>$ はトラヒック密度である. この関係式は[[クラインロックの保存則]] (Kleinrock's conservation law) と呼ばれる [3].
+ここで, クラス<math>c\, </math>に対しE<math>(L_{qc})\, </math>は平均待ち行列長 (時間平均), E<math>(S_c)\, </math>, E<math>(S_c^2)\, </math> はサービス時間の1, 2次積率, <math>\rho_c \ (= \lambda_c \mbox{E} (S_c))\, </math> はトラヒック密度である. この関係式は[[クラインロックの保存則]] (Kleinrock's conservation law) と呼ばれる [3].
 　(3) にリトルの公式 (2) を適用すると
-:<math>
+<center>
+<math>
 \sum_{c = 1}^C \rho_c\, \mbox{E}(W_{qc}) =
-</math>一定　　　　　<math>(4)\, </math>
+\, </math>一定　　　　　<math>(4)\, </math>
+</center>
-という関係式が得られる. ここで $<math>\mbox{E}(W_{qc})</math>$ はクラス$c$ の客の平均待ち時間,  $<math>\rho_c = \lambda_c \, \mbox{E}(S_c)</math>$ はクラス $<math>c</math>$ の客の利用率である. この (4) は, 優先権などを用いてあるクラスの客の平均待ち時間を小さくしようとすると, かならず他のいずれかのクラスの客の平均待ち時間が長くなってしまうことを示している.
+という関係式が得られる. ここで <math>\mbox{E}(W_{qc})\, </math> はクラスc の客の平均待ち時間,  <math>\rho_c = \lambda_c \, \mbox{E}(S_c)\, </math> はクラス <math>c\, </math> の客の利用率である. この (4) は, 優先権などを用いてあるクラスの客の平均待ち時間を小さくしようとすると, かならず他のいずれかのクラスの客の平均待ち時間が長くなってしまうことを示している.
 '''その他の関係式'''　リトルの公式やPASTAのように待ち行列システムの性能尺度や関連する確率過程の関係を表す式には, 他にも[[バークの定理]], フィンチの定理等がある.
-　このような関係式は特性量の間の関係を議論しているだけであり, 具体的に特性量の値そのものを導出するのには力不足, と見られたこともあったが, [[点過程論]] (point process theory) を用いると, 非マルコフシステムや複雑なシステムの解析において, 特性量の近似値を求めたりすることもできる. 例えば, 通常の GI/GI/1 待ち行列システムに対して, ブルメルの公式 (残余仕事量と待ち時間の関係式) と[[拡散近似]]を適用すると, 平均待ち時間の近似式が得られるが, これはポアソン入力 (M/GI/1 システム) の場合には厳密解に一致する. また, 多重待ち行列システムに対して擬保存則(歩行時間のあるサーバ巡回型システムに対する保存則)を用いると, 精度の良い平均待ち時間近似式が得られる.
+　このような関係式は特性量の間の関係を議論しているだけであり, 具体的に特性量の値そのものを導出するのには力不足, と見られたこともあったが, [[点過程|点過程論]] (point process theory) を用いると, 非マルコフシステムや複雑なシステムの解析において, 特性量の近似値を求めたりすることもできる. 例えば, 通常の GI/GI/1 待ち行列システムに対して, ブルメルの公式 (残余仕事量と待ち時間の関係式) と[[拡散近似]]を適用すると, 平均待ち時間の近似式が得られるが, これはポアソン入力 (M/GI/1 システム) の場合には厳密解に一致する. また, 多重待ち行列システムに対して擬保存則(歩行時間のあるサーバ巡回型システムに対する保存則)を用いると, 精度の良い平均待ち時間近似式が得られる.
-　これらの関係式の研究は, 従来, 個別に行われていたが, 宮沢の[[率保存則]] (rate conservation law) の発見以降, それらは統一的に扱うことが可能になってきた. 従来の率保存則は, たとえばK&ouml;nigら [4] のように複雑な積分表現になっており, 扱いにくかった. 宮沢 [6] はK&ouml;nigらの結果と等価な微分型の率保存則を見出した. 宮沢の率保存則により前述の関係式を初めとする待ち行列理論における殆ど全ての諸関係式が容易に求められることが分かって来た [2]. 率保存則の証明自体も最近では工夫されている. 当初はパルムの逆変換公式を用いた幾分難解なものだったが, その後, 宮沢 [7], Br&eacute; [1]により簡単化され, その理解には必ずしも実関数論を必要としないことが明らかにされている.
+　これらの関係式の研究は, 従来, 個別に行われていたが, 宮沢の[[率保存則]] (rate conservation law) [8] の発見以降, それらは統一的に扱うことが可能になってきた. 従来の率保存則は, たとえばK&ouml;nigら [4] のように複雑な積分表現になっており, 扱いにくかった. 宮沢 [6] はK&ouml;nigらの結果と等価な微分型の率保存則を見出した. 宮沢の率保存則により前述の関係式を初めとする待ち行列理論における殆ど全ての諸関係式が容易に求められることが分かって来た [2]. 率保存則の証明自体も最近では工夫されている. 当初はパルムの逆変換公式を用いた幾分難解なものだったが, その後, 宮沢 [7], Br&eacute;maud [1]により簡単化され, その理解には必ずしも実関数論を必要としないことが明らかにされている.
@@ 68行目: / 76行目: @@
 [4] D. K&ouml;nig, T. Rolski, V. Schmidt and D. Stoyan, "Stochastic Processes with Imbedded Marked Point Processes (PMP) and Their Application in Queueing," ''Mathematische Operationsforschung und Statistik, Ser. Optimization'', '''9''' (1978), 125-141.
-[5] J. D. C. Little, "A Proof of the Queueing Formula $L= \lambda W$," ''Operations Research'', '''9''' (1961), 383-387.
+[5] J. D. C. Little, "A Proof of the Queueing Formula L= \lambda W," ''Operations Research'', '''9''' (1961), 383-387.
 [6] M. Miyazawa, "The Derivation of Invariance Relations in Complex Queueing System with Stationary Input," ''Advanced Applied Probability'', '''15''' (1983), 874-855.
@@ 74行目: / 82行目: @@
 [7] M. Miyazawa, "The Intensity Conservation Law for Queues with Randomly Changed Service Rate," ''Journal Applied Probability'', '''22''' (1985), 408-418.
-[8] R. W. Wolff, "Poisson Arrivals See Time Averages,"''Operations Research'', '''30''' (1982), 223-231.
+[8] 宮沢政清, 『待ち行列の数理とその応用』, 牧野書店, 2006.
+[9] R. W. Wolff, "Poisson Arrivals See Time Averages,"''Operations Research'', '''30''' (1982), 223-231.
+[[category:待ち行列|まちぎょうれつにおけるかんけいしき]]

「《待ち行列における関係式》」の版間の差分

2008年8月5日 (火) 19:08時点における最新版

案内メニュー

検索