TEORÍA DE COLAS

CAPÍTULO 17- Investigación de Operaciones II

HILLIER
LAS COLAS…

Las colas son frecuentes en nuestra

vida cotidiana:
En un banco
En un restaurante de comidas rápidas
Al matricular en la universidad
Los autos en un lavauto
LAS COLAS…

En general, a nadie le gusta esperar

Cuando la paciencia llega a su límite,
la gente se va a otro lugar
Sin embargo, un servicio muy rápido
tendría un costo muy elevado
Es necesario encontrar un balance
adecuado
 TEORÍA DE COLAS
Una cola es una línea de espera
La teoría de colas es un conjunto de
modelos matemáticos que describen
sistemas de líneas de espera particulares
El objetivo es encontrar el estado estable
del sistema y determinar una capacidad de
servicio apropiada
TEORÍA DE COLAS
Existen muchos sistemas de colas distintos
Algunos modelos son muy especiales
Otros se ajustan a modelos más generales
Se estudiarán ahora algunos modelos
comunes
Otros se pueden tratar a través de la
simulación
SISTEMAS DE COLAS: MODELO BÁSICO

Un sistema de colas puede dividirse en

dos componentes principales:
La cola
La instalación del servicio
Los clientes o llegadas vienen en
forma individual para recibir el
servicio
SISTEMAS DE COLAS: MODELO BÁSICO

Los clientes o llegadas pueden ser:

Personas
Automóviles
Máquinas que requieren reparación
Documentos
Entre muchos otros tipos de artículos
SISTEMAS DE COLAS: MODELO BÁSICO

Si cuando el cliente llega no hay nadie

en la cola, pasa de una vez a recibir
el servicio
Si no, se une a la cola
Es importante señalar que la cola no
incluye a quien está recibiendo el
servicio
SISTEMAS DE COLAS: MODELO BÁSICO

Las llegadas van a la instalación del

servicio de acuerdo con la disciplina
de la cola
Generalmente ésta es primero en
llegar, primero en ser servido
Pero pueden haber otras reglas o
colas con prioridades
SISTEMAS DE COLAS: MODELO BÁSICO

Sistema de colas

Llegadas Disciplina Instalación Salidas

Cola de la cola del
servicio
 ESTRUCTURAS TÍPICAS DE SISTEMAS DE
COLAS: UNA LÍNEA, UN SERVIDOR
Sistema de colas

Llegadas Salidas
Cola Servidor
ESTRUCTURAS TÍPICAS DE SISTEMAS DE COLAS: UNA
LÍNEA, MÚLTIPLES SERVIDORES

Sistema de colas
Salidas
Servidor

Llegadas Salidas
Cola Servidor

Salidas
Servidor
ESTRUCTURAS TÍPICAS DE COLAS: VARIAS LÍNEAS,
MÚLTIPLES SERVIDORES

Sistema de colas
Salidas
Cola Servidor

Llegadas Salidas
Cola Servidor

Salidas
Cola Servidor
ESTRUCTURAS TÍPICAS DE COLAS: UNA LÍNEA,
SERVIDORES SECUENCIALES
Sistema de colas
Llegadas
Cola

Servidor

Cola

Salidas
Servidor
COSTOS DE UN SISTEMA DE COLAS

1. Costo de espera: Es el costo para el

cliente al esperar
Representa el costo de oportunidad
del tiempo perdido
Un sistema con un bajo costo de
espera es una fuente importante de
competitividad
COSTOS DE UN SISTEMA DE COLAS

2. Costo de servicio: Es el costo de

operación del servicio brindado
Es más fácil de estimar
 El objetivo de un sistema de colas
es encontrar el sistema del costo
total mínimo
 SISTEMAS DE COLAS: LAS LLEGADAS
El tiempo que transcurre entre dos llegadas
sucesivas en el sistema de colas se llama
tiempo entre llegadas
El tiempo entre llegadas tiende a ser muy
variable
El número esperado de llegadas por
unidad de tiempo se llama tasa media de
llegadas ()
SISTEMAS DE COLAS: LAS LLEGADAS

El tiempo esperado entre llegadas es

1/
Por ejemplo, si la tasa media de
llegadas es  = 20 clientes por hora
Entonces el tiempo esperado entre
llegadas es 1/ = 1/20 = 0.05 horas
o 3 minutos
SISTEMAS DE COLAS: LAS LLEGADAS

Además es necesario estimar la

distribución de probabilidad de los
tiempos entre llegadas
Generalmente se supone una
distribución exponencial
Esto depende del comportamiento de
las llegadas
SISTEMAS DE COLAS: LAS LLEGADAS –
DISTRIBUCIÓN EXPONENCIAL
La forma algebraica de la distribución
exponencial es:
 t
