平均値分析

Mean_value_analysis
待ち行列理論、確率の数学的理論内の分野である平均値分析( MVA ) は、予想される待ち行列の長さ、待ち行列ノードでの待ち時間、および待ち行列の分離可能な閉じたシステムの平衡状態でのスループットを計算するための再帰的手法です。最初の近似手法は、Schweitzer と Bard によって個別に公開され、その後、1980 年に Lavenberg と Reiser によって正確なバージョンが公開されました 。
これは到着定理に基づいており、この定理では、 M人の顧客の閉じたシステムの 1 人の顧客がサービス施設に到着すると、システムの残りの部分がM  − 1 人の顧客を持つシステムの平衡状態にあることを観察します。
コンテンツ
1 問題設定
2 アルゴリズム
3 Bard-Schweitzer 法
3.1 疑似コード
4 マルチクラス ネットワーク
5 拡張機能
6 ソフトウェア
7 こちらもご覧ください
8 参考文献
9 外部リンク

問題設定
M人の顧客がシステム内を循環しているK M/M/1 キューの閉じたキューイング ネットワークを考えてみましょう。ネットワークの顧客クラスが 1 つになるように、顧客が互いに区別できないとします。各ノードでの平均キューの長さと待機時間、およびシステムのスループットを計算するために、顧客が 0 人のネットワークから開始する反復アルゴリズムを使用します。
ノードiでのサービス レートをμ i、顧客ルーティング マトリックスをPと書きます。ここで、要素p ijは、ノードiでサービスを終了した顧客がサービスのためにノードjに移動する確率を示します。このアルゴリズムを使用するには、まず訪問率の行ベクトルvを計算します。これはv  =  v  Pとなるベクトルです。
ここで、合計n人の顧客がシステム内にいる場合 (これには、キューiで現在処理されているジョブが含まれます) 、キューiの顧客の平均数を Li (n) と書き、平均消費時間をW j ( n )と書きます。システムに合計n人の顧客がいる場合、キューiの顧客によって。顧客がm人のシステムのスループットをλ mで表します。

アルゴリズム
アルゴリズムは、空のネットワーク (ゼロの顧客) から開始し、システム内に必要な数 ( M ) の顧客が存在するまで、各反復で顧客の数を 1 ずつ増やします。
初期化するには、k  = 1，…， Kに対してL k (0) = 0 を設定します。(これにより、顧客がいないシステムの平均キュー長がすべてのノードでゼロに設定されます。)
m  = 1，…， Mについて繰り返します。
1. k  = 1， …， Kの場合、到着定理を使用して各ノードでの待機時間を計算します W k ( メートル) = 1 + L k (メートル− 1 ) μ k .
{ W_{k}(m)={frac {1+L_{k}left(m-1right)}{mu _{k}}}.}

2. 次に、リトルの法則
を使用してシステム スループットを計算します。 λ メートル = メートル ∑ k=1 W k( メートル) v
k . { lambda _{m}={frac {m}{sum _{k=1}^{K}W_{k}(m)v_{k}}}.}

3. 最後に、各キューに適用されるリトルの法則を使用して、 k  = 1、…、K
の平均キュー長を計算します。L k( メートル) = v k λ
メートルW k( メートル) .
{ L_{k}(m)=v_{k}lambda _{m}W_{k}(m).}

リピート終了。

Bard-Schweitzer 法
Bard-Schweitzer 近似は、ノードkでのジョブの平均数を と推定します。L k( メートル− 1 ) ≒
メートル− 1
メートルL k( メートル ) { L_{k}(m-1)approx {frac {m-1}{m}}L_{k}(m)}

これは線形補間です。上記の式から、この近似は、数値的に解くことができる固定小数点関係を生成します。この反復アプローチは、概算 MVA (AMVA) と呼ばれることが多く、通常、MVA の再帰的アプローチよりも高速です。 : 38 

