La mayor parte de los modelos elementales de colas suponen que las entradas (llegada de clientes) y las salidas (clientes que se van) del sistema ocurren de acuerdo al proceso de nacimiento y muerte.
El estado del sistema, N(t), en el tiempo t (t >= 0) es el número de clientes que hay en ese momento. El proceso de nacimiento y muerte describe en términos probabilísticos cómo cambia N(t) al aumentar t. En general, los nacimientos y muertes individuales ocurren aleatoriamente, sus tasas medias de ocurrencia dependen del estado actual del sistema. De manera más precisa, las suposiciones del proceso de nacimiento y muerte son las siguientes:
Como consecuencia de las suposiciones 1 y 2, el proceso de nacimiento y muerte es un tipo especial de Cadena de Markov de tiempo continuo. Los modelos de colas que se pueden representar por una cadena de Markov de tiempo continuo son mucho más manejables analíticamente que cualquier otro y la suposición 3 simplifica mucho más el análisis.
La distribución exponencial, implica que las ln y mn son tasas medias, estas suposiciones se pueden resumir en el diagrama de tasas que se muestra en la fig. 1.
l0 l1 l2 ln-2 ln-1 ln
Estado: 0 1 2
3 ... n -2 n
-1 n n+1
m1 m2 m3 mn-1 mn mn+1
Representa un "Nacimiento" (llegada)
Representa una "Muerte" (se completa el trámite)
Figura 1: Diagrama de tasas para el proceso de nacimiento y muerte [1]
Las flechas en este diagrama muestran las únicas transiciones posibles en el estado del sistema (como lo especifica la suposición 3) y el elemento junto a cada flecha da la tasa media para esa transición (como lo especifican las suposiciones 1 y 2) cuando el sistema se encuentra en el estado que hay en la base de la flecha.
La mayor parte de los sistemas de cola con tiempos exponenciales entre llegadas y tiempos exponenciales de servicio pueden modelarse como procesos de nacimiento y muerte.
Un proceso de nacimiento y muerte es un proceso estocástico continuo en el tiempo para el que el estado del sistema en cualquier tiempo es un entero no negativo.
Considérese cualquier estado n (n = 0, 1, 2, ...) del sistema. Supóngase que se inicia el conteo del número de veces que el sistema entra a éste estado y el número de veces que sale de él, como se muestra a continuación:
[2] En (t) = número de veces que el proceso entra al estado n hasta el tiempo t.
[3] Ln (t) = número de veces que el proceso sale del estado n hasta el tiempo t.
Como los dos tipos de eventos (entrar y salir) deben alternarse, estos dos números serán iguales o diferirán en sólo 1; es decir,
|En
(t) - Ln
(t)| <= 1.
Dividiendo ambos lados por t y después haciendo que t ® ¥ se obtiene
En (t) _ Ln
(t) <=
1 así:
t t t
lím En (t) _ Ln (t) = 0
t ¥
t t
Al dividir En (t) y Ln (t) por t se obtiene la tasa real (número de eventos por unidad de tiempo) a la que ocurren estos dos tipos de eventos, y haciendo que t ® ¥ se obtiene entonces la tasa media (número esperado de eventos por unidad de tiempo).
lím En (t) = tasa media a la que el proceso entra al estado n.
t ¥
t
lím Ln (t) = tasa media a la que el proceso sale al estado n.
t ¥
t
Este resultado conduce al siguiente principio clave:
PRINCIPIO : Para
cualquier estado n (n = 0, 1, 2, ...) del sistema, la suma de las tasas medias
que entran a cada estado debe ser igual a la suma de las tasas medias que salen
del mismo estado (cada tasa multiplicada por su respectiva probabilidad).
La ecuación que expresa este principio se llama ecuación de balance para el estado n. Después de construir las ecuaciones de balance para todos los estados en términos de las probabilidades p(n) desconocidas, se puede resolver este sistema de ecuaciones para encontrar estas probabilidades.
Para ilustrar una ecuación de balance, considérese el estado 0. El proceso entra a este estado sólo desde el estado 1. Así, la probabilidad de estado estable de encontrarse en el estado 1 (p(1)) representa la proporción de tiempo que es posible que el proceso entre al estado 0. Dado que el proceso se encuentra en el estado 1, la tasa media de entrada al estado 0 es m1. (En otras palabras, para cada unidad acumulada de tiempo que el proceso pasa en el estado 1, el número esperado de veces que lo dejaría para entrar al estado 0 es m1) Desde cualquier otro estado, esta tasa media es 0. Por lo tanto, la tasa media global a la que el proceso deja su estado actual para entrar al estado 0 (la tasa media de entrada) es:
m1 p(1) + 0(1 - p(1))
= m1 p(1)
Por el mismo razonamiento, la tasa media de ocurrencia de los eventos de salida debe ser l0 p(0) de manera que la ecuación de balance para el estado 0 es:
m1
p(1) = l0
p(0)
Para todos los demás estados, existen dos transiciones posibles, hacia adentro y hacia afuera del estado. Entonces, cada lado de las ecuaciones de balance para estos estados representa la suma de las tasas medias para las dos transiciones incluidas. Por lo demás, el razonamiento es igual que para el estado 0. Estas ecuaciones de balance se resumen en la tabla 1. Obsérvese que la primera ecuación de balance contiene dos variables ( p(0) y p(1)), las siguientes dos ecuaciones contienen tres variables ( p(0) , p(1) y p(2)), y así sucesivamente, de que siempre se tiene una variable "adicional".
En el equilibrio (ecuación de balance), el número de transiciones en uno y en otro sentido ha de ser igual, por termino medio, sino la cola se encontrará vacía permanentemente o crecerá sin límite.
Estado |
Ecuación |
0 |
m1 p(1) = l0 p(0) |
1 |
l0 p(0) + m2 p(2) = (l1 +m1) p(1) |
2... |
l1 p(1) + m3 p(3) = (l2 +m2) p(2)
... |
n-1 |
ln-2 p(n-2) + mn p(n) = (ln-1 +mn-1)
p(n-1) |
n... |
ln-1 p(n-1) + mn+1 p(n+1) = (ln +mn) p(n) ... |
El procedimiento para resolver estas ecuaciones es despejar todas las variables en términos de una de ellas, entre las cuales la más conveniente es p(0). La primera ecuación se usa para despejar p(1) en términos de p(0), después se usa este resultado en la segunda ecuación para obtener p(2) en términos de p(0) etc. Al final, el requisito de que la suma de todas las probabilidades debe ser igual a 1 se puede usar para evaluar p(0). Si se aplica este procedimiento se obtienen los siguientes resultados:
Estado
0:
1:
2:
. .
. .
n –1
n
. .
. .
Para simplificar la notación, sea:
Ecuación nº 1 para n = 1,2,...
que es la relación entre las n tasas de entrada y las n tasas de salida.
Entonces, reemplazando, las probabilidades de estado estable son:
Ecuación nº 2 para
n = 1,2,...
Estos resultados de estado estable se desarrollaron bajo la
suposición de que los parámetros ln
y mn tienen valores tales que el
proceso, de hecho, puede alcanzar la condición de estado estable. Esta
suposición siempre se cumple si ln
= 0 para algún valor de n mayor
que el estado inicial, de forma que sólo son posibles un número finito de
estados (aquellos menores que esta n).
También se cumple siempre que l
y m están definidas y y
= l /mSk
< 1. No se cumple si , ya que no existe
distribución de estado estable.
Los resultados generales de estado estable que se acaban de dar en los recuadros se utilizarán una y otra vez para obtener los resultados específicos de estado estable para estos modelos.
MODELOS DE COLAS BASADOS EN EL PROCESO DE NACIMIENTO Y
MUERTE
Como se puede asignar cualquier valor no negativo a cada una de las tasas medias l0, l1,...,m1, m2, ... del proceso de nacimiento y muerte, se cuenta con una gran flexibilidad al modelar un sistema de colas. Los modelos que acaso sean los que más se usan en teoría de colas están basados directamente en este proceso. Las suposiciones 1 y 2 dicen que estos modelos tienen una entrada Poisson y tiempos de servicio exponenciales. Los modelos difieren sólo en las suposiciones sobre cómo cambian las ln y las mn según el estado n.
El modelo M/M/S supone que todos los tiempos entre llegadas son independientes e idénticamente distribuidos de acuerdo a una distribución exponencial (es decir, el proceso de entrada es Poisson), que todos los tiempos de servicio son independientes e idénticamente distribuidos de acuerdo a otra distribución exponencial y que el número de servidores es S (cualquier entero positivo). En consecuencia, este modelo es sólo un caso especial del proceso de nacimiento y muerte cuando la tasa media de llegadas al sistema de colas y la tasa media de servicio por servidor ocupado son constantes (l y m, respectivamente) e independientes del estado del sistema.
Recordando la ecuación nº 1, donde Cn es la relación entre las n tasas de entrada y las n tasas de salida, para éste caso particular, las l son iguales entre sí (ln = l) y los m también (mn = m) entonces, reemplazando, se obtiene:
p(n) =
Entonces las probabilidades de estado estable son:
p(n) = para n = 1,2,...
A partir del requisito
se obtiene:
Cuando el sistema tiene sólo un servidor (S = 1), la implicación es que los parámetros para el proceso de nacimiento y muerte son ln = l (n = 0,1, 2, ...) y mn = m (n = 1, 2, ...). En la figura 2a se muestra el diagrama de tasas que se obtiene.
a) Caso de un Servidor (S=1) ln = l, para n=0,1,2,...
mn = m, para n=1,2,...
l l l l l l
Estado 0 1 2 3 ... n -2 n -1 n n +1 ...
m m m m m m
b) Caso de varios Servidores (S>1) ln = l, para n=0,1,2,...
nm, para
n = 1,2,...S
mn=
sm, para n = S, S
+ 1,...
l l l l l l
Estado 0 1 2 3 ... n -2 n -1 n n +1 ...
m 2 m 3 m (S -1)m S m S m
Figura 2 Diagrama de tasas para el modelo M/ M/ S
Cuando el sistema tiene varios servidores (S >1), no es tan sencillo expresar mn.
Recuérdese que mn representa la
tasa media de servicio para el sistema de colas completo (es decir, la tasa media a la que ocurren las
terminaciones de servicio y los clientes dejan el sistema) cuando hay n clientes en el sistema. La
distribución exponencial considera que
la tasa media de servicio por servidor ocupado es m
y la tasa media de servicio global para n
servidores debe ser nm.
Entonces, mn = nm
cuando n S, mientras que mn
= Sm cuando n
Sm ya que los S servidores están ocupados. El diagrama de tasas para
este caso se muestra en la figura 2b.
Por ejemplo, tenemos un sistema de colas M/M/3 en el que los tiempos entre llegadas son exponenciales con l = 4 clientes por unidad de tiempo y los tiempos de servicio son exponenciales con m = 5 clientes por unidad de tiempo. Para modelar este sistema como proceso de nacimiento y muerte utilizaríamos los siguientes parámetros:
ln = 4, para n = 0,1,2,...
m0 = 0, m1 = 5, m2 = 5+ 5 = 10, m3 = 5+5+5 = 15, para n = 3,4,5,...
4 4
4 4 4
Estado
0 1 2 3 4 5 ...
5 10 15 15
15
Si los tiempos entre llegada o los de servicio no son exponenciales, entonces el modelo de proceso de nacimiento y muerte no es adecuado.
Cuando la tasa media de servicio máxima (Sm) exceda a la tasa media de llegadas (l), es decir, cuando el sistema de colas se ajuste a este modelo, tarde o temprano alcanzará la condición de estado estable.
y = <
1
En esta situación se pueden aplicar de manera directa los
resultados de estado estable para el proceso de nacimiento y muerte.
PROCESOS DE LLEGADAS Y SERVICIOS PUROS
Los eventos representan llegadas puras, lo que significa
que los clientes se unen al sistema y nunca lo abandonan. Al proceso se le da el nombre sugerente de nacimiento
puro. Este proceso le puede ilustrar el caso del Registro Civil que computariza todos los registros de nacimiento de niños
en una fecha dada. La información sobre el nacimiento de cada niño se almacena
en forma permanente en la computadora.
La
distribución de p(n)t es
de Poisson con media y varianza iguales a lt. (Entre todas las distribuciones discretas
que se conocen comúnmente, la función densidad de probabilidad de Poisson tiene
la propiedad única de tener igual media y varianza).
La conclusión que se obtiene de lo antes expuesto queda
como sigue: en tanto que el tiempo entre llegadas es
exponencial con media 1/l, el número de llegadas durante el intervalo
de tiempo t es de Poisson con la
media lt.
Ejemplo
Considere el ejemplo del Registro
Civil. Supóngase que los nacimientos en la ciudad están espaciados en el
tiempo según una distribución exponencial
y que el tiempo promedio entre nacimientos sucesivos es de 2 horas.
Para analizar esta situación, debemos comprender que
debido a que el tiempo entre nacimientos (entre llegadas) es de dos horas, se
tiene:
l = = 12 nacimientos por día
Supóngase que el Registro Civil está interesado en
calcular el tamaño o capacidad de almacenamiento de la computadora que se
necesita anualmente. Esto será equivalente a determinar el número promedio de
nacimientos por año; es decir,
lt =
12 X 365
= 4380 registros por año
Otra información que puede ser de interés es el porcentaje de tiempo que permanece ocioso el empleado encargado de almacenar los registros recibidos en la computadora en un periodo de un día. Esto sólo puede suceder si no llegan registros de nacimientos a la computadora; esto es,
El proceso de salidas puras supone que el sistema
comienza con un número N de clientes
que salen de la instalación a la tasa l después de ser atendidos. No se permite que ingresen al
sistema nuevos clientes. Al proceso se le da el nombre sugerente de fallecimiento
puro.
Por ejemplo, las situaciones de inventarios se pueden
modelar a través del proceso de fallecimiento
puro, donde al inicio de un periodo de planeación se pone a disposición un
grupo de N artículos de inventario.
Los artículos del inventario se retiran de existencia a la tasa de m unidades
por tiempo unitario.
Ejemplo
Al inicio de cada semana, se almacenan 15 unidades de un artículo de inventario para
utilizarse durante la semana. Sólo se hacen retiros del almacenamiento durante
los primeros 6 días (la
empresa está cerrada los domingos) y sigue una distribución de Poisson con la
media 3 unidades/día.
Cuando el nivel de existencia llega a 5 unidades, se coloca un nuevo pedido de 15 unidades para ser entregado al principio de la semana entrante. Debido a
la naturaleza del artículo, se desechan todas las unidades que sobran al final
de la semana.
Podemos analizar esta situación en varias formas.
Primero, reconocemos que la tasa de cálculo es m = 3 unidades
por día. Supóngase que nos interesa determinar la probabilidad de tener 5 unidades (el nivel de nuevo pedido) al día t; es decir,
Como ejemplo ilustrativo de los cálculos, tenemos
t (días) 1 2 3 4 5 6 mt 3 6 9 12 15 18 p(5)t 0,0008 0,0413 0,1186 0,1048 0,0486 0,015
Obsérvese que p(5)t
representa la probabilidad de hacer un nuevo pedido al día t. Esta probabilidad llega a su nivel máximo en t = 3 y después disminuye conforme transcurre la semana.
Para cualquier sistema Markoviano de líneas de espera, puede utilizarse el método de ecuación de equilibrio o de balance para anotar las ecuaciones de longitud de línea de espera de estado estable. Aún cuando siempre deberá considerarse que los tiempos de servicios y los tiempos entre llegadas siguen distribuciones exponencial negativas, puede permitirse que los parámetros de estas distribuciones dependan del número de clientes en el sistema.
Por ejemplo, podría considerarse que los servidores proporcionan una tasa más rápida de servicio cuando ven más clientes en la línea de espera, ya sea aumentando su propia tasa o llamando a servidores extras, o que la tasa de llegada de clientes depende del número de clientes en la línea de espera.
Considérese un sistema cuyo diagrama de transacción se da en la figura 1. En este caso tanto las tasas de llegada como de servicio dependen del estado.
Las ecuaciones de equilibrio o de balance son las que se vieron anteriormente.
Podemos citar una de ellas en forma general:
(2)
1< n<= N p(n) = p(0)
ln-1 ln-2 . . . l0
mn mn-1
. .
. m1
Hay representados en la figura 1 dos casos especiales del sistema que vale la pena mencionar. Uno de éstos es la clase de modelos en los cuales la combinación de posibles clientes es finita, a lo que algunas veces se denomina problemas de reparación de máquinas. Hasta ahora, se ha considerado que la población que arriba es infinitamente grande, de manera que el proceso de llegada no depende del número de unidades en el sistema. Para muchas aplicaciones industriales, la población que arriba es tan pequeña que esta consideración deja de ser razonable.
Ejemplo:
Considere un número limitado de máquinas, en el piso de producción de una fábrica, cada una de las cuales puede descomponerse. Una descompostura representa una llegada, mientras que una conclusión de la reparación representa una partida. Una vez que la máquina ha sido reparada vuelve a entrar a la combinación de posibles llegadas. Por lo tanto, cada llegada disminuye la tasa de llegadas y cada partida aumenta la tasa de llegadas.
Se tiene que un operador está a cargo de 4 máquinas idénticas. Con base en las primeras pocas horas de operación de una corrida de producción (después de que el operador se ha familiarizado lo suficiente con el proceso), el ingeniero de producción estima que, en promedio, cada máquina se detiene y requiere atención del operador aproximadamente 6 veces por hora y que el operador tarda, en promedio, 2 minutos en dar servicio a una máquina. Tanto el patrón de tiempo entre llegadas como de tiempo de servicio parecen seguir distribuciones aproximadamente exponencial negativa. ¿Puede un operador manejar adecuadamente 4 máquinas o es excesivamente grande el tiempo total de paro de máquinas?
Expresando las tasas de llegadas y las tasas de servicio para cada máquina por horas, se obtiene un l = 6 [ maq / h ] m =60/2 =30 [ maq / h ]. El estado del sistema se refiere al número de máquinas que requieren atención, de manera que en términos del proceso general de la fig. 1, se tiene:
N= 4, l0 = 4l, l1 = 3l, l2 = 2l, l3 = l y m1 = m2 = m3 = m4 = m.
A partir de (2), pueden obtenerse los siguientes resultados de estado estable:
n
p(0), p(n) =
4! l para n = 1,2,3,4
(4 – n)! m
de manera que
p(0) =
1
2 3 4
1+ 4! l + 4! l + 4 ! l + 4! l
3! m 2! m. 1! m 0! m
Ya que l / m = 0.2, p(0) = 0.398. Entonces, el operador está ocioso aproximadamente el 40% del tiempo, esperando que las máquinas requieran servicio. A partir de este resultado, puede determinarse p(n), fracción de tiempo que las n máquinas requieren servicio:
p(1) = 4! 3!
0.2 (0.398) = 0.319 p(2) =0.191 p(3) =0.077 p(4)
= 0.015
Otro caso especial del sistema de la fig. 1 tiene considerable aplicación en el diseño de sistemas telefónicos.
Considérese esta situación, las llamadas que llegan (clientes) lo hacen siguiendo un proceso de Poisson en un conmutador telefónico que tiene un total de S líneas (servidores) disponibles.
La distribución de la duración de las
llamadas es aproximadamente exponencial
negativa con media 1/ m. Si
se permiten que las llamadas esperen (llamadas
bloqueadas retrasadas) un modelo M/M/S
es adecuado, de manera que el número esperado de líneas en uso es l
/ m
.
Sólo se permiten tantas llamadas como líneas
(S) en el sistema, de manera que un modelo adecuado es M/M/S/S.
Proceso de llegadas: Es la forma en que los clientes llegan a solicitar el
servicio. Las características más
importante del proceso de llegada es el tiempo entre dos llegadas sucesivas
(cuando menor sea el intervalo de tiempo, con más frecuencia llegan los
clientes, lo cual aumenta la demanda de servidores disponibles).
Autores
MORENO, Andrea andreamoreno2000@yahoo.com.ar
ALVERO, Mariela.
DIP, Nancy.
SERRANO, Olga.
SCHVARTZ, Enrique.
VILLACÍS POSTIGO, Fernando.
Universidad
Tecnológica Nacional, Facultad Regional Tucumán.