Capítulo 14 Redes de filas de espera



Descargar 155.15 Kb.
Página1/6
Fecha de conversión10.01.2017
Tamaño155.15 Kb.
  1   2   3   4   5   6

- -

Fuente: www.itu.int/ITU-D/study_groups/ SGP_2002-2006/SG2/133000S4.Doc - Resultado Suplementario
CAPÍTULO 14

Redes de filas de espera

Muchos sistemas se pueden modelar de manera que un cliente obtenga servicios a partir de varios nodos sucesivos, es decir, una vez que un cliente ha finalizado el servicio en un nodo pasa a otro. La demanda total de servicios se compone de demandas de servicios en distintos nodos. Por consiguiente, el sistema es una red de puesta fila de espera en la que cada una de las filas se denomina nodo. Como ejemplos de redes de puesta fila de espera cabe citar los sistemas de telecomunicaciones, los sistemas informáticos, las redes de conmutación de paquetes y los sistemas de fabricación flexibles. En las redes de puesta en fila de espera se define la longitud de la fila en un nodo como el número total de clientes en el nodo, incluidos los clientes que están servidos.

Este Capítulo tiene por objeto introducir la teoría fundamental de las redes de puesta en fila de espera, ilustrada por aplicaciones. Por lo general, se considera que la teoría es bastante complicada, lo que se debe principalmente a la complejidad de la notación. Ahora bien, en este Capítulo se introducirán de manera simple los modelos generales analíticos de redes de puesta en fila de espera sobre la base de formas de producto, el algoritmo de convolución, el algoritmo MDA y los ejemplos pertinentes.

La teoría de las redes de puesta en fila de espera es análoga a la teoría de los sistemas multidimensionales (véanse los Capítulos 10 y 11). En el Capítulo 10 se examinaron los sistemas de pérdidas multidimensionales mientras que en este Capítulo se tratarán las redes de sistemas de puesta en fila de espera.


14.1 Introducción a las redes de puesta en fila de espera


Las redes de puesta en fila de espera se clasifican en abiertas y cerradas. En redes de puesta en fila cerradas la cantidad de clientes es fija mientras que en redes de puesta en fila abiertas la cantidad de clientes varía. En principio, una red abierta se puede transformar en una red cerrada agregando un nodo extra.

El sistema de espera clásico de Erlang, M/N/n, es un ejemplo de un sistema de puesta en fila abierto, mientras que el modelo máquina/reparación de Palm con S terminales es una red cerrada. Si hay más que un tipo de clientes, la red puede ser una mezcla de red abierta y cerrada. En razón que el proceso de salida en un nodo es el proceso de llegada en otro, se deberá prestar especial atención al proceso de salida, en particular cuando se puede modelar como proceso de Poisson. Esto se examinará en el § 14.2 (Sistemas simétricos de puesta en fila).

El estado de una red de puesta en fila se define como la distribución simultánea del número de clientes en cada nodo. Si K representa el número total de nodos, el estado se describe entonces mediante un vector p (i1, i2, . . . iK) donde iK es el número de clientes en el nodo k (k = 1, 2 . . . k). Con frecuencia el espacio de estado es muy amplio y las probabilidades de estado mediante la resolución de ecuaciones de equilibrio de nodos son difíciles de calcular. Si cada nodo es un sistema simétrico de puesta en fila, por ejemplo red de Jackson (véase el § 14.3), se tendrá entonces una forma de producto. Las probabilidades de estado de redes con forma de producto se pueden agregar y obtener utilizando el algoritmo de convolución (véase el § 14.4.1) o el algoritmo MVA (véase el § 14.4.2)

Las redes de Jackson pueden ser generalizadas en redes BCMP (véase el § 14.5), donde hay N tipos de clientes. Los clientes de un tipo específico pertenecen a una denominada cadena. En la figura 14.1 se ilustra un ejemplo de una red de puesta en fila con cuatro cadenas. Cuando el número de cadenas aumenta el espacio de estado se incrementa en consecuencia, y sólo los sistemas con un pequeño número de cadenas se pueden calcular exactamente. En el caso de una red multicadena, el

estado de cada nodo resulta multidimensional (véase el § 14.6). La forma de producto entre nodos se mantienen, y son aplicables los algoritmos de convolución y MVA (véase el § 14.7). La cantidad aproximada de algoritmos para grandes redes se puede encontrar en la literatura.



Figura 14.1  Ejemplo de una red de puesta en fila con cuatro cadenas abiertas

14.2 Sistemas simétricos de puesta en fila de espera


Para analizar los sistemas de puesta en fila es importante conocer cuándo el proceso de salida de un sistema de fila de espera es un proceso de Poisson. Se conocen cuatro modelos de puesta en fila que tienen esta propiedad.

1) M/M/n. Este es el teorema de Burke (1956 [13]), que expresa que el proceso de salida de un sistema M/M/n es un proceso de Poisson. Las probabilidades de espacio de estado están dadas por la ecuación (12.2):



donde A = /

2) M/G/. Esto corresponde al caso de Poisson (véase el § 7.2). Del § 6.3 se sabe que una traslación aleatoria de los eventos de un proceso de Poisson produce un nuevo proceso de Poisson. Este modelo se representa a veces como un sistema con criterio de puesta en fila IS, número infinito de servidores. Las probabilidades de estado vienen dadas por la distribución de Poisson (7.6):

3) M/G/1-PS. Este es un sistema de puesta en fila de un solo servidor con una distribución general del tiempo de servicio y compartición de procesador. Las probabilidades de estado son similares al caso M/M/1 (13.79):



p(i) = (1  A) . Ai, i= 0, 1, 2, . . . . (14.4)

4) M/G/1-LCFS-PR (PR = con derecho prioritario). Este sistema también tiene las mismas probabilidades de espacio de estado que el modelo M/M/1 (14.4).

En la teoría de redes de puesta en fila sólo se consideran, por lo general, estos cuatro criterios de fila de espera. Sin embargo, aun para el sistema de pérdidas de Erlang, el proceso de salida será un proceso de Poisson si se incluyen clientes bloqueados.

Estos cuatro sistemas se conocen como sistemas simétricos de puesta en fila de espera, pues son simétricos en el tiempo. Tanto el proceso de llegada como el de salida son procesos de Poisson y los sistemas son reversibles (Kelly, 1979 [60]). El proceso se denomina reversible pues tiene el mismo aspecto que cuando se invierte el tiempo (por ejemplo, se dice que una película es reversible cuando su reproducción hacia delante o hacia atrás parecen iguales). Con excepción del modelo M/M/n estos sistemas simétricos de puesta en fila tienen como característica común que el cliente es servido inmediatamente a partir de su llegada. A continuación se tratarán básicamente los nodos M/M/n pero el modelo M/M/1 también incluye M/G/1-PS y M/G/1-LCFS-PR.


  1   2   3   4   5   6


La base de datos está protegida por derechos de autor ©bazica.org 2016
enviar mensaje

    Página principal