疑似コード
L k ( m ) = M / Kを設定します
収束するまで繰り返す: λ メートル = メートル∑ k = 1 K
メートル− 1
メートルL k( メートル ) +1 k v k
{ lambda _{m}={frac {m}{sum _{k=1}^{K}{frac {{frac {m-1}{m}}L_{k}( m)+1}{mu _{k}}}v_{k}}}}

L k ( メートル) = v k λ
メートル
メートル− 1
メートルL k( メートル ) +1 k { L_{k}(m)=v_{k}lambda _{m}{frac {{frac {m-1}{m}}L_{k}(m)+1}{mu _{k}}}}

マルチクラス ネットワーク
Rクラスの顧客を持つマルチクラス ネットワークの場合、各キューkは、ジョブ クラスr=1，…，Rごとに異なるサービス レートμ k，rを特徴とすることができますが、先着順の場合には特定の制限が存在します。 -マルチクラスの場合のBCMP 定理の仮定により、サービスを受けるステーション。
キューkでクラスrジョブが経験する待機時間W k，rは、到着定理の一般化を使用して、ノードkでの合計平均キュー長に関連付けることができます。W k r( メートル) = 1 + L k ( メートル− 1 r ) μ k r .
{ W_{k，r}(mathbb {m} )={frac {1+L_{k}left(mathbb {m} -1_{r}right)}{mu _{k 、r}}}.}

どこ
メートル = ( メートル
1 … メートル R) { mathbb {m} =(m_{1}，ldots ，m_{R})}

はRクラスの顧客母集団のベクトルであり、1 r
{ 1_{r}}

のr番目の要素から 1 を減算します
メートル
{ mathbb {m} }

、 仮定して
メートル r 1 { m_{r}geq 1}
. 顧客クラスが 1 つのネットワークの場合、MVA アルゴリズムは非常に高速であり、かかる時間は顧客の数とキューの数に比例して増加します。ただし、マルチクラス モデルでは、乗算と加算の数、および MVA のストレージ要件は、顧客クラスの数に応じて指数関数的に増加します。実際には、このアルゴリズムは 3 ～ 4 人の顧客クラスでうまく機能しますが、これは一般にモデルの実装と構造に依存します。たとえば、ルーティング マトリックスがまばらな場合、Tree-MVA メソッドはより大きなモデルにスケーリングできます。
平均パフォーマンス メトリックの正確な値は、対数二次時間を必要とするモーメント法を使用して大規模モデルで取得できます。モーメント法は、正確な MVA では通常アクセスできない、最大 10 クラスまたは場合によってはそれ以上のクラスの顧客を含む実際のモデルを解決できます。 ただし、この手法は到着定理を使用せず、待ち行列ネットワークの状態確率の正規化定数を含む線形方程式系を解くことに依存しています。
Bard-Schweitzer 法などの近似 MVA (AMVA) アルゴリズムは、代わりに、マルチクラス ネットワークでも複雑さが低く、通常は非常に正確な結果を提供する代替ソリューション手法を提供します。

拡張機能
平均値分析アルゴリズムは、待ち行列ネットワークとキー配布センターのパフォーマンスを記述するPEPAモデルのクラスに適用されています。

ソフトウェア
JMVAは、 MVA を実装するJavaで記述されたツールです。
queuing 、 MVA を含むGNU Octaveのライブラリ。
Lineは、正確な MVA アルゴリズムと近似 MVA アルゴリズムを含む MATLAB ツールボックスです。

こちらもご覧ください
待ち行列理論

