「《待ち行列ネットワーク(ジャクソン型とその応用)》」の版間の差分

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

【まちぎょうれつねっとわーく (じゃくそんがた) (Jackson network) 】

　ジャクソンネットワークの名は J.R.Jackson[5]に因る．1970年代後半から, 計算機システムの評価に応用されはじめた．待ち行列網の状態変化がマルコフ過程として記述され, 平衡方程式の解である定常確率分布が積形式として陽に表される基本的なモデルとして重要なものとなっている．

　この待ち行列網の各ノードは指数分布に従うサービス時間をもつ窓口からなり, １つのノードのサービスを終えた客が，その客の履歴によらず，経路選択確率と呼ぶ一定の確率で次のノードを選ぶモデルである．すなわち， $M\,$ 個のノード $1,2,\ldots ,M\,$ からなり，ノード $i\,$ のサービス率はそのノードにいる客数 $n\,$ の関数で， $C_{i}\,(n)$ と表すことができる．例えば，ノード $i\,$ のサーバー数が $c_{i}\,$ ，サービス時間分布がサービス率 $\mu _{i}\,$ の指数分布ならば， $C_{i}(n)=\min(n,c_{i})\mu _{i}\,$ である．ノード $i\,$ のサービスを終えた客は経路選択確率 $r_{ij}\,$ でノード $j\,$ に移動する．

　この網は，外部からの客の到着を仮定する開放型と，外部からの到着はなく，常に一定数 $N\,$ の客が網内を移動する閉鎖型に大別される．開放型の場合，外部からの到着過程は到着率 $\lambda \,$ のポアソン過程とする．外部から到着した客は確率 $r_{0i}\,$ でノード $i\,$ に進み，ノード $i\,$ のサービスが終了した客は確率 $r_{i0}\,$ で網から退去する．少なくとも一つの $i\,$ について， $r_{i0}\,>0$ とならなければならない．閉鎖型の場合はすべての $i\,$ について， $\textstyle \sum _{j=1}^{M}p_{ij}=1\,$ とする．経路選択確率 $r_{ij}\,$ からなる正方行列を $P\,$ とする．開放型の場合，状態 $0\,$ があるため， $P\,$ は $M+1\,$ 次となり，閉鎖型の場合 $M\,$ 次となる． $P\,$ をマルコフ連鎖の推移確率行列とみたとき，既約であると仮定する．客のクラスが複数の場合の混合型については，発展した型であるBCMP型やケリー型などのネットワークに分類される．また，外部からの到着があるが，系内に入ることができる客数に制限がある有限呼源(もしくは損失型)の場合，外部を一つのノードとみなすことにより，閉鎖型に帰着できる（[5]参照）．

積形式解　この待ち行列網の状態を $(n_{1},n_{2},\ldots ,n_{M})\,$ で表す. ここで $n_{i}\,$ はノード $i\,$ にいる客の数である. 定常状態確率を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle p_{(n_1, n_2, \ldots, n_M)}\, } とすれば, これは次のような積形式になる.

$p_{(n_{1},n_{2},\ldots ,n_{M})}=G^{-1}\prod _{i=1}^{M}\,{\frac {\alpha _{i}^{n_{i}}}{\prod _{n=1}^{n_{i}}C_{i}(n)}}$

上記の積で $n_{i}=0\,$ となる項は1とする. $G\,$ は正規化定数であり, $\alpha _{i}\,$ $(i=1,2,\ldots ,M)\,$ はトラフィック方程式と呼ばれるつぎの方程式の解である.

$\alpha _{i}=p_{0i}\lambda +\sum _{i=1}^{M}\alpha _{j}p_{ji},\quad i=1,2,\ldots ,M,\qquad \,$ 　開放型

$\alpha _{i}=\sum _{i=1}^{M}\alpha _{j}p_{ji},\quad i=1,2,\ldots ,M,\qquad \,$ 　開放型

この方程式は，各ノード毎に到着率が退去率に等しいとして得られる1次の連立方程式である．開放型の場合，解 $\alpha _{i}\,$ は一人の客が網に到着してから退去するまでにノード $i\,$ を訪問する平均回数にネットワークへの総到着率 $\lambda \,$ を乗じたものである．閉鎖型の場合は，トラヒック方程式は $P\,$ の定常確率を求める方程式と同一であり，さらに，例えば $\alpha _{1}=1\,$ とすれば， $\alpha _{i}\,$ はノード1に到着してからまた次にそこに到着するまでの間にノード $i\,$ を訪問する期待回数という意味をもつ．

