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 similares en forma de producto en otras redes ha sido objeto de mucha investigación, [2] incluyendo 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 los 'Diez títulos más influyentes de los primeros cincuenta años de Management Science ' de la revista Management Science . [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 varios nodos, donde cada nodo representa una cola en la que la tasa de servicio puede ser dependiente del nodo (diferentes nodos tienen diferentes tasas de servicio) y dependiente 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 los trabajos siguen la misma distribución del tiempo de servicio y el mismo mecanismo de enrutamiento. En consecuencia, no hay noción de prioridad en el servicio a los puestos de trabajo: todos los puestos de trabajo en cada nodo se sirven en un primer llegado, primer servido base.
Las redes de Jackson, donde una población finita de trabajos viaja alrededor de 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:
- si la red está abierta, cualquier llegada externa al nodo i forma un proceso de Poisson ,
- Todos los tiempos de servicio se distribuyen exponencialmente y la disciplina de servicio en todas las colas es por orden de llegada ,
- un cliente que completa el servicio en la cola i me moveré a una nueva cola j con probabilidad o dejar el sistema con probabilidad , que, para una red abierta, es distinto de cero para algún subconjunto de las colas,
- 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, la distribución de probabilidad del estado de equilibrio existe y para el estado viene dado por el producto de las distribuciones de equilibrio de las colas individuales
El resultado También es válido para estaciones modelo M / M / c con servidores c i en el estación, con requisito de utilización .
Definición
En una red abierta, los trabajos llegan del exterior siguiendo un proceso de Poisson con tasa. Cada llegada se enruta de forma independiente al nodo j con probabilidad y . Una vez completado el servicio en el nodo i , un trabajo puede ir a otro nodo j con probabilidad o salir de la red con probabilidad .
Por lo tanto, tenemos la tasa de llegada general al nodo i ,, incluidas las llegadas externas y las transiciones internas:
(Dado que la utilización en cada nodo es menor que 1, y estamos viendo 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 en j y ignoramos la tarifa del servicio en lo anterior.)
Definir , entonces podemos resolver .
Todos los trabajos salen de cada nodo también siguiendo el proceso de Poisson y definen como la tasa de servicio del nodo i cuando haytrabajos en el nodo i .
Dejar denotar el número de trabajos en el nodo i en el tiempo t , y. Entonces la distribución de equilibrio de, está determinada por el siguiente sistema de ecuaciones de equilibrio:
dónde denotar el vector unitario .
Teorema
Suponga un vector de variables aleatorias independientes con cada tener una función de masa de probabilidad como
dónde . Si es decir está bien definida, entonces la distribución de equilibrio de la red abierta de Jackson tiene la siguiente forma de producto:
para todos .⟩
Basta con verificar la ecuación Está satisfecho. Por la forma del producto y la fórmula (3), tenemos:
Sustituyendo estos en el lado derecho de obtenemos:
Entonces usa , tenemos:
Sustituyendo lo anterior en , tenemos:
Esto puede ser verificado por . Por lo tanto, ambos lados de son iguales.⟨
Este teorema amplía el que se muestra arriba al permitir la tasa de servicio dependiente del estado de cada nodo. Relaciona la distribución depor un vector de variable independiente.
Ejemplo
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/d/d5/Open_jackson_network_%28final%29.png/330px-Open_jackson_network_%28final%29.png)
Supongamos que tenemos una red Jackson de tres nodos que se muestra en el gráfico, los coeficientes son:
Luego, por el teorema, podemos calcular:
Según la definición de , tenemos:
Por lo tanto, la probabilidad de que haya un trabajo en cada nodo es:
Dado que la tasa de servicio aquí no depende del estado, la s simplemente siguen una distribución geométrica .
Red Jackson generalizada
Una red Jackson generalizada permite procesos de llegada de renovación que no necesitan ser procesos de Poisson y tiempos de servicio no exponenciales distribuidos de forma idéntica e independientes. 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 leves, el proceso de longitud de la cola [ aclaración necesaria ] de una red Jackson generalizada abierta puede aproximarse mediante un movimiento browniano reflejado definido como, dónde 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 de Jackson general con una red de fluidos homogénea y el movimiento browniano reflejado.
Los parámetros del proceso browniano reflejado se especifican de la siguiente manera:
donde los símbolos se definen como:
símbolo | Significado |
---|---|
un vector J que especifica las tasas de llegada a cada nodo. | |
un vector J que especifica las tarifas de servicio de cada nodo. | |
matriz de enrutamiento. | |
llegada efectiva de nodo. | |
variación del tiempo de servicio en nodo. | |
variación del tiempo entre llegadas a nodo. | |
coeficientes para especificar la correlación entre nodos. Se definen de esta manera: Vamos ser el proceso de llegada del sistema, entonces en distribución, donde es un proceso browniano sin deriva con matriz de covariables , con , para cualquier |
Ver también
Referencias
- ^ Walrand, J .; Varaiya, P. (1980). "Tiempos de estancia y la condición de adelantamiento en redes jacksonianas". Avances en probabilidad aplicada . 12 (4): 1000–1018. doi : 10.2307 / 1426753 . JSTOR 1426753 .
- ^ Kelly, FP (junio de 1976). "Redes de Colas". Avances en probabilidad aplicada . 8 (2): 416–432. doi : 10.2307 / 1425912 . JSTOR 1425912 .
- ^ Jackson, James R. (diciembre de 2004). "Comentarios sobre" sistemas de colas similares a Jobshop ": el trasfondo". Ciencias de la gestión . 50 (12): 1796–1802. doi : 10.1287 / mnsc.1040.0268 . JSTOR 30046150 .
- ^ Jackson, James R. (octubre de 1963). "Sistemas de colas tipo Jobshop". Ciencias de la gestión . 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
- ^ Jackson, JR (1957). "Redes de líneas de espera". Investigación operativa . 5 (4): 518–521. doi : 10.1287 / opre.5.4.518 . JSTOR 167249 .
- ^ Jackson, James R. (diciembre de 2004). "Sistemas de colas tipo Jobshop". Ciencias de la gestión . 50 (12): 1796–1802. doi : 10.1287 / mnsc.1040.0268 . JSTOR 30046149 .
- ^ 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 .
- ^ Walrand, Jean (noviembre de 1983). "Una mirada probabilística a las redes de colas casi reversibles". Transacciones IEEE sobre teoría de la información . 29 (6): 825. doi : 10.1109 / TIT.1983.1056762 .
- ^ Jackson, RRP (1995). "Reseña del libro: redes de colas y formas de productos: un enfoque de sistemas". Revista IMA de Matemáticas de Gestión . 6 (4): 382–384. doi : 10.1093 / imaman / 6.4.382 .
- ^ Gordon, WJ; Newell, GF (1967). "Sistemas de colas cerradas con servidores exponenciales". Investigación operativa . 15 (2): 254. doi : 10.1287 / opre.15.2.254 . JSTOR 168557 .
- ^ Goodman, Jonathan B .; Massey, William A. (diciembre de 1984). "La red Jackson no ergódica". Revista de probabilidad aplicada . 21 (4): 860–869. doi : 10.2307 / 3213702 .
- ^ Walrand, J .; Varaiya, P. (diciembre de 1980). "Tiempos de estancia y la condición de adelantamiento en redes jacksonianas". Avances en probabilidad aplicada . 12 (4): 1000–1018. doi : 10.2307 / 1426753 .
- ^ Chen, Hong; Yao, David D. (2001). Fundamentos de las redes de colas: rendimiento, asintótica y optimización . Saltador. ISBN 0-387-95166-0.