ジャクソンネットワーク

Mathematical discipline

待ち行列理論（数学的確率論の一分野）において、ジャクソン ネットワーク（ジャクソンニアン ネットワークとも呼ばれる^[1] ）は、ネットワークが積形式解を持つため均衡分布の計算が特に簡単な待ち行列ネットワークの一種である。これは待ち行列ネットワーク理論における最初の重要な発展であり、この定理のアイデアを一般化して適用し、他のネットワークで同様の積形式解を探す研究は、インターネットの開発に使用されたアイデアを含め、多くの研究の対象となってきた^{[2] 。 [3]}このネットワークは、James R. Jacksonによって初めて特定され^{[4] [5] 、彼の論文は}Management Science誌の「Ten Most Influential Titles of Management Sciences First Fifty Years」に再掲載された。 ^[6]

ジャクソンはバークとライヒの研究に触発されたが^{[7] 、}ジャン・ウォーランドは「積形式の結果は…ジャクソン自身が基礎論文で信じていたほど出力定理の直接的な結果ではない」と指摘している^{[8] 。}

以前の積形式の解法は、RRPジャクソンによってタンデムキュー（各顧客が順番に各キューを訪問しなければならない有限のキューの連鎖）と循環ネットワーク（各顧客が順番に各キューを訪問しなければならないキューのループ）に対して発見されました。^[9]

ジャクソンネットワークは複数のノードで構成され、各ノードはキューを表します。キューのサービスレートはノード依存（ノードごとにサービスレートが異なる）と状態依存（キューの長さに応じてサービスレートが変化する）の両方になります。ジョブは固定のルーティングマトリクスに従ってノード間を移動します。各ノードのすべてのジョブは単一の「クラス」に属し、同じサービス時間配分と同じルーティングメカニズムに従います。したがって、ジョブの処理に優先順位はなく、各ノードのすべてのジョブは先着順で処理されます。

有限個のジョブが閉じたネットワークを巡回するジャクソンネットワークも、ゴードン・ニューウェル定理によって記述される積形式解を持つ。^[10]

ジャクソンネットワークの必要条件

m個の相互接続されたキューのネットワークは、次の条件を満たす場合、ジャクソンネットワーク^[11]またはジャクソンネットワーク^[12]と呼ばれます。

1. ネットワークが開いている場合、ノードiへの外部からの到着はポアソン過程を形成し、
2. すべてのサービス時間は指数分布しており、すべてのキューでのサービス規律は先着順です。
3. キューiでサービスを完了した顧客は、確率 で新しいキューjに移動する、または確率 でシステムを離れる。オープンネットワークの場合、この確率はキューのいくつかのサブセットではゼロではない。 ${\displaystyle P_{ij}}$ ${\displaystyle 1-\sum _{j=1}^{m}P_{ij}}$
4. すべてのキューの使用率は 1 未満です。

定理

m個の M/M/1キューのオープンジャクソンネットワークにおいて、各キューの利用率 が1未満の場合、均衡状態確率分布が存在し、状態は個々のキューの均衡分布の積で与えられる。 ${\displaystyle \rho _{i}}$ ${\displaystyle \scriptstyle {(k_{1},k_{2},\ldots ,k_{m})}}$

${\displaystyle \pi (k_{1},k_{2},\ldots ,k_{m})=\prod _{i=1}^{m}\pi _{i}(k_{i})=\prod _{i=1}^{m}[\rho _{i}^{k_{i}}(1-\rho _{i})].}$

この結果は、ステーションにc _iサーバーがあり、使用率要件が であるM/M/c モデルステーションにも当てはまります。 ${\displaystyle \pi (k_{1},k_{2},\ldots ,k_{m})=\prod _{i=1}^{m}\pi _{i}(k_{i})}$ ${\displaystyle i^{\text{th}}}$ ${\displaystyle \rho _{i}<c_{i}}$

意味

オープンネットワークでは、ジョブは外部からポアソン過程に従って到着し、その速度は です。各到着ジョブは独立して、確率 および でノードjにルーティングされます。ノードiでのサービスが完了すると、ジョブは確率 で別のノードjに移動するか、確率 でネットワークから離脱します。 ${\displaystyle \alpha >0}$ ${\displaystyle p_{0j}\geq 0}$ ${\displaystyle \sum _{j=1}^{J}p_{0j}=1}$ ${\displaystyle p_{ij}}$ ${\displaystyle p_{i0}=1-\sum _{j=1}^{J}p_{ij}}$

したがって、外部到着と内部遷移の両方を含む ノードiへの全体的な到着率は次のようになります。 ${\displaystyle \lambda _{i}}$

${\displaystyle \lambda _{i}=\alpha p_{0i}+\sum _{j=1}^{J}\lambda _{j}p_{ji},i=1,\ldots ,J.\qquad (1)}$

