Teoria de Colas (líneas de espera)

Teor´ıa de Colas

TC: Parte de la Investigaci ´on Operativa que estudia el comportamiento de sistemas

cuyos elementos incluyen l´ıneas de espera (colas).

IO 07/08 - Teor´ıa de Colas 1

Teor´ıa de Colas: ejemplos

• personas esperando por un servicio (bibliotecas, bancos, gasolineras, urgencias

en hospital, . . . ),

• m´aquinas esperando por una reparaci ´on, piezas de un producto esperando a

ser ensambladas,

• programas de ordenador esperando a ser ejecutados por un procesador,

• informaci´on de internet esperando en un nodo para ser transferida a su destino,

• aviones esperando a despegar o aterrizar,

IO 07/08 - Teor´ıa de Colas 2

Teor´ıa de Colas: historia

Se inici ´o con A. K. Erlang, en la compa˜n´ıa telef ´onica estatal de Dinamarca (principios

del siglo XX).

Se analizaron los tiempos de espera de llamadas a centralitas autom´ aticas (congesti

´on de tr ´afico).

• Objetivo: satisfacer la demanda incierta en el sistema telef ´onico con el menor

coste para la compa˜n´ıa.

IO 07/08 - Teor´ıa de Colas 3

Teor´ıa de Colas

Introducci ´on.

Elementos y relaciones en un sistema.

Modelo M/M/1.

Modelo M/M/s.

Modelo M/M/1/k.

Aplicaciones.

IO 07/08 - Teor´ıa de Colas 4

Introducci ´on

Las l´ıneas de espera generan malestar, ineficiencia, retraso y otros problemas,

lo que origina un coste de tiempo y econ´omico.

Es muy importante evaluar el balance entre el aumento del nivel de servicio y el

tama˜no de las colas de espera.

Por tanto, es necesario entender la relaci ´on entre el n´umero de servidores en un

sistema (o eficacia de los mismos) y la cantidad de tiempo gastado en la cola (o

cantidad de clientes en la misma).

En sistemas de colas sencillos dichas relaciones se pueden encontrar anal´ıticamente.

En sistemas m´as complejos se pueden analizar mediante simulaci ´on.

IO 07/08 - Teor´ıa de Colas 5

Introducci ´on

• Elementos m´as importantes en un sistema de colas: clientes y servicio.

Los clientes se caracterizan por los intervalos de tiempo que separan sus llegadas.

El servicio se caracteriza por el tipo y tiempo de servicio, adem´as de por el

n´umero de servidores. El tipo de servicio o disciplina representa el orden en el

que los clientes se seleccionan de la cola.

Las llegadas de clientes pueden ser deterministas o aleatorios (en este caso se

modelan mediante una distribuci ´on estad´ıstica).

Los tiempos de servicio tambi´en pueden ser deterministas o aleatorios (distribuci

´on estad´ıstica).

IO 07/08 - Teor´ıa de Colas 6

Introducci ´ on: tipos de sistemas

Las variaciones en un sistema de colas pueden ser m´ ultiples. S´ olo se pueden

resolver de forma anal´ıtica un conjunto reducido de sistemas.

IO 07/08 - Teor´ıa de Colas 7

Elementos de un sistema: Llegadas

Pueden existir una o varias fuentes.

Se suele asumir independencia entre llegadas.

Intervalos entre llegadas: deterministas o aleatorios.

Tasa de llegadas: _ _ n´umero medio de clientes que acceden al sistema por

unidad de tiempo.

Tiempo medio entre llegadas: 1

_.

IO 07/08 - Teor´ıa de Colas 8

Elementos de un sistema: Fuente de entrada

Puede ser infinita o finita (sistemas abiertos o cerrados, respectivamente).

Ejemplo de sistema abierto: un banco, ya que es pr ´acticamente imposible que

todos los posibles clientes coincidan en su llegada.

Ejemplo de sistema cerrado: un servidor de internet con un n´umero relativamente

peque˜no de usuarios autorizados (es posible que en un momento

determinado se conecten todos los usuarios al servidor).

