ジャクソンネットワーク - 版の履歴

2008年11月9日 (日) 09:36にAlbeit-Kunによる

2008-11-09T09:36:18Z

Fujimoto: "ジャクソンネットワーク" の保護を解除しました。

2008-08-06T04:45:27Z

"ジャクソンネットワーク" の保護を解除しました。

2008年8月6日 (水) 04:13にSakasegawaによる

2008-08-06T04:13:02Z

2008年8月6日 (水) 01:39にSakasegawaによる

2008-08-06T01:39:04Z

2007年9月20日 (木) 09:50にSaruによる

2007-09-20T09:50:22Z

2007年9月18日 (火) 13:47にSaruによる

2007-09-18T13:47:14Z

2007年8月8日 (水) 13:30にKanda.kによる

2007-08-08T13:30:07Z

Orsjwiki: "ジャクソンネットワーク" を保護しました。 [edit=sysop:move=sysop]

2007-07-20T02:12:52Z

"ジャクソンネットワーク" を保護しました。 [edit=sysop:move=sysop]

122.17.2.240: 新しいページ: ''''【じゃくそんねっとわーく (Jackson network)】''' 各ノードは1つまたは複数の窓口からなり, 指数分布にしたがうサービス時間でサー...'

2007-07-12T10:28:31Z

新しいページ: ''''【じゃくそんねっとわーく (Jackson network)】''' 各ノードは1つまたは複数の窓口からなり, 指数分布にしたがうサービス時間でサー...'

新規ページ

'''【じゃくそんねっとわーく (Jackson network)】'''

各ノードは1つまたは複数の窓口からなり, 指数分布にしたがうサービス時間でサービスを行い, ノードでのサービスを終えた客は次のノードまたは外部を確率的経路選択にしたがって選ぶ待ち行列ネットワーク. 客をクラスにより区別しない. 外部からポアソン過程にしたがって客が到着する開放型と,常に一定数の客が網内を循環している閉鎖型に分けられる. ネットワーク状態の定常確率分布は積形式をもつ. 基本的なモデルとして重要なものであり, 広く応用されている.

← 古い版		2008年11月9日 (日) 09:36時点における版
120行目:		120行目:
	. ''Advances in Applied Probability, '' '''30''' (1998), 1111--1129.		. ''Advances in Applied Probability, '' '''30''' (1998), 1111--1129.

−	[[category:待ち行列ネットワーク\|~~まちぎょうれつねっとわーく（じゃくそんがたとそのおうよう）~~]]	+	[[category:待ち行列\|じゃくそんねっとわーく]]
		+
		+	[[category:待ち行列ネットワーク\|じゃくそんねっとわーく]]
		+
		+	[[category:待ち行列の応用\|じゃくそんねっとわーく]]

@@ 2行目: / 2行目: @@
-=== 概要 ===
+== 概要 ==
 各ノードはひとつまたは複数の[[窓口]]からなり，
@@ 14行目: / 14行目: @@
 基本的なモデルとして重要なものであり，広く応用されている．
-=== 詳説 ===
+== 詳説 ==
 　ジャクソンネットワークの名は J.R.Jackson[5]に因る．1970年代後半から, 計算機システムの評価に応用されはじめた．待ち行列網の状態変化がマルコフ過程として記述され, 平衡方程式の解である定常確率分布が[[積形式解|積形式]]として陽に表される基本的なモデルとして重要なものとなっている．
@@ 25行目: / 25行目: @@
 については，発展した型である[[BCMPネットワーク|BCMP型]]や[[ケリーネットワーク|ケリー型]]などのネットワークに分類される．また，外部からの到着があるが，系内に入ることができる客数に制限がある[[有限呼源待ち行列|有限呼源]](もしくは損失型)の場合，外部を一つのノードとみなすことにより，閉鎖型に帰着できる（[5]参照）．
-'''積形式解'''　この待ち行列網の状態を <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> とすれば, これは次のような積形式になる.
+=== 積形式解 ===
@@ 58行目: / 59行目: @@
 長さは互いに独立になる．また，閉鎖型も含め，各ノードからの退去過程がポアソン過程になる．したがって，どんな部分ネットワークに対しても，部分ネットワー%ク全体を１つのノードで置き換えて，他の部分の定常分布が変えないようにすることができ, すなわち，[[ノートンの定理|ノートンの定理]]が任意の部分ネットワークに対して成り立つ[11]．さらに，１つのノードへの各到着時点で，到着した客が見るネットワークの状態の分布は任意時点の状態分布と一致する．これを[[到着定理|到着定理]]という．ただし，網が閉鎖型の場合には，任意時点の分布として，到着した客を除いた網を使う．さらにその客の退去時点での分布も同様であり[6]，この分布でのもとで，ノード<math>i\, </math>に到着してから，次にそこに戻るまでの平均周期時間はノードごとの平均訪問回数と平均待ち時間の積の総和となること等が求まる．
