Fórmula de Engset

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

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

Ejemplo de aplicación

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

Fórmula

Dejar

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

Entonces, la probabilidad de bloqueo está dada por ^[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}}}.}$

Al reorganizar los términos, se puede reescribir la fórmula anterior como ^[2]

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

¿Dónde está la función hipergeométrica gaussiana ? ${\displaystyle {}_{2}F_{1}}$

Cálculo

Hay varias recursiones ^[3] que se pueden utilizar para realizar cálculos de manera numéricamente estable. ${\displaystyle P}$

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

Python con SciPy

desde  scipy.special  importar  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 / hipergeoma ([ 1 , - c ], N - c , - 1 / ( Lambda * h ))             

Tasa de llegada de origen desconocido

En la práctica, suele suceder que la tasa de llegada a la fuente sea desconocida (o difícil de estimar) mientras que , el tráfico ofrecido por fuente, sí se conoce. En este caso, se puede sustituir la relación ${\displaystyle \lambda }$ ${\displaystyle \alpha >0}$

${\displaystyle \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 de punto fijo

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

dónde

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

Cálculo

Si bien lo anterior elimina la incógnita de la fórmula, introduce un punto adicional de complejidad: ya no podemos calcular la probabilidad de bloqueo directamente y debemos utilizar 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 es divergente cuando se aplica a . ^[2] Alternativamente, es posible utilizar uno de los métodos de bisección o de Newton , para el cual hay disponible una implementación de código abierto. ${\displaystyle \lambda }$ ${\displaystyle f}$

Referencias

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