複数クラスを持つＭ／Ｍ／１待ち行列（１）

「ケリーネットワークの積形式解の存在証明の試み（失敗）」のあと、なかなか問題解決の糸口がつかめていません。つかめていませんが、考えたことをご紹介します。

まず、対象を非常に簡単なものにしてみました。すなわちＭ／Ｍ／１待ち行列にしてみました。しかし、この待ち行列には複数のクラスのジョブがそれぞれ指数分布の到着時刻間隔で到着するものとします。その時の定常状態分布はどのようになるか、考えてみました。
まず、状態の定義をします。クラスのない（クラスが１つだけの）Ｍ／Ｍ／１の場合の状態はシステム内のジョブの数でしたが、今回の場合、どのクラスのジョブが今、処理中であるかによって次に遷移する状態が変わることに気づきます。さらに、処理中のジョブの処理が終了した時、次に処理中になるジョブのクラスは、つまり、それまで処理を待っていた行列の先頭のジョブのクラスであるわけですから、処理中のジョブのクラスだけでなく待っているジョブのクラスも気にしなければならないことが分かります。以上のことから、状態は待ち行列（処理中のものも含める）に並んだ各ジョブのクラスの配列ごとに考えることにします。たとえば、クラスがＡ、Ｂ２つあるとし、下図の左端が処理中のジョブ、そして待ちジョブがその右に順番に並んでいるとすれば、下の図の上下２つの状態は別々の状態であると考えます。

• 

状態をで表します。そして上図の行列を左から順に１、２と番号をつけ、これを位置と呼ぶことにします。位置のクラスをで表します。さらに状態の時にクラスのジョブが到着した状態をで表します。またクラスの数をで表します。ここでは状態の定常状態確率を、は装置の平均処理時間を、はクラスのジョブのスループットを表すとします。すると状態がの間にジョブの処理が終って別の状態に遷移する確率は

• 

と表すことが出来ます。次に状態がの間にクラスのジョブが到着して状態に遷移する確率は

• 

と表すことが出来ます。状態について考えると、定常状態では前記の２つの遷移確率が等しくなるはずですから次の平衡方程式が成り立ちます。

• ・・・・・（１）

（「Ｍ／Ｍ／１における待ち時間の式の導出（２）」に平行した議論が出ています。）

ここでクラスについての利用率を

• ・・・・・（２）

で定義します。このように定義すると、式（２）の両辺を全てのクラスについて合計をとると

• ・・・・・（３）

ここで

• 

はクラスによらずこの待ち行列に到着するジョブのスループットを表していますからこれを

• 

で表すと、結局、式（３）は

• 

よって

• ・・・・・（４）

となります。ただしは装置の利用率を表しています。（４）はが装置の利用率のうちのクラスに関わる部分を表していることを示しています。

式（２）を式（１）に代入して変形すると

• ・・・・・（５）

になります。ここでシステムがまったくジョブを持たない定常状態確率をで表すことにします。すると、システムにクラスのジョブが１個だけ処理中の状態をで表すとすると、式（５）より

• ・・・・・（６）

となります。さらに、処理中のジョブのクラスがで待っているジョブのクラスがであり、この２つのジョブだけが存在する状態をで表すと式（５）と式（６）から

• 

同様に考えて、状態をと表せば、（ただしは状態の時のジョブ数であるとします）

• 

ここでは装置が空いている確率であるからになるはずなので、結局

• ・・・・・（７）

となります。

「複数クラスを持つＭ／Ｍ／１待ち行列（２）」に続きます。