Red Jackson

Disciplina matemática

En la teoría de colas , una disciplina dentro de la teoría matemática de la probabilidad , una red de Jackson (a veces red jacksoniana ^[1] ) es una clase de red de colas donde la distribución de equilibrio es particularmente simple de calcular ya que la red tiene una solución en forma de producto . Fue el primer desarrollo significativo en la teoría de redes de colas , y la generalización y aplicación de las ideas del teorema para buscar soluciones en forma de producto similares en otras redes ha sido objeto de mucha investigación, ^[2] incluidas las ideas utilizadas en el desarrollo de Internet. ^[3] Las redes fueron identificadas por primera vez por James R. Jackson ^{[4] [5]} y su artículo fue reimpreso en la revista Management Science ' Ten Most Influential Titles of Management Sciences First Fifty Years'. ^[6]

Jackson se inspiró en el trabajo de Burke y Reich, ^[7] aunque Jean Walrand señala que "los resultados en forma de producto... [son] un resultado mucho menos inmediato del teorema de salida de lo que el propio Jackson parecía creer en su artículo fundamental". ^[8]

RRP Jackson encontró una solución anterior en forma de producto para colas en tándem (una cadena finita de colas donde cada cliente debe visitar cada cola en orden) y redes cíclicas (un bucle de colas donde cada cliente debe visitar cada cola en orden). ^[9]

Una red Jackson consta de una serie de nodos, donde cada nodo representa una cola en la que la tasa de servicio puede depender tanto del nodo (los distintos nodos tienen diferentes tasas de servicio) como del estado (las tasas de servicio cambian según la longitud de la cola). Los trabajos viajan entre los nodos siguiendo una matriz de enrutamiento fija. Todos los trabajos en cada nodo pertenecen a una única "clase" y siguen la misma distribución de tiempo de servicio y el mismo mecanismo de enrutamiento. En consecuencia, no existe una noción de prioridad en el servicio de los trabajos: todos los trabajos en cada nodo se atienden por orden de llegada .

Las redes de Jackson, en las que una población finita de trabajos se desplazan por una red cerrada, también tienen una solución en forma de producto descrita por el teorema de Gordon-Newell . ^[10]

Condiciones necesarias para una red Jackson

Una red de m colas interconectadas se conoce como red Jackson ^[11] o red jacksoniana ^[12] si cumple las siguientes condiciones:

1. Si la red está abierta, cualquier llegada externa al nodo i forma un proceso de Poisson .
2. Todos los tiempos de servicio se distribuyen exponencialmente y la disciplina de servicio en todas las colas es por orden de llegada .
3. un cliente que completa un servicio en la cola i se moverá a una nueva cola j con probabilidad o abandonará el sistema con probabilidad , que, para una red abierta, no es cero para algún subconjunto de las colas, ${\displaystyle P_{ij}}$ ${\displaystyle 1-\sum _{j=1}^{m}P_{ij}}$
4. La utilización de todas las colas es menor que una.

Teorema

En una red Jackson abierta de m colas M/M/1 donde la utilización es menor que 1 en cada cola, existe la distribución de probabilidad del estado de equilibrio y para el estado está dada por el producto de las distribuciones de equilibrio de las colas individuales. ${\displaystyle \rho _{i}}$ ${\displaystyle \scriptstyle {(k_{1},k_{2},\ldots ,k_{m})}}$

${\displaystyle \pi (k_{1},k_{2},\ldots ,k_{m})=\prod _{i=1}^{m}\pi _{i}(k_{i})=\prod _{i=1}^{m}[\rho _{i}^{k_{i}}(1-\rho _{i})].}$

El resultado también es válido para las estaciones modelo M/M/c con servidores c _i en la estación, con requisito de utilización . ${\displaystyle \pi (k_{1},k_{2},\ldots ,k_{m})=\prod _{i=1}^{m}\pi _{i}(k_{i})}$ ${\displaystyle i^{\text{th}}}$ ${\displaystyle \rho _{i}<c_{i}}$

Definición

En una red abierta, los trabajos llegan desde el exterior siguiendo un proceso de Poisson con una tasa de . Cada llegada se enruta de forma independiente al nodo j con una probabilidad de . Una vez completado el servicio en el nodo i , un trabajo puede ir a otro nodo j con una probabilidad de . o salir de la red con una probabilidad de . ${\displaystyle \alpha >0}$ ${\displaystyle p_{0j}\geq 0}$ ${\displaystyle \sum _{j=1}^{J}p_{0j}=1}$ ${\displaystyle p_{ij}}$ ${\displaystyle p_{i0}=1-\sum _{j=1}^{J}p_{ij}}$

