エングセット式

待ち行列理論では、Engset の式を使用して、M/M/c/c/N 待ち行列のブロック確率を決定します (ケンドールの表記法)。

この式は開発者であるTO Engsetにちなんで名付けられました。

アプリケーション例

車両群とオペレーターのグループを考えてみます。オペレーターはランダムにシステムに参入し、車両の使用を申請します。利用可能な車両がない場合、申請したオペレーターは「ブロック」されます（つまり、オペレーターは車両を利用せずに退出します）。車両群の所有者は、コストを最小限に抑えるために小規模な車両群を選択したいと考えていますが、ブロックされる可能性が許容範囲内となるように、十分な規模も確保したいと考えています。 ${\displaystyle c}$ ${\displaystyle N}$ ${\displaystyle c}$

式

させて

• ${\displaystyle c>0}$ サーバーの（整数）数。
• ${\displaystyle N>c}$ トラフィックのソースの数（整数）
• ${\displaystyle \lambda >0}$ アイドル状態のソース到着率（つまり、空きソースが要求を開始する率）
• ${\displaystyle h>0}$ 平均保留時間（つまり、サーバーがリクエストを処理するのにかかる平均時間）であること。

そして、ブロッキングの確率は^{[ 1 ]}で与えられる。

${\displaystyle P={\frac {{\binom {N-1}{c}}\left(\lambda h\right)^{c}}{\sum _{i=0}^{c}{\binom {N-1}{i}}\left(\lambda h\right)^{i}}}.}$

項を並べ替えると、上記の式は^{[ 2 ]のように書き直すことができる。}

${\displaystyle P={\frac {1}{{}_{2}F_{1}(1,-c;Nc;-1/(\lambda h))}}}$

ここで、 はガウス超幾何関数です。 ${\displaystyle {}_{2}F_{1}}$

計算

数値的に安定した方法で 計算するために使用できる再帰^{[ 3 ]がいくつかあります。}${\displaystyle P}$

あるいは、超幾何関数をサポートする任意の数値計算パッケージを使用することもできます。以下にいくつかの例を示します。

SciPyを使ったPython

scipy.specialからhyp2f1をインポートします。P = 1.0 / hyp2f1 ( 1 , - c , N - c , - 1.0 / ( Lambda * h ))

MATLABとSymbolic Math Toolbox

P = 1 /超幾何([ 1 , - c ], N - c , - 1 / ( Lambda * h ))

不明なソースの到着率

実際には、ソース到着率は不明（または推定困難）である一方、ソースあたりの提供トラフィックは既知であることが多い。この場合、関係式を次のように置き換えることができる。 ${\displaystyle \lambda}$ ${\displaystyle \alpha >0}$

${\displaystyle \lambda h={\frac {\alpha }{1-\alpha (1-P)}}}$

ソース到着率とブロッキング確率の関係をEngset式に代入して固定点方程式を得る

${\displaystyle P=f(P)}$

どこ

${\displaystyle f(P)={\frac {1}{{}_{2}F_{1}(1,-c;Nc;1-P-1/\alpha )}}.}$

計算

上記の方法により式から未知数は除去されますが、複雑さが増します。つまり、ブロッキング確率を直接計算できなくなり、代わりに反復法を使用する必要があります。固定小数点反復法は魅力的ですが、そのような反復法を に適用すると発散することがあることが示されています。^{[ 2 ]}あるいは、二分法またはニュートン法のいずれかを使用することもできます。これらのオープンソース実装は利用可能です。 ${\displaystyle \lambda}$ ${\displaystyle f}$

参考文献

1. Tijms, Henk C. (2003).確率モデル入門. John Wiley and Sons. doi : 10.1002/047001363X .
2. Azimzadeh, Parsiad; Carpenter, Tommy (2016). 「高速Engset計算」.オペレーションズ・リサーチ・レターズ. 44 (3): 313– 318. arXiv : 1511.00291 . doi : 10.1016/j.orl.2016.02.011 . ISSN 0167-6377 . 
3. Zukerman, Moshe (2000). 「待ち行列理論と確率的テレトラフィックモデル入門」(pdf) . 2012年11月27日閲覧。