7.4.2.2.近似の解法:Quantitative System Performance
「7.4.2.1.厳密な解法」の続きです。(目次はこちら)
7.4.2.2.近似の解法
厳密な解法はクラスが多い場合に法外な時間とスペースを要求する可能性があるので、しばしば近似の解法が実際に使用出来る唯一の解法である。さらに、近似解法は非常に正確なので、厳密に解けるネットワークについてであってもそれは一般的な方法として有用である。
複数クラス近似解法は単一クラス近似法の素直な拡張である。式(7.1)〜(7.3)を利用するが、到着時待ち行列長は繰り返して評価される。見積り値は客のフル個体数についてサービスセンターでの時間平均待ち行列長に基づいて得られる。よって、近似解法は最初にゼロ個体数からフル個体数の間の全ての個体数についての解を計算することを要求しない。繰り返しを始めるために時間平均待ち行列長についての初期推定がなされる。この推定をするために近似関数が適用され、その結果の近似到着時待ち行列長が式(7.3)の中で使用される。式(7.1)と(7.2)の適用は時間平均待ち行列長についての新しい見積り値をもたらし、次にそれらは繰り返しの次のステップを開始するために用いることが出来る。繰り返しは時間平均待ち行列長の連続する見積り値が充分近くなるまで続く。近似解法はアルゴリズム7.3としてまとめられた。
- 全ての、についてとセットする。
- 全ての、についてによってを近似する。(の選択は文章中で検討される。)
- 式(7.1)〜(7.3)を適用して全ての、についての新しいひと組を計算する。
- もしステップ3の結果のがステップ2で入力として用いたとある許容範囲(例えば、0.1%)内で一致しなければ、新しいを用いてステップ2に戻る。
アルゴリズム7.3 近似MVA解法(クローズド・モデル)
この方法が厳密解法に目だって優れている点は、空のネットワークについての解から組み立てていくのではなく、フルの客個体数を持つネットワークの解の上を解法が繰り返すことである。よってこの近似は1つの個体数だけについてネットワークの解を維持するので、厳密解法よりずっと少ない記憶場所しか要求しない。特に、記憶場所の要求はとの積に比例する。時間の節約は、近似アルゴリズムの繰り返しの性質のために定量化が難しいが、経験的にはこれらの節約はかなりのものである。繰り返し1回あたりに要求される演算の数はとの積に比例する。(言い換えれば、クラスの個体数は関係がない。) 待ち行列長の0.1%未満の変化への収束のために通常2ダースより少ない繰り返ししか必要ない。この解法の精度は通常、スループットと稼動率について厳密解の数パーセント以内であり、待ち行列長と滞在時間について10%以内である。
前述のように、近似解法は、フル個体数を持つネットワークの解から得られた情報にのみ依存する、各々のクラスについて各々のデバイスでの到着時待ち行列長の見積りに基ついて成り立っている。用いて成功してきた関数の特定の見積りは以下である。
- (7.5)
式(7.5)を厳密な公式(7.4)と比較すると、近似でなされた仮定は、ネットワークからの1個の客の除去は他のクラスの客の配置に影響を与えず、それ自身のクラスの待ち行列長をそのもともとの大きさに比例して縮小することであることは明らかである。実際のところ式(7.5)はうまく働いてきた。より洗練された見積りも用いられてきたが、これらは若干実装が難しく、時間とスペースの面で、より多くのマシン・リソースを必要とする。
近似解法の重要なメリットは非整数のマルチプログラミング・レベルがモデル内に容易に組み込まれることである。単にに(非整数の)マルチプログラミング・レベルを設定し近似を適用するだけである。別々の整数解の間の補正は必要ではない。
クローズド・モデルの例(近似解)
表7.4はセクション7.4.2.1(表7.3)で与えられた例の、近似解法を用いて計算された中間と最終の値を示している。全ての待ち行列の見積りの最大の変化が0.001未満になった時に繰り返しは停止された。
「7.4.3.ミックスド・モデルの解法」に続きます。