定常分布が積形式となることから，開放型の場合，任意時点での，各ノードの列の長さは互いに独立になり，各ノードからの退去過程がポアソン過程になる．また，閉鎖型も含め，どんな部分ネットワークに対しても，部分ネットワーク全体を１つのノードで置き換えて，他の部分の定常分布が変えないようにすることができる．長さは互いに独立になる．また，閉鎖型も含め，各ノードからの退去過程がポアソン過程になる．したがって，どんな部分ネットワークに対しても，部分ネットワー%ク全体を１つのノードで置き換えて，他の部分の定常分布が変えないようにすることができ, すなわち，ノートンの定理が任意の部分ネットワークに対して成り立つ[11]．さらに，１つのノードへの各到着時点で，到着した客が見るネットワークの状態の分布は任意時点の状態分布と一致する．これを到着定理という．ただし，網が閉鎖型の場合には，任意時点の分布として，到着した客を除いた網を使う．さらにその客の退去時点での分布も同様であり[6]，この分布でのもとで，ノード $i\,$ に到着してから，次にそこに戻るまでの平均周期時間はノードごとの平均訪問回数と平均待ち時間の積の総和となること等が求まる．

正規化定数と性能評価量の計算　積形式解から定常分布を求めるためには正規化定数の計算が必要である．開放型の場合は容易であるが，閉鎖型の場合には，可能な状態が $\textstyle \sum _{i=1}^{M}n_{i}=N\,$ を満たすもに限られるので，工夫が必要である．例えば，閉鎖型正規化定数を計算する方法として，たたみ込み法や平均値解析法が知られている．[2]．たたみこみ法では, ノード $i\,$ に対し, $N+1\,$ 次元のベクトルを

$X_{i}=(X_{i}(0),X_{i}(1),\ldots ,X_{i}(N)),\quad X_{i}(0)=1,X_{i}(n)={\frac {\alpha _{i}^{n}}{\Pi _{j=1}^{n}C_{i}(j)}}\quad (n>0),\ n>0\,$

とし， $G=(X_{1}*X_{2}*...*X_{M}){\mathbf {1} }\,$ で与える． $*\,$ はベクトルのたたみ込み演算である．定常分布が求まれば，スループットや平均待ち行列長の計算は比較的簡単である．しかし，正規化定数を計算することなく直接平均待ち行列長を計算する方法もある．例えば，平均値解析法は到着定理とLittleの公式を応用し，平均列長などを系内客数 $N\,$ について0から繰り返し計算する方法である．各ノードでの平均待ち時間は到着時点での平均列長と平均サービス時間から求まる規律，例えば先着順であることが本質的である．

待ち時間 待ち時間の分布については，特殊な網について考察されている．開放型で，サーバー数が1のノード(規律は先着順)が直列に並んでいる網もJackson型の一つであるが，この網で一人の客の各ノードでの滞在時間は互いに独立であることがバークの定理として知られている[1],[9]．これを閉鎖型にした場合，すなわち，最後のノードを退去した客は必ず最初のノードに戻る周期的な網でも，一周する間の一人の客の各ノードでの滞在時間の同時分布も一種の積の形となる[10]．一人の客が他の客に追い越されることがない(overtake free)という性質が本質的であり，バークの定理は，この影響がない最初と最後のノードでのサーバー数が複数の場合でも成り立つ．特に最後のノードのサービス時間分布は任意でよい．その他，セントラルサーバモデルで規律がプロセッサシェアリングである場合の研究もある．(例えば[8])．