P(tiempo de servicio  t )  1  e
Donde t representa una cantidad
expresada en unidades de tiempo (horas,
minutos, etc.)
SISTEMAS DE COLAS: LAS LLEGADAS –
DISTRIBUCIÓN EXPONENCIAL
P(t)

0 Media Tiempo
 SISTEMAS DE COLAS: LAS LLEGADAS –
DISTRIBUCIÓN EXPONENCIAL
La distribución exponencial supone una
mayor probabilidad para tiempos entre
llegadas pequeños
En general, se considera que las llegadas
son aleatorias
La última llegada no influye en la
probabilidad de llegada de la siguiente
SISTEMAS DE COLAS: LAS LLEGADAS - DISTRIBUCIÓN DE
POISSON
Es una distribución discreta empleada con
mucha frecuencia para describir el patrón
de las llegadas a un sistema de colas
Para tasas medias de llegadas pequeñas
es asimétrica y se hace más simétrica y se
aproxima a la binomial para tasas de
llegadas altas
 SISTEMAS DE COLAS: LAS LLEGADAS -
DISTRIBUCIÓN DE POISSON
Su forma algebraica es:
k 
e
P(k ) 
k!
Donde:
 P(k) : probabilidad de k llegadas por unidad de tiempo
  : tasa media de llegadas
 e = 2,7182818…
SISTEMAS DE COLAS: LAS LLEGADAS -
DISTRIBUCIÓN DE POISSON
P

0 Llegadas por unidad de tiempo

SISTEMAS DE COLAS: LA COLA

El número de clientes en la cola es el

número de clientes que esperan el
servicio
El número de clientes en el sistema es
el número de clientes que esperan en
la cola más el número de clientes que
actualmente reciben el servicio
SISTEMAS DE COLAS: LA COLA

La capacidad de la cola es el número

máximo de clientes que pueden estar
en la cola
Generalmente se supone que la cola
es infinita
Aunque también la cola puede ser
finita
 SISTEMAS DE COLAS: LA COLA
La disciplina de la cola se refiere al orden
en que se seleccionan los miembros de la
cola para comenzar el servicio
La más común es PEPS: primero en llegar,
primero en servicio
Puede darse: selección aleatoria,
prioridades, UEPS, entre otras.
SISTEMAS DE COLAS: EL SERVICIO

El servicio puede ser brindado por un

servidor o por servidores múltiples
El tiempo de servicio varía de cliente
a cliente
El tiempo esperado de servicio
depende de la tasa media de servicio
()
SISTEMAS DE COLAS: EL SERVICIO

El tiempo esperado de servicio

equivale a 1/
Por ejemplo, si la tasa media de
servicio es de 25 clientes por hora
Entonces el tiempo esperado de
servicio es 1/ = 1/25 = 0.04 horas,
o 2.4 minutos
 SISTEMAS DE COLAS: EL SERVICIO
Es necesario seleccionar una distribución de probabilidad
para los tiempos de servicio
Hay dos distribuciones que representarían puntos
extremos:
La distribución exponencial (=media)
Tiempos de servicio constantes (=0)
SISTEMAS DE COLAS: EL SERVICIO
Una distribución intermedia es la
distribución Erlang
Esta distribución posee un parámetro de
forma k que determina su desviación
estándar:

1
 media
k
SISTEMAS DE COLAS: EL SERVICIO

Si k = 1, entonces la distribución
Erlang es igual a la exponencial
Si k = ∞, entonces la distribución
Erlang es igual a la distribución
degenerada con tiempos constantes
La forma de la distribución Erlang
varía de acuerdo con k
SISTEMAS DE COLAS: EL SERVICIO
P(t)
k=∞

k=8

k=2
k=1

0 Media Tiempo
 SISTEMAS DE COLAS:
DISTRIBUCIÓN ERLANG
Distribución Desviación estándar
Constante 0
Erlang, k = 1 media
Erlang, k = 2 1 / 2 media
Erlang, k = 4 1/2 media
Erlang, k = 8 1 / 8 media
Erlang, k = 16 1/4 media
Erlang, cualquier k 1 / k media
 NOTACIÓN DE KENDALL PARA MODELOS DE
COLAS
A/B/X/Y/Z:
A = Distribución del tiempo entre llegadas
B = Distribución del tiempo de servicio
G = general (i.e., not specified); M = Markoviano
(exponential); D = determinístico
X = Número de servidores
Y = Capacidad límite de clientes en la cola (in queue + in
service); default is ∞
Z = Disciplina de la cola. Regularmente es FCFS (first come first
served) otros como, LCFS, aleatorio, prioridad
 ESTADO DEL SISTEMA DE COLAS
