Teoría de Colas
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
Teoría de Colas
José María Ferrer Caja
Universidad Pontificia Comillas
Introducción
� Cola: Conjunto de clientes en espera de recibir un
servicio
� Se produce cuando los clientes llegan a un servidor
ocupado y permanecen en espera
� Teoría de Colas: Análisis del comportamiento de un
sistema de colas a lo largo del tiempo
Teoría de Colas- 1
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
sistema de colas a lo largo del tiempo
� Herramientas:
� Teoría de Probabilidades
� Optimización
� Simulación
Elementos
� Fuente: Origen de los clientes
� Cola
� Centro de servicio: Conjunto de servidores
� Sistema: Cola(s)+Servidor(es)
� Salida: Destino de los clientes
Teoría de Colas- 2
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Salida: Destino de los clientes
FUENTE COLA SERVIDORES SALIDA
SISTEMA
Características: Llegadas
� Fuente
� Finita → Sistema cerrado
� Infinita → Sistema abierto
� Número de fuentes
� Una
� Varias
� Forma de llegada
Teoría de Colas- 3
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Forma de llegada
� Unitaria
� En bloques
� Tiempo entre llegadas
� Determinista
� Aleatorio (llegadas independientes)
� Aleatorio (llegadas dependientes)
Características: Cola
� Número de canales
� Interferencia entre canales
� Posibilidad de cambiar de canal
� Imposibilidad de cambiar de canal
� Capacidad del sistema
� Finita
Teoría de Colas- 4
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Finita
� Infinita
� Disciplina
� FIFO: El primero que entra es el primero en ser atendido
� FIFO con límite: El tiempo de servicio es limitado
� LIFO: El último que entra es el primero en ser atendido
� SIRO: Los clientes se seleccionan de forma aleatoria
� PRI: Se atiende antes a los clientes prioritarios
Características: Mecanismo de servicio
� Número de servidores
� Relación entre servidores
� Servidores independientes
� Servidores dependientes
� Homogeneidad entre servidores
Teoría de Colas- 5
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Homogeneidad entre servidores
� Servidores homogéneos
� Servidores heterogéneos
� Tiempo de servicio
� Determinista
� Aleatorio (tiempos independientes)
� Aleatorio (tiempos dependientes)
Características: Comportamiento del cliente
� Comportamiento al encontrar el servidor ocupado
� Entra al sistema y permanece en la cola
� Reintenta la entrada tras un periodo de tiempo
� Renuncia al servicio
� Selección del canal
� Selección aleatoria
� Selección bajo algún criterio
Teoría de Colas- 6
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Selección bajo algún criterio
� Adjudicación automática de canal
� Comportamiento tras un periodo de tiempo en la
cola
� Se mantiene en el canal
� Cambia de canal
� Renuncia al servicio
Parámetros
� Tasa de llegadas → λ: Número medio de clientes que
llegan al sistema por unidad de tiempo
� Tiempo medio entre llegadas → 1/λ
� Tasa de entradas → λef: Número medio de clientes
que entran al sistema por unidad de tiempo
� Tasa de servicio → µ: Número medio de clientes que
son atendidos por un servidor por unidad de tiempo
Teoría de Colas- 7
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
son atendidos por un servidor por unidad de tiempo
� Tiempo medio de servicio → 1/µ
� Tasa de servicio del sistema → µef: Número medio de
clientes que son atendidos por unidad de tiempo
� Número de servidores → s
� Capacidad del sistema → k
� Factor de utilización, intensidad de tráfico → ρ= λef /µef
Estado estacionario: Condición
� N(t) : Número de clientes en el sistema en el instante t
� El sistema puede estabilizarse tras un periodo de
tiempo → Estado estacionario
� Distribución estacionaria: Distribución de probabilidad de N(t) en el estado estacionario N(t)→ N
Teoría de Colas- 8
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
de N(t) en el estado estacionario N(t)→ N
� Condición para que exista distribución estacionaria:
ρ<1
(Tasa de entrada<Tasa de servicio del sistema)
Estado estacionario: Variables
� N: Número de clientes en el sistema
� pn=P(N=n): Probabilidad de que haya n clientes en
el sistema
� Nq: Número de clientes en la cola
� T: Tiempo de un cliente en el sistema
Teoría de Colas- 9
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Tq: Tiempo de un cliente en la cola
Estado estacionario: Medidas de eficiencia
� L: Número medio de clientes en el sistema L=E[N]
� Lq: Número medio de clientes en la cola Lq=E[Nq]
� W: Tiempo medio de clientes en el sistema W=E[T]
� Wq: Tiempo medio de clientes en la cola Wq=E[Tq]
� c : Número medio de servidores ocupados
Teoría de Colas- 10
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� tc: Tiempo medio de servidores desocupados
Estado estacionario: Relaciones
� Fórmulas de Little
� Otras relaciones1
qefq
ef
WL
WL
λ=
λ=
Teoría de Colas- 11
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
µ
λ==
µ
λ+=
µ+=
ef
q
ef
q
q
LLc
LL
WW
-
1
Distribución exponencial
)(exp λ≈T
<
≥λ=
λ
00
0e)(
t-
t
ttf
λ
)(tf
t
� Función de densidad:
Teoría de Colas- 12
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Falta de memoria:
λ=1
]E[T2
1]V[
λ=T ttTt λ=>> -e)(P⇒0
( ) )(PP 00 tTtTttT >=>+>
� Media, varianza, probabilidad:
Distribución de Poisson
≈
λ=]E[N
,...}2,1,0{!
e)(P
-
∈λ
==λ
nn
nNn
� Función de probabilidad
� Media, varianza:
� N≡Número de éxitos/unidad de tiempo → N Poisson(λ)
λ=]V[N
Teoría de Colas- 13
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Reproductividad: La suma de variables independientes
de Poisson es otra variable de Poisson
� Proporcionalidad: El número medio de éxitos es
proporcional al tiempo
� Relación con la exponencial: El número de éxitos sigue
una distribución de Poisson ⇔ el tiempo entre dos
éxitos consecutivos sigue una distribución exponencial
Proceso poissoniano
� Proceso estocástico: Colección de variables aleatorias {N(t)}
� Proceso de conteo:
� N(t) {0, 1, 2,…}
� s t N(s) N(t)
� Proceso markoviano:
� Incrementos estacionarios:
∈
≤⇒≤
Teoría de Colas- 14
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Incrementos estacionarios:
N(t) - N(s) sólo depende de t-s
� Incrementos independientes
� N(0) = 0 c.s.
� N(t) - N(s) Poisson(λ(t-s)), N(t) Poisson(λt)
� En un intervalo cuya longitud tiende a 0, la
probabilidad de que ocurra más de un éxito tiende a 0
≈ ≈
� Nacimiento: Entrada de un cliente
� Muerte: Salida de un cliente una vez servido
� El tiempo entre llegadas es exponencial
� El tiempo entre salidas es exponencial, e
independiente del tiempo entre nacimientos
� N(t): Número de clientes en el sistema en el instante t
Proceso de nacimiento y muerte: Planteamiento
Teoría de Colas- 15
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� N(t): Número de clientes en el sistema en el instante t
� λn: Tasa de entradas si hay n clientes en el sistema
� µn: Tasa de salidas si hay n clientes en el sistema
� Objetivo → Obtener la distribución estacionaria N
pn=P(N=n): Probabilidad de que haya n clientes en el
sistema, en el estado estacionario, n = 0, 1, 2,…
Proceso de nacimiento y muerte: Diagrama de transiciones
� Los procesos que rigen el número de llegadas y el
número de salidas son poissonianos
� De cada estado n sólo es posible pasar a dos
estados:
� n+1 si se produce una llegada
� n-1 si se produce una salida
Teoría de Colas- 16
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
0 1 n-1 n n+12
λ0 λ1 λn-1 λnλ2
µ1 µ2 µn-1 µn µn+1
… …
� n-1 si se produce una salida
Proceso de nacimiento y muerte: Estado estacionarioSupuesto alcanzado el estado estacionario:
� Tasa media de llegada al estado n: λn-1 pn-1 + µn+1 pn+1� Tasa media de salida del estado n: λn pn + µn pn � Tasa media de llegada al estado n = Tasa media de
salida del estado n:
λn-1 pn-1 + µn+1 pn+1 = λn pn + µn pn
Teoría de Colas- 17
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
λn-1 pn-1 + µn+1 pn+1 = λn pn + µn pn � Para el estado n = 0: µ1 p1 = λ0 p0
� A partir de estas expresiones podemos obtener cada pnen función de p0:
� Para obtener p0 basta usar que
0
12
011-0
12
0120
1
01 pppppp
n
nn
µµµ
λλλ=⇒
µµ
λλ=⇒
µ
λ=
K
K
10
=∑∞
=n
np
Proceso de nacimiento y muerte: Medidas de eficiencia
� Número medio de clientes en el sistema
� Número medio de clientes en cola (para un sistema con
s servidores)
� Tasa media de llegadas
∑∞
=
=0n
nnpL
∑∞
=
=sn
nq psnL )-(
Teoría de Colas- 18
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Tasa media de llegadas
� Tiempo medio de permanencia en el sistema
� Tiempo medio de permanencia en cola
∑∞
=
λ=λ0n
nn p
λ= LW
λ= q
q
LW
� Especificaciones del modelo
A / B / c / m / d� A: Distribución tiempo entre llegadas. Puede ser
� M → Exponencial� D → Constante� Ek → Erlang de parámetro k
Modelos clásicos: Notación de Kendall
Teoría de Colas- 19
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
k� G → Genérica
� B: Distribución tiempo de servicio. Puede ser� M, D, Ek, G
� c: Número de servidores
� m: capacidad del sistema
� d: Disciplina de la cola
� Una única fuente de tamaño infinito� No hay impaciencia: Todo cliente que llega al sistema,
entra (a no ser que se haya alcanzado la capacidad máxima), y una vez dentro no lo abandona hasta haber sido servido.
� Un único canal para todos los servidores
Modelos clásicos: Hipótesis generales
Teoría de Colas- 20
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Un único canal para todos los servidores� Servidores independientes y homogéneos� Independencia entre llegadas y servicios� Por defecto, se supone capacidad infinita del sistema y
disciplina FIFO
� Hipótesis:� Tiempos entre llegadas independientes, distribuidos según una
exponencial de parámetro λ� Tiempos de servicio independientes, distribuidos según una
exponencial de parámetro µ� Un único servidor: s=1� Capacidad ilimitada
Disciplina FIFO
Modelos clásicos: M/M/1
Teoría de Colas- 21
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Disciplina FIFO� Factor de utilización: ⇒ ⇒
� Estado estacionario ⇔ ⇔ ⇔
� Distribución estacionaria:
0pp n
n ρ= 10
0 =ρ∑∞
=n
npµ
λ=ρ
ρ=ρ∑
∞
= -1
1
0n
n1<ρ ρ= -10p
,...3,2,1),-1( =ρρ= np n
n
� Medidas de eficiencia :λµ
λ=
ρ
ρ== ∑
∞
= --10n
nnpL
)-(-1)1-(
22
1 λµµ
λ=
ρ
ρ== ∑
∞
=n
nq pnL
)-1(
1
-
1
ρµ=
λµ=
λ=L
W
Modelos clásicos: M/M/1
Teoría de Colas- 22
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
)-1(- ρµλµλ
)-1(
1-
ρµ
ρ=
µ= WW q
� Distribución del tiempo en el sistema y en cola: ))-1((exp)-(exp ρµ≈λµ≈T
:qT
ρ=== -1)0( 0pTP q
ttft µρµρρ=⇒> )--(1e)-1()(0
Distribución mixta
� Hipótesis:� Tiempos entre llegadas independientes, distribuidos según una
exponencial de parámetro λ� s servidores independientes y homogéneos� Tiempos de servicio independientes para cada servidor,
distribuidos según una exponencial de parámetro µ� Capacidad ilimitada
Modelos clásicos: M/M/s
Teoría de Colas- 23
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Disciplina FIFO� Tasas: µ
λ=ρsλ=λ n
>µ
≤µ=µ
sns
snnn
� Diagrama de transiciones:
0 1 s-2 s-1 s2
λ λ λ λλ
µ 2µ (s-2)µ (s-1)µ sµ
…
Modelos clásicos: M/M/s
� Distribución estacionaria ⇔ 1<ρ
∑=
ρ+
ρ
ρ=
1-
0
0
!
)(
)-1(!
)(
1s
n
ns
n
s
s
sp
≥
µ
λ
≤≤
µ
λ
=
sn!
1
1!
1
0-
0
pss
snpn
pn
sn
n
n
� Medidas de eficiencia:
Teoría de Colas- 24
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Medidas de eficiencia:ρ+
ρ
ρρ= sps
sL
s
02)-1(!
)(
λ=L
W
02)-1(!
)(- p
s
ssLL
s
qρ
ρρ=ρ=
λ=
q
q
LW
Modelos clásicos: M/M/s
� Probabilidades
� Probabilidad de no hacer cola
0
1
0 )-1(!
)(1)0( ps
spTP
ss
n
nqρ
ρ−=== ∑
−
=
� Probabilidad de permanecer en cola un tiempo mayor que t
Teoría de Colas- 25
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Probabilidad de permanecer en cola un tiempo mayor que t
tss
q ps
stTP )1(
0 e)1(!
)()( ρ−µ−
ρ−
ρ=>
� Hipótesis:� Caso particular del modelo M/M/s para un número ilimitado de
servidores� No hay cola, cada cliente que llega es servido directamente
≈� Distribución estacionaria (existe siempre):
N Poisson(λ/µ)� Medidas de eficiencia:
Modelos clásicos: M/M/∞∞∞∞
Teoría de Colas- 26
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Medidas de eficiencia:
0
1
0
=
µ=
=
µ
λ=
q
q
W
W
L
L
� Hipótesis:� Tiempos entre llegadas independientes, distribuidos según una
exponencial de parámetro λ� s servidores independientes y homogéneos� Tiempos de servicio independientes para cada servidor,
distribuidos según una exponencial de parámetro µ� Capacidad limitada a k clientes, k≥ s
Modelos clásicos: M/M/s/k
Teoría de Colas- 27
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Disciplina FIFO� Distribución estacionaria (existe siempre). Para 1≠
µ
λ=ρs
…
≤≤
µ
λ
≤≤
µ
λ
=
knspss
snpn
pn
sn
n
n
0-
0
!
1
1!
1
1 que talcon 0
0 =∑=
k
n
n pp
� Tasa de entradas:
[ ]sksks
q sks
spL -1-
20 )-1)(1-(--1)-1(!
)(ρρ+ρ
ρ
ρρ= +
Modelos clásicos: M/M/s/k
)-1( kef pλ=λ
� Medidas de eficiencia :
Teoría de Colas- 28
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
[ ]q sks
pL20 )-1)(1-(--1)-1(!
ρρ+ρρ
=
ef
q
q
LW
λ=
µ+=1
qWW
efWL λ=
� Hipótesis:� Caso particular del modelo M/M/s/k cuando la capacidad del
sistema coincide con el número de servidores � No hay cola, cuando un cliente llega o es servido directamente
o no puede entrar en el sistema� Probabilidad de que el sistema esté saturado
Modelos clásicos: M/M/s/s
Teoría de Colas- 29
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
∑=
ρ
ρ=
s
n
n
s
s
ns
ssp
0
!)(
!)(
� Hipótesis:� Tiempos entre llegadas independientes, distribuidos según una
exponencial de parámetro λ� Tiempos de servicio independientes, distribuidos según una
distribución general F de media y varianza
� Un único servidor: s=1� Capacidad ilimitada
Disciplina FIFO
2σµ/1
Modelos clásicos: M/G/1
Teoría de Colas- 30
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Disciplina FIFO� Factor de utilización:
µ
λρ =
1ρ <� Estado estacionario ⇔� Fórmula de Pollaczek-Khintchine:
)-1(2
222
ρ
σλ+ρ+ρ=L
� Hipótesis:� Fuente finita de m clientes� Tiempos de retorno al sistema distribuidos según una
exponencial de parámetro λ� Tiempos de servicio independientes, distribuidos según una
exponencial de parámetro µ� Un único servidor: s=1
Capacidad ilimitada
Modelos clásicos: M/M/1 cerrado
Teoría de Colas- 31
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Capacidad ilimitada� Disciplina FIFO
� Tasas:� Tasa de retornos� Tasa de llegadas
λ
≥
<λ=λ
mn
mnnmn
0
)-(
� Distribución estacionaria (existe siempre)1
1
0)!-(
!1
−
=
ρ+= ∑
m
n
n
nm
mp
mnpnm
mp
n
n ≤<ρ
= 0)!-(
!0 siendo
µ
λρ =
Modelos clásicos: M/M/1 cerrado
Teoría de Colas- 32
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
λ=λ )-( Lmef
�Medidas de eficiencia
λ=
ρ=
)-(
-1- 0
Lm
LW
pmL
ρ
ρ+
µ=
λ=
ρ
ρ+=
1-
-1
1
)-(
)-1(1
-
0
0
p
m
Lm
LW
pmL
q
q
q
�Tasa media de llegadas
� Hipótesis:� Fuente finita de m clientes� Tiempos de retorno al sistema distribuidos según una
exponencial de parámetro λ� s servidores independientes y homogéneos� Tiempos de servicio independientes para cada servidor,
distribuidos según una exponencial de parámetro µCapacidad ilimitada
Modelos clásicos: M/M/s cerrado
Teoría de Colas- 33
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Capacidad ilimitada� Disciplina FIFO
� Tasas:
≥
<λ=λ
mn
mnnmn
0
)-(
>
≤≤µ
≤≤µ
=µ
mn
mnss
snn
n
0
0
� Distribución estacionaria (existe siempre)
Medidas de eficiencia: No existen fórmulas sencillas.
≤≤
µ
λ
≤≤
µ
λ
=
mnspss
n
n
m
snpn
m
pn
sn
n
n
0-
0
!
!
1
1 que talcon 0
0 =∑=
m
n
n pp
Modelos clásicos: M/M/s cerrado
Teoría de Colas- 34
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
λ=λ )-( Lmef
� Medidas de eficiencia: No existen fórmulas sencillas. Se obtiene L a partir de la definición, y el resto mediante las fórmulas de Little
�Tasa media de llegadas
� Objetivo: Determinar el nivel de servicio que minimiza el coste total del sistema
� Coste total = Coste servicio + Coste clientes� Coste servicio: costes por mantener operativo el
servicio: Aumenta con la tasa de servicio y con el número de servidores
� Coste clientes
Decisión en los sistemas de colas
Teoría de Colas- 35
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Coste clientes� Costes por permanecer en cola� Costes por pérdida de clientes� Costes por dar servicio
� Ambos costes están en conflicto
� Costes por unidad de tiempo� C1 = coste por unidad de µ� C1µ = coste por tener una tasa de servicio µ� C2 = coste por mantener un cliente en el sistema� C2 L(µ) = coste total esperado por mantener los clientes en el
sistema� Función de coste esperado por unidad de tiempo
Optimización de la tasa de servicio
Teoría de Colas- 36
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Función de coste esperado por unidad de tiempo)()( 21 µ+µ=µ LCCCT
� Problema a resolver:)(min 21 µ+µ
µLCC
Optimización de la tasa de servicio y la capacidad del sistema
� Costes por unidad de tiempo� C1 y C2 igual que en el caso anterior
� C3 = coste por unidad de capacidad
� C3k = coste por tener una capacidad k
� C4 = coste por cada cliente perdido
� C4λpk = coste total esperado por clientes perdidos
� Función de coste esperado por unidad de tiempo
Teoría de Colas- 37
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Función de coste esperado por unidad de tiempokpCkCLCCkCT λ++µ+µ=µ 4321 )(),(
� Problema a resolver:∈λ++µ+µ
µkpCkCLCC k
k4321
,)(min ℕ
� Costes por unidad de tiempo� C2 = coste por mantener un cliente en el sistema� C2 L(s) = coste total esperado por mantener los clientes en el
sistema� C5 = coste por servidor
� C5s = coste por tener s servidores
� Función de coste esperado por unidad de tiempo
Optimización del número de servidores
Teoría de Colas- 38
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACIÓNRGANIZACIÓNRGANIZACIÓNRGANIZACIÓN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL
� Función de coste esperado por unidad de tiempo)()( 25 sLCsCsCT +=
� Problema a resolver:∈+ ssLCsC
s)(min 25 ℕ