Colas

Informática. Líneas de espera: modelos matemáticos. Costos. Estructuras. Servidor. Sistemas. Empleo

  • Enviado por: Guerra
  • Idioma: castellano
  • País: México México
  • 16 páginas
publicidad
cursos destacados
Laravel: Framework PHP rápido, potente y divertido
Laravel: Framework PHP rápido, potente y divertido
La tecnología avanza cada vez más rápido y cada vez contamos con menos tiempo para hacer las...
Ver más información

Aprende Game Salad en 30 minutos
Aprende Game Salad en 30 minutos
GameSalad, una aplicación para Mac y Windows que nos permite crear juegos sin necesidad de saber programar es lo que...
Ver más información

publicidad

1. Introducción.

En este trabajo se aplica la teoría de colas. Una Cola es una línea de espera y la teoría de colas es una colección de modelos matemáticos que describen sistemas de líneas de espera particulares o de sistemas de colas. Los modelos sirven para encontrar el comportamiento de estado estable, como la longitud promedio de la línea y el tiempo de espera promedio para un sistema dado.

El problema es determinar que capacidad o tasa de servicio proporciona el balance correcto. Esto no es sencillo, ya que el cliente no llega a un horario fijo, es decir, no se sabe con exactitud en que momento llegarán los clientes. También el tiempo de servicio no tiene un horario fijo.

2. Definiciones, características y Terminología.

Definición.

Una Cola es una línea de espera y la teoría de colas es una colección de modelos matemáticos que describen sistemas de líneas de espera particulares o sistemas de colas. Los modelos sirven para encontrar el comportamiento de estado estable , como la longitud promedio de la línea y el tiempo de espera promedio para un sistema dado. Esta información, junto con los costos pertinentes, se usa, entonces, para determinar la capacidad de servicio apropiada.

Costos de los sistemas de colas.

Un sistema de colas puede dividirse en sus dos componentes de mayor importancia, la cola y la instalación de servicio . Las llegadas son las unidades que entran en el sistema para recibir el servicio. Siempre se unen primero a la cola ; si no hay línea de espera se dice que la cola esta vacía . De la cola, las llegadas van a la instalación de servicio de acuerdo con la disciplina de la cola, es decir, de acuerdo con la regla para decidir cuál de las llegadas se sirve después. El primero en llegar primero en ser servido es una regla común, pero podría servir con prioridades o siguiendo alguna otra regla. Una vez que se completa el servicio, las llegadas se convierten en salidas.

Ambas componentes del sistema tienen costos asociados que deben de considerarse.

Costo de Espera.

Esperar significa desperdicio de algún recurso activo que bien se puede aprovechar en otra cosa y esta dado por :

Costo total de espera = CwL

Donde Cw = costo de espera por hora (en dólares) por llegada por unidad de tiempo y L= longitud promedio de la línea.

Costo de Servicio.

Este en la mayoría se trata de comprar varias instalaciones de servicio , en estos casos solo se ocupan los costos comparativos o diferenciales.

Sistema de costo mínimo.

Aquí hay que tomar en cuenta que para tasas bajas de servicio, se experimenta largas colas y costos de espera muy altos . Conforme aumenta el servicio disminuyen los costos de espera, pero aumenta el costo de servicio y el costo total disminuye , sin embargo , finalmente se llega a un punto de disminución en el rendimiento. Entonces el propósito es encontrar el balance adecuado para que el costo total sea el mínimo.

Estructuras típicas.

Las llegadas pueden ser personas, cartas, carros, incendios, ensambles intermedios en una fabrica, etc. En la siguiente tabla se muestran algunos ejemplos de varios sistemas de colas .

Ejemplos de sistemas de colas

Situación

Llegadas

Cola

Mecanismo de Servicio

Aeropuerto

Aviones

Aviones en carreteo

Pista

Aeropuerto

Pasajeros

Sala de espera

Avión

Depto de bomberos

Alarmas de incendio

Incendios

Depto. De Bomberos.

Compañía telefónica

Números marcados

Llamadas

Conmutador