負の客とシグナル ジャクソンネットワークの特徴は，ネットワーク内の各ノードに滞在する客数を要素とするベクトルを状態に取ると連続時間マルコフ連鎖により表されることにある．1990年代に[4]は，到着すると客数を減らす負の客という概念を導入し，同様なマルコフ連鎖によるモデル化を行い，ジャクソンネットワークと同様な積形式の定常分布をもつことを証明した．到着客が待ち行列に並んだ後にサービスを受けずに退去することがあるので，各ノードへの通常の客の総到着率は減少し，客の強制退去を考慮した非線形なトラヒック方程式の解として求められる．定常分布はこの変更された総到着率を使って表すことができる．その後，このモデルは，負の客が複数のノードを瞬間的に動き回るシグナル到着ネットワークへ拡張され，積形式の定常分布をもつことが証明されている（[3]参照）．例えば，各ノードで集団サービスが行われるジャクソン型と同様なネットワークで，予定された大きさの集団がサービスされた集団のみ1つの客となり経路を選択するモデルは，シグナル到着ジャクソンネットワークの例である．

集団移動型 ジャクソンネットワークと同様にポアソン到着やサービス時間が指数分布に従うモデルで，集団到着や集団退去があるモデルもあり，集団移動型と呼ばれる．このモデルは上記で述べた特別な場合を除いて，積形式の定常分布をもたないが，サービス集団の大きさがノードごとに独立であり経路の選択が集団ごとにまとめて行われる場合には，定常分布の補分布の上限を与える積形式分布が知られている（\[7],[12]参照）．また，このモデルは，サービス完了時刻でネットワークの変化を追うと離散時間型のモデルと見なすこともできる．

参考文献

[1] P. J. Burke, "The Output Process of a Stationary M/M/s Queuing System, The Annals of Mathematical Statistics, 39 (1968), 1144-1152.

[2] K. M. Chandy and C. H. Sauer, "Computational Algorithms for Product Form Queueing Networks," Communications of the Association for Computing Machinery, 23 (1980), 573-583.

[3]X. Chao, M. Miyazawa and M. Pinedo, Queueing Networks; customers, signals and product form solutions, Wiley, 1999.

[4]E. Gelenbe, ``Product-form queueing networks with negative and positive customers, Journal of Applied Probability}, (1991), 656--663.

[5] J. R. Jackson, "Jobshop-like Queueing Systems," Management Science, 10 (1963), 131-142.

[6]T. Kawashima, ``A Property of two Palm measures in queueing networks and its applications,Journal of the Operations Research Society of Japan, (1982), 16--28.

[7]M. Miyazawa, P. Taylor, ``A geometric product-form distribution for a queueing network with nonstandard batch arrivals and batch transfers, Advances in Applied Probability 29, (1997), 523--544.

[8] J. A. Morrison and D. Mittra, "Heavy-usage Asymptotic Expansions for the Waiting Time in Closed Processor-sharing Systems with Multiple Casese," Advances in Applied Probability, 17 (1985), 163-185.

[9] E. Reich "Note on Queues in Tandem," The Annals of Mathematical Statistics, 34 (1963), 338-341.

[10] R. Schassberger and H. Daduna. "Sojourn Times in Queueing Networks with Multiserver Nodes," Journal of Applied Probability, 24 (1987), 511-521.

[11] J. Walrand, An Introduction to Queueing Networks, Prentice Hall, 1988.

[12]H. Yamashita, M. Miyazawa,``Product form queueing networks with concurrent movements, . Advances in Applied Probability, 30 (1998), 1111--1129.

@@ 1行目: / 1行目: @@
 '''【まちぎょうれつねっとわーく (じゃくそんがた) (Jackson network) 】'''
