Social Optimization Systems Laboratory: 待ち行列：BCMP Network(1)

BCMPネットワークについて考えていきます。
BCMP ネットワークでは待ち行列ネットワークが拡張されています。開放型、閉鎖型の両方が表現でき、複数の客クラスを持てます。またサービスについても、FCFS(First Come First Served)、プロセッサーシェアリング、LCFS-PR(Last Come First Served with Preemption)、無限サーバがありますが、ここではFCFSを扱います。

(1) 今回のモデルの特徴をまとめると下記になります。

閉鎖型待ち行列ネットワーク。ノード数：m、ネットワーク内客数：N
複数の客クラスを持つ。クラス数：J
各ノードでのサービスはFCFS。サービス時間はμi(ni)の指数分布に従う(全ての客クラスで共通)

(2) 推移確率の定義
ノード：i、クラス：μから、ノード：j、クラス：νに移動する確率を次のようにする。

クラスの集合Tを次のように定義しておく。

推移確率は次を満たす。

推移確率行列Rは上記になります。ノードへの移動の推移確率行列のブロックが、クラス推移に対してそれぞれ存在します。

(2) ノードiへのクラスμの客の総到着率：トラフィック方程式を解く(閉鎖型)
ノードiへのクラスμの客の総到着率を求めるために、トラフィック方程式 α = α R (閉鎖型)を解いていきます。ここでαはクラス別にm個のノードを並べたm * J 個のベクトルです。

トラフィック方程式の右辺は下の式になります。

これを計算すると、m * J個のベクトルができますが、それぞれの成分はαとRの列(To Class)の内積になります。簡単に書くと、次のようになります。

最初の第1成分だけ取り出して見ると(上の図の一番左側)、m個のベクトルができます。この時、(1) クラスを固定、(2) ノードkを動かして計算していきます。

To Class 1だけで考えると、上記のm個のベクトルができるので、これをTo Class 全てで考えると、m * J 個のベクトルができます。

つまり、ノードi、クラスμにおけるトラフィック方程式を成分で書くと、

この m * J 個の連立方程式を解くことになります。この場合、解は相対値で出てきますが、解を固定するために、α11 = 1とおきます。

を式変形すると、Rの転置行列を使って、次のように変形できます。

さらに、α11 = 1とすると、式変形ができますが、簡単に４行４列でやった場合が次になります。

つまり、転置した行列の第１行と第１列要素を取り除いた行列を作成し、右辺に転置行列の第１列の第２成分から全てを書きます。転置前の行列では赤の部分になります。

(3) トラフィック方程式を実際に求める
簡単に考えるために、客は２クラスで同じ推移確率で動くとします。ノード数は12です。クラス間の移動は無いものとします。
例えば推移確率行列を図のように作ってみました。

緑の部分はクラス1からクラス１へのノード間推移確率行列です。右上と左下のグレーの部分はそれぞれ、クラス1 -> クラス2、クラス2 -> クラス1へ移動する場合のノード間推移確率です。クラス間の移動が無いため、全て0となります。右下の黄色の部分はクラス2でのノード間推移確率になります。ノード数が12、クラス数が2のため12*2=24、24*24の推移確率行列になります。

次にトラフィック方程式用の行列を用意します。上でも書いた通り、Rを転置して、１行、１列の要素を全て取り除き、対角要素は-1したものです。(m * J -1) × (m * J -1)の大きさになります。

実は、このようにクラス間移動が無い場合、閉鎖型待ち行列ネットワークのモデルとして、うまくないです。このようにクラス間移動がない場合、閉鎖型待ち行列ネットワークが２個あるのと同じになります。ノードの平均系内人数は足し合わせたものになります。（これは今の僕の考え。変わるかも）
実際これをα11=1として解いてみてもクラス1は数値が求められますが、クラス2は全て0となってしまいます。クラス2のα12=1としないと求められないです。
エクセルファイル
[確認事項]
・クラス間の移動が無くても、大丈夫なはずなので、トラフィック方程式を確認(クラス間の移動がない場合、クラス2でもα12=1としないといけないか？式変形の問題なので計算してみる)

BCMPモデルとしてクラス間の移動があった場合の方がモデルとして適していると考えます。そこで次のような推移確率行列を定義します。