(各ノードでの利用率は 1 未満であり、均衡分布、つまり長期平均動作を見ているため、jからiに移行するジョブのレートは、 jへの到着レートの一部によって制限され、上記ではサービス レートは無視されます。) ${\displaystyle \mu _{j}}$

を定義すると、 を解くことができます。 ${\displaystyle a=(\alpha p_{0i})_{i=1}^{J}}$ ${\displaystyle \lambda =(I-P^{T})^{-1}a}$

すべてのジョブもポアソン過程に従って各ノードから出発し、ノードiにジョブがある場合のノードiのサービス率として定義されます。 ${\displaystyle \mu _{i}(x_{i})}$ ${\displaystyle x_{i}}$

時刻tにおけるノードiのジョブ数を、 とすると、の均衡分布は次のバランス方程式系によって決定されます。 ${\displaystyle X_{i}(t)}$ ${\displaystyle \mathbf {X} =(X_{i})_{i=1}^{J}}$ ${\displaystyle \mathbf {X} }$ ${\displaystyle \pi (\mathbf {x} )=P(\mathbf {X} =\mathbf {x} )}$

${\displaystyle {\begin{aligned}&\pi (\mathbf {x} )\sum _{i=1}^{J}[\alpha p_{0i}+\mu _{i}(x_{i})(1-p_{ii})]\\={}&\sum _{i=1}^{J}[\pi (\mathbf {x} -\mathbf {e} _{i})\alpha p_{0i}+\pi (\mathbf {x} +\mathbf {e} _{i})\mu _{i}(x_{i}+1)p_{i0}]+\sum _{i=1}^{J}\sum _{j\neq i}\pi (\mathbf {x} +\mathbf {e} _{i}-\mathbf {e} _{j})\mu _{i}(x_{i}+1)p_{ij}.\qquad (2)\end{aligned}}}$

ここで は単位ベクトルを表します。 ${\displaystyle \mathbf {e} _{i}}$ ${\displaystyle i^{\text{th}}}$

定理

それぞれが確率質量関数を持つ独立確率変数のベクトルを仮定する。 ${\displaystyle (Y_{1},\ldots ,Y_{J})}$ ${\displaystyle Y_{i}}$

${\displaystyle P(Y_{i}=n)=p(Y_{i}=0)\cdot {\frac {\lambda _{i}^{n}}{M_{i}(n)}},\quad (3)}$

ここで、 ieが適切に定義されている場合、オープンジャクソンネットワークの均衡分布は次の積の形を持ちます。 ${\displaystyle M_{i}(n)=\prod _{j=1}^{n}\mu _{i}(j)}$ ${\displaystyle \sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}<\infty }$ ${\displaystyle P(Y_{i}=0)=\left(1+\sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}\right)^{-1}}$

${\displaystyle \pi (\mathbf {x} )=\prod _{i=1}^{J}P(Y_{i}=x_{i}).}$

すべての人のために。⟩ ${\displaystyle \mathbf {x} \in {\mathcal {Z}}_{+}^{J}}$

証拠

式が満たされていることを確認するだけで十分である。積の形と式(3)より、次式が得られる。 ${\displaystyle (2)}$

${\displaystyle \pi (\mathbf {x} )=\pi (\mathbf {x} +\mathbf {e} _{i})\mu _{i}(x_{i}+1)/\lambda _{i}=\pi (\mathbf {x} +\mathbf {e} _{i}-\mathbf {e} _{j})\mu _{i}(x_{i}+1)\lambda _{j}/[\lambda _{i}\mu _{j}(x_{j})]}$

これらを の右側に代入すると次のようになります。 ${\displaystyle (2)}$

${\displaystyle \sum _{i=1}^{J}[\alpha p_{0i}+\mu _{i}(x_{i})(1-p_{ii})]=\sum _{i=1}^{J}[{\frac {\alpha p_{0i}}{\lambda _{i}}}\mu _{i}(x_{i})+\lambda _{i}p_{i0}]+\sum _{i=1}^{J}\sum _{j\neq i}{\frac {\lambda _{i}}{\lambda _{j}}}p_{ij}\mu _{j}(x_{j}).\qquad (4)}$

次に を使用すると、次のようになります。 ${\displaystyle (1)}$

${\displaystyle \sum _{i=1}^{J}\sum _{j\neq i}{\frac {\lambda _{i}}{\lambda _{j}}}p_{ij}\mu _{j}(x_{j})=\sum _{j=1}^{J}[\sum _{i\neq j}{\frac {\lambda _{i}}{\lambda _{j}}}p_{ij}]\mu _{j}(x_{j})=\sum _{j=1}^{J}[1-p_{jj}-{\frac {\alpha p_{0j}}{\lambda _{j}}}]\mu _{j}(x_{j}).}$