-　ジャクソン型待ち行列ネットワークは, J. R. Jackson [3] によって導入された最も基本的な[[待ち行列ネットワーク|待ち行列ネットワークモデル]]である. このモデルではシステムの状態変化がマルコフ連鎖で記述され, 定常状態確率が[[積形式解|積形式]]で陽に表現される. 計算機システムの性能評価をはじめ実際問題の解析にも頻繁に応用されている.
+　ジャクソンネットワークの名は J.R.Jackson[5]に因る．1970年代後半から, 計算機システムの評価に応用されはじめた．待ち行列網の状態変化がマルコフ過程として記述され, 平衡方程式の解である定常確率分布が[[積形式解|積形式]]として陽に表される基本的なモデルとして重要なものとなっている．
+　この待ち行列網の各ノードは指数分布に従うサービス時間をもつ窓口からなり, １つのノードのサービスを終えた客が，その客の履歴によらず，[[経路選択確率]]と呼ぶ一定の確率で次のノードを選ぶモデルである．すなわち，<math>M\, </math>個のノード<math>1, 2, \ldots, M\, </math>からなり，ノード<math>i\, </math>のサービス率はそのノードにいる客数<math>n\, </math>の関数で，<math>C_{i}\,(n) </math>と表すことができる．例えば，ノード<math>i\, </math>のサーバー数が<math>c_{i}\, </math>，サービス時間分布がサービス率<math>\mu_{i}\, </math>の[[指数分布]]ならば，<math>C_i(n)=\min(n, c_{i})\mu_{i}\, </math>である．ノード<math>i\, </math>のサービスを終えた客は経路選択確率<math>r_{ij}\, </math>でノード<math>j\, </math>に移動する．
-'''ジャクソンネットワーク'''　ジャクソン型待ち行列ネットワークでは, 各ノードは[[指数サービス]]を行う1つもしくは複数の窓口と1つの容量無限の待ち合室 (バッファ) からなり, あるノードでサービスを終えた客は[[経路選択確率]]と呼ばれる一定の確率で次のノードを選ぶ. ネットワークのノード数を <math>M\, </math> とし, 各ノードをノード <math>1, 2, \ldots, M\, </math> で表す. ノード <math>i\, </math> におけるサービス率はそのノードにいる客数 <math>n\, </math> の関数として <math>C_i(n)\, </math> で与えられる. 例えばノード <math>i\, </math> の窓口数が <math>c\, </math>, 各窓口のサービス率が <math>\mu\, </math> ならば, <math>C_i(n)=\min(n, c)\mu\, </math> である. ノード <math>i\, </math> でサービスを終えた客は経路選択確率 <math>p_{ij}\, </math> でノード <math>j\, </math> に移動する.
+　この網は，外部からの客の到着を仮定する[[開放型ネットワーク|開放型]]と，外部からの到着はなく，常に一定数<math>N\, </math>の客が網内を移動する[[閉鎖型ネットワーク|閉鎖型]]に大別される．開放型の場合，外部からの到着過程は到着率<math>\lambda\, </math>の[[ポアソン到着|ポアソン過程]]とする．外部から到着した客は確率<math>r_{0i}\, </math>でノード<math>i\, </math>に進み，ノード<math>i\, </math>のサービスが終了した客は確率<math>r_{i0}\, </math>で網から退去する．少なくとも一つの<math>i\, </math>について，<math>r_{i0}\,>0 </math>とならなければならない．閉鎖型の場合はすべての<math>i\, </math>について，<math>\textstyle \sum_{j=1}^Mp_{ij} =1\, </math> とする．
+経路選択確率<math>r_{ij}\, </math> からなる正方行列を<math>P\, </math>とする．開放型の場合，状態<math>0\, </math>があるため，<math>P\, </math>は<math>M+1\, </math>次となり，閉鎖型の場合<math>M\, </math>次となる．
+<math>P\, </math>をマルコフ連鎖の推移確率行列とみたとき，既約であると仮定する．客のクラスが複数の場合の[[混合型待ち行列ネットワーク|混合型]]
+については，発展した型である[[BCMPネットワーク|BCMP型]]や[[ケリーネットワーク|ケリー型]]などのネットワークに分類される．また，外部からの到着があるが，系内に入ることができる客数に制限がある[[有限呼源待ち行列|有限呼源]](もしくは損失型)の場合，外部を一つのノードとみなすことにより，閉鎖型に帰着できる（[5]参照）．
-　ジャクソンネットワークは, 外部からの客の到着を仮定する[[開放型待ち行列ネットワーク|開放型]]と, 外部からの到着はなく, 常に一定数 <math>N\, </math> の客がネットワーク内を移動する[[閉鎖型待ち行列ネットワーク|閉鎖型]]に大別される. 開放型の場合, 客は外部から到着率 <math>\lambda\, </math> のポアソン過程にしたがって到着する. 外部から到着した客は確率 <math>p_{0i}\, </math> でノード <math>i\, </math> に進み, ノード <math>i\, </math> のサービスが終了した客は確率 <math>p_{i0}\, </math> で網から退去する. <math>0\, </math> を含むすべての <math>i\, </math> について <math>\textstyle \sum_{j=0}^M p_{ij} =1\, </math> である. ただし <math>p_{00}\, </math> は <math>0\, </math> とする. 閉鎖型の場合は, すべての <math>i\, </math> について <math>\textstyle \sum_{j=1}^Mp_{ij} =1\, </math> である. 経路選択確率 <math>p_{ij}\, </math> からなる正方行列を <math>P\, </math> とする. 開放型の場合 <math>P\, </math> は <math>M+1\, </math>次であり, 閉鎖型の場合<math>M\, </math>次である. 小さなモデルに分割されるケースを除外するため, <math>P\, </math> をマルコフ連鎖の推移確率行列とみたとき, 既約であると仮定する.
+'''積形式解'''　この待ち行列網の状態を <math>(n_1, n_2, \ldots, n_M)\, </math> で表す. ここで <math>n_i\, </math> はノード <math>i\, </math> にいる客の数である. 定常状態確率を <math>p_{(n_1, n_2, \ldots, n_M)}\, </math> とすれば, これは次のような積形式になる.
-'''定常状態確率'''　この待ち行列網の状態を <math>(n_1, n_2, \ldots, n_M)\, </math> で表す. ここで <math>n_i\, </math> はノード <math>i\, </math> にいる客の数である. 定常状態確率を <math>p_{(n_1, n_2, \ldots, n_M)}\, </math> とすれば, これは次のような積形式になる.
 <center>
 <math>
