Word Whitt: The Queueing Network Analyzer（１３） - 工場統計力学（建設中！）

「Word Whitt: The Queueing Network Analyzer（１２）」の続きです。
今日も２ページ。

モーメントの代わりに我々は到着レート $\lambda$ と平均サービス時間 $\tau$ 、２乗変動係数 $c_a^2$ と $c_s^2$ を用いる。単一ノードに注目するので、このセクションの中ではノードを示す下付き添え字を省略する。

　この時点で適用することの出来る多くの手続きがある。我々は完全な分布に諸パラメータを合わせ*1次にGI/G/m待ち行列や特殊な場合を解くための任意の既存アルゴリズムを適用する。魅力的な選択肢の中には、Gi/G/1待ち行列を解析するための手続き*2やフェーズ型サービス時間分布を持つM/PH/m待ち行列 *3 *4 *5 *6 *7 *8や超指数サービス時間分布を持つGI/H_k/m待ち行列 *9 *10やアーラン・サービス時間分布を持つGI/E_k/m待ち行列 *11が存在する。高負荷極限や低負荷極限の振る舞いに基づいた近似もまた利用可能である。*12 *13しかし、QNAのこのバージョンで用いられる実際の手順は非常に初歩的である。GI/G/1待ち行列に関する我々の研究*14 *15 *16 *17 *18は、これらの初歩的手続きが使用可能な限られた情報と矛盾しないことを示唆している。到着過程は通常、再生過程ではないので、そして個々の分布について２つのパラメータだけが知られているので、より手の込んだ手続きからは得られるものがほとんどない。実際、QNAのユーザは、待ち時間分布の裾野（tail）のような詳細の記述にあまり重く信頼を置き過ぎないよう警告されるべきである。そのような詳細の記述はかなり正確であることが証明されるだろうが、それらは確かにシミュレーションによってチェックされるべきである。

　さて、QNAが提供する混雑尺度を説明しよう。セクション5.1では単一サーバ・ノードを扱い、セクション5.2では複数サーバ・ノードを扱う。

5.1 GI/G/1待ち行列
　（サービスを開始する前の）定常状態待ち時間から始め、これを $W$ で表す。主要混雑尺度は平均 $EW$ であるが、 $W$ についての確率分布全体も我々は生成する。まず、平均の近似公式は(2)で示したように、
				(44)
である。ただし $g{\eq}g(\rho, c_a^2, c_s^2)$ は
	 	(45)
と定義される。 $c_a^2<1$ の場合、(44)はKraemerとLangenbach-Belzの近似*19であり、これはうまく作動することが知られている*20 *21 *22 *23 *24 *25。 $c_a^2>1$ の場合、元々のKraemerとLangenbach-Belzの改良は役立つようには見えず、よって、それは使われない。(44)は $c_a^2=1$ であるM/G/1については正確であることに注意しよう。

　設備内の客の数をサービス中のものも含めて $N$ で表すことにしよう。サーバが任意の時刻にビジーである確率 $P(N>0)$ と平均 $EN$ はリトルの公式から得ることが出来る（HeymanとSobel*26のセクション11.3を参照）
						(46)
と
					(47)
公式(46)は定常非再生到着過程についてさえも正確であり、(47)は与えられた $EW$ において正確である。

　遅延の確率 $P(W>0)$ 、ここでは $\sigma$ で表す、については、KraemerとLangenbach-Belzの近似*27
		(48)
を用いる。ただし、
	 	(49)
公式(48)はM/G/1システム、つまり、 $\rho$ についても正しい値をもたらす。(48)についてさらに支持する証拠はWhitt*28に含まれている。

　次に我々はサーバがビジーな場合の条件遅延に注目し、 $D$ で示そう。明らかに、 $ED=EW/\sigma$ 。我々は最初に $D$ の２乗変動係数 $c_D^2$ についての近似公式を与える。この公式はサービス時間分布が $c_s^2{\ge}1$ の時 $H_2^b$ であり、 $c_s^2=k^{-1}$ の時 $E_k$ であるようなM/G/1待ち行列について正確な公式である。ただし $H_2^b$ はバランスのとれた平均を持つ超指数分布であり、 $E_k$ はアーラン分布である（Cohen*29のp.256とWhitt*30のセクション３を参照）。この近似の背後にあるアイディアはGI/G/1待ち行列における（総遅延 $W$ よりむしろ）条件遅延 $D$ は到着間隔時間分布によりもサービス時間分布により多く依存するというものである。よって $c_D^2$ についてのM/G/1公式を全てのGI/G/1システムの近似として用いる。 $c_D^2$ についてのM/G/1公式は
				(50)
であり、ただし $d_s^3=E(v^3)/(Ev)^3$ で $v$ はサービス時間確率変数である。 $E(v^3)$ が利用可能である場合でさえ(50)は使用できるが、 $E(v^3)$ は２パラメータでは使用可能ではないので、 $d_s^3$ についての近似を利用する。近似は $H_2^b$ と $E_k$ の分布に基づいている。

「Word Whitt: The Queueing Network Analyzer（１４）」に続きます。

*1:W. Whitt,「再生過程による点過程の近似、I：２つの基本的方法」Oper. Res., 30, No.1 (January-February 1982),pp.125-47.