Por lo tanto, tenemos la tasa de llegada general al nodo i , incluyendo tanto las llegadas externas como las transiciones internas: ${\displaystyle \lambda _{i}}$

${\displaystyle \lambda _{i}=\alpha p_{0i}+\sum _{j=1}^{J}\lambda _{j}p_{ji},i=1,\ldots ,J.\qquad (1)}$

(Dado que la utilización en cada nodo es menor a 1 y estamos observando la distribución de equilibrio, es decir, el comportamiento promedio a largo plazo, la tasa de trabajos que pasan de j a i está limitada por una fracción de la tasa de llegada a j e ignoramos la tasa de servicio en lo anterior). ${\displaystyle \mu _{j}}$

Definamos , luego podemos resolver . ${\displaystyle a=(\alpha p_{0i})_{i=1}^{J}}$ ${\displaystyle \lambda =(I-P^{T})^{-1}a}$

Todos los trabajos salen de cada nodo también siguiendo el proceso de Poisson y se definen como la tasa de servicio del nodo i cuando hay trabajos en el nodo i . ${\displaystyle \mu _{i}(x_{i})}$ ${\displaystyle x_{i}}$

Sea t el número de puestos de trabajo en el nodo i en el momento t , y . Entonces la distribución de equilibrio de , se determina mediante el siguiente sistema de ecuaciones de equilibrio: ${\displaystyle X_{i}(t)}$ ${\displaystyle \mathbf {X} =(X_{i})_{i=1}^{J}}$ ${\displaystyle \mathbf {X} }$ ${\displaystyle \pi (\mathbf {x} )=P(\mathbf {X} =\mathbf {x} )}$

${\displaystyle {\begin{aligned}&\pi (\mathbf {x} )\sum _{i=1}^{J}[\alpha p_{0i}+\mu _{i}(x_{i})(1-p_{ii})]\\={}&\sum _{i=1}^{J}[\pi (\mathbf {x} -\mathbf {e} _{i})\alpha p_{0i}+\pi (\mathbf {x} +\mathbf {e} _{i})\mu _{i}(x_{i}+1)p_{i0}]+\sum _{i=1}^{J}\sum _{j\neq i}\pi (\mathbf {x} +\mathbf {e} _{i}-\mathbf {e} _{j})\mu _{i}(x_{i}+1)p_{ij}.\qquad (2)\end{aligned}}}$

donde denota el vector unitario . ${\displaystyle \mathbf {e} _{i}}$ ${\displaystyle i^{\text{th}}}$

Teorema

Supongamos un vector de variables aleatorias independientes , cada una de las cuales tiene una función de masa de probabilidad como ${\displaystyle (Y_{1},\ldots ,Y_{J})}$ ${\displaystyle Y_{i}}$

${\displaystyle P(Y_{i}=n)=p(Y_{i}=0)\cdot {\frac {\lambda _{i}^{n}}{M_{i}(n)}},\quad (3)}$

donde . Si ie está bien definido, entonces la distribución de equilibrio de la red abierta de Jackson tiene la siguiente forma de producto: ${\displaystyle M_{i}(n)=\prod _{j=1}^{n}\mu _{i}(j)}$ ${\displaystyle \sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}<\infty }$ ${\displaystyle P(Y_{i}=0)=\left(1+\sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}\right)^{-1}}$

${\displaystyle \pi (\mathbf {x} )=\prod _{i=1}^{J}P(Y_{i}=x_{i}).}$

para todos .⟩ ${\displaystyle \mathbf {x} \in {\mathcal {Z}}_{+}^{J}}$

Prueba

Basta con comprobar que se cumple la ecuación. Por la forma del producto y la fórmula (3), tenemos: ${\displaystyle (2)}$

${\displaystyle \pi (\mathbf {x} )=\pi (\mathbf {x} +\mathbf {e} _{i})\mu _{i}(x_{i}+1)/\lambda _{i}=\pi (\mathbf {x} +\mathbf {e} _{i}-\mathbf {e} _{j})\mu _{i}(x_{i}+1)\lambda _{j}/[\lambda _{i}\mu _{j}(x_{j})]}$

Sustituyendo estos en el lado derecho obtenemos: ${\displaystyle (2)}$