-p_{(n_1, n_2, \ldots, n_M)}=G^{-1} \prod_{i=1}^M
+p_{(n_1, n_2, \ldots, n_M)}=G^{-1}  \prod_{i=1}^M
-      \prod_{n=1}^{n_i} \frac{\alpha_i}{C_i(n)}
+\, \frac{\alpha_i^{n_i}}{\prod_{n=1}^{n_i} C_i(n)}
-\, </math>
+      </math>
 </center>
-ここで <math>n_i=0\, </math> のときは上記の積は1とみなす. <math>G\, </math> は正規化定数であり, <math>\alpha_i\, </math> <math>(i=1, 2, \ldots, M)\, </math> は[[トラヒック方程式]]と呼ばれるつぎの方程式の解である.
+上記の積で <math>n_i=0\, </math> となる項は1とする. <math>G\, </math> は[[ネットワーク状態分布の正規化定数|正規化定数]]であり, <math>\alpha_i\, </math> <math>(i=1, 2, \ldots, M)\, </math> は[[トラフィック方程式]]と呼ばれるつぎの方程式の解である.
 <center>
@@ 33行目: / 34行目: @@
 \alpha_i = \sum_{i=1}^M \alpha_j p_{ji},
         \quad i=1, 2, \ldots, M, \qquad
-\, </math>　閉鎖型
+\, </math>　開放型
 </center>
