Teoria De Colas

Teoría de colas
Andrés Ramos Universidad Pontificia Comillas http://www.iit.upcomillas.es/aramos/ Andres.Ramos@upcomillas.es
TEORÍA DE COLAS 1

Sistemas de colas
• Una cola se produce cuando la demanda de un servicio por parte de los clientes excede la capacidad del servicio. • Se necesita conocer (predecir) el ritmo de entrada de los clientes y el tiempo de servicio con cada cliente.Objetivo: Equilibrar los costes de capacidad del servicio y el “coste” de una espera larga.

TEORÍA DE COLAS Estudio matemático de las características de los sistemas de colas.

TEORÍA DE COLAS

2

Proceso en una cola
1. Entrada de clientes

 cola o línea de espera 2. Sistema de colas   mecanismo de servicio
3. Salida de clientes SISTEMA DE COLAS FUENTE ENTRADA CLIENTES

COLAMECANISMO SERVICIO

SALIDA CLIENTES

TEORÍA DE COLAS

3

Ejemplos
Clientes Clientes tienda Clientes banco Clientes supermercado Automóvil Automóvil Avión Llamadas telefónicas Enfermos Cajas Juicios pendientes Servicio Venta artículo Operación financiera Cobro compra Llenar depósito Reparación avería Aterrizaje / despegue Conversación Atención médica Transporte Juicio Servidores DependienteVentanilla Caja Surtidor Operarios taller Pista Centralitas Médico Robot de almacenamiento Jueces

TEORÍA DE COLAS

4

Entrada de clientes
TAMAÑO Número total de clientes potenciales (población de entrada): • Finito (fuente limitada) (sistema cerrado) • Infinito (fuente ilimitada) (sistema abierto) Suposición habitual: tamaño infinito (es decir, el número de clientes en la cola NO afecta elnúmero potencial de clientes fuera de ella) ENTRADA O FUENTE • Unitaria • Por bloques TIEMPO ENTRE LLEGADAS • Determinista • Probabilista (distribución de probabilidad exponencial) TASA MEDIA DE LLEGADA λ Número medio de entrada de clientes por unidad de tiempo Llegadas de clientes son independientes e idénticamente distribuidas (IID)

TEORÍA DE COLAS

5

Cola
Número máximo de clientesadmisible • Finito • Infinito Suposición habitual: colas de longitud infinita (pérdida del cliente o reintento) Número de canales (carriles de una calle ante un semáforo) en la cola e interferencia entre ellos

Disciplina de la cola
Orden de selección de sus miembros para ser atendidos • FIFO, FIFO con límite • LIFO • SIRO (Aleatorio) • Por prioridad (interruptora o no)

TEORÍA DE COLAS

6Mecanismo de servicio
SERVIDORES Proporcionan el servicio al cliente Número de servidores: • Uno • Varios Independencia o no entre servidores TIEMPO DE SERVICIO • Determinista • Probabilista (distribución de probabilidad exponencial) TASA MEDIA DE SERVICIO µ Número medio de clientes que son atendidos en un servidor por unidad de tiempo. Servicios a clientes son independientes e idénticamentedistribuidas (IID)

TEORÍA DE COLAS

7

Especificación de un sistema de colas
Distribución del tiempo entre llegadas / Distribución del tiempo de servicio / Número de servidores / Número máximo de clientes en el sistema / Disciplina de la cola M D E G exponencial degenerada (tiempos constantes) Erlang (Gamma) general

Ejemplos: M/M/s M/M/s/K/FIFO M/M/s/s M/G/1

tiempo entre llegadasexponencial / tiempo de servicio exponencial / s servidores

TEORÍA DE COLAS

8

Medidas de eficacia de un sistema de colas
λ µ tasa de llegada 1/λ tiempo medio entre llegadas consecutivas tasa de servicio 1/µ tiempo medio de servicio factor de utilización (intensidad de tráfico): fracción esperada de tiempo que están

ρ

ocupados los s servidores N L Nq Lq T W Tq Wq c

ρ=

λ sµhabitualmente ρ < 1

estado del sistema, número de clientes en el sistema (cola + servicio) número medio de clientes en el sistema L = E[N] longitud de la cola, número de clientes en la cola número medio de clientes en la cola Lq = E[Nq] tiempo de estancia de los clientes en el sistema tiempo medio de estancia de los clientes en el sistema W = E[T] tiempo de espera de los clientes en la cola...