Fórmula de Engset

En la teoría de colas , la fórmula de Engset se utiliza para determinar la probabilidad de bloqueo de una cola M/M/c/c/N (en la notación de Kendall ).

La fórmula recibe su nombre de su desarrollador, TO Engset .

Ejemplo de aplicación

Consideremos una flota de $c$ vehículos y $N$ operadores. Los operadores ingresan al sistema aleatoriamente para solicitar el uso de un vehículo. Si no hay vehículos disponibles, un operador solicitante es "bloqueado" (es decir, el operador se va sin un vehículo). El propietario de la flota desea elegir $c$ pequeño para minimizar los costes, pero lo suficientemente grande como para garantizar que la probabilidad de bloqueo sea tolerable.

Fórmula

Dejar

$c>0$ sea el número (entero) de servidores.
$N>c$ sea el número (entero) de fuentes de tráfico;
$\lambda >0$ sea la tasa de llegada de fuentes inactivas (es decir, la tasa a la que una fuente libre inicia solicitudes);
$h>0$ sea el tiempo de espera promedio (es decir, el tiempo promedio que tarda un servidor en procesar una solicitud);

Entonces, la probabilidad de bloqueo viene dada por ^{[ 1 ]}

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

Reorganizando los términos, se puede reescribir la fórmula anterior como ^{[ 2 ].}

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

dónde ${}_{2}F_{1}$ es la función hipergeométrica gaussiana .

Cálculo

Existen varias recursiones ^{[ 3 ]} que se pueden utilizar para calcular $P$ de manera numéricamente estable.

Como alternativa, se puede utilizar cualquier paquete numérico que admita la función hipergeométrica . A continuación se muestran algunos ejemplos.

Python con SciPy

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

MATLAB con la Caja de Herramientas de Matemáticas Simbólicas

P = 1 / hipergeometría ([ 1 , - c ], N - c , - 1 / ( Lambda * h ))

Tasa de llegada de origen desconocido

En la práctica, suele ocurrir que la tasa de llegada de la fuente $\lambda$ es desconocido (o difícil de estimar) mientras $\alpha >0$ , el tráfico ofrecido por fuente, es conocido. En este caso, se puede sustituir la relación

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

entre la tasa de llegada de la fuente y la probabilidad de bloqueo en la fórmula de Engset para llegar a la ecuación del punto fijo

P=f(P)

dónde

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

Cálculo

Si bien lo anterior elimina lo desconocido $\lambda$ A partir de la fórmula, se introduce un punto adicional de complejidad: ya no podemos calcular la probabilidad de bloqueo directamente, y debemos usar un método iterativo en su lugar. Si bien una iteración de punto fijo es tentadora, se ha demostrado que dicha iteración a veces diverge cuando se aplica a $f$ . ^{[ 2 ]} Alternativamente, es posible utilizar uno de los métodos de bisección o de Newton , para los cuales existe una implementación de código abierto .

Referencias

↑ Tijms, Henk C. (2003). Un primer curso de modelos estocásticos . John Wiley and Sons. doi : 10.1002/047001363X .
1 2 Azimzadeh, Parsiad; Carpenter, Tommy (2016). "Cálculo rápido de Engset". Operations Research Letters . 44 (3): 313– 318. arXiv : 1511.00291 . doi : 10.1016/j.orl.2016.02.011 . ISSN 0167-6377 .
↑ Zukerman, Moshe (2000). "Una introducción a la teoría de colas y a los modelos estocásticos de teletrafico" (pdf) . Recuperado el 27 de noviembre de 2012 .

[Tijms2003-1] Tijms, Henk C. (2003). Un primer curso de modelos estocásticos . John Wiley and Sons. doi : 10.1002/047001363X .

[AzimzadehCarpenter2016-2] 1 2 Azimzadeh, Parsiad; Carpenter, Tommy (2016). "Cálculo rápido de Engset". Operations Research Letters . 44 (3): 313– 318. arXiv : 1511.00291 . doi : 10.1016/j.orl.2016.02.011 . ISSN 0167-6377 .

[Zukerman-3] Zukerman, Moshe (2000). "Una introducción a la teoría de colas y a los modelos estocásticos de teletrafico" (pdf) . Recuperado el 27 de noviembre de 2012 .

[ 1 ]

[ 2 ].

[ 3 ]