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

A.J.E.M. JanssenとJ.S.H. van Leeuwaardenの論文「M/D/s待ち行列の根とErlang、Crommelin、Pollaczekの業績に戻る」と同じようにM/D/sに関する論文であるHenk Tijmsの「New and old results for the M/D/c queue」を訳すことにします。

M/D/c待ち行列の新しい結果と古い結果
Henk Tijms
Vrije University, Department of Econometrics and Operations Research,
オランダ、アムステルダム、De Boelelaan 1105, 1081 HV.

摘要
この論文で我々は、ポアソン到着と一定時間のサービスを持つ複数サーバ待ち行列における定常待ち時間確率の数値計算についての新しい結果と古い結果を検討する。無限待合室と有限待合室の両方のモデルが考察される。
(c)2006 Elsevier GmbH, All rights reserved.
キーワード：M/D/c待ち行列、待ち時間確率、状態確率、M/D/c/c＋N待ち行列

１　導入
Paul Kuihnの本「Tables on Delay Systems（待ち行列システムに関する表）」は1976年に発行された。[1]参照。この記念碑的な成果は、70年代の終わりにアムステルダムの私のグループで開始した待ち行列のアルゴリズム的方法に関する研究プロジェクトに大きく影響を与えた。Kuihnの表の本はポアソン到着と一定時間のサービスを持つ複数サーバM/D/c待ち行列についての広範囲の結果を与える最初の本であった。到着の順番にサービスが与えられる場合について、待ち時間の確率が $c=10$ サーバまで正確に計算され、 $c>10$ についてはそれらはワイブル分布を待ち時間の最初の２つのモーメントについて合せ込むことによって近似的に計算された。これらのモーメントはシステム内の客の数についての状態確率から得られた。状態確率は、無限連立一次方程式の有限打ち切りへの連続過緩和（？　successive over-relaxation）の方法を適用することで計算された。
　Pual Kuihnが用いた一般理論はイギリスの通信トラフィック技術者であるCrommelinの1932年からの先駆的な論文によって開発された理論であった。[2]参照。この論文でCrommelinはまずシステム内の数についての状態確率の計算方法を示した。次に巧みな検討を用いて彼は、状態確率を含む定常状態待ち時間確率の明示的な式を導き出した。この明示的な式は、個々の項の符号が交互に変わり、一般にその合計よりずっと大きいような無限和である。その結果、この和の数値的な見積りは顕著な桁落ちのための丸め誤差によって邪魔されている。数値計算の困難はCrommelinによってすでに気付かれており、その打開策として彼は、正の項だけの無限和の形をした待ち時間確率の等価な式を提案した。あいにく、この代替案の式はほとんど役に立たない。この代替案の式の数値計算上の問題は無限和の収束が遅いことである。収束が達成される前に計算は指数関数的な上位と下位の桁あふれによって停止するだろう。待ち時間確率の計算に向けての改善は[3]でなされた。そこでは待ち時間確率についての、Crommelinの論文に隠れていた再帰公式と漸近展開が組み合わされた。
　大きな値の $c$ についてM/D/c待ち行列における待ち時間確率の単純で正確な計算は現実的でないように見えた。近年、[4]で、待ち時間確率の正確な計算についての迅速で数値計算的に安定したアルゴリズムがFranxによって提案された。彼は一見したところ関係のない生産計画システムに関する工学的環境で働いている時に見事な解法のアイディアに行き当たった。彼の美しい公式は、状態確率の計算を検討したのちにセクション２で与えられる。興味あるひとつの問いは、M/D/cについての結果が有限の待合室を持つM/D/c/c+N待ち行列に拡張することが出来るかどうかである。この疑問はセクション３で扱われる。