Engset-Formel

In der Warteschlangentheorie wird die Engset-Formel verwendet, um die Blockierungswahrscheinlichkeit einer M/M/c/c/N-Warteschlange (in Kendalls Notation ) zu bestimmen.

Die Formel ist nach ihrem Entwickler, T. O. Engset, benannt .

Betrachten wir eine Fahrzeugflotte mit Fahrern. Fahrer melden sich zufällig im System an, um ein Fahrzeug anzufordern. Stehen keine Fahrzeuge zur Verfügung, wird der anfragende Fahrer „blockiert“ (d. h., er verlässt das System ohne Fahrzeug). Der Flottenbesitzer möchte eine kleine Flotte auswählen, um die Kosten zu minimieren, aber gleichzeitig eine ausreichend große, um eine akzeptable Blockierungswahrscheinlichkeit zu gewährleisten. ${\displaystyle c}$${\displaystyle N}$${\displaystyle c}$

Lassen

• ${\displaystyle c>0}$sei die (ganzzahlige) Anzahl der Server.
• ${\displaystyle N>c}$die (ganzzahlige) Anzahl der Verkehrsquellen;
• ${\displaystyle \lambda >0}$die Ankunftsrate der freien Quelle (d. h. die Rate, mit der eine freie Quelle Anfragen initiiert);
• ${\displaystyle h>0}$die durchschnittliche Wartezeit (d. h. die durchschnittliche Zeit, die ein Server benötigt, um eine Anfrage zu bearbeiten);

Die Wahrscheinlichkeit einer Blockierung ergibt sich dann aus ^{[ 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}}}.}$

Durch Umstellen der Terme lässt sich die obige Formel wie folgt umschreiben: ^{[ 2 ]}

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

wobei die Gaußsche hypergeometrische Funktion ist . ${\displaystyle {}_{2}F_{1}}$

Es gibt mehrere Rekursionen ^{[ 3 ]} , mit denen sich numerisch stabile Berechnungen durchführen lassen .${\displaystyle P}$

Alternativ kann jedes numerische Softwarepaket verwendet werden , das die hypergeometrische Funktion unterstützt. Einige Beispiele sind unten aufgeführt.

Python mit SciPy

from scipy.special import hyp2f1 P = 1.0 / hyp2f1 ( 1 , - c , N - c , - 1.0 / ( Lambda * h ))

MATLAB mit der Symbolic Math Toolbox

P = 1 / hypergeom ([ 1 , - c ], N - c , - 1 / ( Lambda * h ))

In der Praxis ist es häufig der Fall, dass die Ankunftsrate der Quelle unbekannt (oder schwer abzuschätzen) ist, während der angebotene Datenverkehr pro Quelle bekannt ist. In diesem Fall kann man die Beziehung einsetzen. ${\displaystyle \lambda }$${\displaystyle \alpha >0}$

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

Die Gleichung zwischen der Quellankunftsrate und der Blockierungswahrscheinlichkeit wird in die Engset-Formel eingesetzt, um zur Fixpunktgleichung zu gelangen.

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

Wo

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

Obwohl die obige Vorgehensweise die Unbekannte aus der Formel entfernt , führt sie zu einer zusätzlichen Komplexität: Die Blockierungswahrscheinlichkeit lässt sich nicht mehr direkt berechnen, sondern muss iterativ berechnet werden . Eine Fixpunktiteration erscheint zwar verlockend, es hat sich jedoch gezeigt, dass sie bei Anwendung auf bestimmte Parameter manchmal divergent ist . ^{[ 2 ]} Alternativ kann man die Bisektionsmethode oder das Newton-Verfahren verwenden , für die jeweils eine Open-Source-Implementierung verfügbar ist. ${\displaystyle \lambda }$${\displaystyle f}$