BCMPネットワーク

待ち行列理論は、確率論の数学理論の一分野であり、BCMPネットワークは、積形式の平衡分布が存在する待ち行列ネットワークの一種です。このネットワークは、最初に記述された論文の著者であるBaskett、Chandy 、Muntz、Palaciosにちなんで名付けられました。この定理は、特定のサービス規律に従う限り、事実上任意の顧客ルーティングとサービス時間分布を可能にするJacksonネットワークの重要な拡張です。 ^{[ 1 ]}

この論文はよく知られており、この定理は1990年にJ.マイケル・ハリソンとルース・J・ウィリアムズによって「過去20年間の待ち行列理論における画期的な成果の1つ」と評された。^{[ 2 ]}

m個の相互接続されたキューのネットワークは、各キューが以下の4つのタイプのいずれかに該当する場合、BCMPネットワークと呼ばれます。

1. FCFS規律では、すべての顧客が同じ負の指数分布のサービス時間分布を持ちます。サービス率は状態に依存する可能性があるため、次のように記述します。${\displaystyle \scriptstyle {\mu _{j}}}$待ち行列の長さがjの場合のサービス率について。
2. プロセッサ共有キュー
3. 無限サーバーキュー
4. LCFS（事前再開機能付き）（作業内容は失われません）

最後の３つのケースでは、サービス時間分布は有理ラプラス変換を持つ必要があります。これは、ラプラス変換が^{[ 3 ]}の形式である必要があることを意味します。

${\displaystyle L(s)={\frac {N(s)}{D(s)}}.}$

また、以下の条件を満たす必要があります。

1. ノードiへの外部到着(ある場合) はポアソン過程を形成し、
2. キューiでサービスを完了した顧客は、一定の確率で新しいキューjに移動します。${\displaystyle P_{ij}}$または確率的にシステムを離れる${\displaystyle 1-\sum _{j=1}^{m}P_{ij}}$これは、キューの一部のサブセットに対してゼロ以外の値をとる。

m個のキューからなるBCMPネットワーク（オープン、クローズド、または混合型）において、各キューがタイプ1、2、3、または4である場合、平衡状態確率は次のように与えられる。

${\displaystyle \pi (x_{1},x_{2},\ldots ,x_{m})=C\pi _{1}(x_{1})\pi _{2}(x_{2})\cdots \pi _{m}(x_{m}),}$

ここで、Cは平衡状態確率の合計が 1 になるように選択された正規化定数であり、${\displaystyle \scriptstyle {\pi _{i}(\cdot )}}$は、キューiの均衡分布を表します。