1. Educación

ESTRUCTURA DE UN MODELO DE COLAS
Sistema de colas
Fuente de
entrada
Clientes
Cola
Mecanismo
de servicio
Clientes
servidos
TERMINOLOGÍA Y NOTACIÓN EN TEORÍA DE COLAS
Estado del Sistema = número de clientes en el sistema
Longitud de la cola = número de clientes que esperan servicio
= (estado del sistema) - (número de
clientes a quienes se está sirviendo)
Clientes servidos
Sistema de colas
Cola
Clientes
CCCCCCC
C
C
C
S
S
S
Clientes servidos
Mecanismo
de servicio
TERMINOLOGÍA Y NOTACIÓN EN TEORÍA DE COLAS
N(t) = número de clientes en el sistema en el tiempo t
Pn(t) = P{ N(t) = n }
s = número de servidores
ln = número esperado de llegadas por unidad de tiempo (tasa
media de llegadas) de nuevos clientes, cuando hay n
clientes en el sistema
mn = número esperado de clientes que completan su servicio
por unidad de tiempo (tasa media de servicio para todo el
sistema), cuando hay n clientes en el sistema
TERMINOLOGÍA Y NOTACIÓN EN TEORÍA DE COLAS
mn representa la tasa combinada a la que todos los servidores ocupados logran
terminar sus servicios.
Cuando ln es constante para toda n se denota l. Cuando la tasa media de
servicio por servidor ocupado es constante para toda
n  1 se denota m
(entonces mn = sm cuando n ≥ s, es decir todos los servidores ocupados). En
este caso 1/l y 1/m, son los tiempos esperados entre llegadas y los tiempos
esperados servicio, respectivamente. Además, al cociente r = l/sm , se le llama
factor de utilización para la instalación de servicio (la fracción esperada de
tiempo que los servidores individuales están ocupados).
TERMINOLOGÍA Y NOTACIÓN EN TEORÍA DE COLAS
Condición transitoria del sistema: cuando el sistema recién
inicia sus operación y el estado del sistema esta muy afectado
por el estado inicial y el tiempo que ha pasado desde el inicio
Condición de estado estable del sistema: situación en la que el
sistema se vuelve independiente del estado inicial y del tiempo
trascurrido desde el inicio. La distribución de probabilidad del
estado del sistema se conserva a través del tiempo.
TERMINOLOGÍA Y NOTACIÓN EN TEORÍA DE COLAS
En condiciones de estado estable:
Pn = probabilidad de que haya exactamente n clientes en el
sistema

L = número esperado de clientes en el sistema, L =  nPn

