Análisis del valor medio

En la teoría de colas , una disciplina dentro de la teoría matemática de la probabilidad , el análisis del valor medio ( MVA ) es una técnica recursiva para calcular las longitudes esperadas de las colas, el tiempo de espera en los nodos de cola y el rendimiento en equilibrio para un sistema cerrado y separable de colas. Las primeras técnicas aproximadas fueron publicadas independientemente por Schweitzer ^{[ 1 ]} y Bard, ^{[ 2 ] [ 3 ]} seguidas posteriormente por una versión exacta de Lavenberg y Reiser publicada en 1980. ^{[ 4 ] [ 5 ]}

Se basa en el teorema de llegada , que establece que cuando un cliente en un sistema cerrado de M clientes llega a un centro de servicio, observa que el resto del sistema se encuentra en el estado de equilibrio para un sistema con M − 1 clientes.  

Consideremos una red de colas cerrada con K M/M/1 colas y M clientes circulando por el sistema. Supongamos que los clientes son indistinguibles entre sí, de modo que la red tiene una sola clase de clientes. Para calcular la longitud media de la cola, el tiempo de espera en cada nodo y el rendimiento del sistema, utilizamos un algoritmo iterativo que comienza con una red sin clientes.

Escriba μ _i para la tasa de servicio en el nodo i y P para la matriz de enrutamiento del cliente donde el elemento p _ij denota la probabilidad de que un cliente que termina el servicio en el nodo i se mueva al nodo j para recibir servicio. Para usar el algoritmo, primero calculamos el vector fila de la razón de visitas v , un vector tal que v  = v P.  

Ahora escriba L _i ( n ) para el número medio de clientes en la cola i cuando hay un total de n clientes en el sistema (esto incluye el trabajo que actualmente se está atendiendo en la cola i ) y W _j ( n ) para el tiempo medio que pasa un cliente en la cola i cuando hay un total de n clientes en el sistema. Denote el rendimiento de un sistema con m clientes por λ _m .

El algoritmo ^{[ 6 ]} comienza con una red vacía (cero clientes), luego aumenta el número de clientes en 1 en cada iteración hasta que haya el número requerido ( M ) de clientes en el sistema.

Para inicializar, establezca L _k (0)  =  0 para k  =  1,..., K . (Esto establece la longitud promedio de la cola en un sistema sin clientes a cero en todos los nodos).

Repetir para m  =  1,..., M :

1. Para k  =  1, ..., K, calcule el tiempo de espera en cada nodo utilizando el teorema de llegada:

${\displaystyle W_{k}(m)={\frac {1+L_{k}\left(m-1\right)}{\mu _{k}}}.}$

2. A continuación, calcule el rendimiento del sistema utilizando la ley de Little :

${\displaystyle \lambda _{m}={\frac {m}{\sum _{k=1}^{K}W_{k}(m)v_{k}}}.}$

3. Finalmente, utilice la ley de Little aplicada a cada cola para calcular las longitudes medias de las colas para k  =  1, ..., K:

${\displaystyle L_{k}(m)=v_{k}\lambda _{m}W_{k}(m).}$

Fin de la repetición.

La aproximación de Bard-Schweitzer estima que el número promedio de trabajos en el nodo k es: ^{[ 1 ] [ 7 ]}

${\displaystyle L_{k}(m-1)\approx {\frac {m-1}{m}}L_{k}(m)}$

que es una interpolación lineal. A partir de las fórmulas anteriores, esta aproximación produce relaciones de punto fijo que pueden resolverse numéricamente. Este enfoque iterativo se conoce a menudo como MVA aproximado (AMVA) y suele ser más rápido que el enfoque recursivo de MVA. ^{[ 8 ] : 38}

En el caso de redes multiclase con R clases de clientes, cada cola k puede presentar diferentes tasas de servicio μ _k,r para cada clase de trabajo r=1,...,R , aunque existen ciertas restricciones en el caso de estaciones de primero en llegar, primero en ser atendido debido a los supuestos del teorema BCMP en el caso multiclase.

El tiempo de espera W _k,r experimentado por los trabajos de clase r en la cola k aún puede relacionarse con la longitud media total de la cola en el nodo k utilizando una generalización del teorema de llegada:

${\displaystyle W_{k,r}(\mathbb {m} )={\frac {1+L_{k}\left(\mathbb {m} -1_{r}\right)}{\mu _{k,r}}}.}$

dónde${\displaystyle \mathbb {m} =(m_{1},\ldots ,m_{R})}$es un vector de población de clientes para las clases R y${\displaystyle 1_{r}}$resta uno del r -ésimo elemento de${\displaystyle \mathbb {m} }$, suponiendo que${\displaystyle m_{r}\geq 1}$.

Para redes con una sola clase de cliente, el algoritmo MVA es muy rápido y el tiempo empleado aumenta linealmente con el número de clientes y el número de colas. Sin embargo, en modelos multiclase, el número de multiplicaciones y sumas, así como los requisitos de almacenamiento para MVA, aumentan exponencialmente con el número de clases de cliente. En la práctica, el algoritmo funciona bien para 3-4 clases de cliente, ^{[ 9 ]} aunque esto generalmente depende de la implementación y la estructura del modelo. Por ejemplo, el método Tree-MVA puede escalar a modelos más grandes si la matriz de enrutamiento es dispersa. ^{[ 10 ]}

Los valores exactos para las métricas de rendimiento promedio se pueden obtener en modelos grandes utilizando el método de los momentos , que requiere tiempo log-cuadrático. El método de los momentos puede resolver en la práctica modelos con hasta 10 clases de clientes o a veces más, que normalmente son inaccesibles mediante MVA exacto. ^{[ 9 ] [ 11 ]} Sin embargo, esta técnica no utiliza el teorema de llegada y se basa en la resolución de sistemas de ecuaciones lineales que involucran la constante de normalización de las probabilidades de estado para la red de colas.

Los algoritmos MVA aproximados (AMVA), como el método de Bard-Schweitzer, ofrecen una técnica de solución alternativa que proporciona baja complejidad también en redes multiclase y generalmente ofrecen resultados muy precisos. ^{[ 12 ]}

El algoritmo de análisis del valor medio se ha aplicado a una clase de modelos PEPA que describen redes de colas y el rendimiento de un centro de distribución clave . ^{[ 13 ]}

• JMVA , una herramienta escrita en Java que implementa MVA. ^{[ 14 ]}
• colas , una biblioteca para GNU Octave que incluye MVA. ^{[ 15 ]}
• Line , una caja de herramientas de MATLAB que incluye algoritmos MVA exactos y aproximados.

• teoría de colas

• J. Virtamo: Redes de colas . El documento de Helsinki Tech ofrece una buena visión general del teorema de Jackson y del MVA.
• Simon Lam: Una derivación sencilla del algoritmo MVA . Muestra la relación entre el algoritmo de Buzen y MVA.