Teorema de Gordon-Newell

En la teoría de colas , una disciplina dentro de la teoría matemática de la probabilidad , el teorema de Gordon-Newell es una extensión del teorema de Jackson de las redes de colas abiertas a las redes de colas cerradas de servidores exponenciales donde los clientes no pueden abandonar la red. ^[1] El teorema de Jackson no se puede aplicar a redes cerradas porque la longitud de la cola en un nodo de la red cerrada está limitada por la población de la red. El teorema de Gordon-Newell calcula la solución de red abierta y luego elimina los estados inviables renormalizando las probabilidades. El cálculo de la constante de normalización hace que el tratamiento sea más complicado ya que se debe enumerar todo el espacio de estados. El algoritmo de Buzen o el análisis del valor medio se pueden utilizar para calcular la constante de normalización de manera más eficiente. ^[2]

Definición de una red Gordon-Newell

Una red de m colas interconectadas se conoce como red Gordon-Newell ^[3] o red Jackson cerrada ^[4] si cumple las siguientes condiciones:

1. la red está cerrada (ningún cliente puede entrar o salir de la red),
2. Todos los tiempos de servicio se distribuyen exponencialmente y la disciplina de servicio en todas las colas es FCFS .
3. un cliente que completa un servicio en la cola i se moverá a la cola j con probabilidad , con tal que , ${\displaystyle P_{ij}}$ ${\displaystyle P_{ij}}$ ${\textstyle \sum _{j=1}^{m}P_{ij}=1}$
4. La utilización de todas las colas es menor que una.

Teorema

En una red cerrada de Gordon-Newell de m colas, con una población total de K individuos, escriba (donde k _i es la longitud de la cola i ) para el estado de la red y S ( K ,  m ) para el espacio de estados ${\displaystyle \scriptstyle {(k_{1},k_{2},\ldots ,k_{m})}}$

${\displaystyle S(K,m)=\left\{\mathbf {k} \in \mathbb {N} ^{m}{\text{ such that }}\sum _{i=1}^{m}k_{i}=K\right\}.}$

Entonces la distribución de probabilidad del estado de equilibrio existe y está dada por

${\displaystyle \pi (k_{1},k_{2},\ldots ,k_{m})={\frac {1}{G(K)}}\prod _{i=1}^{m}\left({\frac {e_{i}}{\mu _{i}}}\right)^{k_{i}}}$

donde los tiempos de servicio en la cola i se distribuyen exponencialmente con parámetro μ _i . La constante de normalización G ( K ) viene dada por

${\displaystyle G(K)=\sum _{\mathbf {k} \in S(K,m)}\prod _{i=1}^{m}\left({\frac {e_{i}}{\mu _{i}}}\right)^{k_{i}},}$

y e _i es la relación de visitas, calculada resolviendo las ecuaciones simultáneas

${\displaystyle e_{i}=\sum _{j=1}^{m}e_{j}p_{ji}{\text{ for }}1\leq i\leq m.}$

Véase también

• Red BCMP

Referencias

1. Gordon, WJ; Newell, GF (1967). "Sistemas de colas cerradas con servidores exponenciales". Investigación de operaciones . 15 (2): 254. doi :10.1287/opre.15.2.254. JSTOR  168557.
2. Buzen, JP (1973). "Algoritmos computacionales para redes de colas cerradas con servidores exponenciales" (PDF) . Comunicaciones de la ACM . 16 (9): 527. doi :10.1145/362342.362345. Archivado desde el original (PDF) el 2016-05-13 . Consultado el 2015-08-29 .
3. Daduna, H. (1982). "Tiempos de paso para caminos sin adelantamiento en redes Gordon-Newell". Avances en probabilidad aplicada . 14 (3): 672–686. doi :10.2307/1426680.
4. Gong, Q.; Lai, KK; Wang, S. (2008). "Redes de la cadena de suministro: modelos y propiedades de la red cerrada de Jackson". Revista Internacional de Economía de la Producción . 113 (2): 567. doi :10.1016/j.ijpe.2007.10.013.