上記を に代入すると、次のようになります。 ${\displaystyle (4)}$

${\displaystyle \sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}p_{i0}}$

これは によって検証できます。したがって の両辺は等しいです。⟨ ${\displaystyle \sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}}$ ${\displaystyle (2)}$

この定理は、各ノードの状態依存のサービス率を許容することで、上記の定理を拡張する。これは、 の分布を独立変数のベクトルで関連付けるものである。 ${\displaystyle \mathbf {X} }$ ${\displaystyle \mathbf {Y} }$

例

3ノードのオープンジャクソンネットワーク

グラフに示す 3 つのノードを持つジャクソン ネットワークがあるとします。係数は次のようになります。

${\displaystyle \alpha =5,\quad p_{01}=p_{02}=0.5,\quad p_{03}=0,\quad }$

${\displaystyle P={\begin{bmatrix}0&0.5&0.5\\0&0&0\\0&0&0\end{bmatrix}},\quad \mu ={\begin{bmatrix}\mu _{1}(x_{1})\\\mu _{2}(x_{2})\\\mu _{3}(x_{3})\end{bmatrix}}={\begin{bmatrix}15\\12\\10\end{bmatrix}}{\text{ for all }}x_{i}>0}$

すると定理により次のように計算できます。

${\displaystyle \lambda =(I-P^{T})^{-1}a={\begin{bmatrix}1&0&0\\-0.5&1&0\\-0.5&0&1\end{bmatrix}}^{-1}{\begin{bmatrix}0.5\times 5\\0.5\times 5\\0\end{bmatrix}}={\begin{bmatrix}1&0&0\\0.5&1&0\\0.5&0&1\end{bmatrix}}{\begin{bmatrix}2.5\\2.5\\0\end{bmatrix}}={\begin{bmatrix}2.5\\3.75\\1.25\end{bmatrix}}}$

の定義によれば、次のようになります。 ${\displaystyle \mathbf {Y} }$

${\displaystyle P(Y_{1}=0)=\left(\sum _{n=0}^{\infty }\left({\frac {2.5}{15}}\right)^{n}\right)^{-1}={\frac {5}{6}}}$

${\displaystyle P(Y_{2}=0)=\left(\sum _{n=0}^{\infty }\left({\frac {3.75}{12}}\right)^{n}\right)^{-1}={\frac {11}{16}}}$

${\displaystyle P(Y_{3}=0)=\left(\sum _{n=0}^{\infty }\left({\frac {1.25}{10}}\right)^{n}\right)^{-1}={\frac {7}{8}}}$

したがって、各ノードに 1 つのジョブがある確率は次のようになります。

${\displaystyle \pi (1,1,1)={\frac {5}{6}}\cdot {\frac {2.5}{15}}\cdot {\frac {11}{16}}\cdot {\frac {3.75}{12}}\cdot {\frac {7}{8}}\cdot {\frac {1.25}{10}}\approx 0.00326}$

ここでのサービス率は状態に依存しないため、は単純に幾何分布に従います。 ${\displaystyle Y_{i}}$

一般化ジャクソンネットワーク

一般化ジャクソンネットワークは、ポアソン過程である必要のない更新到着過程と、独立かつ同一分布に従う非指数分布のサービス時間を許容する。一般に、このネットワークは積形定常分布を持たないため、近似値が求められる。^[13]

ブラウン運動近似

ある穏やかな条件下では、開放型一般化ジャクソンネットワークのキュー長過程^[要説明] は、と定義される反射ブラウン運動で近似できる。ここで、は過程のドリフト、は共分散行列、は反射行列である。これは、均質流体ネットワークを持つ一般化ジャクソンネットワークと反射ブラウン運動の関係から得られる2次の近似である。 ${\displaystyle Q(t)}$ ${\displaystyle \operatorname {RBM} _{Q(0)}(\theta ,\Gamma ;R).}$ ${\displaystyle \theta }$ ${\displaystyle \Gamma }$ ${\displaystyle R}$

反射ブラウン運動過程のパラメータは次のように指定されます。

${\displaystyle \theta =\alpha -(I-P^{T})\mu }$

${\displaystyle \Gamma =(\Gamma _{k\ell }){\text{ with }}\Gamma _{k\ell }=\sum _{j=1}^{J}(\lambda _{j}\wedge \mu _{j})[p_{jk}(\delta _{k\ell }-p_{j\ell })+c_{j}^{2}(p_{jk}-\delta _{jk})(p_{j\ell }-\delta _{j\ell })]+\alpha _{k}c_{0,k}^{2}\delta _{k\ell }}$

${\displaystyle R=I-P^{T}}$

ここで、記号は次のように定義されます。

近似式における記号の定義