-これらの式は, 各ノード毎に <math>\alpha_i\, </math> を到着率とみなし, これが退去率に等しいとして得られる1次の連立方程式と解釈できる. 開放型の場合, <math>\alpha_i\, </math> は一人の客がネットワークに到着してから退去するまでにノード <math>i\, </math> を訪問する平均回数に<math>\lambda\, </math>を乗じたものとなっている. 閉鎖型の場合, トラヒック方程式は <math>P\, </math> の定常状態確率を求める方程式と同一であり, さらに例えば <math>\alpha_1=1\, </math> という条件をおけば, <math>\alpha_i\, </math> はノード1に到着してからまた再びノード1に戻ってくるまでにノード <math>i\, </math> を訪問する平均回数という意味をもつ.
+この方程式は，各ノード毎に到着率が退去率に等しいとして得られる1次の連立方程式である．開放型の場合，解<math>\alpha_i\, </math>は一人の客が網に到着してから退去するまでにノード<math>i\, </math>を訪問する平均回数にネットワークへの総到着率<math>\lambda\, </math>を乗じたものである．閉鎖型の場合は，トラヒック方程式は<math>P\, </math>の定常確率を求める方程式と同一であり，さらに，例えば<math>\alpha_1=1\, </math>とすれば，<math>\alpha_{i}\, </math>はノード1に到着してからまた次にそこに到着するまでの間にノード<math>i\, </math>を訪問する期待回数という意味をもつ．
+定常分布が積形式となることから，開放型の場合，任意時点での，各ノードの列の長さは互いに独立になり，各ノードからの退去過程がポアソン過程になる．また，閉鎖型も含め，どんな部分ネットワークに対しても，部分ネットワーク全体を１つのノードで置き換えて，他の部分の定常分布が変えないようにすることができる．
+長さは互いに独立になる．また，閉鎖型も含め，各ノードからの退去過程がポアソン過程になる．したがって，どんな部分ネットワークに対しても，部分ネットワー%ク全体を１つのノードで置き換えて，他の部分の定常分布が変えないようにすることができ, すなわち，[[ノートンの定理|ノートンの定理]]が任意の部分ネットワークに対して成り立つ[11]．さらに，１つのノードへの各到着時点で，到着した客が見るネットワークの状態の分布は任意時点の状態分布と一致する．これを[[到着定理|到着定理]]という．ただし，網が閉鎖型の場合には，任意時点の分布として，到着した客を除いた網を使う．さらにその客の退去時点での分布も同様であり[6]，この分布でのもとで，ノード<math>i\, </math>に到着してから，次にそこに戻るまでの平均周期時間はノードごとの平均訪問回数と平均待ち時間の積の総和となること等が求まる．
-'''いろいろな性質'''　定常分布が積形式となることから, ジャクソンネットワークではいろいろ好ましい性質が成り立つことが証明されている. まず開放型の場合, 任意時点での各ノードの客の数は互いに独立になる. ただし, 閉鎖型の場合は可能な状態が <math>\textstyle \sum_{i=1}^M n_i =N\, </math> を満たすものに限られるので, 客の数は独立とはならない. また, 閉鎖型も含め, 各ノードからの退去過程はポアソン過程になる. したがって, どんな部分ネットワークに対しても, 部分ネットワーク全体を1つのノードで置き換えて, 他の部分の定常分布が変わらないようにすることができる. すなわち[[ノートンの定理]]が任意の部分ネットワークに対して成り立つ [8]. さらに, 1つのノードへの到着時点で, 到着した客が見るネットワークの状態の分布は任意時点の状態分布と一致する. これを[[到着定理]]という. ただし, ネットワークが閉鎖型の場合には, 任意時点の分布として (到着した客を除いたことに対応する) システム内客数が <math>N-1\, </math> のネットワークにおける定常分布を使う. さらに客の退去時点での分布も同様であり [4], この分布のもとで, ノード <math>i\, </math> に到着してから次にそこに戻るまでの平均周期は, ノードごとの平均訪問回数と平均待ち時間の積の総和で与えられる.
+'''正規化定数と性能評価量の計算'''　積形式解から定常分布を求めるためには正規化定数の計算が必要である．開放型の場合は容易であるが，閉鎖型の場合には，可能な状態が<math>\textstyle \sum_{i=1}^M n_i =N\, </math>を満たすもに限られるので，工夫が必要である．例えば，閉鎖型正規化定数を計算する方法として，[[たたみ込み法]]や[[平均値解析法]]が知られている．[2]．たたみこみ法では, ノード <math>i\, </math> に対し, <math>N+1\, </math> 次元のベクトルを
-　正規化定数, スループット, 各ノードの平均客数などを求めることは, 開放型ネットワークの場合は容易である. 各ノードの客数が互いに独立になるためである. しかし, 閉鎖型の場合には, 可能な状態が <math>\textstyle \sum_{i=1}^M n_i =N\, </math> を満たすものに限られるという制約のため, 工夫が必要である. 例えば, 正規化定数を計算する方法として, [[たたみ込み法]]や[[平均値解析法]]が知られている[2]. たたみ込み法では, ノード <math>i\, </math> に対し, <math>N+1\, </math> 次元のベクトルを
 <center>
 <math>
 X_i=(X_i(0), X_i(1), \ldots, X_i(N)),
-   \quad X_i(0)=1, \quad X_i(n)=\prod_{j=1}^n \alpha_i/C_i(j),
+   \quad X_i(0)=1, X_i(n)= \frac {\alpha_i^{n}} {\Pi_{j=1}^n C_{i}(j)} \quad (n>0),
    \  n>0
 \, </math>
