En la teoría de las colas , una disciplina dentro de la teoría matemática de la probabilidad , el algoritmo de Buzen (o algoritmo de convolución ) es un algoritmo para calcular la constante de normalización G ( N ) en el teorema de Gordon-Newell . Este método fue propuesto por primera vez por Jeffrey P. Buzen en 1973. [1] Se requiere calcular G ( N ) para calcular la distribución de probabilidad estacionaria de una red de cola cerrada. [2]
Realizar un cálculo ingenuo de la constante de normalización requiere la enumeración de todos los estados. Para un sistema con N trabajos y M estados, haycombinaciones. El algoritmo de Buzen "calcula G (1), G (2), ..., G ( N ) usando un total de NM multiplicaciones y NM adiciones". Esta es una mejora significativa y permite realizar cálculos con redes mucho más grandes. [1]
Configuración del problema
Considere una red de colas cerrada con M instalaciones de servicio y N clientes circulantes. Escriba n i ( t ) para el número de clientes presentes en la i- ésima instalación en el momento t , de modo que. Suponemos que el tiempo de servicio para un cliente en la i- ésima instalación viene dado por una variable aleatoria distribuida exponencialmente con el parámetro μ i y que después de completar el servicio en la i- ésima instalación, el cliente procederá a la j- ésima instalación con probabilidad p ij . [2]
Del teorema de Gordon-Newell se deduce que la distribución de equilibrio de este modelo es
donde las X i se encuentran resolviendo
y G ( N ) es una constante de normalización elegida que las probabilidades anteriores suman 1. [1]
El algoritmo de Buzen es un método eficaz para calcular G ( N ). [1]
Descripción del algoritmo
Escriba g ( N , M ) para la constante de normalización de una red de cola cerrada con N clientes circulantes y M estaciones de servicio. El algoritmo comienza por resolver las relaciones anteriores para X i y luego establece las condiciones iniciales [1]
La relación de recurrencia [1]
se utiliza para calcular una cuadrícula de valores. El valor buscado G ( N ) = g ( N , M ). [1]
Distribuciones marginales, número esperado de clientes
Los coeficientes g ( n , m ), calculados mediante el algoritmo de Buzen, también se pueden utilizar para calcular las distribuciones marginales y el número esperado de clientes en cada nodo.
el número esperado de clientes en la instalación i por
Implementación
Se supondrá que las X m se han calculado resolviendo las ecuaciones relevantes y están disponibles como entrada para nuestra rutina. Aunque g es en principio una matriz bidimensional, se puede calcular columna por columna a partir de la columna más a la izquierda. La rutina usa un vector C de una sola columna para representar la columna actual de g .
C [ 0 ] : = 1 para n : = 1 paso 1 hasta que N haga C [ n ] : = 0 ;para m : = 1 paso 1 hasta que M hacer para n : = 1 paso 1 hasta N hacer C [ n ] : = C [ n ] + X [ m ] * C [ n - 1 ] ;
Al finalizar, C contiene los valores deseados G (0), G (1) a G (N) . [1]
Referencias
- ↑ a b c d e f g h 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 .
- ^ a b 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 .