mssi 03 teoria colas
TRANSCRIPT
TEMA 3
LOS FENOMENOS DE CONGESTIÓN
Prof. Antonio Olmedo Narbona
Dpto. Economía y Administración de Empresas
1
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Contenidos
• TEORÍA DE COLAS
– Introducción
– Estructura básica de una cola
– Sistemas de colas
– Notación Kendall
– Modelos de colas
– Análisis económico de las colas
• MODELO GENERALIZADO
– Modelo generalizado
– Ecuación de Little, medidas del rendimiento
• TAXONOMIA
– Modelo básico
– Modelos de colas con un servidor (M/M/1, M/G/1,M/D/1)
– Modelos de colas con s servidores (M/M/S,MG/S)
2
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Las colas…
Todos hemos experimentado en alguna ocasión la sensación de
estar perdiendo el tiempo al esperar en una cola. El fenómeno de
las colas nos parece natural: esperamos en el coche al estar en un
tapón, o un semáforo mal regulado, o en un peaje; esperamos en el
teléfono a que nos atienda un operador y en la cola de un
supermercado para pagar....
La respuesta es casi siempre simple, en algún momento la
capacidad de servicio ha sido (o es) menor que la capacidad
demandada.
Generalmente esta limitación se puede eliminar invirtiendo en
elementos que aumenten la capacidad. En estos casos la pregunta
es: ¿Compensa invertir?
La teoría de colas intenta responder a estas preguntas utilizando
análisis matemáticos detallados
3
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Las colas…
• Las colas de espera están presentes en todas partes:
– En un banco
– Cajas en un supermercado
– Gasolineras
– Nº de grúas de descarga en un puerto.
– Aeropuertos
– Semáforos.
– Sistema de mantenimiento.
– Sistemas de transmisión de datos
4
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Las colas…
En general, a nadie le gusta esperar
No siempre quienes esperan servicios son únicamente
personas, sino actividades productivas, máquinas,
equipo, etc
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
5
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Teoría de colas
• La teoría de colas es un conjunto de modelos
matemáticos que describen sistemas de colas
particulares
• El estudio de colas determina las medidas del
funcionamiento de una situación de colas, incluyendo el
tiempo de espera y la longitud promedio, entre otras
• El objetivo es encontrar el estado estable del sistema y
determinar una capacidad de servicio apropiada
6
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES 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
7
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Estructura básica de los modelos de colas
Los clientes que requieren un servicio se generan a lo largo del tiempo en una fuente de entrada
Estos clientes entran al sistema y con ellos se forma una cola
En determinado momento, se selecciona un miembro de la cola para darle servicio, mediante alguna regla conocida como disciplina de cola
Se proporciona al cliente seleccionado el servicio mediante el mecanismo del mismo
El cliente servido sale del sistema
Fuente de entrada
Cola
Mecanismo de servicio
Servidor
Clientes
SIS
TE
MA
DE C
OLA
S
Clientes servidos
8
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Estructura básica de los modelos de colas
Llegadas
Sistema de colas
Cola Servicio Disciplina
de la cola
Salidas
9
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Estructura básica de los modelos de colas
• Los clientes, usuarios o llegadas pueden ser:
– Personas
– Automóviles
– Máquinas que requieren reparación
– Documentos
– Cualquier artículo entre muchos tipos de artículos
– ……..
10
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Estructura básica de los modelos de colas: fuente de
entrada
• Su principal característica es su tamaño, es decir, el número total de clientes que podría solicitar servicio. A estos se les llama población de entrada
• La población de entrada puede ser finita o infinita
• La llegada de clientes se representa por el tiempo entre llegadas y es de carácter probabilística
• Generalmente, la suposición de que la población es infinita facilita algunos cálculos
• Hay que tener en cuenta el patrón estadístico mediante el cual se generan los clientes en el tiempo, es decir el nº de llegadas en un periodo
11
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Estructura básica de los modelos de colas: llegadas
En situaciones de cola habituales, la llegada es estocástica, es decir
la llegada depende de una cierta variable aleatoria, en este caso es
necesario conocer la distribución probabilística entre dos llegadas de
cliente sucesivas. Además habría que tener en cuenta si los clientes
llegan independiente o simultáneamente. En este segundo caso (es
decir, si llegan lotes) habría que definir la distribución probabilística de
éstos.
También es posible que los clientes sean “impacientes”. Es decir, que
lleguen a la cola y si es demasiado larga se vayan, o que tras esperar
mucho rato en la cola decidan abandonar.
Por último es posible que el patrón de llegada varíe con el tiempo. Si
se mantiene constante le llamamos estacionario, si por ejemplo varía
con las horas del día es no-estacionario.
12
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Estructura básica de los modelos de colas: llegadas
• Al tiempo que transcurre entre dos llegadas consecutivas
se le denomina tiempo entre llegadas
• Los tiempos de llegada entre los clientes se distribuyen
de manera exponencial
• Se define como (distribución exponencial)
λ = Número de llegadas por unidad de tiempo (tasa)
• Esta suposición supone que los tiempos de llegada son
completamente aleatorios, lo que implica olvido.
• La distribución exponencial supone una mayor
probabilidad para tiempos entre llegadas pequeños
0,)( ttetf
13
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Estructura básica de los modelos de colas
Las llegadas
Media Tiempo 0
P(t)
Distribución exponencial Tiempo de llegadas entre clientes
14
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Estructura básica de los modelos de colas
Las llegadas
DISTRIBUCIÓN EXPONENCIAL
• Además es necesario estimar la distribución de probabilidad de los
tiempos entre llegadas
• La forma algebraica de la distribución exponencial es:
• Donde t representa una cantidad expresada en unidades de tiempo (horas, minutos, etc.) y
λ la tasa de llegadas (usuarios/tiempo)
t
tt
etserviciodetiempoP
edtP
1)(
|e t) servicio de tiempo( 0
t
0
t-
0,)( ttetf
15
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Estructura básica de los modelos de colas
Las llegadas
Distribución de Poisson
• Cuando el tiempo entre llegadas tiene una distribución exponencial,
el número de llegadas en un periodo tiene una 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
16
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Sistemas de colas: llegadas
Distribución de Poisson
• Su forma algebraica es (con media λt llegadas durante t) :
• Donde:
– P(t) : probabilidad de k llegadas por unidad de tiempo
– : tasa media de llegadas
– e = 2,7182818…
• El tiempo entre llegadas se define como la probabilidad de que no llegue
ningún cliente
!
)()(
n
ettP
tn
n
Llegadas por unidad de tiempo 0
P
Es una distribución discreta empleada con mucha frecuencia para describir el patrón de las llegadas a un sistema de colas
t
o etP )(
17
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Propiedades del patrón de llegadas o servicio
Poisson-Exponencial
El uso de este patrón de llegada (o de servicio) tiene, entre otras las
siguientes propiedades:
P1 El número de llegadas en intervalos de tiempo no superpuestos es
estadísticamente independiente
P2 La probabilidad de que una llegada ocurra entre el tiempo t y t+Δt
es λΔt+o(Δt), donde λ es la tasa de llegada y o(Δt) cumple
P3 La distribución estadística del número de llegadas en intervalos de
tiempo iguales es estadísticamente equivalente
18
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Propiedades del patrón de llegadas o servicio
Poisson-Exponencial
P4 Si el número de llegadas sigue una distribución de Poisson el
tiempo entre llegadas sigue una distribución exponencial de media
(1/λ) y al contrario
P5 Si el proceso de llegada es Poisson, los tiempos de llegada son
completamente aleatorios con una función de probabilidad
uniforme sobre el periodo analizado.
P6 Para conocer los datos que definen un proceso de Poisson solo es
necesario conocer el número medio de llegadas
P7 Amnesia de la Distribución exponencial: La probabilidad de que
falten t unidades para que llegue el siguiente cliente es
independiente de cuanto tiempo llevamos sin que llegue ningún
cliente. 19
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Estructura básica de los modelos 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 ()
• 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
22
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Estructura básica de los modelos de colas
Fuente de entrada (revisión)
• La suposición usual es que esto ocurre mediante un proceso Poisson, es
decir, el número de clientes que llega hasta un determinado momento tiene
una distribución Poisson
• Esta suposición corresponde con la situación en que las llegadas ocurren de
manera aleatoria, pero con una tasa media fija y sin importar cuántos clientes
ya están ahí (lo cual equivale a suponer que el tamaño de la fuente de
entrada es infinito)
• También debe especificarse cualquier supuesto inusual sobre el
comportamiento de los clientes, por ejemplo, si s pierden clientes cuando la
fila es muy larga
23
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Estructura básica de los modelos de colas
La cola
• Es el lugar donde los clientes esperan antes de recibir el servicio
• Puede ser de longitud finita o infinita, generalmente se supone esto último
• 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
• La cola no incluye a quien está recibiendo el servicio
• Tiempo de espera. Tiempo transcurrido desde que el cliente entra en el
sistema hasta que empieza recibir los servicios (Wq)
24
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Estructura básica de los modelos de colas
La cola
• El número de clientes en la cola es el número de clientes
que esperan el servicio (Lq)
• 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 (Ls= Lq+N)
• La capacidad de la cola es el número máximo de clientes
que pueden estar en la cola
25
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Estructura básica de los modelos de colas
Disciplina de cola
• Se refiere al método por el cual se seleccionan los miembros de la cola para darle servicio
– Primero en entrar, primero en salir (first in, first out; FIFO) (first come, first served; FCFS) (PEPS)
– Último en entrar, primero en salir (last in, first out; LIFO) (last come, first served; LCFS)
– Reparto equitativo entre todas las tareas (round robin; RR)
– Por jerarquía o prioridad
26
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Estructura básica de los modelos 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 (Ws) depende de la tasa media de 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)
27
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Estructura básica de los modelos de colas
El servicio
• Es necesario seleccionar una distribución de probabilidad
para los tiempos de servicio
• Hay otras distribuciones que representarían puntos
intermedios:
– La distribución exponencial (=media)
– Tiempos de servicio constantes (=0)
– 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:
mediak
1
28
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Estructura básica de los modelos 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
• Tasa media de servicio µ (p.ejemplo 25 clientes por hora)
• El tiempo esperado de servicio equivale a 1/
• Entonces el tiempo esperado de servicio es 1/ = 1/25 =
0.04 horas, o 2.4 minutos
29
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Media Tiempo 0
P(t) k = ∞
k = 1 k = 2
k = 8
Distribución Desviación
estándar
Constante 0
Erlang, k = 1 media
Erlang, k = 2
Erlang, k = 4 1/2 media
Erlang, k = 8
Erlang, k = 16 1/4 media
Erlang, cualquier k
Estructura básica de los modelos de colas
El servicio Distribución de Erlang
mediak
1
30
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Sistemas de colas: una línea, un servidor
Llegadas
Sistema de colas
Cola Servidor Salidas
31
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Sistemas de colas : una línea, múltiples servidores
Llegadas
Sistema de colas
Cola
Servidor Salidas
Servidor
Servidor
Salidas
Salidas
32
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Sistemas de colas : varias líneas, múltiples servidores
Llegadas
Sistema de colas
Cola Servidor Salidas
Servidor
Servidor
Salidas
Salidas
Cola
Cola
33
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Sistemas de colas : una línea, servidores secuenciales
Llegadas
Sistema de colas
Cola
Servidor
Salidas
Cola
Servidor
34
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Notación Kendall
• La notación utilizada para describir las características de un sistema de colas es la propuesta por David G. Kendall, a mediados del s. XX:
(A/B/c):(d/e/f) – A = Distribución de los tiempos de llegada
– B = Distribución de los tiempos de servicio
– c = Número de servidores
– d = Disciplina de la cola • LIFO = Última entrada, primera salida.
• FIFO = Primera entrada, primera salida.
• SIRO = Servicio aleatorio.
• URG = Orden en función de la urgencia de ser atendido.
• DG = Disciplina general.
• NPRP : Disciplina de no prioridad.
• PRP : Disciplina de prioridad.
CONTINUA..
35
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Notación Kendall
(A/B/c):(d/e/f) – e = Número máximo de clientes permitido en el sistema
– f = Tamaño de la fuente
• Los valores comunes para A y B son: – M = Distribución exponencial entre llegadas (de Poisson).
– D = Tiempo entre llegadas determinista o constante.
– Ek = Distribución de Erlang o gamma de la distribución de tiempo entre llegadas.
– G = Distribución de salidas general ( ó tiempo de servicio).
– GI = Distribución de llegadas general independiente(ó tiempo entre llegadas).
36
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Notación Kendall
Cuando se omiten (d/e/f)
• (A/B/c):(d/e/f)
– A = Distribución de los tiempos de llegada
– B = Distribución de los tiempos de servicio
– c = Número de servidores
– d = Disciplina de la cola FIFO o G
– e = Número máximo de clientes permitido en el sistema: Infinito (∞)
– f = Tamaño de la fuente: Infinito (∞)
• Ejemplo
– Un sistema M / M / 1 indica un sistema con tiempos de llegada Markovianos (exponenciales) que tiene un único servidor
– Es el modelo de cola más simple 37
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Notación Kendall
Ejemplos
• La cola de un multicine en el que existen varias ventanillas para
adquirir el ticket. (M , M, s)(FIFO , N , )
• Una clínica dental en la que solo hay un dentista y un número N limitado de sillas en la sala de espera. (M ,M , 1)(PRP , N , )
• La elección de productos en un supermercado ,donde se pueden elegir los productos sin esperar ninguna cola.(M , M, )(DG , , )
• Una compañía de alquiler de automóviles en el que se tienen 5 servidores y mucho tiempo de espera, ya que existe mucha demanda. Pero esta compañía no puede hacer frente a una inversión para poner más servidores y toma la decisión de confeccionar una lista con un número de clientes a los que pueden ofrecer su servicio en una jornada. (D , D, 5)(DG , N , )
38
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Estado del sistema de colas
• Estado del sistema, el número de clientes presentes en
el sistemas.
• 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 de operación)
• Existen otras condiciones anormales (horas pico, etc.)
• Lo que interesa es el estado estable
Llegada de clientes Transitorio Estable
Tie
mp
o d
e e
sp
era
39
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo generalizado de colas
0 1 2 n-1 n n+1
Las llegadas y salidas con base en Poisson -> los tiempos entre llegadas y
de servicio siguen una distribución exponencial.
El modelo generalizado supone que las tasas de llegadas y salida son
dependientes del estado -> dependen del nº de usuarios en las instalaciones
n = Número de usuarios en el sistema (cola+servicio)
n = Tasa de llegada de usuarios dado n en el sistema
n = Tasa de salida de usuarios dados n en el sistema
pn = Probabilidad de estado estable de n clientes en el sistemas
n-1 n 0 1
n+1 n 2 1
40
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo generalizado de colas
0 1 2 n-1 n n+1
En condiciones estables, para n>0, las tasas esperadas de flujo de entrada y salida de
un estado n deben ser iguales, n puede cambiar a n-1 o n+1
Tasa esperada de flujo de
entrada hacia el estado n = n-1 pn-1+ n+1 pn+1
Tasa esperada de flujo de
salida en el estado n = (n+ n )pn para n=0 -> 0 p0 = 1 p1 ; 0
1
01 pp
n-1 pn-1+ n+1 pn+1 = (n+ n )pn ; n=1,2,..
para n=1 ; 0 p0+ 2 p2 = (1+ 1 )pn ; sustituimos p1 y simplificamos 0
1
02
2
1 pp
,..2,1;1
1
210
1
0
1
0
...
...
np
i
ip
nn
nnpn
n
n
0n
1por determina se ppn0
n-1 n 0 1
n+1 n 2 1
41
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
0 1 2 n-1 n n+1
Calculamos ahora el valor de p0
1n
1
0n
1por determina se ppppn0n0
n-1 n 0 1
n+1 n 2 1
1
1
0
1
0
1
11
111
1
1n
; común factor Sacando
1n
p
p1p
0
01n
0
n
n
n
n
n
n
i
ip
i
ip
i
i
42
Modelo generalizado de colas
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
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 .
• Se requiere que < 1
• Su fórmula, con un servidor y con s servidores,
respectivamente, es:
s
43
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Análisis económico de un sistema de colas
La utilización de un servidor supone un coste.
Cuando el número de servidores es pequeño respecto al
número de clientes que se atienden, la ocupación de los
servidores es mayor y, por lo tanto, se obtiene una mayor
rentabilidad. Podríamos concluir entonces que cuantos menos
servidores mejor.
Si hay pocos servidores, los clientes tendrán que esperar más
tiempo. El coste de espera generalmente lo asume el cliente,
pero se asocia con calidad de servicio. Es frecuente que si la
espera excede en una cantidad de tiempo determinada muchos
clientes se pierdan. Así pues, hay que buscar un equilibrio entre
ocupación del servidor y tiempo de espera del cliente.
44
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Análisis económico de un sistema de colas
Coste
Tasa de servicio Tasa óptima de servicio
Coste de espera
Coste del servicio
Coste total
La calidad del servicio se refleja en el coste de espera del cliente. Cuanto menor
sea éste mejor será la calidad. El número de servidores es el coste del servicio.
Mientras que éste es un coste para el proveedor del servicio, el coste de espera
repercute en quien lo recibe. Lo que se pretende encontrar es el nivel de servicio que
minimice el coste total. En este coste total se incluye tanto el coste de espera como el
coste de servicio
45
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Análisis económico de un sistema de colas
1. Coste de espera: Es el coste 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
2. Coste de servicio: Es el coste 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
46
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
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 determinista de tiempos
de servicio
47
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
MODELO BÁSICO
M/M/1/FIFO/∞/∞
0y ; doconsideran ,..2,1;1
1
210ii0
1
0
1
0
...
...
np
i
ip
nn
nnpn
i
n
llamamos ; ..... ;2
2
; 00201
pn
n
ppppp n
10 para )1(1
111
1 dosustituyen 1
1
11.... ;por ndomultiplica ....1
1....)1(
0n
1
0
1
000
3232
32
0n
p
n
n
n
in
pp
ppp
p
i
i
S
SSSSS
pLa suma de las probabilidades de que el
sistema esté en cualquier estado posible es
1
48
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
MODELO BÁSICO
M/M/1/FIFO/∞/∞
sistema el en clientes de medio nº el es este
valor con para infinita serie una es
P
P
servicio)(cola sistema el en clientes de medio nº del
n
n
1)1()1(')1(
)1('
1)1('
1''
1..1
....;32'
)1()1(
)1()1(
2
2
432
4
32
1
111
0
32
SL
SSSS
ρρρρρS'S'
nS
nnnL
P
LCálculo
s
n
n
n
nn
nn
s
n
s
Ls Valor el número de clientes
presentes en cada estado posible por la
probalibidad de que el sistema esté en ese
estado
49
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
MODELO BÁSICO
M/M/1/FIFO/∞/∞
11
)1(
111Re
)1(
)1(
1
0
;
2
0
1
111
dosustituyen que
P dosustituyen P j
PP 1 es sistema del posibles estados los todos de adesprobabilid las de
PP j P 1)-(j 1)-(j habrá entonces clientes, jhay Si
esperando cliente unhay solo
servicio recibido ha no aún que sistema el en presentes que clientes de medio número el es
cola la en esperando clientes de medio nº del
oj1j
oj
jjj
q
q
sqs
j
jjj
q
q
q
LLcordemos
LLPSi
LLL
La
L
LSi
LCálculo
50
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
FORMULA DE LITTEL RELACION ENTRE LONGITUD ESPERADA DE LA COLA Y EL
TIEMPO MEDIO DE ESPERA
• Ejemplo 1. Por razones vinculadas con el control de calidad, se necesita saber la cantidad L de personas que en un instante determinado del día están transitando sobre cierta escalera mecánica. Para plantear la cuestión de la manera más sencilla posible, vamos a suponer en primer término que el flujo de personas que llega a su boca de entrada es constante durante un largo período de tiempo: por ejemplo, durante una hora. Además, aceptaremos que una vez en la escalera, los pasajeros no caminarán sobre la misma, tal como lo sugieren las normas de seguridad para este tipo de transporte. Así expuesto, el problema se resuelve con sencillez.
• En efecto, basta con determinar la cantidad de personas que llegan a la boca de la escalera por segundo, a la que denominamos “tasa de llegada” (λ), y considerar además la cantidad de segundos W que tarda un escalón desde la boca de entrada hasta la boca de salida. Las tres cantidades estarán ligadas de manera exacta mediante la ecuación siguiente: L = λW : (Lq = λW q y Ls = λW s)
• Si entran cuatro personas por segundo (λ= 4) y cada una permanece 40 segundos en la escalera (T = 40) entonces, en cualquier instante, habrá W = 160 personas en la escalera.
51
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
MODELO BÁSICO
M/M/1/FIFO/∞/∞
)1(
1 W
1 WW
)1(
1 WL
WL
1
1 que Re
espera de medio tiempoely cola de esperada Longitud entreRelación
WL Little de flujo deEcuación
ss
2
ss
ss
q
s
W
LW
L
Lcordemos
servicio elen empleado medio tiempoes 52
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
MODELO BÁSICO
M/M/1/FIFO/∞/∞
Factor de utilización del sistema o tráfico = /
Número esperado de clientes en el sistema SS WL ·1
Número esperado de clientes en la cola
Tiempo esperado de espera en el sistema
11
)1·(
1
WqWS
Tiempo esperado de espera en la cola )·()1·(
qW
Probabilidad de que no haya ningún elemento en el sistema
110P
Probabilidad de que haya n elementos en el sistema
nn
nn PP
1·)·1( 0
WqLq ·)(1
22
53
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Ejemplo 1
• Supongamos una gasolinera 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
• Calcular las medidas del rendimiento la cola
54
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Ejemplo 1
• Modelo M/M/1/DG/∞/∞
• 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
clientesWL
clientesWL
WW
W
ss
qs
q
25.2375.0 cola laen clientes de Nº
3475.0 sistema elen clientes de Nº
min41
13
1 sistema elen espera de Tiempo
min3 cola laen espera de Tiempo
55
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Ejemplo2
• Una sucursal bancaria tiene una persona atendiendo al público, un cajero. Llegan 15 clientes a la hora siguiendo una distribución de Poisson . El tiempo medio que tarda cada cliente en la ventanilla son 3 minutos siguiendo una distribución exponencial. Al director le interesa saber los siguiente:
• Nº medio de clientes esperando
• Nº medio de clientes presentes en la sucursal
• Tiempo de espera del cliente para ser atendido
• Tiempo que pasa el cliente en la sucursal
• Cuánto tiempo dispone el cajero para realizar otras tareas.
56
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Ejemplo 2
• Modelo M/M/1/DG/∞/∞
• es 15 clientes/hora
• es 1/3 minuto x 60 minutos = 20 clientes/hora
• = / = 15/20 = 0.75
• Nº de clientes esperado en la cola
• Nº de clientes en la sucursal
• Tiempo que espera el cliente para ser atendido
• Tiempo medio que pasa el cliente en la sucursal
• Tiempo libre del cajero
25.275.01
75.0
1
22
qL
375.01
75.0
1
SL
(9minutos) 15.015
25.2 · horas
LWqWqL
q
q
minutos) (12 2.015
3 · horas
LWsWsL s
s
libre tiempo%2525.075.0110 P57
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
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 clientes espere en el sistema más de un tiempo t
t
t
s
s
dttWP
W
)1(
0
e )1(
11
)1(
1
58
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/1
Formulario
1,0
)(
)(
)(
)1()1(
)(
1:
)(:
)1(
)1(
1
0
2
t
etWPP
etWPP
nLPP
PP
WWTiempos
LLTamaños
t
q
t
s
n
s
n
n
qs
qs
cola la en t tiempo un de mas espera cliente un que de drobabilida
sistema el en t tiempo un de más espera cliente un que de drobabilida
elementos n de más haya sistemas el en que de drobabilida
59
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/1
Ejemplo 3
• Un tren de lavado automático puede atender un automóvil cada 10 minutos y la tasa media de llegadas es de 4 automóviles por hora. Los coches que llegan se pueden estacionar en la calle
• El gerente quiere diseñar un estacionamiento. Para ello desea que un coche que llega encuentre espacio al menos el 90% de las veces.
60
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/1
ejemplo 3
p1- p
expresión la usando
0.91221 5ny 0.86831 4n que observamos , n para acumulados valores los Calculando
sistema el en coches nhay si ocasiones de 90% el en espacio encuentra coche Un
sistema el en 1n es espacios tener ientoestacionam de espacios los son
0
0
nn
nn
n
qs
qs
pp
pppp
nn
hrsWhrsW
clientesLclientesL
estableSistema
.)1(
9.0.........
min8.1933.0)(
min3050.01
33.1)(
2
66.06
4,6
10
60,4
210
2
n Pn Pn Aculumulado
1 0,22222 0,55556
2 0,14815 0,70370
3 0,09877 0,80247
4 0,06584 0,86831
5 0,04390 0,91221
6 0,02926 0,94147
7 0,01951 0,96098
8 0,01301 0,97399
9 0,00867 0,98266
10 0,00578 0,98844
11 0,00385 0,99229 61
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/1
ejemplo 3
coches 5 para espacio logaritmos tomando
ndosimplifica
(1-
1-
1- truncada geometrica serie Suma
)(1(1-
tedirectamen Calculando
sistema el en coches nhay si ocasiones de 90% el en espacio encuentra coche Un
sistema el en 1n es espacios n tener ientoestacionam de espacios los son n
:tedirectamen ndodesarrolla ejercicio, anterior el rdesarrolla podría se También
1n
1n
1n
2
679.41667.0ln
1.0ln
1.0
9.0)9.0)...
)1(
9.0.........
9.0.........
min8.1933.0)(
min3050.01
33.1)(
2
66.06
4,6
10
60,4
210
210
2
n
p
pppp
pppp
hrsWhrsW
clientesLclientesL
estableSistema
nn
n
n
n
qs
qs
62
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/1
ejemplo 4
• Un tren de lavado automático puede atender un automóvil cada 5 minutos y la tasa media de llegadas es de 9 automóviles por hora
a. Obtenga las medidas de desempeño de acuerdo con el modelo M/M/1
b. 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
63
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/1
ejemplo 4
17.0)60/30(
22.0)60/30( )
32.0)3( )
25.0)1( )
min1525.0)(
min2033.01
25.2)(
3
75.012
9,12,9
)1(
)1(
13
0
0
2
t
q
t
s
s
q
s
qs
eWP
eWPc
LPb
Pa
hrsW
hrsW
clientesLclientesL
64
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/1/DG/N/∞
Este sistema tiene en común con el anterior:
• La llegada de clientes sigue una distribución de Poisson de
parámetro A (es decir, el intervalo de tiempo entre llegadas
sigue una distribución exponencial negativa con tiempo medio
de 1/λ).
• El servicio de atención al cliente sigue una distribución
exponencial con tiempo medio 1/μ.
• Hay un solo servidor.
• La población origen es infinita.
La diferencia es que se trata de un sistema que tiene una
capacidad limitada. Es decir, el número máximo de clientes en
el sistema es N. Debido a esto, los clientes que llegan al
sistema cuando está saturado (o lo que es lo mismo, cuando
hay ya N clientes en el sistema) se pierden 65
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/1/DG/N/∞
La tasa de llegadas es igual λ, siempre < 1
Cuando el estado es N, la capacidad del sistema ha llegado a
su tope y no puede entrar ningún cliente más. Por la misma
razón, nunca existirá un estado superior a N, no puede darse
porque no caben en el sistema.
Para calcular el tiempo empleado en el sistema aplicamos la
fórmula de Little, pero utilizaremos la tasa de llegada real. Así
pues, consideraremos que cuando el sistema está en estado N,
no puede entrar ningún cliente porque se halla completo. Es
decir, no caben más. Por eso, en lugar de utilizar λ se utiliza λ(1 -
PN. Así, descontamos la tasa de llegadas durante el porcentaje
de tiempo en el que no se producen entradas, esto es, mientras
que el sistema está en estado N. Esto ocurre con una
probabilidad PN.
66
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/1/DG/N/∞
El valor de ρ (λ/µ) necesita no ser < 1, puesto que las llegadas están controladas por N del sistema. Interesa conocer las tasa efectiva λefectiva.
λperdida = λPN λefectiva= λ- λperdida= λ(1-PN)
Fuente Sistema
λperdida
λefectiva λ
Una vez que el número de elementos en el sistema alcanza N , no se
permiten más llegadas
67
0 1 2 N-1 N
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/1/DG/N/∞
1
11
1.
1
1
1
11
1
1
1
1
11
,...1,0
02
00
10
10
1
0
1
0
00
NPPPP
PP
P
P
PPn
NNpara
para
non
o
N
n
on
N
n
nn
N
nn
N
N
N
n
Nn
N
n
n
N
n
on
n
n
n
1)(N .. (1
; PPP 1 de caso el Para
1 paraP P
1 para P
1 finita serie
; finito es N
0,1,......n para
n
0,1,2,.n
00n
nn
0
Una vez que el número de elementos en el sistema alcanza N , no se permiten
más llegadas
68
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/1/DG/N/∞
1
)1()1()1(
)1(
)1(
)1(
)1()1()1(
1
)1(
1
1
1
1
1
11
)(1
1
)(
1
1
1
1
L
1
11
1
1
1
1
00
01
1
1
01
01
0
s
22
N
NNNN
Ns
N
Ns
Nn
N
n
nN
n
nN
nNs
nn
nN
nNs
nN
nNs
N
n
n
NNL
derivandod
dL
d
dL
rollandodo y desarsustituyen
nd
d
nLnL
nP
para finita serie una es
69
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/1/DG/N/∞
2
)1(
2
)1(1
)1(
11
)1()1(
)1(
)1(
1
)1()1()1(
)1(
)1(
1
1
1
1
1
2
2
NNNL
NL
NL
NL
s
Ns
N
N
s
N
NN
s
N
N
0
n que puesto 1 para
1 para
operandoy términos oReordenand
P-1-L -L L N
ssq
efectiva
N
ss
sP-1
L
L W
efectiva
N
qqq
P-1
LL W
efectiva
λefectiva
λefectiva
70
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/1/DG/N/∞
ejemplo 5
Una gasolinera dispone de un único servidor. Está situada
en una calle muy transitada y más bien estrecha. La
situación es tal que sólo puede haber tres coches esperando
a ser atendidos (si llega uno más no se le permite esperar
porque dificultaría el tráfico de la calle). El tiempo medio que
se emplea en poner gasolina a un vehículo son 2 minutos. El
número medio de clientes que llegan es de 20 coches por
hora.
Calcule:
1. La probabilidad de que el surtidor esté vacío.
2. Número medio de coches presentes en la gasolinera.
3. Tiempo que emplea un coche desde que llega hasta que
está listo para irse.
71
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/1/DG/N/∞
ejemplo 5
72
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/G/1
• Se trata de un sistema similar al anterior en el que la llegada sigue
una distribución de Poisson de parámetro λ ( es decir, el tiempo
entre una llegada y la siguiente sigue una distribución exponencial)
• En cambio, el tiempo empleado en el servicio no sigue una
distribución exponencial sino una distribución genérica con una
media E(t)= 1/µ y una varianza var(t)= σ2.
• Como el tiempo de servicio no sigue una distribución exponencial,
no son aplicables las formulas empleadas en el caso anterior,
denominadas de nacimiento y muerte. Aquí aplicaremos
emplearemos el análisis de las cadenas de Markov, la llamada
fórmula de Pollaczek-Khintchine (P-K) donde E(t)<1.
73
)1(2
222
qL
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/G/1
11
)(
)(1
1
1
)1(2
0
0
222
PtEsi
tEP
LWWW
LW
LLL
W
L
qqservicio
servicio
q
sistema el en elemento ningún haya no que de adProbabilid
sistema el en apermanenci de Tiempo
W servicio el en apermanenci de Tiempo
cola la en apermanenci de Tiempo
L sistema el en elementos nº
L servicio el en elementos nº
Pollaczek de formula cola la en elementos nº
servicio
servicio
servicio
74
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/G/1
ejemplo 6
• Un tren de lavado automático puede atender un automóvil
cada 5 minutos de media y una desviación típica es 2 . La
tasa media de llegadas es de 9 automóviles/hora.
• 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
75
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/G/1
ejemplo 6
75.025.01
min7.8145.0
min7.13228.01
31.1)1(2
06.275.31.1
0
222
w
q
q
qs
q
qs
PP
hrsL
W
hrsWW
clientesL
clientesLL
76
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/D/1
• Sistema de líneas de espera con llegadas aleatorias, tiempo de
servicio constante, una línea de servicio y una línea de espera.
• En este modelo los tiempos de servicio son determinísticos, este es
un caso especial de la situación M / G / 1 que se analizó con
anterioridad, en donde la varianza es igual a cero. En este caso se
puede conocer el numero de unidades que están esperando a ser
atendidas (Lq), a través de la siguiente ecuación:
• Todas las demás características de operación pueden determinarse
a partir de este valor. Si utilizamos Lq podemos determinar el valor
de L, por medio de la siguiente ecuación:
)1(2)1(2
22
222
LqLq 0 si
qq LLLL servicioL
77
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/D/1
1 Para
1
)1(2
2
q
q
q
q
q
WL
W
LW
LL
L
78
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/D/1
ejemplo 7
• Un tren de lavado automático puede atender un automóvil
cada 5 min.
• La tasa media de llegadas es de 9 automóviles/hora.
• Obtenga las medidas de desempeño de acuerdo con el
modelo M/D/1
79
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/D/1
ejemplo
min5.1221.01
min5.7125.0
125.1)1(2
875.1
2
hrsWW
hrsL
W
clientesL
clientesWL
q
q
q
q
s
80
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
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
81
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
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
82
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
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
83
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo (M, M, s):(DG, , )
En este modelo los clientes llegan siguiendo uan distribución
de Poisson con una tasa y un máximo de s clientes pueden
ser atendidos simultáneamente.
La tasa de servicio por servidor activo es también de Poisson
e igual a .
El número de elementos del sistema, así como el tamaño de
la fuente emisora es infinito.
El efecto último de usar s servidores paralelos es acelerar la
tasa de servicios al permitir servicios simultáneos.
84
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo (M, M, s):(DG, , )
Si el número de clientes en el sistema n es menor o igual s,
, habrá n servidores funcionando y ningún cliente esperando
Si hay n>s clientes en el sistema, los s servidores estarán
funcionando y (n-s) clientes esperando.
Siempre que hay n clientes habrá el mínimo número entre
n y s servidores ocupados.
Tasa de servicio de la instalación es s. o si es n menor
que s, la tasa de servicio es igual a n. Tasa de llegada n = , para n 0
Tasa de servicio n = n, para n s
n = s, para n s
85
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
M/M/s, varios servidores
0
02
1
02
1
0
0
0
0
0
0
!
1
1
1;
)()!1()()!1(..)(
!1
1
!
1
,!
,!
1
Ps
s
sP
WWL
W
LLLLL
LWWL
Pss
Pss
PsnL
n
s
s
P
snsiPss
P
snsiPn
P
PP
sw
qsq
q
qqservicioqs
servicioservicioservicioservicio
ss
n
sn
q
s
n
ns
sn
n
n
n
n
n
i
ni
i
ocupados esten servidores los todas que de dProbablida
sistema el en cola la en apermanenci de Tiempo
μλ sistema el en
; como
ndo..desarrolla cola la en elementos de nº
sistema el en elemento ningún haya no que de Probalidad
ocupado este sistema el que adProbabilid
o
sistema el en elementos n haya que de adProbabilid
efectiva
Si n ≤ s no hay clientes en la cola
86
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/s
ejemplo 8
• El teléfono directo de ayuda al cliente para ordenadores NTI-
Computer es atendido por un técnico. Reciben, aleatoriamente, 5
llamadas por hora y siguiendo una distribución de Poisson. Se
resuelven 7 por hora, siguiendo una distribución exponencial. El
director del Dpto. ha recibido numerosas quejas sobre el tiempo de
espera al teléfono directo.
• El director del Dpto. desea determinar el tiempo medio espera de
los clientes antes de que el técnico conteste a sus llamadas. Si el
tiempo de medio de espera es más de 5 minutos, desea determinar
el nº de técnicos para reducir el tiempo de espera el tiempo de
espera a 2 minutos o menos.
88
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/s
ejemplo 8
• λ, tasa de llegada 5 5
• µ, tasa de servicio 7 7
• Nº de servidores 1 2
• ρ, utilización 71.43% 35.71%
• P(0), probabilidad de que no haya nadie 0.2857 0.4737
• Lq, longitud de la cola 1.7857 0.1044
• L, longitud del sistema 2.5000 0.8187
• Wq, tiempo de espera en la cola 0.3571 0.0209
Wq, tiempo de espera en la cola en minutos 21.4` 1.254`
• W, tiempo de espera en el sistema 0.5000 0.1637
• Probabilidad de espera del cliente 0.7143 0.1880
89
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/s
ejemplo 9
• 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/s. Además la probabilidad de tener 2 clientes en el sistema
ρ, utilización 80,00%
P(0), probabilidad que el sistema esté vacío 0,0130
Lq, longitud esperada de la cola 2,2165
Ls, número esperado en el sistema 6,2165
Wq, tiempo esperado en la cola 0,0277 horas
Ws, tiempo total esperado en el sistema 0,0777 horas
Pw, Probabilidad que un cliente espere 0,5541
P(2) Probabilidad que haya 2 usuarios 0,1039
90
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/ ∞ :G/∞/∞
Modelo autoservicio
• El número de servidores es ilimitado porque el cliente también es un servidor por tanto siempre hay un servidor disponible para cada llegada. Todo el tiempo que pasa el cliente en el sistema es su tiempo de servicio.
• El modelo generalizado es:
L
1
colahay No
colahay No
espera de tiempohay no ;
0,1,2....n ny
1E(S) sistema el en empleado tiempo del medio
llegadas entre tiempo del medio Valor
s
n
s
nn
n
o
n
o
n
n
n
n
n
n
n
q
q
S
n
Wn
eP
nP
ePP
n
PPn
P
Pn
P
W
L
W
Valor
AE
!!
1
...!2
1
1
!
1!
1
!
0
0
11
)(
0
02
0
1
00
0
91
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/ ∞ :G/∞/∞
ejemplo 10
• Una academia de idiomas sabe que cada semana se matriculan 2 nuevos alumnos. El tiempo medio que el alumno permanece en la academia son 10 semanas. ¿Cuál es el número medio de alumnos en la academia?¿Cuál es la probabilidad de que haya exactamente 10?
61020
0 1086.5!10
20
!!
20102
1
e
n
eP
nP
alumnosL
nn
n
s
semanas 10
anaalumno/sem 2
92
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/s:G/N/∞, s≤ N
cola de espera finita
• Este modelo se diferencia del genérico en el que se fija un límite N sobre la capacidad del sistema ( el tamaño de la cola será N-s).
• Las tasas de llegada y de servicio son λ y µ. La frecuencia efectiva de llegas λefectiva es menor que λ por causa de N
• Los clientes buscan servicio, si todos los servidores están ocupados se les niega el servicio
• En términos del modelo generalizado
Nns para
n0 para
N n para
Nn0 para
s
sn
p
np
i
ip
nn
nnp
n
n
n
n
n
n
n
0
1
,..2,1;1
1
21
0
0
1
0
1
0
...
...
93
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/s:G/N/∞, s≤ N
cola de espera finita
Nn s s!s
Po Pn
s n 0 n!
Po Pn
s-n
n
n
1-1-S
0n
sn
1-s
1sNs
n
1s
, 1 s- N s!
n!
1s
,
1-
s-1 !
s1
n! Po
0n
s
1
0
1
0
0
11
0
1
1,!2
1
1,111²!1
s
n
n
s
n
qns
s
sNsNs
q
PsLnPL
ss
sNsNP
sss
sNsss
P
L
λperdida = λPN λefectiva= λ- λperdida= λ(1-PN)
Para el cálculo de Wq utilizar λefectiva y para Ws, Ls
94
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/s:G/N/∞
ejemplo 11
Una centralita telefónica de 4 líneas, recibe 16 llamada por hora con una
duración promedio de 12 minutos, dispone de un buffer de espera de 6
clientes. Determinar la probabilidad de que estén ocupadas exactamente 2
ρ, utilización 77,14%
P(0), probabilidad que el sistema esté vacío 0,0312
Lq, longitud esperada de la cola 1,1542
Ls, número esperado en el sistema 4,2398
Wq, tiempo esperado en la cola 0,0748 ́
Ws, tiempo total esperado en el sistema 0,2748 ́
Pw, Probabilidad que un cliente espere 0,5387
P(2) Probabilidad que haya 2 usuarios 0,0357
95
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/k:G/k/∞
cola de espera finita
)1(
!
!
0
j
s
k
k
j
P
Número
k
j
N
(carga) ocupados servidores de promedio
P
sdisponible servidores s dados ocupados, servidores j haya que de adProbabilid
j
96
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/k:G/k/∞
ejemplo 12
iPP
k
j
ii
s
k
k
j
1
543210
2
2
0
j
%4.3034.0
54321
10
4321
10
321
10
21
10
1
10
!0
10
12
10
P
!
!P
sdisponible servidores s dados ocupados, servidores j haya que de adProbabilid
Una centralita telefónica de 5 líneas, recibe 1 llamada por minuto con una
duración promedio de 10 minutos, dispone de un buffer de espera de 6
clientes. Determinar la probabilidad de que estén ocupadas exactamente 2
97
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/1:G/N/N
servicio de máquinas
• Este modelo es un ejemplo de una fuente de llamadas finitas, en el que se dispone de un número de servidores para dar servicio a un total de N máquinas.
• La tasa de avería por máquina es λ • La tasa de reparación de los mecánicos será µ • La tasa de avería para todo el taller es proporcional al nº de máquinas que
funcionan (n). La tasa de avería para el taller λn=(N-n)λ
nn
n
sn
nN
mecánico solo un para
Kn para 0
Nns para N
n0 para
Kn para 0
Nn0 para ,)(
98
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/1:G/N/N
servicio de máquinas
• Este modelo es un ejemplo de una fuente de llamadas finitas, en el que se dispone de 1 servidor para dar servicio a un total de N clientes.
;1
)( ;)(
Po)-(1 Po)-(1 L ndodesarrolla
)!(
!
)!(
!
)!(
! 1
)!(
! dosustituyen 1
)!(
! ndodesarrolla
,..2,1;1
1
21
0
s
1
0n
n
1
0n
0
0
n
0
n
0
0
1
0
1
0
...
.....)2()1(
...
...
WqWs
LsNLN
LWq
NLNnpL
nN
N
nN
Np
nN
NPPo
nN
Np
PonN
Nppp
np
i
ip
nn
nnp
efectiva
s
q
q
N
n
nS
N
n
n
N
n
N
n
N
n
n
nn
n
n
n
NNN
99
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/s:G/N/N; s<N
servicio de máquinas
• Este modelo es un ejemplo de una fuente de llamadas finitas, en el que se dispone de s servidores para dar servicio a un total de N clientes. Como estos servidores, son los únicos que pueden atender ese servicio, el número máximo de posibles clientes tiene que ser N.
)( ;
s).disponible técnicos(de sdesocupado servidores de esperado número el representa s
1,1
1),(
;
1,11
1
1,
!
!
0
; !
!
_
0
0
1
0
01
0 1
0
K
0n
LsNL
W
sP
N
sssn
L
sPN
sPsn
L
NnsPss
n
n
N
snPn
N
Pss
n
n
N
n
NP
efectiva
efectiva
q
q
c
nnPS
n
N
sn
q
sn
n
n
n
s
n
N
snsn
nn
)!(!
!
nNn
N
n
N
100
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Modelo M/M/s:G/N/N; s<K
ejemplo 12
• La empresa Talleres MiguelB mantiene un taller que contiene 22 máquinas. Se sabe que cada máquina se avería cada dos horas, en promedio. Se requiere de un promedio de 12 minutos para terminar una reparación. Tanto el tiempo entre averías como el de reparación siguen una distribución exponencial. Talleres MiguelB está interesada en determinar el número de mecánicos necesarios para mantener el taller funcionando uniformemente.
..continua..s
L
de
dadproductivi
de
dadproductivi
s
5 horas; por averias 1/2
máquinas las
sdisponible Máquinas
averiadas Máquinas-sdisponible Máquinas
máquinas las
......;3,2,1
10022
22
100
101
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
Tasa de llegada 0.5 0.5 0.5 0.5 Tasa de servicio 5 5 5 5 Nº de mecánicos 1 2 3 4 Nº de máquinas 22 22 22 22
Utilización 100,01% 88,16% 65,11% 49,75% P(0), probabilidad que el sistema esté vacío 0,0004 0,0564 0,1078 0,1199 Lq, longitud esperada de la cola 11,009 2,6046 0,5127 0,1102 L, número esperado en el sistema 12,009 4,3678 2,4661 2,1002 Wq, tiempo esperado en la cola 2,2037 0,2954 0,0525 0,0111 W, tiempo total esperado en el sistema 2,4038 0,4954 0,2525 0,2111 Probabilidad que un cliente espere 0,9996 0,8196 0,4061 0,1545
Productividad de las máquinas 45.44 80.15 88.79 90.45 Incremento 34.71 8.64 1.66
Modelo M/M/s:G/N/N; s<K
ejemplo 12
102
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
103
Colas exponenciales en serie
Salidas Servidor
Servidor
Servidor
Servidor
Servidor
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
104
Colas exponenciales en serie
Teorema de descomposición de Jackson Si en un sistema de las en serie se cumple que:
1. el tiempo de llegada sigue una distribución exponencial negativa de
parámetro λ,
2. los tiempos de servicio en cada etapa i siguen distribuciones
exponenciales.
3. entre una etapa y la siguiente existe espacio suficiente como para albergar
indos los clientes, de manera que se puede considerar de capacidad
infinita, entonces el tiempo de llegada a cada etapa del sistema es
exponencial de parámetro λ
Lo que nos dice este teorema es que si en cada etapa existe la capacidad
suficiente como para atender a los clientes que llegan (es decir, la tasa de
servicio es superior a la tasa de llegadas), se podrá atender a todos los
clientes a la velocidad a la que llegan (que es λ). Por lo tanto, una vez que son
atendidos en la etapa 1 pasan a la etapa 2 con una tasa de llegadas λ, y así
sucesivamente en cada una de las k etapas. La consecuencia práctica es que
los cálculos en cada etapa se hacen como si fuera sistema independiente de
capacidad infinita.
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
105
Colas exponenciales en serie
Ejemplo Sea un proceso que tiene dos etapas. En la primera se hace el montaje con
una tasa de 30 productos hora. Para esta primera fase hay un solo servidor.
En segunda fase hay tres servidores que hacen el proceso de pintado a una
tasa de 111 productos hora cada una. Cada producto tiene que pasar por uno
de los tres servidores únicamente únicamente. El proceso se recoge en la
figura.
Al sistemas llegan 26 productos por hora. Se desea saber el número de
productos presentes en el proceso (longitud media del sistema total)
Servidor2
Servidor3
Servidor4
Servidor1 λ
µ1
µ2
capacidadtienefase
capacidadtienefase
2361233
26
130
26
´2
2´2
1
1
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
106
Colas exponenciales en serie
Ejemplo
Servidor2
Servidor3
Servidor4
Servidor1 λ
µ1
µ2
productos 10.03 3.536.5L
3.39 sistema el en
cola la en elementos de nº
sistema el en elementos haya no que de dProbablida
y
30
2
1
hPss
hdosustituyenLL
Pss
hL
n
h
s
hP
shDefinimos
MM
L
MM
s
qs
s
q
s
n
ns
S
2
02
1
0
0
)(!
)(!
0861.0
!1
1
!
1
1226
3//
5.62630
26
1
26
1//
MO
DEL
AD
O Y
SIM
ULA
CIÓ
N D
E SI
STEM
AS
IND
UST
RIA
LES
107
Sistemas de colas abiertas
Servidor
Salidas Servidor
Servidor
Servidor
Servidor
Servidor
Servidor
Servidor
Servidor
k
i
i
k
j
jijii
rλ sistemas egadas delobal de llLa tasa gl
pλrλ
1
1