${\displaystyle \sum _{i=1}^{J}[\alpha p_{0i}+\mu _{i}(x_{i})(1-p_{ii})]=\sum _{i=1}^{J}[{\frac {\alpha p_{0i}}{\lambda _{i}}}\mu _{i}(x_{i})+\lambda _{i}p_{i0}]+\sum _{i=1}^{J}\sum _{j\neq i}{\frac {\lambda _{i}}{\lambda _{j}}}p_{ij}\mu _{j}(x_{j}).\qquad (4)}$

Luego usamos , tenemos: ${\displaystyle (1)}$

${\displaystyle \sum _{i=1}^{J}\sum _{j\neq i}{\frac {\lambda _{i}}{\lambda _{j}}}p_{ij}\mu _{j}(x_{j})=\sum _{j=1}^{J}[\sum _{i\neq j}{\frac {\lambda _{i}}{\lambda _{j}}}p_{ij}]\mu _{j}(x_{j})=\sum _{j=1}^{J}[1-p_{jj}-{\frac {\alpha p_{0j}}{\lambda _{j}}}]\mu _{j}(x_{j}).}$

Sustituyendo lo anterior en , tenemos: ${\displaystyle (4)}$

${\displaystyle \sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}p_{i0}}$

Esto se puede verificar mediante . Por lo tanto, ambos lados de son iguales.⟨ ${\displaystyle \sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}}$ ${\displaystyle (2)}$

Este teorema extiende el mostrado anteriormente al permitir una tasa de servicio dependiente del estado de cada nodo. Relaciona la distribución de mediante un vector de variable independiente . ${\displaystyle \mathbf {X} }$ ${\displaystyle \mathbf {Y} }$

Ejemplo

Una red Jackson abierta de tres nodos

Supongamos que tenemos una red Jackson de tres nodos que se muestra en el gráfico, los coeficientes son:

${\displaystyle \alpha =5,\quad p_{01}=p_{02}=0.5,\quad p_{03}=0,\quad }$

${\displaystyle P={\begin{bmatrix}0&0.5&0.5\\0&0&0\\0&0&0\end{bmatrix}},\quad \mu ={\begin{bmatrix}\mu _{1}(x_{1})\\\mu _{2}(x_{2})\\\mu _{3}(x_{3})\end{bmatrix}}={\begin{bmatrix}15\\12\\10\end{bmatrix}}{\text{ for all }}x_{i}>0}$

Luego por el teorema podemos calcular:

${\displaystyle \lambda =(I-P^{T})^{-1}a={\begin{bmatrix}1&0&0\\-0.5&1&0\\-0.5&0&1\end{bmatrix}}^{-1}{\begin{bmatrix}0.5\times 5\\0.5\times 5\\0\end{bmatrix}}={\begin{bmatrix}1&0&0\\0.5&1&0\\0.5&0&1\end{bmatrix}}{\begin{bmatrix}2.5\\2.5\\0\end{bmatrix}}={\begin{bmatrix}2.5\\3.75\\1.25\end{bmatrix}}}$

Según la definición de , tenemos: ${\displaystyle \mathbf {Y} }$

${\displaystyle P(Y_{1}=0)=\left(\sum _{n=0}^{\infty }\left({\frac {2.5}{15}}\right)^{n}\right)^{-1}={\frac {5}{6}}}$

${\displaystyle P(Y_{2}=0)=\left(\sum _{n=0}^{\infty }\left({\frac {3.75}{12}}\right)^{n}\right)^{-1}={\frac {11}{16}}}$

${\displaystyle P(Y_{3}=0)=\left(\sum _{n=0}^{\infty }\left({\frac {1.25}{10}}\right)^{n}\right)^{-1}={\frac {7}{8}}}$

Por lo tanto, la probabilidad de que haya un trabajo en cada nodo es:

${\displaystyle \pi (1,1,1)={\frac {5}{6}}\cdot {\frac {2.5}{15}}\cdot {\frac {11}{16}}\cdot {\frac {3.75}{12}}\cdot {\frac {7}{8}}\cdot {\frac {1.25}{10}}\approx 0.00326}$

Dado que la tasa de servicio aquí no depende del estado, las s simplemente siguen una distribución geométrica . ${\displaystyle Y_{i}}$

Red Jackson generalizada

Una red de Jackson generalizada permite procesos de llegada de renovación que no necesitan ser procesos de Poisson y tiempos de servicio independientes, idénticos y no exponenciales. En general, esta red no tiene una distribución estacionaria en forma de producto , por lo que se buscan aproximaciones. ^[13]

