Algoritmo de Buzen

En la teoría de 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 su tesis doctoral de 1971 ^[1] y posteriormente publicado en una revista arbitrada en 1973. ^[2] El cálculo de G( N ) es necesario para calcular la distribución de probabilidad estacionaria de una red de colas cerrada. ^[3]

Para realizar un cálculo ingenuo de la constante de normalización es necesario enumerar todos los estados. Para una red cerrada con N clientes circulantes y M instalaciones de servicio, G( N ) es la suma de términos individuales, y cada término consta de M factores elevados a potencias cuya suma es N . El algoritmo de Buzen calcula G( N ) utilizando solo NM multiplicaciones y NM adiciones. Esta mejora espectacular abrió la puerta a la aplicación del teorema de Gordon-Newell a modelos de sistemas informáticos del mundo real, así como a sistemas de fabricación flexible y otros casos en los que se pueden formar cuellos de botella y colas dentro de redes de instalaciones de servicio interconectadas. ^[4] Los valores de G(1), G(2) ... G( N -1), que se pueden utilizar para calcular otras cantidades importantes de interés, se calculan como subproductos del algoritmo. ${\displaystyle {\tbinom {N+M-1}{M-1}}}$

Configuración del problema

Consideremos una red de colas cerrada con M instalaciones de servicio y N clientes circulantes. Supongamos que el tiempo de servicio para un cliente en la instalación de servicio i está dado por una variable aleatoria distribuida exponencialmente con parámetro μ _i y que, después de completar el servicio en la instalación de servicio i , un cliente procederá a la siguiente instalación de servicio j con probabilidad p _ij . ^[3]

Sea la probabilidad en estado estacionario de que el número de clientes en el centro de servicio i sea igual a n _i para i = 1, 2, ... , M . Del teorema de Gordon-Newell se deduce que ${\displaystyle \mathbb {P} (n_{1},n_{2},\cdots ,n_{M})}$

${\displaystyle \mathbb {P} (n_{1},n_{2},\cdots ,n_{M})={\frac {1}{{\text{G}}(N)}}}$ ${\displaystyle \left(X_{1}\right)^{n_{1}}}$ ${\displaystyle \left(X_{2}\right)^{n_{2}}}$.... ${\displaystyle \left(X_{M}\right)^{n_{M}}}$

Este resultado suele escribirse de forma más compacta como

${\displaystyle \mathbb {P} (n_{1},n_{2},\cdots ,n_{M})={\frac {1}{{\text{G}}(N)}}\prod _{i=1}^{M}\left(X_{i}\right)^{n_{i}}}$

Los valores de Xi se _determinan resolviendo

${\displaystyle \mu _{j}X_{j}=\sum _{i=1}^{M}\mu _{i}X_{i}p_{ij}\quad {\text{ for }}j=1,\ldots ,M.}$

G ( N ) es una constante normalizadora elegida de modo que la suma de todos los valores de sea igual a 1. El algoritmo de Buzen representa el primer procedimiento eficiente para calcular G( N ). ^{[2] [4]} ${\displaystyle {\tbinom {N+M-1}{M-1}}}$ ${\displaystyle \mathbb {P} (n_{1},n_{2},\cdots ,n_{M})}$

Descripción del algoritmo

Los términos individuales que deben sumarse para calcular G( N ) tienen todos la siguiente forma:

${\displaystyle \left(X_{1}\right)^{n_{1}}}$ ${\displaystyle \left(X_{2}\right)^{n_{2}}}$.... . Nótese que este conjunto de términos se puede dividir en dos grupos. El primer grupo comprende todos los términos cuyo exponente de es mayor o igual a 1. Esto implica que elevado a la potencia 1 se puede factorizar de cada uno de estos términos.   ${\displaystyle \left(X_{M}\right)^{n_{M}}}$ ${\displaystyle \left(X_{M}\right)}$ ${\displaystyle \left(X_{M}\right)}$

Después de factorizar , surge un resultado sorprendente: los términos modificados en el primer grupo son idénticos a los términos utilizados para calcular la constante de normalización para la misma red con un cliente eliminado. Por lo tanto, la suma de los términos en el primer grupo se puede escribir como “ X _M por G( N -1)”. Esta idea proporciona la base para el desarrollo del algoritmo. ^[4] ${\displaystyle \left(X_{M}\right)}$  

Consideremos ahora el segundo grupo. El exponente de X _M para cada término de este grupo es cero. Como resultado, la instalación de servicio M desaparece efectivamente de todos los términos de este grupo (ya que se reduce en todos los casos a un factor de 1). Esto deja el número total de clientes en las M -1 instalaciones de servicio restantes igual a N . El segundo grupo incluye todos los acuerdos posibles de estos N clientes.

Para expresar este concepto con precisión, supongamos que se han obtenido X ₁ , X ₂ , … X _M para una red dada con M instalaciones de servicio. Para cualquier n ≤ N y m ≤ M, defina g( n,m ) como la constante de normalización para una red con n clientes, m instalaciones de servicio (1,2, … m ), y valores de   X ₁ , X ₂ , … X _m  que coinciden con los primeros m miembros de la secuencia original X ₁ , X ₂ , … X _M .

Dada esta definición, la suma de los términos del segundo grupo ahora puede escribirse como g( N , M -1).

También se deduce inmediatamente que “ X _M por G( N -1)”, la suma de los términos del primer grupo, puede reescribirse como “ X _M por g( N -1, M )”.  

