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

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

　一般的な方法は、全ての到着過程とサービス時間の分布を２，３のパラメータで表現することである。個々の設備での混雑は次に、これらのパラメータにのみ依存する近似公式によって記述される。内部フローについての諸パラメータは、３つの基本ネットワーク・オペレーション、すなわち、重ね合わせ（合流）、分岐、待ち行列を通る流れ（出発）、の各々についてパラメータを変形する初等演算を適用することにより決定される。これらの基本オペレーションを図２に示す。

図２：基本ネットワーク・オペレーション。(a)重ね合わせ、あるいは合流、(b)分解、あるいは分岐、(c)出発、あるいは待ち行列を通る流れ。

　ネットワークに戻りがない（例えば、直列の待ち行列の）時には、基本的な変形を一度に１つずつ引き続いて適用出来るが、一般には連立方程式を解く、あるいは繰り返しを用いる必要がある。まとめると、この一般的方法には４つの主要要素がある。

適用例において使用可能になり、個々のノードでの混雑の近似においてかなりの記述能力のある、流れとノードを特徴付ける諸パラメータ

個々のノードで到着過程とサービス時間の分布を特徴付ける諸パラメータによって提供される部分情報に基づいた複数サーバ待ち行列の近似

基本ネットワーク・オペレーション、つまり合流、分岐、出発、を表す諸パラメータを変形するための計算法

ネットワークに適用された基本計算からの結果の連立方程式を解くための合成アルゴリズム

　QNAの現在バージョンは到着過程とサービス時間を特徴付けるために２つのパラメータ、１つはレートを表し、もう一つは変動を表す、を用いている。（しかし、３パラメータ・アルゴリズムを開発中である。）　サービス時間について、２パラメータは最初の２つのモーメントである。しかし、実際には我々は平均サービス時間 $\tau$ と２乗変動係数 $c_s^2$ 、これはサービス時間の分散をその平均の２乗で割ったものである、で動かしている。ユーザには $\tau$ の代わりにサービス・レート $\mu=\tau^{-1}$ で動かす選択肢がある。到着過程について、パラメータは再生過程近似に関係している。最初の２つのパラメータは再生過程を近似する際の再生間隔（連続する点の間の間隔）の最初の２つのモーメントと等価である。我々が使用する等価パラメータは到着レート $\lambda$ （これは再生間隔平均の逆数）と２乗変動係数 $c_a^2$ （これは再生間隔の分散をその平均の２乗で割ったもの）である。
　我々は、Albun*1 *2によって合流のために開発されたハイブリッドな手続きのような改良を組み込んだ、Whitt*3での点過程の近似のための一般的なフレームワークと基本手順を適用することによりフローの近似を得る。もちろん、確率的点過程の単純な２パラメータ近似の一般的アイディアは少なくとも溢れる流れの近似のための等価なランダム方法（Wilkinson*4、Cooper*5とそこの参考文献を参照）までさかのぼる。そのような点過程のための再生過程近似はKuczura*6によって導入された（またRathとSheng*7を参照）。QNAと類似した待ち行列のネットワークのための２パラメータ近似もまた他の人々とによって、恐らく最初はReiserとコバヤシ*8、(Kuehn*9、Sevcik他*10、ChandyとSauer*11、GelenbeとMitrani*12の第４章、ShanthikumarとBuzacott*13も参照)によって開発されてきた。これらの待ち行列のネットワーク用の２パラメータ近似はまた代替ルートのあるブロッキング・システムのネットワーク用の２パラメータ近似に精神においては類似している（Katz*14を参照）。
　何名かの著者は拡散近似*15 *16として待ち行列のネットワークのために、これらの２パラメータ・ヒューリスティック近似を参照してきたが、拡散過程は実際には使用していない。拡散近似と関連する高流量極限理論は文献上の、そしてQNAにおけるヒューリスティック近似のいくつかを動機付けてきており、点過程の近似のための漸近法と密接に関連しているが、QNAにおけるヒューリスティック近似はIglehartとWhitt*17、HarrisonとReiman*18、Reiman*19 *20における待ち行列のネットワークのための、より複雑な拡散近似とは同じではない。
　QNAにおける近似法はたぶんパラメトリック分解法*21として最もよく記述されるだろう。というのはノードは内部のフローのパラメータを決定したあとで別々に解析されるからである。さらに、混雑尺度がネットワーク全体のために計算される時、ノードは確率的に独立であるとして（近似的に）扱われる。この独立性はマルコフ型ネットワークについて、つまり、個々のノードでの客の均衡数を表すベクトルの要素が確率的に独立なので、そのベクトルについての確率関数が要素の確率関数の積であるようなマルコフ・モデルにおいて、成り立つ積形式解の一般化として解釈できる。

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