Lavado de carros

Autos

Autos sucios

Mecanismo de lavado

La corte

Casos

Casos atrasados

Juez

Panadería

Clientes

Clientes con números

Vendedor

Carga de camiones

Camiones

Camiones en espera

Muelle de carga

Oficina de correos

Cartas

Buzón

Empleados por correos

Crucero

Autos

Autos en línea

Crucero

Fábrica

Subensamble

Inventario en proceso

Estación de trabajo.

Cartas de negocios

Notas de dictado

Cartas para mecanografiar

Secretaria

Reproducción

Pedidos

Trabajos

Copiadoras

Hospital

Pacientes

Personas enfermas

Hospital

Permitiendo que varíen el número de colas y el número de servidores, pueden hacerse los diagramas de los cuatro tipos de sistemas de la siguiente figura. Cada línea de espera individual y cada servidor individual se muestra por separado.

El primer sistema que se muestra en la figura, se llama un sistema de un servidor y una cola o puede describir un lavado de carros automático o un muelle de descarga de un solo lugar.

El segundo, una línea con múltiples servidores, es típico de una peluquería o una panadería en donde los clientes toman un número al entrar y se les sirve cuando llega el turno.

El tercer sistema, aquél en que cada servidor tiene una línea de separada, es característico de los bancos y las tiendas de autoservicio.

El cuarto sistema , es una línea con servidores en serie, puede describir una fábrica.

3. Modelo de un servidor y una cola.

Este modelo puede aplicarse a personas esperando en una cola para comprar boletos para el cine, a mecánicos que esperan obtener herramientas de un expendio o a trabajos de computadora que esperan tiempo de procesador.

Llegadas.

Consiste en la entrada al sistema que se supone es aleatoria. No tienen horario, es impredecible en que momento llegarán . El modelo también supone que las llegadas vienen de una población infinita y llegan una a la vez .

Cola.

En este modelo se considera que el tamaño de la cola es infinito. La disciplina de la cola es primero en llegar, primero en ser servido sin prioridades especiales. También se supone que las llegadas no pueden cambiar lugares en la línea (cola) o dejar la cola antes de ser servidas.

Instalación de Servicio.

Se supone que un solo servidor proporciona el servicio que varía aleatoriamente.

Salidas.

No se permite que las unidades que salgan entren inmediatamente al servicio.

Características de operación .

Un servidor y una cola.

Llegada Poisson.

Cola infinita, primero en llegar primero en ser servido.

Tiempos de servicio exponenciales.

Cola :

Longitud promedio de la línea :

Tiempo de espera promedio :

Sistema:

Longitud promedio de la línea :

Tiempo de espera promedio :

Utilización de la instalación :

Probabilidad de que la línea exceda a n :

Donde:

A = tasa promedio de llegada.

S = tasa promedio de servicio.

Ejemplo : (Un supermercado )

Supóngase un supermercado grande con muchas cajas de salida, en donde los clientes llegan para que les marquen su cuenta con una tasa de 90 por hora y que hay 10 cajas en operación. Si hay poco intercambio entre las líneas, puede tratarse este problema como 10 sistemas separados de una sola línea, cada uno con una llegada de 9 clientes por hora. Para una tasa de servicio de 12 por hora :

Dados:

A = 9 clientes por hora

S = 12 clientes por hora

Entonces :

= 2.25 Clientes

= 0.25 horas o 15 minutos.

= 3 clientes.

= 0.33 horas o 20 minutos.

= 0.75 o 75%

0.32

Entonces, para este ejemplo, el cliente promedio espera 15 minutos antes de ser servido. En promedio, hay un poco más de dos clientes en la línea o tres en el sistema. El proceso completo lleva un promedio de 20 minutos. La caja está ocupada el 75 % del tiempo. Y finalmente, el 32 % del tiempo habrá cuatro personas o más en el sistema ( o tres o más esperando en la cola).

4. Evaluación del sistema cuando se conoce el costo de espera.

Los costos de servicio influyen en el método para encontrar el sistema de menor costo. Si el costo de servicio es un función lineal de la tasa de servicio, puede encontrarse una solución general para la tasa óptima.