Lq = longitud esperada de la cola, Lq =  (n  s) Pn
n =0
n=s
W = tiempo de espera en el sistema (incluye tiempo de
servicio) para cada cliente
W q = tiempo de espera en la cola (excluye tiempo de
servicio) para cada cliente
W = E(W )
Wq = E(Wq )
TERMINOLOGÍA Y NOTACIÓN EN TEORÍA DE COLAS
Relaciones entre L , W , Lq y Wq (medidas de desempeño):
1) L = lW
2) Lq = lWq
si las ln no son todas iguales, usamos la tasa media promedio
entre llegadas: l =  ln Pn
3)
W = Wq 
1
m
se supone que tiempo medio de servicio es el mismo para todo n 1
Ejemplo 1: Una tienda tiene un estacionamiento pequeño
adyacente con tres espacios reservados para los clientes. Si la
tienda esta abierta los autos llegan y usan un espacio con una tasa
media de 2 por hora. Para n = 0,1,2 y 3 la probabilidad Pn de que
hayan n espacios ocupados es: P0 = 0.2 , P1 = 0.3 , P2 = 0.3 y
P3=0.2. Determine las medidas de desempeño básicas L, Lq, W y
Wq para este sistema de colas
Ejemplo 2: La agencia del Banco Mercantil en Terrazas del Avila
tiene dos cajeras. Los clientes llegan a las cajas con una tasa media
de 40 por hora. Una cajera requiere, en promedio, 2 minutos para
servir a un cliente. Cuando ambas cajeras están ocupadas el cliente
que llega se une a la cola y espera que lo atiendan. Por experiencia
se sabe que los clientes esperan en la cola un promedio de 1 minuto
antes de pasar a la caja. Determine las medidas de desempeño
básicas Wq, W, Lq y L.
Proceso de Nacimiento y Muerte
• En el contexto de teoría de colas, se refiere al modelo
probabilístico que describe las llegadas (nacimientos) y
salidas (muertes) de clientes, en un sistema de colas.
• El estado del sistema en el tiempo t, que se denota N(t),
es el número de clientes que hay en el sistema de colas
en el tiempo t
Proceso de Nacimiento y Muerte
• Supuesto 1:
Dado N(t) = n , la distribución de probabilidad actual del tiempo
que falta para el próximo nacimiento (llegada) es exponencial
con parámetro ln .
• Supuesto 2:
Dado N(t) = n , la distribución de probabilidad actual del tiempo
que falta para la próxima muerte (salida) es exponencial con
parámetro mn .
Proceso de Nacimiento y Muerte
• Supuesto 3.
• La variable aleatoria de la suposición 1 (tiempo que falta hasta el
próximo nacimiento) y la variable aleatoria de la suposición 2
(tiempo que falta hasta la próxima muerte) son mutuamente
independientes. Además la siguiente transición del estado del
proceso es
•
n → n+1 (un solo nacimiento) o
•
n → n-1 (una sola muerte)
• dependiendo de cuál de las dos variables es más pequeña
Proceso de Nacimiento y Muerte
• Diagrama de tasas para el proceso de nacimiento y
muerte
l0
0
l1
1
m1
l2
2
m2
ln-2
3
m3
...
n-2
ln
ln-1
n-1
mn-1
n
mn
n+1
mn+1
...
Proceso de Nacimiento y Muerte:
Ecuaciones de Balance
• En(t) = número de veces que el proceso entra al
estado n, hasta el tiempo t
• Ln(t) = número de veces que el proceso sale del
estado n, hasta el tiempo t
Proceso de Nacimiento y Muerte:
Ecuaciones de Balance
En (t )  Ln (t )  1 
En (t ) Ln (t )
1

  0 cuando t  
t
t
t
lim t 
En (t )
= tasa media a la que el proceso entra al estado n
t
lim t 
Ln (t )
= tasa media a la que el proceso sale del estado n
t
tasa media de entrada = tasa media de salida
Proceso de Nacimiento y Muerte:
Ecuaciones de Balance
• .
Estado
0
Tasa media de entrada = tasa media de salida
1
l0 P0 + m2 P2 = (l1+ m1)P1
l1 P1 + m3 P3 = (l2+ m2)P2
.
.
2
m1 P1 = l0 P0
.
.
n
.
ln-1 Pn-1 + mn+1 Pn+1 = (ln+ mn)Pn
.
.
.
Ejemplo 3: Considere un proceso de nacimiento y muerte con las siguientes tasas
medias:
l0 = 2 , l1 = 3 , l2 =2 , l3 = 1 , ln = 0 para n > 3
a) m1 = 3 , m2 =4 , m3 = 1 , mn = 2 para n > 3
b) Construya el diagrama de tasas
c) Desarrolle las ecuaciones de balance
d) Resuelva las ecuaciones de balance para encontrar las distribución de probabilidad
e) Calcule L, Lq, W y Wq
Ejemplo 4. Una gasolinera cuenta con una bomba de gasolina. Los carros llegan de
acuerdo a un proceso de Poisson con una tasa media de 20 por hora. Sin embargo, si
la bomba se está usando, estos clientes potenciales pueden desistir (ir a otra
gasolinera). En particular, si hay n automóviles en la gasolinera, la probabilidad de
que un cliente potencial desista es n/3 para n =1,2,3. El tiempo que se necesita para
servir un auto tiene una distribución exponencial con media de cuatro minutos:
a) Construya el diagrama de tasas para este sistema de colas.
b) Desarrolle las ecuaciones de balance y resuélvalas para encontrar la distribución de
probabilidad de estado estable del número de autos en la gasolinera.
c) Encuentre el tiempo de espera esperado (incluyendo servicio) para los automóviles
que se quedan.
Proceso de Nacimiento y Muerte
De las Ecuaciones de balance se deduce que, para n≥1
Pn = CnP0
donde
ln1ln2 ...l0
Cn =
mn mn1...m1
para n = 1, 2,...
y se obtiene finalmente que
P0 =
1
con Co = 1