Además, la constante normalizadora G( N ) en el teorema de Gordon-Newell ahora puede reescribirse como g( N , M ).

Dado que G( N ) es igual a la suma combinada de los términos del primer y segundo grupo,

G( N ) = g( N , M ) = X _M g( N -1, M ) + g( N , M -1)

Esta misma relación de recurrencia existe claramente para cualquier valor intermedio de n desde   1 hasta N , y para cualquier valor intermedio de m desde 1 hasta M.

Esto implica que g( n,m ) = X _m g( n -1, m ) + g( n,m -1). El algoritmo de Buzen es simplemente la aplicación iterativa de esta relación de recurrencia fundamental, junto con las siguientes condiciones de contorno.

g(0, m ) = 1 para m = 1, 2, … M

g( n ,1) = ( X _i ) ⁿ para n = 0, 1, … N

Distribuciones marginales, número esperado de clientes

El teorema de Gordon-Newell permite a los analistas determinar la probabilidad estacionaria asociada con cada estado individual de una red de colas cerrada. Estas probabilidades individuales deben sumarse para evaluar otras probabilidades importantes. Por ejemplo, P( n _i ≥ k ), la probabilidad de que el número total de clientes en el centro de servicio i sea mayor o igual a k , debe sumarse sobre todos los valores de n _i ≥ k y, para cada uno de esos valores de n _i , sobre todas las formas posibles en que los N – n _i clientes restantes pueden distribuirse entre los otros M -1 centros de servicio en la red.

Muchas de estas probabilidades marginales pueden calcularse con un mínimo esfuerzo adicional. Esto es fácil de ver para el caso de P( n _i ≥ k ). Claramente, Xi debe _elevarse a la potencia k o superior en cada estado donde el número de clientes en el centro de servicio i sea mayor o igual a k . Por lo tanto, _Xi k ^puede factorizarse de cada una de estas probabilidades, dejando un conjunto de probabilidades modificadas cuya suma está dada por G( N -k)/G( N ). Esta observación produce el siguiente resultado simple y altamente eficiente:

P( n _i ≥ k ) = ( X _i ) ^k G( N - k )/G( N )

Esta relación se puede utilizar luego para calcular las distribuciones marginales y el número esperado de clientes en cada instalación de servicio.

${\displaystyle \mathbb {P} (n_{i}=k)={\frac {X_{i}^{k}}{G(N)}}[G(N-k)-X_{i}G(N-k-1)]\quad {\text{ for }}k=0,1,\ldots ,N-1,}$

${\displaystyle \mathbb {P} (n_{i}=N)={\frac {X_{i}^{N}}{G(N)}}.}$

El número esperado de clientes en la instalación de servicio i viene dado por

${\displaystyle \mathbb {E} (n_{i})=\sum _{k=1}^{N}X_{i}^{k}{\frac {G(N-k)}{G(N)}}.}$

Estas caracterizaciones de cantidades de interés en términos de G( n ) también se deben a Buzen. ^[2]

Implementación

Se supondrá que los X _m se han calculado resolviendo las ecuaciones pertinentes y están disponibles como entrada para nuestra rutina. Aunque g( n,m ) es en principio una matriz bidimensional, se puede calcular columna por columna comenzando desde la parte superior de la columna más a la izquierda y recorriendo cada columna hasta la parte inferior antes de proceder a la siguiente columna a la derecha. La rutina utiliza un único vector de columna C para representar la columna actual de g .

El primer bucle del algoritmo siguiente inicializa el vector columna C[n] de modo que C[0] = 1 y C(n) = 0 para n≥1. Nótese que C[0] permanece igual a 1 en todas las iteraciones subsiguientes.  

En el segundo bucle, cada valor sucesivo de C(n) para n≥1 se establece igual al valor correspondiente de g( n,m) a medida que el algoritmo avanza hacia abajo en la columna m. Esto se logra estableciendo cada valor sucesivo de C(n) igual a:

g( n,m-1 ) más X _m por g( n-1,m ).  

Tenga en cuenta que g( n,m-1 ) es el valor anterior de C(n), y g( n-1,m ) es el valor actual de C(n-1)

C [ 0 ] := 1 para n := 1 paso 1 hasta N hacer C [ n ] := 0 ;             para m := 1 paso 1 hasta M hacer para n := 1 paso 1 hasta N hacer C [ n ] := C [ n ] + X [ m ] * C [ n - 1 ] ;                      

Al finalizar, los valores finales de C[n] corresponden a la columna M de la matriz g( n,m ). Por lo tanto, representan los valores deseados G (0), G (1), ... , G (N) . ^[2]

Referencias

1. Buzen, JP (1971-08-01). DTIC AD0731575: Modelos de red de colas de multiprogramación.
2. Buzen, JP (1973). "Algoritmos computacionales para redes de colas cerradas con servidores exponenciales" (PDF) . Comunicaciones de la ACM . 16 (9): 527–531. doi :10.1145/362342.362345. S2CID  10702. Archivado desde el original (PDF) el 2016-05-13 . Consultado el 2006-04-15 .
3. 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.
4. Denning, Peter J. (24 de agosto de 2016). "Replanteando la aleatoriedad: una entrevista con Jeff Buzen, parte I". Ubiquity . 2016 (agosto): 1:1–1:17. doi : 10.1145/2986329 .

• Jain: El algoritmo de convolución (material para la clase)
• Menasce: un enfoque de convolución para algoritmos de colas (presentación)