Para aplicar una solución general, se necesita una tasa de servicio que pueda variar de manera continua.

Cuando los costos de servicio cambian en forma escalonada, se usa la técnica de prueba y error para encontrar el sistema de menor costo. Se calcula el costo total para una tasa de servicio, después para la siguiente y así sucesivamente. Esto continúa hasta que se encuentra un límite inferior o un mínimo tal, que el aumentar o el disminuir las tasas de servicio da costos totales más altos.

Ejemplo:

Se esta estudiando un muelle de carga y descarga de camiones para aprender cómo debe formarse una brigada. El muelle tiene espacio sólo para un camión, así es un sistema de un servidor. Pero el tiempo de carga o descarga puede reducirse aumentando el tamaño de la brigada.

Supóngase que puede aplicarse el modelo de un servidor y una cola (llegadas Poisson, tiempos de servicio exponenciales) y que la tasa promedio de servicio es un camión por hora para un cargador. Los cargadores adicionales aumentan la tasa de servicio proporcionalmente.

Además, supóngase que los camiones llegan con una tasa de dos por hora en promedio y que el costo de espera es de $ 20 por hora por un camión. Si se le paga $ 5 por hora a cada miembro de la brigada, ¿Cuál es el mejor tamaño de esta?

Datos :

A = 2 camiones por hora.

S = 1 camión por persona.

Cw = costo de espera = $20 por hora por camión.

CS = costo de servicio = $ 5 por hora por persona.

Ahora sea k = número de personas en la brigada. Se busca k tal que la suma de los costos de espera y servicio se minimicen :

Costo total = Cw LS + k CS

Las pruebas deben de empezar con tres miembros de la brigada, ya que uno o dos no podrían compensar la tasa de llegadas de dos camiones por hora. Para una brigada de tres, la tasa de servicio es de tres camiones por hora y puede encontrarse Ls con la siguiente ecuación :

De la misma manera, para una brigada de cuatro :

El costo es menor, por tanto se sigue adelante.

Para una brigada de cinco :

Este todavía es menor :

Como este costo es mayor que el de la brigada de cinco, se rebasó el límite inferior de la curva de costo; el tamaño óptimo de la brigada es cinco personas.

5. Evaluación del sistema con costos de espera desconocidos .

En lugar de estimar el costo de espera, el administrador puede especificar un promedio mínimo de tiempo de espera o de longitud de línea . Esto establece un límite superior para Wq , el tiempo de espera en la cola (o para Lq, la longitud de línea en la cola).

Con este límite superior puede encontrarse la tasa de servicio necesaria para cualquiera tasa de llegadas dadas.

Ejemplo :

Considérese un restaurante de comida rápida con un menú limitado. El restaurante se está diseñando para que todos los clientes se unan a una sola línea para ser servidos. Una persona tomará la orden y la servirá. Con sus limitaciones, la tasa de servicio puede aumentarse agregando más personal para preparar la comida y servir las ordenes.

Esto constituye un sistema de un servidor y una cola. Si las llegadas y salidas son aleatorias, puede aplicarse el modelo de una cola. Supóngase que la administración quiere que el cliente promedio no espere más de dos minutos antes de que se tome su orden . Esto se expresa como :

Wq = 2 minutos

Supóngase también que la tasa máxima de llegadas es de 30 órdenes por hora.

ordenando términos,

Como la tasa de servicio debe ser mayor que la tasa de llegadas, puede descartarse la solución negativa. Entonces :

Para este ejemplo, se supuso :

A = 30 ordenes por hora.

Wq = 2 minutos o 0.033 horas

Entonces :

= 15 + 33.5 = 48.5 órdenes por hora.

Para cumplir los requerimientos, se necesita una tasa de casi 50 órdenes por hora. Si, por ejemplo, una brigada de cinco pueden manejar 45 órdenes por hora y una de seis puede procesar 50 por hora, entonces sería necesario tener la brigada de seis.

6. Modelo de un servidor con tiempos de servicio constantes.