C
n =0
n
• Nos referiremos a la mayoría de los modelo de colas que
vamos a estudiar, usando la notación M/M/s/PLPS/∞/ ∞, lo
cual significa: tiempos entre llegadas con distribución
exponencial i.d.(Markoviano)/ tiempos de servicio con
distribución exponencial i.d.(Markoviano) /el número de
servidores disponibles = s /disciplina de cola: Primero en
Llegar-Primero en Salir /tamaño permisible de clientes en el
sistema = ∞ / tamaño de la poblacion de donde vienen los
clientes = ∞
•
Atención: i.d. significa idénticamente distribuidos, además debe tenerse presente
la independencia entre los tiempos de llegadas y los tiempos de salida
Caso (M/M/s=1/PLPS/∞/ ∞)
• Si ln = l y mn = m entonces Cn = (l/m)n = rn por lo
tanto, si se tiene sólo un servidor:
P0 = 1  r
l
L =  nPn =  n (1  r)r =
n =0
n =0
ml


• L = número esperado de clientes en el sistema
n
Caso (M/M/s=1/PLPS/∞/ ∞)
• Recordando que Lq es la longitud esperada
de la cola (se excluye a los clientes del sistema
que están siendo servidos en el único
servidor):
l
Lq =  (n  1)Pn =
n =1
m(m  l)

2
Caso (M/M/s=1/PLPS/∞/ ∞)
Si denotamos como W al tiempo que el cliente pasa
en el sistema, se puede demostrar que
P(W > t ) = e-m(1-r)t
por lo tanto
W=E (W ) = 1/(m-l)
Caso (M/M/s=1/PLPS/∞/ ∞)
Si denotamos como Wq al tiempo que el cliente
espera en la cola antes de ser servido, se puede
demostrar que
P(Wq > t ) = re-m(1-r)t
por lo tanto
Wq =E (Wq ) = l /m(m-l)
Ejemplo 5. Los trabajos llegan a un centro de procesado de acuerdo a un
proceso Poisson, con una tasa media de dos por día, el tiempo de operación tiene
una distribución exponencial con media de 1/4 día. Se cuenta en este centro con
suficiente espacio para material en proceso para acomodar tres trabajos además
del que se está procesando. Los trabajos adicionales se guardan temporalmente
en un lugar menos conveniente. ¿Qué proporción del tiempo será adecuado el
espacio que tiene el centro de procesado, para acomodar todos los trabajos que
lleguen? Proponga otras preguntas y, con base en las fórmulas desarrolladas hasta
ahora, respóndalas.
Ejemplo 6. Los mecánicos que trabajan en una planta de troquelado debe sacar
herramientas de un almacén. Llega un promedio de diez mecánicos por hora
buscando partes. En la actualidad el almacén está a cargo de un empleado a quien
se le pagan 6 dólares/h y necesita un promedio de 5 min. para entregar las
herramientas de cada solicitud. Como a los mecánicos se les paga 10 dólares/h,
cada hora que un mecánico en el almacén de herramientas le cuesta 10 dólares a
la empresa. Esta debe decidir si vale la pena contratar, a 4 dólares/h, un ayudante
del almacenista. Si se contrata al ayudante, el almacenista sólo tardará un
promedio de 4 min. Para atender las solicitudes de herramientas. Suponga que son
exponenciales tanto los tiempos de servicio como el tiempo entre llegadas. ¿Se
debe contratar al ayudante?
Caso (M/M/s/PLPS/∞/ ∞)
• s = # servidores ,
• ln = l para n = 1, 2, . . .
nm

mn = 
sm

para n = 1,2,...,s
para n = s  1,....
Caso (M/M/s/PLPS/∞/ ∞)
• Tendremos:
 (l / m )
 n!

Cn = 
 (l / m ) n

n s
 s! s
n
para n = 1,2,...,s  1
para n = s, s  1,....
Caso (M/M/s/PLPS/∞/ ∞)
 (l / m )
 n! P0

Pn = 
 (l / m ) n
P0

n s
 s! s
n
para 0  n  s  1
para
ns
Caso M/M/s/PLPS/∞/ ∞
Suponiendo que r = l/sm < 1 , tendremos:
P0 =
1
 s1 (l / m)
(l / m )
1 


n =0 n!

s! 1  l /(sm) 

n
s
Caso (M/M/s/PLPS/∞/ ∞)
P0 (l / m ) s r
Lq =  (n  s) Pn =
2
s!(1  r )
n=s