-'''正規化定数と性能評価量の計算'''　積形式解から定常分布を求めるためには正規化定数の計算が必要である．開放型の場合は容易であるが，閉鎖型の場合には，可能な状態が<math>\textstyle \sum_{i=1}^M n_i =N\, </math>を満たすもに限られるので，工夫が必要である．例えば，閉鎖型正規化定数を計算する方法として，[[たたみ込み法]]や[[平均値解析法]]が知られている．[2]．たたみこみ法では, ノード <math>i\, </math> に対し, <math>N+1\, </math> 次元のベクトルを
+=== 正規化定数と性能評価量の計算 ===
 <center>
@@ 71行目: / 73行目: @@
 とし，<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]参照）．また，このモデルは，サービス完了時刻でネットワークの変化を追うと離散時間型のモデルと見なすこともできる．
+=== 集団移動型 ===
@@ 86行目: / 91行目: @@
 ----
-'''参考文献'''
+=== 参考文献 ===
 [1] P. J. Burke, "The Output Process of a Stationary M/M/s Queuing System, ''The Annals of Mathematical Statistics'', '''39''' (1968), 1144-1152.

@@ 1行目: / 1行目: @@
 '''【 じゃくそんねっとわーく (Jackson network) 】'''
 各ノードはひとつまたは複数の[[窓口]]からなり，
@@ 11行目: / 14行目: @@
 基本的なモデルとして重要なものであり，広く応用されている．
-詳しくは[[《待ち行列ネットワーク(ジャクソン型とその応用)》|基礎編：待ち行列ネットワーク(ジャクソン型とその応用)]]を参照していただきたい．
+=== 詳説 ===

@@ 1行目: / 1行目: @@
 '''【 じゃくそんねっとわーく (Jackson network) 】'''
-各ノードは1つまたは複数の窓口からなり，
+各ノードはひとつまたは複数の[[窓口]]からなり，
-指数分布にしたがうサービス時間でサービスを行い，
+[[指数分布]]にしたがうサービス時間でサービスを行い，
-ノードでのサービスを終えた客は次のノードまたは外部を確率的経路選択に
+ノードでのサービスを終えた[[客]]は次のノードまたは外部を[[確率的経路選択]]に
-したがって選ぶ待ち行列ネットワーク．
+したがって選ぶ[[待ち行列ネットワーク]]．
 客をクラスにより区別しない．
-外部からポアソン過程にしたがって客が到着する開放型と，
+外部から[[ポアソン過程]]にしたがって客が到着する開放型と，
 常に一定数の客が網内を循環している閉鎖型に分けられる．
 ネットワーク状態の定常確率分布は積形式をもつ．

@@ 1行目: / 1行目: @@
-'''【じゃくそんねっとわーく (Jackson network)】'''
+'''【 じゃくそんねっとわーく (Jackson network) 】'''
-各ノードは1つまたは複数の窓口からなり, 指数分布にしたがうサービス時間でサービスを行い, ノードでのサービスを終えた客は次のノードまたは外部を確率的経路選択にしたがって選ぶ待ち行列ネットワーク. 客をクラスにより区別しない. 外部からポアソン過程にしたがって客が到着する開放型と,常に一定数の客が網内を循環している閉鎖型に分けられる. ネットワーク状態の定常確率分布は積形式をもつ. 基本的なモデルとして重要なものであり, 広く応用されている.
+各ノードは1つまたは複数の窓口からなり，
-詳しくは[[《待ち行列ネットワーク(ジャクソン型とその応用)》|基礎編：待ち行列ネットワーク(ジャクソン型とその応用)]]を参照.
+詳しくは[[《待ち行列ネットワーク(ジャクソン型とその応用)》|基礎編：待ち行列ネットワーク(ジャクソン型とその応用)]]を参照していただきたい．

← 古い版	2008年8月6日 (水) 04:45時点における版
(相違点なし)

← 古い版		2007年8月8日 (水) 13:30時点における版
2行目:		2行目:

	各ノードは1つまたは複数の窓口からなり, 指数分布にしたがうサービス時間でサービスを行い, ノードでのサービスを終えた客は次のノードまたは外部を確率的経路選択にしたがって選ぶ待ち行列ネットワーク. 客をクラスにより区別しない. 外部からポアソン過程にしたがって客が到着する開放型と,常に一定数の客が網内を循環している閉鎖型に分けられる. ネットワーク状態の定常確率分布は積形式をもつ. 基本的なモデルとして重要なものであり, 広く応用されている.		各ノードは1つまたは複数の窓口からなり, 指数分布にしたがうサービス時間でサービスを行い, ノードでのサービスを終えた客は次のノードまたは外部を確率的経路選択にしたがって選ぶ待ち行列ネットワーク. 客をクラスにより区別しない. 外部からポアソン過程にしたがって客が到着する開放型と,常に一定数の客が網内を循環している閉鎖型に分けられる. ネットワーク状態の定常確率分布は積形式をもつ. 基本的なモデルとして重要なものであり, 広く応用されている.
		+
		+	詳しくは[[《待ち行列ネットワーク(ジャクソン型とその応用)》\|基礎編：待ち行列ネットワーク(ジャクソン型とその応用)]]を参照.