参考文献
^ Schweitzer， PJ; セラッツィ、Ｇ．ブログリア、M. (1993)。「キューの閉じたネットワークにおけるボトルネック分析の調査」。コンピュータおよび通信システムの性能評価。コンピュータ サイエンスの講義ノート。巻。729.p。491.ドイ: 10.1007/BFb0013865 . ISBN 978-3-540-57297-8.
^ バード、ヨナサン（1979）。マルチクラス キューイング ネットワーク分析の一部の拡張。コンピュータ システムのモデリングとパフォーマンス評価に関する第 3 回国際シンポジウムの議事録: コンピュータ システムのパフォーマンス。North-Holland Publishing Co. pp. 51–62。ISBN 978-0-444-85332-5.
^ アダン、I.; ウォル、J.（2011）。「平均値テクニック」。キューイング ネットワーク。オペレーションズ リサーチと経営科学の国際シリーズ。巻。154.p。561.ドイ: 10.1007/978-1-4419-6472-4_13 . ISBN 978-1-4419-6471-7.
^ ライザー、M。ラベンバーグ、SS (1980)。「クローズド マルチチェーン キューイング ネットワークの平均値分析」。ACM のジャーナル。27 (2): 313. doi : 10.1145/322186.322195 .
^ Reiser、M.（2000）。「平均値分析：個人アカウント」. パフォーマンス評価: 起源と方向性。コンピュータ サイエンスの講義ノート。巻。1769. pp. 491–504. ドイ: 10.1007/3-540-46506-5_22 . ISBN 978-3-540-67193-0.
^ ボーズ、サンジェイK.（2001）。待ち行列システムの紹介。スプリンガー。p。174.ISBN _ 978-0-306-46734-9.
^ Schweitzer、ポール (1979)。「キューのマルチクラスの閉じたネットワークの近似分析」。確率制御と最適化に関する国際会議の議事録。
^ テイ、YC （2010)。「コンピュータ システムの分析パフォーマンス モデリング」。コンピュータサイエンスの総合講義。2 : 1 ～ 116。ドイ：10.2200/S00282ED1V01Y201005CSL002。
^ カサーレ、G. （2011)。「モーメント法による性能モデルの正確な分析」 (PDF) . パフォーマンス評価。68 (6): 487–506. CiteSeerX  10.1.1.302.1139 . ドイ: 10.1016/j.peva.2010.12.009 .
^ Hoyme、KP。サウスカロライナ州ブリュール。アフシャリ、PV。ケイン、RY（1986）。「ツリー構造の平均値分析アルゴリズム」。コンピューター システム上の ACM トランザクション。4 (2): 178–185. ドイ: 10.1145/214419.214423 .
^ カサーレ、G. （2008)。「CoMoM: マルチクラス キューイング ネットワークの確率論的評価のためのクラス指向アルゴリズム」 . ソフトウェア工学に関するIEEEトランザクション。35 (2): 162–177. CiteSeerX  10.1.1.302.1139 . ドイ: 10.1016/j.peva.2010.12.009 .
^ ザホージャン、ジョン。熱心な、デレク L.; Sweillam、Hisham M. (1988)。「近似平均値解析の精度・速度・収束」. パフォーマンス評価。8 (4): 255–270。ドイ：10.1016/0166-5316(88)90028-4 .
^ トーマス、N.; Zhao， Y. （2010)。「PEPA モデルのクラスの平均値分析」 . 計算します。J. 54 (5): 643–652. ドイ: 10.1093/comjnl/bxq064 .
^ ベルトリ、M。カサーレ、Ｇ．Serazzi、G.（2009）。「JMT: システム モデリングのためのパフォーマンス エンジニアリング ツール」 (PDF) . ACM SIGMETRICS パフォーマンス評価レビュー。36 (4): 10.ドイ: 10.1145/1530873.1530877 .
^ Marzolla、M.（2014）。「オクターブ キューイング パッケージ」 . システムの定量的評価。コンピュータ サイエンスの講義ノート。巻。8657. pp. 174–177. ドイ: 10.1007/978-3-319-10696-0_14 . ISBN 978-3-319-10695-3.

外部リンク
J. Virtamo: 待ち行列ネットワーク。ヘルシンキ工科大学からの配布資料には、ジャクソンの定理と MVA の概要が説明されています。
Simon Lam: MVA アルゴリズムの簡単な派生. Buzenのアルゴリズムと MVAの関係を示します。”