Contenido
PalancaEjercicios corregidos: Cola
Los ejercicios corregidos a continuación se refieren a la cola, cadenas de Markov en tiempo continuo.
Ejercicio 1
Un sistema cliente-servidor recibe un promedio de 1000 solicitudes por segundo, que llegan en un proceso de Poisson. Tiene un solo servidor que puede procesar un promedio de 2000 clientes por segundo. Se supone que el tiempo de servicio de un cliente se distribuye de acuerdo con la ley exponencial. Calcule la probabilidad de que el tiempo de servicio supere los 2 ms.
¿Cuál es el porcentaje de clientes rechazados para un sistema que no tiene cola?
La misma pregunta para un sistema con una cola de 1 asiento. Calcule la tasa de aplicación del servidor.
Misma pregunta para un sistema con una cola de 2 lugares.
Al elegir el milisegundo como unidad de tiempo, obtenemos una tasa de natalidad de 1 y una tasa de mortalidad de 2. El tiempo de servicio TS de un cliente sigue una ley exponencial del parámetro 2 por lo que la probabilidad de que el tiempo de servicio supere los dos segundos es de 0.0183 gracias a la siguiente fórmula:
La cadena (a) representa una capacidad en la cola de 0 asientos, mientras que la cadena (b) representa una capacidad en la cola de 1 asiento. Para cada nuevo lugar, basta con agregar un estado.
Para la primera cadena, calcularemos la distribución estacionaria:
Por lo tanto, tenemos 1/3 de clientes rechazados (si estamos 1/3 del tiempo en el estado 1, entonces ya no podemos recibir clientes en 1/3 del funcionamiento de la cola). La tasa de ocupación es pi0 = 2/3.
Para la segunda cadena, calcularemos la distribución estacionaria:
Y para una capacidad de 2 en la cola obtenemos pi3 = 1/15 y pi0 = 8/15.
Ejercicio 2
Un sistema cliente-servidor recibe un promedio de 1000 solicitudes por segundo, que llegan en un proceso de Poisson. Como experimento, estamos considerando un sistema sin cola pero que comprende varios servidores front-end. Cuando todos los servidores están ocupados, las solicitudes se rechazan.
¿Cuál es el porcentaje de clientes rechazados para un sistema con 1 servidor que procesa 4000 solicitudes por segundo?
La misma pregunta para un sistema con dos servidores, cada uno procesando 2000 solicitudes por segundo.
La misma pregunta para un sistema con cuatro servidores, cada uno procesando 1000 solicitudes por segundo.
Independientemente del número de servidores, la idea de computación en paralelo sin colas siempre se construye de la misma manera: con cada nuevo cliente, opera un servidor más.
Simplemente calcule la distribución estacionaria, el número de clientes rechazados es igual a la distribución del último estado (el máximo a la derecha aquí).
Para un servidor: 1/5
Para dos servidores: 1/13
Para cuatro servidores: 1/65
Ejercicio 3
Los camiones llegan a una estación de servicio para realizar pruebas de seguridad, siguiendo un proceso de Poisson de tasa de 6 por día. La duración de las pruebas para cada camión es un rango exponencial de expectativa matemática de 1 hora y 30 minutos. Se asume que el proceso de llegada no se detiene y que la estación está funcionando las 24 horas del día.
¿Admite el sistema una distribución estacionaria?
Si es así, calcúlelo y proporcione el número promedio de usuarios en el sistema, el tiempo promedio que permanecen en el sistema, la longitud promedio de la cola y el tiempo promedio que permanecen en la cola (en modo estacionario).
Tenemos lambda = 1/4 y mu = 2/3 (en horas). Como rho = 3/8 <1, el sistema es ergódico. De las fórmulas para calcular los parámetros de los sistemas M / M / 1, tendremos:
La longitud promedio de la cola y el tiempo de espera en la cola vienen dados por:
Ejercicio 4
Una empresa de construcción tiene dos máquinas idénticas, cada una de las cuales puede averiarse independientemente de la otra siguiendo un proceso de Poisson 5 veces al mes. Se supone que el tiempo de reparación es un rv que sigue una ley exponencial con parámetro mu (tasa de servicio). ¿Para qué valor de mu, las dos máquinas estarán simultáneamente en funcionamiento por lo menos la mitad del tiempo?
El sistema está modelado por un proceso de nacimiento y muerte con 3 estados (0, 1 o 2 máquinas averiadas) con el siguiente diagrama de transición:
Nosotros tenemos :
De donde
siendo p0 la probabilidad estacionaria de que las dos máquinas estén en funcionamiento, debemos tener:
Teniendo en cuenta la positividad de mu, debemos tener
Por lo tanto, requerirá una tarifa de servicio al menos igual a 13,660254 para que ambas máquinas funcionen al menos cada dos veces.
Ejercicio 5
Una lavandería tiene 3 máquinas idénticas e independientes. Cada máquina tiene un tiempo de funcionamiento independiente del pasado, siguiendo una ley exponencial de expectativa de dos días. Una máquina que se avería es reparada por un técnico; la duración de la reparación es una expectativa de un día. La lavandería tiene un solo técnico.
Dibuja el diagrama de transición.
¿Cuál es la fracción de tiempo que todas las máquinas están funcionando y todas las máquinas están apagadas?
¿Cuál es el número medio de máquinas en funcionamiento? ¿Cuál es el número medio de máquinas inmovilizadas?
- Suponga que el estado Ej designa el estado en el que j máquinas están inmovilizadas. Tenemos el siguiente diagrama de transición:
- Tenemos en estado estacionario las siguientes ecuaciones: De donde
Por tanto, las fracciones deseadas son 4/19 (para todas las máquinas en funcionamiento) y 3/19 (para todas las máquinas inmovilizadas).
- El número medio de máquinas en funcionamiento es: 4 * (4/19) + 2 * (6/19) + 1 * (6/19) = 30/19. Y el número medio de máquinas inmovilizadas es 9/19 + 12/19 + 6/193.
Ejercicio 6
Un servidor de base de datos recibe un promedio de 100 solicitudes por segundo, que llegan en un proceso de Poisson. El tiempo de procesamiento de una solicitud sigue la ley exponencial del parámetro µ. Cuando el servidor está ocupado, las solicitudes se almacenan en un disco grande para su posterior procesamiento por orden de llegada. Hay 4 tipos diferentes de servidores en el mercado que pueden procesar 100, 150, 200 o 300 solicitudes por segundo, respectivamente, cuando están operando sin interrupción.
¿Qué pasará si planea instalar un servidor que pueda manejar 100 solicitudes por segundo?
Queremos que un cliente que emite una solicitud tenga la respuesta después de 1/100 de segundo en promedio. ¿Qué tipo de servidor debo proporcionar?
Estamos de acuerdo en que cuando ya hay 8 solicitudes almacenadas en la cola, las nuevas solicitudes que llegan se verían demasiado penalizadas en términos de tiempo de respuesta. Entonces decidimos que en este caso serán redirigidos instantáneamente a un servidor auxiliar. Para simplificar, supondremos que esta nueva disposición tiene una influencia insignificante sobre la antigua distribución estacionaria (calculada sin servidor auxiliar). Calcule la probabilidad de que una solicitud que llega al servidor principal sea redirigida al servidor auxiliar. ¿Cuántas solicitudes, en promedio, recibirá el servidor auxiliar por segundo?
Esta es una cola M / M / 1, por lo que podemos usar las leyes de Little. Hay una distribución estacionaria si λ / μ <1, si tomamos un servidor que procesa 100 / segundo, entonces tenemos λ / μ = 1 ¡la cadena no es ergódica (acumulación infinita de solicitudes)!
Si queremos un tiempo de respuesta de 1/100 de segundo, entonces tenemos que resolver la ecuación 1/100 = E (T) = 1 / (μ - λ) entonces μ = 200 solicitudes / segundo.
Las solicitudes se redirigen si ya hay 8 solicitudes en el sistema. Entonces hay redirección cuando el sistema llega a 9 solicitudes en el sistema. Basta con calcular π9 para conocer la probabilidad de que la solicitud sea redireccionada. Según la ley de Little π9 = (1 - ρ) ρ9 =1/1024.
Dado que el sistema recibe 100 solicitudes por segundo, el servidor auxiliar recibe 100/1024 solicitudes por segundo.
Ejercicio 7
En una planta de producción de automóviles se estudió el problema de determinar el número óptimo de empleados para colocar en los mostradores de una tienda encargada de suministrar las herramientas necesarias a los trabajadores. El estudio de la tienda comenzó por determinar las características estadísticas de las llegadas de los trabajadores (1,6 llegadas / minuto) y el tiempo empleado por los empleados para proporcionar las herramientas necesarias (0,9 servicio / minuto).
Calcule el tiempo medio de espera en la cola (Wq) para S = 2, S = 3, S = 4. Calcule el número medio de clientes en un día de 8 horas y el tiempo medio de servicio correspondiente. Según el número de empleados (S), calcule el número de horas de inactividad por día de 8 horas.
¿Calcular el tiempo perdido cada día por los trabajadores, debido a la espera? Si el costo por hora de un empleado es 40.00 $ y el de un trabajador es 80.00 $, ¿cuál es el costo total de horas perdidas?
Concluya dando el número óptimo de empleados que se esperan para la tienda.
Conociendo lym, hemos calculado l / m = 1.6 / 0.9 = 1.77> 1.
Como l / m> 1, solo nos interesaban los valores de S = 2, S = 3 y S = 4.
Para calcular el tiempo de espera promedio en la cola, primero buscamos P0, para cada valor respectivo de S.
S = 2, P0 = 0.061 S = 3, P0 = 0,152 S = 4, P0 = 0.166
Que dan
S = 2, Wq = 4.00
S = 3, Wq = 0.31
S = 4, Wq = 0.06
Ahora calculemos el número promedio de clientes en un día de 8 horas.
ancho x 60 x 8 = 1,6 x 60 x 8 = 768
y, para este número de llegadas, será necesario (con un tiempo de servicio de 1 / m)
768 / m = 768 / 0.9 = 853 minutos de servicio por día.
= 14,21 horas
Ejercicio 8
Un laboratorio contiene 2 microcomputadoras idénticas. Los usuarios llegan según un proceso de Poisson con parámetro l = 3 usuarios por hora. La duración de uso de un microordenador es un va exponencial de 0,6 horas de media (m = 1 / 0,6).
- Tasa de utilización de laboratorio
- Número de usuarios en la cola
- Tiempo de espera en la cola.
El jefe descubre que la gente pierde demasiado tiempo esperando y decide agregar microcomputadoras. Quiere que el tiempo medio de espera sea inferior a 20 minutos. ¿Cuántos debería agregar? ¿Cuál es la nueva tasa de utilización del laboratorio?
¿Qué pasaría con respecto al tiempo de espera de los usuarios si los separamos en 3 grupos, asignando un microordenador a cada grupo?
¿Qué concluyes?
Tenemos una cola M / M / 2.
r = l / 2m = 0,9
P0 = 1/19 P1 = l / m P0 = 1.8 / 19
Q = [r / 1-r] (1 - P0 - P1) = 7.674
Wq = 2,56 h
El sistema solo se usa en 90%, pero cada usuario tiene que esperar en promedio más de 2 horas y 30 minutos.
El jefe descubre que la gente pierde demasiado tiempo esperando y decide agregar microcomputadoras. Quiere que el tiempo medio de espera sea inferior a 20 minutos. ¿Cuántos debería agregar?
Podemos probar con varios valores de S = s, y calcular Wq para cada caso:
s = 3
Q = 0,532
Wq = 0,177 h. »10,6 min
Con 3 microcomputadoras, la restricción se satisface, pero la tasa de utilización del sistema ahora es r = 0,6.
¿Qué pasaría si separamos a los usuarios en 3 grupos, asignando un microordenador a cada grupo?
Ahora tenemos 3 colas M / M / 1, cada una con una tasa de llegada l = 3/3 = 1, una tasa de servicio m = 1 / 0,6 y un factor de utilización r = 0,6.
Obtenemos :
Wq = r² / [l (1-r)] = 0.9 hora
= 54 min.
Por tanto, es preferible compartir los recursos.
De este modo,
S = 2 empleados tendrían 2 x 8 - 14.21 = 1.79 horas de inactividad por día
S = 3 empleados tendrían 3 x 8 - 14,21 = 9,79 horas de inactividad por día
S = 4 empleados tendrían 4 x 8 - 14.21 = 17.79 horas de inactividad por día
Fijémonos ahora en el tiempo perdido todos los días por los trabajadores, debido a la espera:
S = 2768 x 4 = 3072 min. = 51,2 horas
S = 3768 x 0,31 = 238 min. = 3.96 horas
S = 4768 x 0,06 = 46 min. = 0,76 horas
El costo total de las horas perdidas tiene el valor:
S = 2 $ 4 167,60 = 1,79 x 40 + 51,2 x 80
S = 3 $ 708.40 = 9.79 x 40 + 3.96 x 80 ¡el mejor!
S = 4 $ 772,40 = 17,79 x 40 + 0,76 X 80