*2:A. A. Fredericks, 「GI/G/1待ち行列システムにおける待ち時間分布のための近似のクラス」B.S.T.J.,61, No. 3 (March 1982), pp. 295-325.

*3:Y. Takahashi and Y. Takami,「一般クラスにおけるGI/G/c待ち行列システムの定常状態確率のための数値的方法」J. Oper. Res. Soc. Japan, 19(1976), pp. 147-57.

*4:H. C. Tijms, M. H. van Hoorn, and A. Federgruen,「M/G/c待ち行列の定常状態確率のための近似」Adv. Appl. Prob., 13, No. 1 (March 1981), pp. 186-206.

*5:H. Groenevelt, M. H. van Hoorn, and H. C. Tijms,「フェーズ型サービスを持つM/G/c待ち行列システムのための表」Report No. 85, Department of Actuarial Sciences and Econometrics, The Free University, Amsterdam, The Netherlands, 1982.

*6:M. F. Neuts,「確率モデルにおける行列幾何的解。アルゴリズム的方法」Baltimore: The Johns Hopkins University Press, 1981.

*7:M. F. Neuts, 「M/PH/c待ち行列を解析するためのプログラム」Department of Mathematics, University of Delaware, 1981.

*8:P. Hokstad,「非指数分布サーバ時間を持つ多くのサーバ待ち行列のためのいくつかの数値結果と近似」Department of Mathematics, University of Trondheim, Norway, 1981.

*9:J. H. A. de Smit,「さまざまなタイプの客を持つ待ち行列GI/M/s、あるいは、待ち行列GI/Hm/s」Adv. Appl. Prob., 15, No.2 (June 1983), pp. 392-419.

*10:J. H. A. de Smit,「GI/Hk/s待ち行列を解析するためのプログラム」Department of Applied Mathematics, Twente University of Technology, Enschede, The Netherlands, 1982.

*11:A. Ishikawa,「待ち行列システムGI/Ek/mのための平衡解について」T.R.U. Mathematics, 15, No. 1 (1979), pp. 47-66.

*12:A. Ishikawa,「待ち行列システムGI/Ek/mのための平衡解について」T.R.U. Mathematics, 15, No. 1 (1979), pp. 47-66.

*13:S. Halfin and W. Whitt,「多くの指数分布サーバを持つ待ち行列についての高負荷極限」Oper. Res., 29, No. 3 (May-June 1981), pp. 567-88.

*14:W.Whitt,「待ち行列の近似について、I：極値分布」B.S.T.J.,63, No.1, Part 1 (January 1984), to be published.

*15:J. G. Klincewicz and W. Whitt,「待ち行列の近似について、II：形の制約」B.S.T.J.,63,No.1, Part 1 (January 1984).

*16:W. Whitt,「待ち行列の近似について、III：指数分布の混合」B.S.T.J.,63,No.1, Part 1 (January 1984).

*17:W. Whitt,「IMRL/G/1待ち行列のMarshall and Stoyan境界はきつい」Oper. Res. Letters, 1, No.6 (December 1982), pp.209-13.

*18:W. Whitt,「待ち行列の拡散近似の洗練」Oper, Res. Letters, 1, No.5 (November 1982), pp.165-9.

*19:W. Kraemer and M. Langenbach-Belz,「待ち行列システムGI/G/1における遅延についての近似公式」Congressbook, Enghth Int. Teletraffic Cong., Melbourne, 1976, pp. 235-1/8.

*20:W.Whitt,「待ち行列の近似について、I：極値分布」B.S.T.J.,63, No.1, Part 1 (January 1984), to be published.

*21:J. G. Klincewicz and W. Whitt,「待ち行列の近似について、II：形の制約」B.S.T.J.,63,No.1, Part 1 (January 1984).

*22:W. Whitt,「待ち行列の近似について、III：指数分布の混合」B.S.T.J.,63,No.1, Part 1 (January 1984).

*23:W. Whitt,「IMRL/G/1待ち行列のMarshall and Stoyan境界はきつい」Oper. Res. Letters, 1, No.6 (December 1982), pp.209-13.

*24:W. Whitt,「待ち行列の拡散近似の洗練」Oper, Res. Letters, 1, No.5 (November 1982), pp.165-9.

*25:J. G. Shanthikumar and J. A. Buzacott,「単一サーバ待ち行列の近似について」Int. J. Prod. Res. 18, No. 6 (1980), pp. 761-73.

*26:D. P. Heyman and M. J. Sobel,「オペレーションズ・リサーチにおける確率モデル、巻I」New York: McGraw-Hill, 1982.

*27:W. Kraemer and M. Langenbach-Belz,「待ち行列システムGI/G/1における遅延についての近似公式」Congressbook, Enghth Int. Teletraffic Cong., Melbourne, 1976, pp. 235-1/8.

*28:W. Whitt,「GI/G/1待ち行列における遅延の最小化」Oper. Res., 32 (1984), to be published.

*29:J. W. Cohen,「単一サーバ待ち行列」A,sterdam: North-Holland, 1969.

*30:W. Whitt,「再生過程による点過程の近似、I：２つの基本的方法」Oper. Res., 30, No.1 (January-February 1982),pp.125-47.