Aproximación browniana

En algunas condiciones moderadas, el proceso de longitud de cola ^{[ aclaración necesaria ]} de una red Jackson generalizada abierta se puede aproximar mediante un movimiento browniano reflejado definido como , donde es la deriva del proceso, es la matriz de covarianza y es la matriz de reflexión. Esta es una aproximación de dos órdenes obtenida por la relación entre la red Jackson general con la red de fluido homogénea y el movimiento browniano reflejado. ${\displaystyle Q(t)}$ ${\displaystyle \operatorname {RBM} _{Q(0)}(\theta ,\Gamma ;R).}$ ${\displaystyle \theta }$ ${\displaystyle \Gamma }$ ${\displaystyle R}$

Los parámetros del proceso browniano reflejado se especifican de la siguiente manera:

${\displaystyle \theta =\alpha -(I-P^{T})\mu }$

${\displaystyle \Gamma =(\Gamma _{k\ell }){\text{ with }}\Gamma _{k\ell }=\sum _{j=1}^{J}(\lambda _{j}\wedge \mu _{j})[p_{jk}(\delta _{k\ell }-p_{j\ell })+c_{j}^{2}(p_{jk}-\delta _{jk})(p_{j\ell }-\delta _{j\ell })]+\alpha _{k}c_{0,k}^{2}\delta _{k\ell }}$

${\displaystyle R=I-P^{T}}$

donde los símbolos se definen como:

Véase también

• Red Gordon-Newell
• Red BCMP
• Red G
• Ley de Little

Referencias

1. Walrand, J. ; Varaiya, P. (1980). "Tiempos de permanencia y condición de adelantamiento en redes jacksonianas". Avances en probabilidad aplicada . 12 (4): 1000–1018. doi :10.2307/1426753. JSTOR  1426753.
2. Kelly, FP (junio de 1976). "Redes de colas". Avances en probabilidad aplicada . 8 (2): 416–432. doi :10.2307/1425912. JSTOR  1425912.
3. Jackson, James R. (diciembre de 2004). "Comentarios sobre "sistemas de colas tipo taller": antecedentes". Management Science . 50 (12): 1796–1802. doi :10.1287/mnsc.1040.0268. JSTOR  30046150.
4. Jackson, James R. (octubre de 1963). "Sistemas de colas tipo taller". Management Science . 10 (1): 131–142. doi :10.1287/mnsc.1040.0268. JSTOR  2627213.Una versión de enero de 1963 está disponible en http://www.dtic.mil/dtic/tr/fulltext/u2/296776.pdf Archivado el 12 de abril de 2018 en Wayback Machine.
5. Jackson, JR (1957). "Redes de colas de espera". Investigación de operaciones . 5 (4): 518–521. doi :10.1287/opre.5.4.518. JSTOR  167249.
6. Jackson, James R. (diciembre de 2004). "Sistemas de colas tipo taller". Management Science . 50 (12): 1796–1802. doi :10.1287/mnsc.1040.0268. JSTOR  30046149.
7. Reich, Edgar (septiembre de 1957). "Tiempos de espera cuando las colas están en tándem". Anales de estadística matemática . 28 (3): 768. doi : 10.1214/aoms/1177706889 . JSTOR  2237237.
8. Walrand, Jean (noviembre de 1983). "Una mirada probabilística a las redes de colas cuasi-reversibles". IEEE Transactions on Information Theory . 29 (6): 825. doi :10.1109/TIT.1983.1056762.
9. Jackson, RRP (1995). "Reseña de libro: Redes de colas y formas de producto: un enfoque de sistemas". IMA Journal of Management Mathematics . 6 (4): 382–384. doi :10.1093/imaman/6.4.382.
10. 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.
11. Goodman, Jonathan B.; Massey, William A. (diciembre de 1984). "La red no ergódica de Jackson". Journal of Applied Probability . 21 (4): 860–869. doi :10.2307/3213702.
12. Walrand, J.; Varaiya, P. (diciembre de 1980). "Tiempos de permanencia y condición de adelantamiento en redes jacksonianas". Advances in Applied Probability . 12 (4): 1000–1018. doi :10.2307/1426753.
13. Chen, Hong; Yao, David D. (2001). Fundamentos de las redes de colas: rendimiento, asintótica y optimización . Springer. ISBN 0-387-95166-0.