@@ 54行目: / 54行目: @@
-とし, これらのベクトルを客数の和が <math>N\, </math> 以下の範囲でたたみこみ演算して <math>G\, </math> を求める. 平均値解析法は到着定理と[[リトルの公式]]を応用し, 各ノードの平均客数, 1回あたりの平均滞在時間, スループットなどを, システム内客数 <math>N\, </math> について <math>0\, </math> から繰り返し計算する方法である. 各ノードでの規律は, 平均待ち時間が到着時点での平均客数と平均サービス時間から求まるもの, 例えば先着順であること, が本質的である.
+とし，<math>G=(X_1*X_2*...*X_M){\mathbf 1}\, </math>で与える．<math>*\, </math>はベクトルのたたみ込み演算である．定常分布が求まれば，スループットや平均待ち行列長の計算は比較的簡単である．しかし，正規化定数を計算することなく直接平均待ち行列長を計算する方法もある．例えば，平均値解析法は到着定理と[[リトルの公式|Littleの公式]]を応用し，平均列長などを系内客数<math>N\, </math>について0から繰り返し計算する方法である．各ノードでの平均待ち時間は到着時点での平均列長と平均サービス時間から求まる規律，例えば先着順であることが本質的である．
+'''待ち時間''' 待ち時間の分布については，特殊な網について考察されている．開放型で，サーバー数が1のノード(規律は先着順)が直列に並んでいる網もJackson型の一つであるが，この網で一人の客の各ノードでの滞在時間は互いに独立であることが[[バークの定理|バークの定理]]として知られている[1],[9]．これを閉鎖型にした場合，すなわち，最後のノードを退去した客は必ず最初のノードに戻る周期的な網でも，一周する間の一人の客の各ノードでの滞在時間の同時分布も一種の積の形となる[10]．一人の客が他の客に追い越されることがない(overtake free)という性質が本質的であり，バークの定理は，この影響がない最初と最後のノードでのサーバー数が複数の場合でも成り立つ．特に最後のノードのサービス時間分布は任意でよい．その他，[[セントラルサーバモデル]]で規律が[[プロセッサシェアリング]]である場合の研究もある．(例えば[8])．
+'''負の客とシグナル''' ジャクソンネットワークの特徴は，ネットワーク内の各ノードに滞在する客数を要素とするベクトルを状態に取ると連続時間マルコフ連鎖により表されることにある．1990年代に[4]は，到着すると客数を減らす[[負の客]]という概念を導入し，同様なマルコフ連鎖によるモデル化を行い，ジャクソンネットワークと同様な積形式の定常分布をもつことを証明した．到着客が待ち行列に並んだ後にサービスを受けずに退去することがあるので，各ノードへの通常の客の総到着率は減少し，客の強制退去を考慮した非線形なトラヒック方程式の解として求められる．定常分布はこの変更された総到着率を使って表すことができる．その後，このモデルは，負の客が複数のノードを瞬間的に動き回る[[シグナル到着ネットワーク]]へ拡張され，積形式の定常分布をもつことが証明されている（[3]参照）．例えば，各ノードで集団サービスが行われるジャクソン型と同様なネットワークで，予定された大きさの集団がサービスされた集団のみ1つの客となり経路を選択するモデルは，シグナル到着ジャクソンネットワークの例である．
+'''集団移動型''' ジャクソンネットワークと同様にポアソン到着やサービス時間が指数分布に従うモデルで，集団到着や集団退去があるモデルもあり，[[集団移動型ネットワーク|集団移動型]]と呼ばれる．このモデルは上記で述べた特別な場合を除いて，積形式の定常分布をもたないが，サービス集団の大きさがノードごとに独立であり経路の選択が集団ごとにまとめて行われる場合には，定常分布の補分布の上限を与える積形式分布が知られている（\[7],[12]参照）．また，このモデルは，サービス完了時刻でネットワークの変化を追うと離散時間型のモデルと見なすこともできる．
-　待ち時間の分布については, 特殊なネットワークについてのみ考察されている. 開放型で, サーバー数が1のノード (規律は先着順) が直列に並んでいるネットワークもJackson型の一つであるが, このネットワークで一人の客の各ノードでの滞在時間は互いに独立であることが[[バークの定理]]として知られている [1],[6]. これを閉鎖型にした場合, すなわち最後のノードを退去した客は必ず最初のノードに戻る循環型のネットワークでも, 一周する間の一人の客の各ノードでの滞在時間の同時分布も一種の積の形となる [7]. これはどの客も他の客に追い越されることがない (overtake free) という性質が本質的であり, バークの定理はこの影響がない最初と最後のノードでのサーバー数が複数の場合でも成り立つ. 特に最後のノードのサービス時間分布は任意でよい. その他, セントラルサーバモデルで規律がプロセッサーシェアリングである場合の研究もある [5].
-　履歴により経路選択確率が変化する場合も含め, 客のクラスが複数の場合の[[混合型待ち行列ネットワーク|混合型]]については, 発展型である[[BCMPネットワーク|BCMP型]], [[ケリーネットワーク|ケリー型]]などのネットワークで扱われる. また, 外部からの到着があるが, 系内に入ることができる客数に制限がある[[有限呼源待ち行列|有限呼源]] (もしくは損失型) の場合, 外部を一つのノードとみなすことにより, 閉鎖型に帰着できる [3].
@@ 70行目: / 77行目: @@
 [2] K. M. Chandy and C. H. Sauer, "Computational Algorithms for Product Form Queueing Networks," ''Communications of the Association for Computing Machinery'', '''23''' (1980), 573-583.