En principio el sistema está en un estado
inicial
Se supone que el sistema de colas llega a
una condición de estado estable (nivel
normal de operación)
Existen otras condiciones anormales (horas
pico, etc.)
Lo que interesa es el estado estable
DESEMPEÑO DEL SISTEMA DE COLAS

Para evaluar el desempeño se

busca conocer dos factores
principales:
1. El número de clientes que esperan
en la cola
2. El tiempo que los clientes esperan
en la cola y en el sistema
 MEDIDAS DEL DESEMPEÑO DEL SISTEMA DE
COLAS
1. Número esperado de clientes en la cola
Lq
2. Número esperado de clientes en el
sistema Ls
3. Tiempo esperado de espera en la cola
Wq
4. Tiempo esperado de espera en el
sistema Ws
MEDIDAS DEL DESEMPEÑO DEL SISTEMA DE COLAS:
FÓRMULAS GENERALES
1
Ws  Wq 

Ls  Ws
Lq  Wq

Ls  Lq 

MEDIDAS DEL DESEMPEÑO DEL SISTEMA DE
COLAS: EJEMPLO
Suponga una estación de gasolina a
la cual llegan en promedio 45 clientes
por hora
Se tiene capacidad para atender en
promedio a 60 clientes por hora
Se sabe que los clientes esperan en
promedio 3 minutos en la cola
 MEDIDAS DEL DESEMPEÑO DEL SISTEMA DE
COLAS: EJEMPLO
La tasa media de llegadas  es 45 clientes
por hora o 45/60 = 0.75 clientes por
minuto
La tasa media de servicio  es 60 clientes
por hora o 60/60 = 1 cliente por minuto
MEDIDAS DEL DESEMPEÑO DEL SISTEMA DE
COLAS: EJEMPLO
Wq  3 min
1 1
Ws  Wq   3   4 min
 1
Ls  Ws  0.75  4  3 clientes
Lq  Wq  0.75  3  2.25 clientes
 MEDIDAS DEL DESEMPEÑO DEL SISTEMA DE
COLAS: EJERCICIO
Suponga un restaurant de comidas rápidas
al cual llegan en promedio 100 clientes por
hora
Se tiene capacidad para atender en
promedio a 150 clientes por hora
Se sabe que los clientes esperan en
promedio 2 minutos en la cola
Calcule las medidas de desempeño del
sistema
 PROBABILIDADES COMO MEDIDAS DEL
DESEMPEÑO
Beneficios:
Permiten evaluar escenarios
Permite establecer metas
Notación:
Pn : probabilidad de tener n clientes en el
sistema
P(Ws ≤ t) : probabilidad de que un cliente no
espere en el sistema más de t horas
FACTOR DE UTILIZACIÓN DEL SISTEMA
Dada la tasa media de llegadas  y la
tasa media de servicio , se define el factor
de utilización del sistema .
Generalmente se requiere que  < 1
Su fórmula, con un servidor y con s
servidores, respectivamente, es:

 
 
 s
FACTOR DE UTILIZACIÓN DEL SISTEMA -
EJEMPLO
Con base en los datos del ejemplo
anterior,  = 0.75,  = 1
El factor de utilización del sistema si se
mantuviera un servidor es
 = / = 0.75/1 = 0.75 = 75%
Con dos servidores (s = 2):
 = /s = 0.75/(2*1) = 0.75/2 =
37,5%
 MODELOS DE UNA COLA Y UN SERVIDOR
M/M/1: Un servidor con llegadas de Poisson y tiempos de
servicio exponenciales
M/G/1: Un servidor con tiempos entre llegadas
exponenciales y una distribución general de tiempos de
servicio
M/D/1: Un servidor con tiempos entre llegadas
exponenciales y una distribución degenerada de tiempos de
servicio
M/Ek/1: Un servidor con tiempos entre llegadas
exponenciales y una distribución Erlang de tiempos de
servicio
MODELO M/M/1
 MODELO M/M/1: EJEMPLO
Un lavauto puede atender un auto cada 5 minutos y la tasa
media de llegadas es de 9 autos por hora
Obtenga las medidas de desempeño de acuerdo con el
modelo M/M/1
Además la probabilidad de tener 0 clientes en el sistema, la
probabilidad de tener una cola de más de 3 clientes y la
probabilidad de esperar más de 30 min. en la cola y en el
sistema
MODELO M/M/1: EJEMPLO
MODELO M/G/1
 
2 2 2
Ls  Lq   Lq 
2(1   )
1 Lq
Ws  Wq  Wq 
 
P0  1   Pw  
 1
 MODELO M/G/1: EJEMPLO
Un lavauto puede atender un auto cada 5
min. y la tasa media de llegadas es de 9
autos/hora,  = 2 min.
Obtenga las medidas de desempeño de
acuerdo con el modelo M/G/1
Además la probabilidad de tener 0 clientes
en el sistema y la probabilidad de que un
cliente tenga que esperar por el servicio
MODELO M/G/1: EJEMPLO

