...

Ejercicios de Teorıa de Colas

by user

on
Category: Documents
0

views

Report

Comments

Transcript

Ejercicios de Teorıa de Colas
Ejercicios de Teorı́a de Colas
Investigación Operativa
Ingenierı́a Informática, UC3M
Curso 08/09
1. Demuestra que en una cola M/M/1 se tiene:
ρ
.
1−ρ
L=
Solución.
L=
=
∞
X
n=0
∞
X
npn
nρn (1 − ρ)
n=0
=
∞
X
n
nρ −
n=0
=
∞
X
∞
X
nρn+1
n=0
ρn
n=1
∞
X
=ρ
ρn
n=0
=
ρ
.
1−ρ
2. Demuestra que en una cola M/M/1 se tiene:
Lq =
Solución.
Lq = λWq = λ
ρ2
.
1−ρ
ρ
ρ2
=
.
µ(1 − ρ)
1−ρ
3. En un servidor de la universidad se mandan programas de ordenador para ser ejecutados. Los programas llegan al servidor con una tasa de 10 por minuto. El tiempo medio de ejecución de cada programa
es de 5 segundos y tanto los tiempos entre llegadas como los tiempos de ejecución se distribuyen exponencialmente.
a) ¿Qué proporción de tiempo está el servidor desocupado?
1
b) ¿Cuál es el tiempo esperado total de salida de un programa?
c) ¿Cuál es el número medio de programas esperando en la cola del sistema?
Solución. El sistema es M/M/1 con λ = 10 trabajos por minuto y µ = 12 trabajos por minuto. Se
asumirá que el sistema es abierto y que la capacidad es infinita. Como ρ = 10/12 < 1, el sistema
alcanzará el estado estacionario y se pueden usar las fórmulas obtenidas en clase.
a) El servidor estará desocupado 1 − 5/6 = 1/6 del total, esto es, 10 segundos cada minuto (ya
que el ordenador está ocupado 5 × 10 = 50 segundos por minuto).
b) Tiempo medio total es W =
1
µ(1−ρ)
=
1
12(1−5/6)
= 1/2 minuto por programa.
c) El número medio de programas esperando en la cola es Lq =
ρ2
1−ρ
= 4.16 trabajos.
4. La ventanilla de un banco realiza las transacciones en un tiempo medio de 2 minutos. los clientes
llegan con una tasa media de 20 clientes a la hora. Si se supone que las llegadas siguen un proceso de
Poisson y el tiempo de servicio es exponencial, determina
a) El porcentaje de tiempo en el que el cajero está desocupado.
b) El tiempo medio de estancia de los clientes en la cola.
c) La fracción de clientes que deben esperar en la cola.
Solución. Sistema M/M/1 con λ = 20 y µ = 30.
a) P (cajero ocioso) = p0 = 1 − ρ = 1/3. El 33 % de tiempo el cajero está ocioso.
b) Wq = 1/15 = 4 minutos.
c) L = 2, Lq = 4/3, por tanto la fracción de clientes que deben esperar en la cola es Lq /L =
2/3 ≡ 66.6 %.
5. Una tienda de alimentación es atendida por una persona. Aparentemente el patrón de llegadas de
clientes durante los sábados se comporta siguiendo un proceso de Poisson con una tasa de llegadas de
10 personas por hora. A los clientes se les atiende siguiendo un orden tipo FIFO y debido al prestigio
de la tienda, una vez que llegan están dispuestos a esperar el servicio. Se estima que el tiempo que
se tarda en atender a un cliente se distribuye exponencialmente, con un tiempo medio de 4 minutos.
Determina:
a) La probabilidad de que haya lı́nea de espera.
b) La longitud media de la lı́nea de espera.
c) El tiempo medio que un cliente permanece en cola.
Solución. Sistema M/M/1 con λ = 10 y µ = 15.
a) P (lı́nea de espera) = 1 − p0 − p1 = 4/9.
b) Lq = 4/3 personas en cola.
c) Wq = 2/15 horas = 8 minutos de media en cola.
2
6. En una fábrica existe una oficina de la Seguridad Social a la que los obreros tienen acceso durante
las horas de trabajo. El jefe de personal, que ha observado la afluencia de obreros a la ventanilla,
ha solicitado que se haga un estudio relativo al funcionamiento de este servicio. Se designa a un
especialista para que determine el tiempo medio de espera de los obreros en la cola y la duración
media de la conversación que cada uno mantiene con el empleado de la ventanilla. Este analista
llega a la conclusión de que durante la primera y la última media hora de la jornada la afluencia es
muy reducida y fluctuante, pero que durante el resto de la jornada el fenómeno se puede considerar
estacionario. Del análisis de 100 periodos de 5 minutos, sucesivos o no, pero situados en la fase
estacionaria, se dedujo que el número medio de obreros que acudı́an a la ventanilla era de 1.25 por
periodo y que el tiempo entre llegadas seguı́a una distribución exponencial. Un estudio similar sobre
la duración de las conversaciones, llevó a la conclusión de que se distribuı́an exponencialmente con
duración media de 3.33 minutos. Determina:
a) Número medio de obreros en cola.
b) Tiempo medio de espera en la cola.
c) Compara el tiempo perdido por los obreros con el tiempo perdido por el oficinista. Calcula el
coste para la empresa, sin una hora de inactividad del oficinista vale 250 euros y una hora del
obrero 400 euros. ¿Serı́a rentable poner otra ventanilla?
Solución. Sistema M/M/1 con λ = 0.25 y µ = 0.3.
a) Lq = 4.166 obreros.
b) Wq = 16.66 minutos.
c) Durante cada hora hay, en media, Lq = 4.166 clientes haciendo cola. Es decir, el coste horario
por obreros ociosos es de 4.166 × 400 = 1666.66 euro. Por otro lado, 1 − ρ = 0.166, de forma
que el coste del tiempo que el oficinista está ocioso es de 250 × 0.166 = 41.5 euros horarios,
que es mucho inferior.
Si se pusiera otra ventanilla, el sistema serı́a M/M/2. En ese caso, p0 = 0.411 y p1 = 0.34, de
forma que el tiempo de oficinista que se perderı́a cada hora serı́a, en media, 2p0 + p1 = 1.166
horas. Lo que supone un coste de 291.5 euros cada hora. Por otro lado, cada hora habrı́a, en
media, Lq = 1.01 obreros en la cola. De forma que el tiempo perdido por los obreros tendria un
coste de 400 × 1.01 = 404 euros la hora.
La suma de los dos costes es mucho menor en este segundo caso, de forma que sı́ serı́a rentable
poner otra ventanilla.
7. Una entidad bancaria considera la posibilidad de instalar una red de cajeros en una de sus oficinas.
Dado que se desconoce la afluencia de público que va a demandar dicho servicio, coloca un único
cajero durante un mes. Diariamente se recogen datos sobre los tiempos de llegadas de los clientes,
ası́ como de los tiempos de servicio. Suponiendo que la sucursal se encuentra emplazada en un barrio
dende no existe otro servicio semejante, el cliente que llega prefiere esperar a poder utilizar el cajero,
cuando éste esté ocupado.
Tras el oportuno análisis de los datos recogidos, se estima que: (i) las llegadas siguen un proceso de
Poisson; (ii) la distribución del tiempo de servicio es exponencial; (iii) el tiempo medio transcurrido
3
entre dos llegadas consecutivas es de 7.5 minutos; (iv) el tiempo medio de servicio es de 5 minutos
por cliente.
Calcula:
a) Tiempo medio de espera que debe sufrir cada cliente en cola.
b) Tamaño medio de la cola y probabilidad de que al acudir al cajero ya haya alguna persona en la
cola.
Solución. Sistema M/M/1 con λ = 1/7.5 y µ = 1/5.
a) Wq = 10 minutos.
b) El número medio de las colas es de Lq = 1.33 personas, y la probabilidad de que haya al menos
dos personas en el sistema es de 1 − p0 − p1 = 4/9.
8. Los trabajadores de una fábrica tienen que llevar su trabajo al departamento de control de calidad
antes de que el producto llegue al final del proceso de producción. Hay un gran número de empleados
y las llegadas son aproximadamente de 20 por hora, siguiendo un proceso de Poisson. El tiempo para
inspeccionar una pieza sigue una distribución exponencial de media 4 minutos. Calcula el número
medio de trabajadores en el control de calidad si hay:
a) 2 inspectores.
b) 3 inspectores.
Solución.
a) Sistema M/M/2 con λ = 20 y µ = 15. Entonces L = 2.4 empleados.
b) Sistema M/M/3 con λ = 20 y µ = 15. Entonces L = 1.87 empleados.
9. Un avión tarda unos 4 minutos de media en aterrizar a partir del momento en que la torre de control
le da la señal de aterrizaje. Si las llegadas de los aviones se producen por término medio, a razón de 8
por hora y siguiendo un proceso de Poisson, ¿cuánto va a esperar el piloto dando vueltas al aeropuerto
antes de recibir la señal de tierra?
Solución. Sistema M/M/1 con λ = 8 y µ = 15. Por tanto, Wq = 4.56 minutos.
10. Una compañı́a de ordenadores posee un ordenador central al que pueden acceder los clientes a través
de unos terminales (de distintos tipos) que se alquilan. Un cliente desea determinar la velocidad
óptima del terminal que deberı́a alquilar. Los trabajos del cliente se generan según un proceso de
Poisson con una tasa de 50 programas por dı́a de 8 horas. El tamaño medio de un programa es de
1000 sentencias. Se sabe que el tiempo de lectura de sentencias es exponencial. El cliente estima
en 10 euros el coste de retrasar un programa un dı́a. La compañı́a estima que una velocidad de 100
sentencias por minuto, y cualquier aumento semejante, incrementa el precio del alquiler diario del
terminal en 100 euros. Determina la velocidad óptima del terminal.
Solución. Sistema M/M/1 con λ = 50 programas mandados al dı́a y µ =? programas ejecutados
por dı́a (variable de decisión). El coste por retrasar un programa un dı́a es de 10 euros. Como 100
4
sentencias por minuto equivalen a 48 programas por dı́a, entonces el coste por programa por unidad
de incremento de µ y por dı́a es de 100/48 = 2.083 euros.
Por tanto, el coste total es igual a
10L + 2.083µ
que se maximiza en µ = 52.19 programas leı́dos al dı́a.
11. Una compañı́a ferroviaria pinta sus propios vagones, según se vayan necesitando, en sus propios
talleres donde se pinta a mano de uno en uno con una velocidad que se distribuye según una exponencial de media un cada 4 horas y un coste anual de 4 millones de euros. Se ha determinado que los
vagones pueden llegar según un proceso de Poisson de media un cada 5 horas. Además el coste por
cada vagón que no está activo es de 500 euros la hora.
Se plantean otras dos posibilidades. Una es encargar dicho trabajo a una empresa de pintura que lo
harı́a con aerosol con el consiguiente ahorro de tiempo. Sin embargo el presupuesto para esta segunda
alternativa es de 10 millones de euros anuales. En este caso, el proceso se aproxima a uno de Poisson
con una tasa de uno cada 3 horas. La otra opción es poner otro taller exactamente igual al que hay
actualmente, con igual tasa de servicio y coste anual que permita pintar dos vagones a la vez.
En todos los casos el trabajo se considera ininterrumpido, esto es, se trabajan 24 × 365 = 8760 horas
anuales. ¿Cuál de los tres procedimientos es preferible?
Solución. Taller con pintura a mano: sistema M/M/1 con λ = 1/5 y µ = 1/4 vagones/hora. Por
tanto,
4 × 106
= 2456.62 euros por vagón.
CT = 500L +
8760
Taller con pintura con aerosol: sistema M/M/1 con λ = 1/5 y µ = 1/3 vagones/hora. Por tanto,
CT = 500L +
10 × 106
= 1891.55 euros por vagón.
8760
Dos talleres con pintura a mano: sistema M/M/2 con λ = 1/5 y µ = 1/4 vagones/hora. Por tanto,
CT = 500L +
8 × 106
= 1389.43 euros por vagón.
8760
Coste anual por hora = 2456.62 . Coste con aerosol = 1891.55 . Coste con dos servidores = 1389.43 .
Por tanto, es preferible poner dos talleres.
12. Una empresa de reparación de ordenadores recibe una media de 10 solicitudes de reparación al dı́a,
que se distribuyen según un proceso de Poisson. Se supone que µ es la velocidad de reparación de
la persona reparadora en ordenadores/dı́a, y el tiempo de reparación es exponencial. Cada unidad de
velocidad de reparación supone un coste de 100 euros por semana. Además, se ha estimado que el
coste de tener ordenadores no reparados supone 200 euros por ordenador y semana, siendo este coste
proporcional al tiempo. Suponiendo que una semana tiene cinco dı́as laborables, se pide:
a) Que determines la velocidad de reparación óptima.
b) Que determines si serı́a más económico tener dos personas, cada una con la mitad de la velocidad
determinada en el apartado anterior.
5
Solución. Sistema M/M/1 con λ = 10 y µ =?.
a) El coste total es 20µ + 40L euros diarios. Por tanto, la tasa óptima es de 14.47 ordenadores por
dı́a, con un coste diario de 378.43225 euros.
b) En este caso se trata de un sistema M/M/2. Por tanto, el coste diario de 395.184 euros, que es
peor que el anterior.
13. Una base de mantenimiento de aviones dispone de recursos para revisar únicamente un motor de
avión a la vez. Por tanto, para devolver los aviones lo antes posible, la polı́tica que se sigue consiste
en aplazar la revisión de los 4 motores de cada avión. En otras palabras, solamente se revisa un
motor del avión cada vez que un avión llega a la base. Con esta polı́tica, los aviones llegan según
una distribución de Poisson de tasa media uno al dı́a. El tiempo requerido para revisar un motor (una
vez que se empieza el trabajo) tiene una distribución exponencial de media 1/2 dı́a. Se ha hecho
una propuesta para cambiar la polı́tica de revisión de manera que los 4 motores se revisen de forma
consecutiva cada vez que un avión llegue a la base. A pesar de que ello supondrı́a cuadruplicar el
tiempo esperado de servicio, cada avión necesitarı́a ser revisado únicamente con una frecuencia 4
veces menor. Utilizar la teorı́a de colas para comparar las 2 alternativas.
Solución. En los dos casos se trata de colas M/M/1, puesto que tanto los tiempos entre llegadas como
los tiempos de servicio son variables aleatorias con distribución exponencial.
En la situación actual, la tasa de llegadas es λ = 1 avión al dı́a y la tasa de servicio es µ = 2 aviones
al dı́a. Con estos parámetros, ρ = 0.5 < 1, y por tanto existe el estado estacionario. Los valores de
las cantidades de interés son:
L = 1 avión, Lq = 1/2 avión, W = 1 dı́a, Wq = 1/2 dı́a
Si se siguiera la propuesta para cambiar la polı́tica, la cola seguiria siendo una M/M/1, pero ahora
las tasas de llegada y de servicio serian λ = 0.25 aviones al dı́a, y µ = 0.5 aviones al dı́a, respectivamente. En este caso, ρ sigue siendo 0.5 y por tanto sigue existiendo el estado estacionario. Los
valores de las cantidades de interés son:
L = 1 avión, Lq = 1/2 avión, W = 4 dı́as, Wq = 2 dı́as
Con la configuración propuesta, cada vez que un avión vaya a ser revisado pasará en el sistema
el cuádruple del tiempo que pasaba con el sistema anterior, pero como cada avión va a ir con una
frecuencia cuatro veces menor, el tiempo perdido en el taller a largo plazo va a ser igual. En este caso,
la decisión entre una configuración y la otra deberı́a ser tomada en función de los costes de operación.
6
Fly UP