-[3] J. R. Jackson, "Jobshop-like Queueing Systems," ''Management Science'', '''10''' (1963), 131-142.
+[3]X. Chao, M. Miyazawa and M. Pinedo, ''Queueing Networks; customers, signals and product form solutions,''   Wiley, 1999.
+[4]E. Gelenbe, ``Product-form queueing networks with negative and positive customers,'' Journal of Applied Probability}, (1991), 656--663.
+[5] J. R. Jackson, "Jobshop-like Queueing Systems," ''Management Science'', '''10''' (1963), 131-142.
+[6]T. Kawashima,
+``A Property of two Palm measures in queueing networks and its applications,''Journal of the Operations Research Society of Japan, (1982), 16--28.
+[7]M. Miyazawa, P. Taylor,
+``A geometric product-form distribution for a queueing network with nonstandard batch arrivals and batch transfers,'' Advances in Applied Probability 29, (1997), 523--544.
+[8] J. A. Morrison and D. Mittra, "Heavy-usage Asymptotic Expansions for the Waiting Time in Closed Processor-sharing Systems with Multiple Casese," ''Advances in Applied Probability'', '''17''' (1985), 163-185.
-[4] T. Kawashima, "A Property of Two Palm Measures in Queueing Networks and Its Applications," ''Journal of the Operations Research Society of Japan'', '''25''' (1982), 16-28.
+[9] E. Reich "Note on Queues in Tandem," ''The Annals of Mathematical Statistics'', '''34''' (1963), 338-341.
-[5] J. A. Morrison and D. Mittra, "Heavy-usage Asymptotic Expansions for the Waiting Time in Closed Processor-sharing Systems with Multiple Casese," ''Advances in Applied Probability'', '''17''' (1985), 163-185.
+[10] R. Schassberger and H. Daduna. "Sojourn Times in Queueing Networks with Multiserver Nodes," ''Journal of Applied Probability'', '''24''' (1987), 511-521.
-[6] E. Reich "Note on Queues in Tandem," ''The Annals of Mathematical Statistics'', '''34''' (1963), 338-341.
+[11] J. Walrand, ''An Introduction to Queueing Networks'', Prentice Hall, 1988.
-[7] R. Schassberger and H. Daduna. "Sojourn Times in Queueing Networks with Multiserver Nodes," ''Journal of Applied Probability'', '''24''' (1987), 511-521.
+[12]H. Yamashita, M. Miyazawa,``Product form queueing networks with concurrent movements,''
+. ''Advances in Applied Probability, '' '''30''' (1998), 1111--1129.
-[8] J. Walrand, ''An Introduction to Queueing Networks'', Prentice Hall, 1988.
+[[category:待ち行列ネットワーク|まちぎょうれつねっとわーく（じゃくそんがたとそのおうよう）]]

「《待ち行列ネットワーク(ジャクソン型とその応用)》」の版間の差分

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

案内メニュー

検索