シンボル	意味
${\displaystyle \alpha =(\alpha _{j})_{j=1}^{J}}$	各ノードへの到着率を指定するJベクトル。
${\displaystyle \mu =(\mu )_{j=1}^{J}}$	各ノードのサービスレートを指定するJベクトル。
${\displaystyle P}$	ルーティング マトリックス。
${\displaystyle \lambda _{j}}$	ノードの有効な到着。 ${\displaystyle j^{\text{th}}}$
${\displaystyle c_{j}}$	ノードでのサービス時間の変動。 ${\displaystyle j^{\text{th}}}$
${\displaystyle c_{0,j}}$	ノードにおける到着間隔の変動。 ${\displaystyle j^{\text{th}}}$
${\displaystyle \delta _{ij}}$	ノード間の相関を指定するための係数。 これらは次のように定義されます。 がシステムの到着過程であるとすると、分布において、 は共変量行列 を持つドリフトレスブラウン過程であり、は任意の ${\displaystyle A(t)}$ ${\displaystyle A(t)-\alpha t{}\approx {\hat {A}}(t)}$ ${\displaystyle {\hat {A}}(t)}$ ${\displaystyle \Gamma ^{0}=(\Gamma _{ij}^{0})}$ ${\displaystyle \Gamma _{ij}^{0}=\alpha _{i}c_{0,i}^{2}\delta _{ij}}$ ${\displaystyle i,j\in \{1,\dots ,J\}}$

参照

• ゴードン・ニューウェルネットワーク
• BCMPネットワーク
• Gネットワ​​ーク
• リトルの法則

参考文献

1. Walrand, J. ; Varaiya, P. (1980). 「ジャクソンネットワークにおける滞在時間と追い越し条件」.応用確率論の進歩. 12 (4): 1000–1018 . doi :10.2307/1426753. JSTOR  1426753.
2. Kelly, FP (1976年6月). 「キューのネットワーク」.応用確率論の進歩. 8 (2): 416– 432. doi :10.2307/1425912. JSTOR  1425912.
3. ジャクソン、ジェームズ・R.（2004年12月）「『ジョブショップ型待ち行列システム』に関するコメント：背景」マネジメントサイエンス誌50 (12): 1796–1802 . doi :10.1287/mnsc.1040.0268. JSTOR  30046150.
4. ジャクソン、ジェームズ・R. (1963年10月). 「ジョブショップ型待ち行列システム」.経営科学. 10 (1): 131– 142. doi :10.1287/mnsc.1040.0268. JSTOR  2627213.1963年1月のバージョンは、http://www.dtic.mil/dtic/tr/fulltext/u2/296776.pdf で入手できます。2018年4月12日にWayback Machineでアーカイブされました。
5. Jackson, JR (1957). 「待ち行列のネットワーク」.オペレーションズ・リサーチ. 5 (4): 518– 521. doi :10.1287/opre.5.4.518. JSTOR  167249.
6. ジャクソン、ジェームズ・R. (2004年12月). 「ジョブショップ型待ち行列システム」.マネジメントサイエンス. 50 (12): 1796– 1802. doi :10.1287/mnsc.1040.0268. JSTOR  30046149.
7. ライヒ, エドガー (1957年9月). 「行列がタンデムになっている場合の待ち時間」. Annals of Mathematical Statistics . 28 (3): 768– 773. doi : 10.1214/aoms/1177706889 . JSTOR  2237237.
8. ウォーランド、ジーン（1983年11月）「準可逆キューネットワークの確率的考察」IEEE Transactions on Information Theory . 29 (6): 825– 831. doi :10.1109/TIT.1983.1056762.
9. Jackson, RRP (1995). 「書評：待ち行列ネットワークと積形式：システムアプローチ」. IMA Journal of Management Mathematics . 6 (4): 382– 384. doi :10.1093/imaman/6.4.382.
10. Gordon, WJ; Newell, GF (1967). 「指数関数型サーバーを備えた閉キューイングシステム」.オペレーションズ・リサーチ. 15 (2): 254. doi :10.1287/opre.15.2.254. JSTOR  168557.
11. Goodman, Jonathan B.; Massey, William A. (1984年12月). 「非エルゴード的ジャクソンネットワーク」. Journal of Applied Probability . 21 (4): 860– 869. doi :10.2307/3213702. JSTOR  3213702.
12. Walrand, J.; Varaiya, P. (1980年12月). 「ジャクソンネットワークにおける滞在時間と追い越し条件」.応用確率論の進歩. 12 (4): 1000–1018 . doi :10.2307/1426753. JSTOR  1426753.
13. チェン・ホン、ヤオ・デイビッド・D. (2001). 『待ち行列ネットワークの基礎：性能、漸近論、最適化』 シュプリンガー. ISBN 0-387-95166-0。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Jackson_network&oldid=1309532552"