*1:S.L. Albin,「重ね合わせ到着過程を持つ待ち行列の近似」Ph.D dissertation, Department of Industrial Engineering and Operation Research, Columbia University, 1981.

*2:S.L. Albin,「再生過程による点過程の近似、II：待ち行列への重ね合わせ到着過程」Department of Industrial Engineering, Rutgers University, 1982.

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

*4:R.I.Wilkinson,「USAにおける交通事故工学のための諸理論」B.S.T.J.,35,No.2(March 1956),pp.421-514.

*5:R.B.Cooper,「待ち行列理論の紹介、第２版」New York: North Holland, 1981.

*6:A. Kuczura,「溢れ過程としての中断されたポアソン過程」B.S.T.J.,52, No.3(March 1973), pp.437-48.

*7:J.H. Rath and D.D. Sheng,「有限待ち領域を持つ待ち行列からの溢れのための近似」Oper. Res., 27, No.6(November-December 1979), pp.1208-16.

*8:M. Reiser and H. Kobayashi,「いくつかの待ち行列システムのための拡散近似の精度」IBM J. Res. Dev., 18 (March 1974), pp.110-24

*9:P.J. Kuehn,「分解による一般待ち行列ネットワークの近似解析」IEEE Trans. Commun., COM-27, No.1 (January 1979), pp.113-26.

*10:K.C. Sevcik, A.I. Levy, S.K. Tripathi, and J.L. Zahorjan,「集約待ち行列ネットワーク・サブシステムの近似の改善」in Computer Performance, K. M. Chandy and M. Reiser (eds.), Amsterdam: North Holland, 1977, pp.1-22.

*11:K. M. Chandy and C. H. Sauer,「計算システムの待ち行列ネットワーク・モデルのための近似法」ACM Computing Surveys, 10, No.3 (September 1978), pp.281-317.

*12:E. Gelenbe and I. Mitrani,「コンピュータ・システムの解析と総合」New York: Academic Press, 1980

*13:J.G.Shanthikumar and J.A. Buzacott,「動的ジョブショップの開放型待ち行列ネットワーク・モデル」Int. J. Prod. Res., 19, No.3(1981), pp.255-66.

*14:S. Katz, 「スイッチド通信ネットワークの確率的パフォーマンス解析」Fifth Int. Teletraffic Cong., Rockefeller University, New York, 1967, pp.566-75.

*15:E. Gelenbe and I. Mitrani,「コンピュータ・システムの解析と総合」New York: Academic Press, 1980

*16:M. Reiser and H. Kobayashi,「いくつかの待ち行列システムのための拡散近似の精度」IBM J. Res. Dev., 18 (March 1974), pp.110-24

*17:D. L. Iglehart and W. Whitt,「高流量での複数チャネル待ち行列、II：順序とネットワークとバッチ」Adv. Appl, Prob., 2, No.2 (Autumn 1970), pp.355-69.

*18:J. M. Harrison and M. I. Reiman,「多次元反射ブラウン運動の分布について」SIAMJ. Appl. Math., 41,No.2 (Octorber 1981), pp.345-61.

*19:M. I. Reiman, 「高流量での開放型待ち行列ネットワーク」unpublished work, 1981.

*20:M. I. Reiman, 「ジャクソン・ネットワークにおけるSojourn時間のための高流量拡散近似」Applied Probability and Computer Science--The Interface, Volume 2, R. L. Disney and T. J. Ott(eds.), Boston: Birkhauser, 1982, pp.409-21.

*21:P.J. Kuehn,「分解による一般待ち行列ネットワークの近似解析」IEEE Trans. Commun., COM-27, No.1 (January 1979), pp.113-26.