Este modelo es igual que el anterior, excepto que se supone que el tiempo de servicio es exactamente el mismo en cada llegada en lugar de ser aleatorio. Todavía se tiene una sola línea, tamaño de la cola infinito, disciplina de la cola como primero en llegar primero en ser servido y llegadas Poisson.

Las aplicaciones típicas de este modelo pueden incluir un autolavado automático, una estación de trabajo en una pequeña fábrica o una estación de diagnóstico de mantenimiento preventivo. En general, el servicio lo proporciona una máquina.

Las características de operación están dadas por 4 :

En donde:

A = tasa promedio de llegadas (llegadas por unidad de tiempo)

S = tasa constante de servicio (llegadas por unidad de tiempo).

Ejemplo:

Supóngase un lavado automático de autos con una línea de remolque, de manera que los autos se mueven a través de la instalación de lavado como en una línea de ensamble.

Una instalación de este tipo tiene dos tiempos de servicio diferentes : el tiempo entre autos y el tiempo para completar un auto. Desde el punto de vista de teoría de colas, el tiempo entre autos establece el tiempo de servicio del sistema. Un auto cada cinco minutos da una tasa de 12 autos por hora. Sin embargo, el tiempo para procesar un auto es el tiempo que se debe esperar para entregar un auto limpio. La teoría de colas no considera este tiempo.

Supóngase que el lavado de autos puede aceptar un auto cada cinco minutos y que la tasa promedio de llegadas es de nueve autos por hora ( con distribución Poisson). Sustituyendo :

7. Modelo con servidores múltiples.

Supóngase que las llegadas son Poisson, los tiempos de servicio son exponenciales, hay una sola línea, varios servidores y una cola infinita que opera con la disciplina de primero en llegar primero en ser servido. Las ecuaciones para las características de operación se vuelven un poco más complicadas.

Sea :

N = número de servidores.

A = tasa promedio de llegadas (llegadas por unidad de tiempo).

S = tasa promedio de servicio por cada servidor (llegadas por unidad de tiempo).

Entonces:

La cantidad P0, es la probabilidad de que no haya llegadas en una unidad de tiempo, lo cual no lo hace más fácil de calcular.

Para dos o tres servidores pueden combinarse y simplificar las dos ecuaciones para obtener, para N = 2

Nótese que para N = 1 este modelo se reduce al modelo de un servidor.

Ejemplo:

|Considérese la biblioteca de una universidad cuyo personal está tratando de decidir cuántas copiadoras debe de instalar para uso de los estudiantes. Se ha escogido un equipo particular que puede hacer hasta 10 copias por minuto.

No se sabe cuál es el costo de espera para un estudiante, pero se piensa que no deben tener que esperar más de dos minutos en promedio. Si el número promedio de copias que se hacen por usuario es cinco, ¿cuántas copiadoras se deben instalar?.

Se usa prueba y error para resolver este tipo de problemas, no se encuentra una solución general como se hizo para el modelo de un servidor. Se tratará primero con dos copiadoras, después con tres, y así hasta que se satisfaga el criterio del tiempo de espera.

¿Cuál es la tasa de servicio? Si el número promedio de copias es cinco y la copiadora puede hacer hasta 10 copias por minuto, entonces pueden servirse en promedio hasta dos estudiantes por minuto. Pero, en esto no se toma en cuenta el tiempo para insertar la moneda, cambiar originales, para que un estudiante desocupe y otro comience a copiar.

Supóngase que se permite un 70 % del tiempo para estas actividades. Entonces la tasa de servicio neta baja a 0.6 estudiantes por minuto. Además se supone que los periodos pico de copiado tienen una tasa de llegada de 60 estudiantes por hora, o 1 por minuto.

Se comenzará con dos copiadoras, ya que una no sería suficiente.

A = 1 por minuto.

S = 0.6 por minuto.

N = 2

Esto excede el criterio del máximo de 2 minutos de espera para el estudiante promedio. Se tratarán tres copiadoras.

Se necesitan tres copiadoras. La utilización de cada una será :