待ち行列システムGI/G/1における待ちについての近似公式（１）
これから
にある
- W. Kraemer and M. Langenbach-Belz,「Approximate Formulae for the Delay in the Queueing System GI/G/1」Congressbook, Enghth Int. Teletraffic Cong., Melbourne, 1976, pp. 235-1/8.
- 待ち行列システムGI/G/1における待ちについての近似公式
の私による和訳を公開していきます。
待ち行列システムGI/G/1における待ちについての近似公式
Wolfgang KraemerとManfred Lagenbach-Belz
シュトゥットガルト大学、ドイツ連邦共和国シュトゥットガルト
摘要
一般単一サーバシステムGI/G/1はさまざまに取り扱われてきたが、扱い易い公式は若干の特別な場合についてのみ可能である。非常にしばしば、正確な計算は実務技術者にとっては扱いづら過ぎ、また精緻過ぎである。また上限下限は一般に大雑把過ぎる近似である。よって、２モーメント近似に基づいた単純で明快な近似公式でトラフィック技術者をサポートする必要が感じられた。
この論文では平均待ち時間と待ち確率についてのそのような公式がヒューリスティックに導かれる。
これらの公式の品質は正確な結果やシミュレーションの結果との数値の比較によってチェックされてきたが、サーバ稼働率が0.2から0.9までという最も興味のある範囲では、以下の分布のタイプ：D、E4、E2、M、H2で特徴付けられる到着とサービスの過程の全ての組合せについて誤差が20%未満（通常は10%未満）であるというものである。
これらのタイプのほかに妥当性確認のために、他の分布関数についても３次以上のモーメントを変えて調査された。
これらの公式はまたバッチ到着システムについても、等価な単一到着の構成を考慮することにより同程度の精度で簡単に適用可能である。
既知の関係により、例えば、対応する出発過程の変動や、空き時間の分布の１次と２次のモーメントや稼働期間の平均長さについても単純な近似が提供される。
１ 導入
1.1 概論
コンピュータと通信のシステムにおいて非常にしばしば待ち行列の問題がタイプGI/G/1（一般到着で一般サービス過程で単一サーバ）の待ち行列システムで表現される。特にトラフィック技術者にとっては、システムの解析と設計において平均待ち時間と待ち確率は興味がある。文献ではそのような待ち行列システムの正確で明快な解法は、ある種のタイプの到着とサービスの過程についてのみ利用可能である（例えば、M/G/1）。
非常に多くの場合、さまざまなトラフィックの諸仮定についてのこれらのさまざまな解法は、超越方程式の根の、コンピュータの助けを借りての数値計算を必要とする。他のタイプの到着過程とサービス過程については、非明示的解法が知られている（例。Lindleyの積分方程式に基づくもの）。しかししばしばこれらの解法は簡単ではなく、多くの計算を必要とする。
トラフィック工学の多くの応用において、これらの解法のための手続きやツールは技術者には納期内に使用可能ではないか、あるいは計算作業の量が迅速な見積もりに見合わないかのどちらかである。一方、待ちについての既知の近似公式は適用の範囲に強く制約される（例、重負荷近似）。
よって、平均待ち時間と待ち確率についての単純で明快で、かつ一般的な近似公式でトラフィック技術者をサポートする緊急の必要性が感じられた。
到着間隔とサービス時間の分布関数の１次と２次のモーメントに制限することは以下の理由で手近にあった。
- ポアソン到着の場合、平均待ち時間はサービス時間分布関数の１次と２次のモーメントにだけ依存する。
- ２モーメント近似は例えばオーバフローしたシステムについて有用であることが証明されていた。
- システム解析に用いられるモデルはしばしばそれ自身が近似モデルでありしばしば正確な分布関数はまったく知られていない。
さらに、直列待ち行列に２モーメント近似を適用し、サービス時間の多くのさまざまな分布関数を考慮して非常に心強い結果が得られた*1（3.3章も参照）。
*1:Kraemer, W. Investigations of Systems with Queues in Series (Untersuchung von Systemen mit seriellem Warten) Dissertation University of Stuttgart 1975 and 22nd Report on Studies in Congestion Theory, Institute of Switching and Data Technics 1975 ( In German).
