【論文翻訳】M/D/c待ち行列の新しい結果と古い結果（２）

2. M/D/c待ち行列
M/D/cモデルで客の到着過程はレート $\lambda$ のポアソン過程であり、客のサービス時間は定数 $D$ であり $c$ 個の同等のサーバが使用可能である。無限の待合室が存在する。客は到着の順番にサービスを受ける。サーバ稼働率 $\rho=\lambda{D}$ は１より小さいと仮定する。
M/D/c待ち行列の正確なアルゴリズムの分析はすでにCrommelinが1932年に発行した仕事にまでさかのぼる。[2]参照。状態確率についての無限連立一次方程式はセクション2.1で与えられる。またこのセクションではこれらの方程式の数値解のための洗練されかつ効率的な方法が検討される。セクション2.2では[4]で提案された、定常待ち時間確率の計算のための近年のアルゴリズムを与える。セクション2.3ではM/D/c待ち行列での平均待ち時間と待ち時間のパーセンタイルの迅速な工学的近似を、M/M/c待ち行列での対応する結果とともに与える。

2.1. 状態確率
時刻 $t$ にシステム内に客が $j$ 人いる確率を $p_j(t)$ で示すことにし、 $j=0,1,$ …について状態確率 $p_j$ を $p_j=\lim_{t\rightar\infty}p_j(t)$ で定義する。 $p_j$ は $j=0,1,$ …についての方程式
$p_j=e^{-\lambda{D}}\frac{(\lambda{D})^j}{j!}\Bigsum_{k=0}^cp_k+\Bigsum_{k=c+1}^{c+j}p_ke^{-\lambda{D}}\frac{(\lambda{D})^{j-k+c}}{(j-k+c)!}$
と正規化の式 $\Bigsum_{j=0}^{\infty}p_j=1$ の唯一解である。[2,5]参照。この無限連立一次方程式は[5]で検討された幾何的裾野方法を用いることによって比較的小さな連立一次方程式に簡略することが出来る。状態確率 $p_j$ は $j\rightar\infty$ で幾何的裾野の振る舞い $p_j\sim\sigma\tau^{-j}$ を示す。ただし $\tau$ は方程式 $e^{\lambda{D}(1-\tau)}\tau^c=1$ の間隔(1,∞)での唯一解であり $\sigma$ は正の定数である。 $j$ が充分に大きい時に $p_j/p_{j-1}\approx\tau^{-1}$ なので、適切に $M$ を選んで $j{\ge}M$ の時に $p_j$ を $pM\tau^{-(j-M)}$ で置き換える。 $p_j$ についての無限連立方程式と正規化方程式 $\Bigsum_{j=0}^{\infty}p_j=1$ はそこで $M+1$ 次元の有限連立方程式に簡略化される。比較的小さな $M$ の値が通常実務上において充分よい。というのは $p_j$ の漸近展開は比較的小さな $j$ の値についてすでに適合しているからである。[5]参照。言いかえれば、この有限連立方程式の大きさは通常、力ずくの打ち切りによって得られた有限連立方程式の大きさよりずっと小さい。システムのトラフィック負荷が１に近づく時、 $M$ の値は実用的な範囲を越えて大きくならない。幾何的裾野法は、ガウスの消去法によって通常解くことの出来る、比較的小さい連立一次方程式をもたらす。この方法はあらかじめ漸近展開の遅れファクタ $1/\tau$ を計算する必要がある。これは数値解析では標準的なことであり、 $\tau$ についての方程式の両辺の対数をとり、変形 $\eta=1/\tau$ を用いることが勧められている。有限連立一次方程式を解くことによってM/D/c待ち行列での状態確率は普通に計算することが出来ると我々は結論出来る。 $p_j$ の計算値の精度の検証はビジーサーバの数の平均値についてのリトルの関係 $\Bigsum_{j=1}^{c-1}jp_j+c\left(\Bigsum_{j=c}^{\infty}p_j\right)=\lambda{D}$ である。