l
L = lW = l (W  ) = L 
m
m
1
q
q
Caso (M/M/s/PLPS/∞/ ∞)
• Con relación a la ley de probabilidad de los
tiempos de espera P(W > t ) es igual a:
s

 mt 1  P0 (l / m )
e 
 s!(1  r )
 mt ( s 1l / m )
1 e

 s 1  l / m



Proceso de Nacimiento y Muerte
Además
P(Wq > t ) = [1-P{Wq =0}]e-sm(1-r)t
donde
s 1
P{Wq = 0} = n=0Pn
Ejemplo 5. Un banco emplea cuatro cajeras para servir a sus clientes. Los clientes
llegan de acuerdo con un proceso Poisson con una tasa media de tres por minuto.
Si un cliente encuentra todas las cajas ocupadas, se una a una cola a la que le dan
servicio todas las cajeras, es decir, no hay colas frente a cada cajera , sino que
esperan en una cola por la primera cajera que se desocupa. El tiempo para
realizar las transacciones entre la cajera y el cliente tienen una distribución
exponencial con media setenta segundos. Construya el diagrama de tasas para
este sistema de colas. Encuentre la distribución de probabilidad de estado estable
para el número de clientes en el banco. Calcule L. ¿Cuál es la probabilidad de que
haya mas de un cliente en cola?. ¿Cuál es la probabilidad de que un cliente pase
mas de 2 minutos en el área de caja?
Ejemplo 6. Una tienda de tipo “minisuper” tiene una sola caja con un cajero de
tiempo completo. Los clientes llegan a la caja de manera “aleatoria”, de acuerdo a
un proceso de entradas Poisson, con una tasa media de 30 por hora. Cuando sólo
hay un cliente en la caja, el cajero lo atiende solo, con un tiempo de servicio
esperado de 1,5 minutos, pero hay un ayudante que tiene la instrucción “siempre
que haya más de un cliente en al área de caja debes ayudar al cajero a empacar
la mercancía”. Esta ayuda reduce el tiempo esperado de servicio a un minuto. En
ambos casos, la distribución de estos tiempos de servicio es exponencial..
Construya el diagrama de tasas para este sistema de colas y determine la
distribución de probabilidad de estado estable del número de cliente en la caja
Caso (M/M/s/PLPS/K/ ∞)
• No se permite que el número de clientes supere una
cantidad específica, digamos K, por lo tanto, la
modificación que debe hacerse al modelo
(M/M/s/PLPS/ ∞/ ∞) es cambiar los parámetros ln
como se indica a continuación:
l
ln= 
0
para n =1,2,....,K
para n  K
Caso (M/M/s/PLPS/K/ ∞)
• Para s  1 y s  K tenemos:
 (l / m ) n
 n!


n

C n =  (l / m )
 s!s n s



0
para n = 1,2,...,s  1
para n = s, s  1,...K
para n  K
Caso (M/M/s/PLPS/K/ ∞)
• Por lo cual
n
(
l
/
m
)

 n! P0


 (l / m ) n
Pn = 
P0
n s
 s! s



0
para
0  n  s 1
para n = s, s  1,...,K
para n  K
• Ejemplo 7. Una instalación de servicio consiste de una persona que puede
atender un promedio de 2 clientes por hora. Los tiempos de servicio son
exponenciales. Llega un promedio de 3 clientes por hora y se supone que
los tiempos entre llegadas son exponenciales. La capacidad del sistema es
de tres clientes.a) ¿Cuál es la probabilidad de que quien atiende, este
ocupado? b)En promedio, ¿cuántos clientes logran entrar al sistema?
c)Calcule L, Lq, W y Wq
• Ejemplo 8. Una oficina de boletos de una aerolínea tiene dos agentes que
contestan las llamadas para reservaciones. Una llamada se puede poner
en espera hasta que uno de los agentes se desocupa para tomarla. Si las
tres líneas (de ambos agentes y de espera) están ocupadas, el cliente
potencial obtiene tono de ocupado y se supone que llamará a otra oficina
de boletos perdiéndose la venta. Las llamadas y los intentos de llamada
ocurren aleatoriamente, según un proceso de Poisson a una tasa media de
15 por hora. La duración de una conversación telefónica tiene una
distribución exponencial con media de 4 minutos. Construya el diagrama
de tasas de este sistema. Encuentre la probabilidad de estado estable de
que: (a)Un cliente pueda hablar de inmediato con un agente. b)El cliente
queda en espera. c)El cliente obtenga tono de ocupado