Ls  Lq    1.31  .75  2.06 clientes

2 2   2
Lq   1.31 clientes
2(1   )
1
Ws  Wq   0.228 hrs  13.7 min

Lq
Wq   0.145 hrs  8.7 min

P0  1    0.25 Pw    0.75
MODELO M/D/1
 2
Ls  Ws Lq 
2(1   )
1 Lq
Ws  Wq  Wq 
 
 1
 MODELO M/D/1: EJEMPLO
Un lavauto puede atender un auto cada 5
min.
La tasa media de llegadas es de 9
autos/hora.
Obtenga las medidas de desempeño de
acuerdo con el modelo M/D/1
MODELO M/D/1: EJEMPLO

Ls  Ws  1.875 clientes

2
Lq   1.125 clientes
2(1   )
1
Ws  Wq   0.21 hrs  12.5 min

Lq
Wq   0.125 hrs  7.5 min

MODELO M/E K/1
 (k  1)
2
Ls  Ws Lq 
2k (1   )
1 Lq
Ws  Wq  Wq 
 
 1
MODELO M/E K/1: EJEMPLO

Un lavauto puede atender un auto

cada 5 min.
La tasa media de llegadas es de 9
autos/hora. Suponga  = 3.5 min (aprox.)
Obtenga las medidas de desempeño
de acuerdo con el modelo M/Ek/1
MODELO M/E K/1: EJEMPLO

Ls  Ws  2.437 clientes

 (k  1)
2
Lq   1.6875 clientes
2k (1   )
1
Ws  Wq   0.2708 hrs  16.25 min

Lq
Wq   0.1875 hrs  11.25 min

MODELOS DE UN SERVIDOR: EJERCICIO: COMPLETE
EL CUADRO EJEMPLO LAVAUTO
Modelo Ls Ws Lq Wq

M/M/1

M/G/1

M/D/1

M/Ek/1
 MODELOS DE VARIOS SERVIDORES
M/M/s: s servidores con llegadas de Poisson y tiempos de servicio
exponenciales
M/D/s: s servidores con tiempos entre llegadas exponenciales y una
distribución degenerada de tiempos de servicio
M/Ek/s: s servidores con tiempos entre llegadas exponenciales y una
distribución Erlang de tiempos de servicio
M/M/S, UNA LÍNEA DE ESPERA

1
P0 
 s  s  s 1  n
   
s!  s    n 0 n!
 s   Lq
Lq  P Ls  Lq  Wq 
( s  1)!( s   ) 2 0
 
1 n
Ws  Wq  Pn  P0 , si n  k
 n!
n 1 s  s 
Pn  P0 , si n  k Pw     P0
s! s ns
s!  s   
M/M/S, UNA LÍNEA DE ESPERA
Si s  2
 3
Lq 
4 2

Si s  3
 4
Lq 
(3   )(6  4    )2
ANÁLISIS ECONÓMICO DE LÍNEAS DE ESPERA
Costos

Costo total

Costo del servicio

Costo de espera
Tasa óptima Tasa de servicio
de servicio
 MODELO M/M/1: EJERCICIO
A un supermercado llegan en promedio 80 clientes por
hora que son atendidos entre sus 5 cajas.
Cada caja puede atender en promedio a un cliente
cada 3 minutos
Obtenga las medidas de desempeño de acuerdo con el
modelo M/M/1
Además la probabilidad de tener 2 clientes en el
sistema, la probabilidad de tener una cola de más de 4
clientes y la probabilidad de esperar más de 10 min. en
la cola
 MODELO M/G/1: EJERCICIO
A un supermercado llegan en promedio 80 clientes por hora
que son atendidos entre sus 5 cajas.
Cada caja puede atender en promedio a un cliente cada 3
minutos. Suponga  = 5 min
Obtenga las medidas de desempeño de acuerdo con el
modelo M/G/1
Además la probabilidad de tener 0 clientes en el sistema y
la probabilidad de que un cliente tenga que esperar por el
servicio
 MODELO M/D/1: EJERCICIO
A un supermercado llegan en promedio 80
clientes por hora que son atendidos entre sus
5 cajas.
Cada caja puede atender en promedio a un
cliente cada 3 minutos.
Obtenga las medidas de desempeño de
acuerdo con el modelo M/D/1
 MODELO M/E K/1: EJERCICIO
A un supermercado llegan en promedio 80
clientes por hora que son atendidos entre sus
5 cajas.
Cada caja puede atender en promedio a un
cliente cada 3 minutos. Suponga k= 4
Obtenga las medidas de desempeño de
acuerdo con el modelo M/E /1
k