Si la fuente es finita, entonces el n´umero de clientes en la cola afecta al n´umero

de clientes fuera del sistema.

La llegada puede ser en bloque o de forma unitaria. Frecuentemente el bloque

se trata como un solo cliente.

IO 07/08 - Teor´ıa de Colas 9

Introducci ´ on: Clientes

Pueden ser impacientes.

Por tanto, los clientes se pueden perder, bien porque no entran en el sistema,

bien porque abandonan tras un tiempo en el sistema.

Tambi´en, los clientes pueden percibir un ritmo m´as acelerado en una cola

distinta y por tanto decidir cambiarse.

IO 07/08 - Teor´ıa de Colas 10

Elementos de un sistema: Cola o canal de espera

Puede ser de uno o varios canales.

Puede existir interferencia entre canales.

Puede ser de capacidad limitada.

Disciplina de la cola: orden de selecci ´on en el servicio (FIFO, LIFO, aleatorio,

orden de prioridad, etc.).

IO 07/08 - Teor´ıa de Colas 11

Elementos de un sistema: Servicio

Pueden existir uno o varios servidores.

Se suele asumir independencia entre tiempos de servicio.

Duraci ´on de los servicios: deterministas o aleatorios.

Tasa de servicio: μ _ n´umero medio de clientes que son atendidos por unidad

de tiempo.

Tiempo medio de servicio: 1

μ.

IO 07/08 - Teor´ıa de Colas 12

An´ alisis de sistemas de colas

Una vez caracterizado el sistema, se pueden contestar a las siguientes preguntas:

¿Qu´e proporci´on de tiempo est ´an los servidores desocupados?.

¿Cu´ al es el tiempo medio de espera para un cliente?, ¿es ´este un tiempo

razonable?, ¿se pierden clientes por tiempos de espera largos?.

¿Es conveniente a˜ nadir m´as servidores para reducir el tiempo medio de espera?.

¿Cu´ al es el n´umero medio de clientes en cola?.

¿Cu´ al es la probabilidad de que la espera sea mayor que una determinada

longitud en un tiempo determinado?.

. . .

IO 07/08 - Teor´ıa de Colas 13

An´ alisis de sistemas de colas

• Notaci ´on de Kendall: las caracter´ısticas del sistema se especifican por los

s´ımbolos:

A/B/s/k/t/d/

donde A y B denotan las distribuciones de los tiempos entre llegadas y de servicio,

respectivamente.

s denota el n´umero de servidores en paralelo o canales, k denota la capacidad

del sistema, t denota el tama˜no de la fuente de entrada, y d es la disciplina de

la cola.

IO 07/08 - Teor´ıa de Colas 14

An´ alisis de sistemas de colas

• La distribuci ´on puede ser

M Exponencial

D Constante o determinista

Ek Erlang de par´ametro k

G Gen´ erica e independiente

• La disciplina puede ser

FCFS First come, first served

LCFS Last come, first served

SIRO Service in random order

GD General discipline

IO 07/08 - Teor´ıa de Colas 15

An´ alisis de sistemas de colas

Por ejemplo, un sistema que se describe como

M/M/1/1/1/FCFS

denota un sistema abierto que contiene un ´unico servidor con tiempos de llegada

y servicio exponenciales, capacidad infinita y disciplina primero que entra,

primero que se sirve.

S´ olo un n´umero peque˜no de sistemas se puede resolver anal´ıticamente.

Modelos sencillos: M/M/1/, M/M/s/, M/M/1/k.

IO 07/08 - Teor´ıa de Colas 16

Distribuciones

En los sistemas de colas normalmente se asume que tanto las llegadas de clientes

como los tiempos de servicio son aleatorios.

Es usual suponer que los tiempos entre llegadas y los de servicio se distribuyan

de forma exponencial. En este caso, la probabilidad instant ´anea de ocurrencia

de un suceso en las siguientes t unidades de tiempo es:

f(t) = _e−_t para t _ 0,

donde _ denota la tasa de llegadas.

Esta distribuci ´on es ´ util ya que tiene la propiedad de falta de memoria y estacionariedad

...