teoria de colas
TRANSCRIPT
![Page 1: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/1.jpg)
Tema 5: Teoría de colas
Ezequiel López Rubio
Departamento de Lenguajes y Ciencias de la Computación
Universidad de Málaga
![Page 2: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/2.jpg)
Sumario
Conceptos básicos Cola M | M | 1 Cola M | M | c Cola M | M | 1 | k Redes de colas
Redes de Jackson abiertas Redes de Jackson cerradas
![Page 3: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/3.jpg)
Conceptos básicos
![Page 4: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/4.jpg)
Concepto de cola
Una cola es una línea de espera para determinado servicio Este servicio lo proporciona uno o varios
dependientes
La teoría de colas analiza la causa de la formación de la cola, que es la existencia de momentos en los que hay una mayor demanda de servicio que la capacidad de servicio
![Page 5: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/5.jpg)
Clasificación de sistemas de colas
Llamaremos clientes, trabajos o tareas a los que demandan servicio, y dependientes, empleados o servidores a los que ofrecen servicio
Un sistema de colas viene dado por varias características: 1º Modelo de llegada de clientes, El índice de
llegadas será el número medio de llegadas por unidad de tiempo, Alternativamente podemos usar el tiempo entre llegadas, que es el tiempo medio entre llegadas sucesivas
![Page 6: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/6.jpg)
Clasificación de sistemas de colas
2º Modelo de servicio, Puede venir dado por el tiempo de servicio o por el número de clientes atendidos por unidad de tiempo, Tendremos una variable aleatoria o bien un servicio determinista, Aquí supondremos que el modelo de servicio es independiente del de llegada
3º Disciplina de la cola, Establece el orden en que se va atendiendo a los clientes: Por orden de llegada (FIFO) Por orden inverso al de llegada (LIFO) Selección aleatoria (RANDOM) Según prioridades (PRIORITY, PR), Dos subtipos:
Con interrupción, Si llega un cliente de más prioridad, el trabajo que se estaba sirviendo se interrumpe para atenderlo
Sin interrupción, No se pueden interrumpir los trabajos Dentro de cada clase de prioridad se podrán aplicar disciplinas LIFO, FIFO
o RANDOM,
![Page 7: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/7.jpg)
Clasificación de sistemas de colas
4º Capacidad del sistema, Es el número máximo de clientes que puede haber en el sistema (finito o infinito), Si llega un cliente y el sistema está lleno, se marcha,
5º Número de canales de servicio, Es el número de dependientes, Puede haber una cola para cada dependiente o bien una sola cola global
6º Número de estados de servicio, Puede haber varias partes en las que se subdivide el trabajo (estados), cada una con su cola y su dependiente, que deben ser completadas sucesivamente, P, ej,, tres estados:
![Page 8: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/8.jpg)
Notación de Kendall
La notación de Kendall nos permite escribir resumidamente todas las características que hemos estudiado, Un sistema de colas se notará como: A | B | X | Y | Z | V, donde: A es el modelo de llegadas, Valores posibles:
M=tiempos entre llegadas exponenciales D=tiempos entre llegadas deterministas G=tiempos entre llegadas generales (cualquier
distribución) B es el modelo de servicio, Puede tomar los
mismos valores que A
![Page 9: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/9.jpg)
Notación de Kendall
X es el número de dependientes (servidores) Y es la capacidad del sistema (número máximo
de clientes en el sistema), Se puede omitir si es infinita
Z es la disciplina, Se puede omitir si es FIFO V es el número de estados de servicio, Se puede
omitir si es 1
Por ejemplo, M | M | 1 | ∞ | FIFO | 1 se escribe abreviadamente M | M | 1
![Page 10: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/10.jpg)
Medidas de rendimiento
Una vez descrito el sistema, nuestro objetivo es evaluar su rendimiento, Para ello tenemos varias medidas de rendimiento: Número medio de clientes en el sistema, notado
L Tiempo medio de espera de los clientes, W Número medio de clientes en la cola, Lq
Tiempo medio de espera en cola de los clientes, Wq
![Page 11: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/11.jpg)
Cola M | M | 1
![Page 12: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/12.jpg)
Descripción del modelo Hay una sola cola, cuya capacidad es infinita, y un
solo servidor, La disciplina será FIFO Las llegadas se producen según un proceso de
Poisson de razón λ, donde λ es el número medio de llegadas por unidad de tiempo y 1/λ es el tiempo medio entre llegadas, Los tiempos entre llegadas se distribuirán exponencialmente, Exp(λ)
Los tiempos entre servicios también se distribuirán exponencialmente, Exp(µ), de tal manera que µ es el número medio de clientes que el servidor es capaz de atender por unidad de tiempo y 1/µ es el tiempo medio de servicio
![Page 13: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/13.jpg)
Condición de no saturación
Se demuestra que si λ≥µ, el sistema se satura, es decir, el número de clientes en la cola crece indefinidamente con el tiempo, Por consiguiente, la condición de no saturación será:
µλρρ =< donde,1
Nosotros sólo estudiaremos las colas que no se saturan, Cuando una cola no se satura, también se dice que alcanza el estado estacionario,
![Page 14: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/14.jpg)
Probabilidades
El parámetro ρ se llama carga, flujo o intensidad de tráfico del sistema, puesto que mide la relación entre la cantidad de trabajos que llegan y la capacidad de procesarlos
Suponiendo que el sistema no se satura, se deduce la siguiente fórmula para las probabilidades pn de que haya n clientes en el sistema, donde n∈N:
( )ρρ −= 1nnp
![Page 15: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/15.jpg)
Medidas de rendimiento
El número medio de clientes en el sistema, L, se calcula así:
( ) ( )∑∑∑∞
=
∞
=
∞
=
−=−==000
11j
j
j
j
jj jjpjL ρρρρ
Sumamos la serie aritmético-geométrica:
...432 432 ++++= ρρρρS
...32 432 +−−−=− ρρρρS
( )ρ
ρρρρρρ−
=++++=−1
...1 432S
( ) ( ) ρρ
ρρρ
−=
−−=⇒
111 2L
![Page 16: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/16.jpg)
Medidas de rendimiento
La utilización del dependiente, notada U, es la fracción de tiempo (en tanto por uno) que el dependiente permanece ocupado, Para hallarla, nos valemos de que cuando no hay saturación, el número medio de clientes que entran en el sistema debe ser igual al número medio de clientes que salen de él:
ρµλµλ ==⇒= UU
Como para deducir la anterior fórmula no hemos usado ninguna característica especial del modelo de entrada ni del de salida, dicha fórmula es válida para colas G | G | 1
![Page 17: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/17.jpg)
Medidas de rendimiento
El tiempo medio de respuesta W es el tiempo medio que un trabajo permanece en el sistema, Si suponemos que un trabajo, al llegar al sistema, se encuentra con que hay por delante de él otros j trabajos, el tiempo medio que tardará en salir del sistema será j+1 veces el tiempo medio de servicio, Por lo tanto:
( )µµµµµ1111
1000
+=+=+= ∑∑∑∞
=
∞
=
∞
=
LppjpjW j
jj
jj
j
Tiempo que se pasaen el sistema sihay j por delante
al llegar
Probabilidad de quehaya j por delante
al llegar
![Page 18: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/18.jpg)
Medidas de rendimiento
Podemos simplificar algo más:
λµµµ −=+= 11L
W
El tiempo medio de espera en la cola Wq se hallará restando a W el tiempo que tarda en ser servido el trabajo (esto es válido para cualquier tipo de cola):
µ1−=WWq
En el caso particular de una cola M | M | 1, obtenemos:
λµρ−
=qW
![Page 19: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/19.jpg)
Ejemplo
Unos mecánicos llegan a una media de 10 por hora a recoger piezas de repuesto, Estas piezas se las da un dependiente pagado con 5 €/hora y que tarda como media 5 min en servir, Cada hora que tiene que esperar un mecánico (en el sistema) le cuesta al taller 10 €, Queremos saber si merece la pena contratar a un ayudante de dependiente, pagado con 4€/hora, de forma que el tiempo medio de servicio se reduzca a 4 min
Nota: Al resolver un problema de colas, tener siempre muy presente la coherencia de unidades
![Page 20: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/20.jpg)
Ejemplo
Tenemos dos opciones: Sin ayudante: 1/µ1 = 5 min = 1/12 h
Con ayudante: 1/µ2 = 4 min = 1/15 h
En ambos casos, λ = 10 clientes/h Opción 1 (sin ayudante):
mecánicos5
1210
1
1210
1;
12
10
1
111 =
−=
−==
ρρρ L
Por tanto, perdemos 5·(10€/h) = 50€/h
![Page 21: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/21.jpg)
Ejemplo
Opción 2 (con ayudante):
mecánicos2
1510
1
1510
1;
15
10
1
112 =
−=
−==
ρρρ L
Por tanto, perdemos 2·(10€/h) = 20€/h debido a la espera de los mecánicos, Pero también perdemos 4€/h debido al sueldo del ayudante, Por tanto, las pérdidas totales son 24€/h
En la opción 1 perdemos 50€/h y en la opción 2 perdemos 24€/h, con lo cual la más ventajosa es la opción 2,
![Page 22: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/22.jpg)
Más medidas de rendimiento
El número medio de trabajos en la cola Lq, se calcula restándole a L el número medio de trabajos que están siendo servidos:
( )ρ
ρρρ
ρρ−
=−−
=−=−−=11
12
0 LpLLq
Probabilidad de que un cliente que llega pase más de t unidades de tiempo en el sistema:
( ) WtetW /−=
( ) Wtq etW /−= ρ
Probabilidad de que un cliente que llega pase más de t unidades de tiempo en la cola:
![Page 23: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/23.jpg)
Ejemplos
Ejemplo: Un canal de comunicación se usa para enviar datos desde unos ordenadores fuente a uno central, Cada fuente envía paquetes de datos según un proceso de Poisson de razón 2 paquetes/seg, Además cada fuente envía independientemente de las otras, Todos los paquetes son idénticos, esperan en una cola común y después se transmiten de uno en uno, Los tiempos de transmisión se distribuyen exponencialmente, con media 25 mseg, Determinar el número máximo de fuentes que se pueden conectar al canal de tal manera que:
![Page 24: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/24.jpg)
Ejemplos
1º El canal no se sature Si tenemos k fuentes, llegarán a la cola 2k
paquetes/seg, Por otro lado, 1/µ = 0,025 seg ⇒ µ = 40 paquetes/seg
El canal no se satura cuando ρ<1:
fuentes2012040
2 <⇒<=== kkk
µλρ
![Page 25: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/25.jpg)
Ejemplos
2º En media los paquetes no pasen en el sistema más de 100 mseg Tal como ocurría en el apartado anterior, llegarán
a la cola 2k paquetes/seg, y tendremos µ = 40 paquetes/seg
Nos exigen W≤0,1 seg:
fuentes151,0240
11 ≤⇒≤−
=−
= kk
Wλµ
![Page 26: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/26.jpg)
Ejemplos
3º En el estado estacionario se garantice que al menos el 95% de los paquetes tenga un tiempo de respuesta que no exceda de 100 mseg Tal como ocurría en el apartado anterior, llegarán a la
cola 2k paquetes/seg, y tendremos µ = 40 paquetes/seg Nos exigen que la probabilidad de que un paquete pase
más de 100 mseg en el sistema sea inferior al 5%, es decir, W(100 mseg)≤0,05:
( ) ( ) ⇒≤−⇒≤⇒≤ −− 05,0ln42,005,005,01,0 2401,0 keW k
)k que (ya fuentes 5021,52,0
05,0ln4N∈≤⇒≤⇒+≤ kkk
![Page 27: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/27.jpg)
Ejemplos
Ejemplo: Supongamos que una cola M|M|1 con parámetros λ y µ se sustituye por n colas M|M|1 independientes de parámetros λ/n y µ/n, Es decir, dividimos la carga de trabajo y la capacidad de proceso en n partes iguales, Evaluar el efecto del cambio usando como medidas de rendimiento el tiempo medio de respuesta y el número medio de trabajos en el sistema
µλ
µ/nλ/n
µ/nλ/n
…
![Page 28: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/28.jpg)
Ejemplos
Alternativa 1 (una sola cola), λ1=λ, µ1= µ :
λµλ
ρρ
−=
−=
1
11 1L
λµλµ −=
−= 11
111W
Alternativa 2 (n colas independientes), λ2=λ/n, µ2=µ/n :
12
2
1 2
22
1111nLnnnnL
n
n
n
nn
i
=−
=−
=−
=−
=−
= ∑= λµ
λ
µλµ
λ
ρρ
ρρ
µ
λ
µ
λ
![Page 29: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/29.jpg)
Ejemplos
122
2
111nWnW
nn
=−
=−
=−
=λµλµ λµ
Como la alternativa 1 tiene menores valores para ambas medidas de rendimiento, concluimos que la dicha alternativa es mejor
Esto nos indica que lo mejor es no dividir la capacidad de procesamiento, es decir, tener un único servidor que atienda a todos los clientes
![Page 30: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/30.jpg)
Teorema de Little
Sea un sistema de colas con cualquier distribución de llegadas y servicios y cualquier estructura, Sean L el número de trabajos presentes en el sistema en el estado estacionario, W es tiempo medio de respuesta en el estado estacionario y λ la razón de llegadas al sistema, Entonces:
WL λ=
![Page 31: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/31.jpg)
Teorema de Little
Explicación intuitiva: Supongamos que cobramos 1€ a cada trabajo por cada unidad de tiempo que pasa en el sistema, Habría dos maneras equivalentes de medir las ganancias:
Colocando un recaudador a la entrada del sistema, le cobrará como media W a cada uno de los λ trabajos que vea pasar por unidad de tiempo
Cada vez que transcurre una unidad de tiempo, cobro 1 € a cada uno de los L trabajos que como media hay en ese instante en el sistema
![Page 32: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/32.jpg)
Teorema de Little
Si aplico el teorema a la cola, dejando fuera del sistema al servidor, obtengo el siguiente resultado, también muy útil:
qq WL λ=
Las dos fórmulas obtenidas nos sirven para ayudarnos a obtener los valores de las medidas de rendimiento, aunque necesitaremos otras ecuaciones para poder conseguir resultados explícitos
![Page 33: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/33.jpg)
Cola M | M | c
![Page 34: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/34.jpg)
Descripción del modelo Hay una sola cola, cuya capacidad es infinita, y c
servidores, La disciplina será FIFO Las llegadas se producen según un proceso de
Poisson de razón λ, donde λ es el número medio de llegadas por unidad de tiempo y 1/λ es el tiempo medio entre llegadas, Los tiempos entre llegadas se distribuirán exponencialmente, Exp(λ)
Los tiempos de servicio también se distribuirán exponencialmente, Exp(µ), de tal manera que µ es el número medio de clientes que cada servidor es capaz de atender por unidad de tiempo y 1/µ es el tiempo medio de servicio
![Page 35: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/35.jpg)
Condición de no saturación
Se demuestra que si λ≥cµ, el sistema se satura, es decir, el número de clientes en la cola crece indefinidamente con el tiempo, Por consiguiente, la condición de no saturación será:
µλρρc
donde =< ,1
Nosotros sólo estudiaremos las colas que no se saturan, Cuando una cola no se satura, también se dice que alcanza el estado estacionario,
![Page 36: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/36.jpg)
Probabilidades
Suponiendo que el sistema no se satura, se deducen las siguientes fórmulas para las probabilidades pn de que haya n clientes en el sistema, donde n∈N:
( )( ) 1
1
00 !1!
−−
=
+
−= ∑
c
n
ncc
n
c
c
cp
ρρ
ρ
( )
=
=caso otroen ,
!
,...,1,0 si ,!
0
0
pc
c
cnpn
c
pnc
n
nρ
ρ
![Page 37: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/37.jpg)
Medidas de rendimiento
Número medio de clientes en cola:
( ) 20
1
1! ρρ
−=
+
c
pcL
cc
q
Usamos razonamientos ya vistos para obtener:
µ1+= qWW
qq WL λ= WL λ=
![Page 38: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/38.jpg)
Otras medidas de rendimiento
Número medio de servidores ocupados, S, En el estado estacionario, la razón de las salidas será igual a la razón de las llegadas:
ρµλλµ cSS ==⇒=
Probabilidad de que un trabajo tenga que esperar para recibir su servicio (fórmula de retraso de Erlang):
( )ρρ
−=
1!0
c
pcq
cc
![Page 39: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/39.jpg)
Ejemplos
Ejemplo: Usando L como medida de rendimiento, comparar estas dos alternativas:
µλ λµ/2
µ/2
Alternativa 1: Alternativa 2:
![Page 40: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/40.jpg)
Ejemplos
Alternativa 1:
ρρ−
=11L
Alternativa 2:
ρµλ
µλρ ===
22
2
( )( ) 1
12
0
22
02 !
2
1!2
2−
−
=
+
−= ∑
n
n
np
ρρ
ρ
![Page 41: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/41.jpg)
Ejemplos
( ) ( )12212
02 12
4422421
12
4−−
−
−+−+=
++
−=
ρρρρρρ
ρρ
p
( ) ρρ
ρρ
+−=
−
+=−
1
1
12
221
02p
ρλµλλλλ
µ2
2122
2222 +=+=
+== qqq WWWWL
( )( )
( ) ( ) ρρρ
ρρρρ
ρρ 211
122
12
42 2
3
202
3
22 ++−
−=+−
=+= pLL q
![Page 42: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/42.jpg)
Ejemplos
( ) ( ) ( ) ( ) ( ) ( )ρρρ
ρρρρρρ
ρρρ
+−=
+−−+=+
+−=
11
2
11
2222
11
2 333
2L
( )( ) ρρρ
ρρρ
ρρ
+<⇒
>
−⇒
−+<
− 1
210
111
2
1
Para que la alternativa 1 sea mejor, ha de cumplirse que L1<L2:
121 <⇒<+⇒ ρρ Como ρ<1 siempre se cumple, tendremos que
la alternativa 1 siempre es mejor, Es decir, no conviene dividir la capacidad de procesamiento en dos servidores
![Page 43: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/43.jpg)
Ejemplos Ejemplo: Usando el número medio de clientes en el
sistema como medida de rendimiento, comparar estas dos alternativas:
µ/2λ/2
λµ/2
µ/2
Alternativa 2:Alternativa 1:
µ/2λ/2
![Page 44: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/44.jpg)
Ejemplos
Alternativa 1 (nótese que hay 2 colas):
µλρ
ρρ
ρρ =
−=
−= donde,
1
2
12
1
11L
Alternativa 2 (es la alternativa 2 del ejemplo anterior):
ρµλ
µλρ ===
22
2
( )( )ρρρ
+−=
11
22L
![Page 45: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/45.jpg)
Ejemplos
( ) ( ) ρρρ
ρρρ
ρρ
+>⇒
>
−⇒
−+>
− 1
110
1
2
11
2
1
2
Para que la alternativa 2 sea mejor, ha de cumplirse que L1>L2:
011 >⇒>+⇒ ρρ
Como ρ>0 siempre se cumple, tendremos que la alternativa 2 siempre es mejor, Es decir, no conviene poner dos colas, sino tener una única cola global
![Page 46: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/46.jpg)
Ejemplos
Ejemplo: En una copistería se dispone de 3 máquinas fotocopiadoras a disposición del público, Cada máquina es capaz de servir, por término medio, 8 trabajos cada hora, A la copistería llegan como promedio 5 clientes a la hora,
Parámetros del sistema: λ = 5 clientes/h, µ = 8 clientes/h, c = 3 servidores, El sistema no se satura porque ρ<1,
245
8·35 ===
µλρc
![Page 47: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/47.jpg)
Ejemplos
¿Cuál es la probabilidad de que las tres máquinas estén libres a la vez?
( )( )
( )( ) =
+
−=
+
−=
−
=
−−
=∑∑
12
0
331
1
00 !
31!3
3!1! n
nc
n
ncc
nnc
cc
pρ
ρρρ
ρρ
( )( ) ( ) ( )
0,5342706569304
12825
85
12432125
!23
!13
!03
1!33
1121033
≈=
+++=
+++
−
−−ρρρ
ρρ
( ) ( ) clientes 0,0072264341791302
1!3
3
1! 256930443
20
1
≈=−
=−
=+
ρρ
ρρ
c
pcL
cc
q
¿Cuál es el número medio de clientes en la cola?
![Page 48: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/48.jpg)
Ejemplos
¿Cuál es el tiempo medio de espera en la cola?
h 00144529,035979
5241791·5302 ≈===
λq
q
LW
¿Cuál es el tiempo medio de espera en el sistema?
h 126445,04065514
81
35979521 ≈=+=+=
µqWW
¿Cuál es el número medio de clientes en el sistema?
clientes0.632226813514
4065514
·5 ≈=== WL λ
![Page 49: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/49.jpg)
Cola M | M | 1 | k
![Page 50: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/50.jpg)
Descripción del modelo Hay una sola cola, cuya disciplina será FIFO, La
capacidad del sistema es limitada, de tal modo que sólo puede haber k clientes como máximo en el sistema, Por lo tanto, el número máximo de clientes en la cola es k–1, Si un cliente llega y el sistema está lleno, es rechazado y nunca más regresa
Las llegadas se producen según un proceso de Poisson de razón λ, Los tiempos entre llegadas se distribuirán exponencialmente, Exp(λ)
Los tiempos entre servicios también se distribuirán exponencialmente, Exp(µ), de tal manera que µ es el número medio de clientes que el servidor es capaz de atender por unidad de tiempo
![Page 51: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/51.jpg)
Probabilidades
El sistema nunca se satura, ya que la capacidad es limitada
Se deduce la siguiente fórmula para las probabilidades pn de que haya n clientes en el sistema, donde n∈{0, 1, 2, …, k}:
( )
=+
≠−
−
=+
1 si ,1k
1
1 si ,1
11
ρ
ρρ
ρρk
n
np
![Page 52: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/52.jpg)
Probabilidades
El valor de ρ determina cómo varían los pn: Si ρ<1, los estados más probables son los de menor
número de clientes, porque la oferta de servicio supera a la demanda
Si ρ>1, los estados más probables son los de mayor número de clientes, porque la demanda de servicio supera a la oferta
Si ρ=1, todos los estados son equiprobables, Podemos llegar a la fórmula del caso ρ=1 aplicando la regla de L’Hôpital al límite para ρ→1 de la fórmula del caso ρ≠1
Si hacemos k→∞, llegamos al modelo M | M | 1
![Page 53: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/53.jpg)
Medidas de rendimiento
Tasa efectiva de llegadas, λef, Es el número medio de clientes admitidos al sistema por unidad de tiempo de entre los λ que intentan entrar (λef<λ):
( )kef p−= 1λλ
( )
=
≠−+−
−=+
+
1 si ,2
1 si ,1
11 1
1
ρ
ρρ
ρρ
ρ
k
k
Lk
k
Número medio de clientes en el sistema (este valor siempre debe ser inferior a k):
![Page 54: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/54.jpg)
Medidas de rendimiento
Podemos obtener las demás medidas de rendimiento mediante razonamientos ya vistos, teniendo en cuenta que la tasa efectiva de llegadas al sistema es λef:
µ1+= qWW
WL efλ=qefq WL λ=
![Page 55: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/55.jpg)
Ejemplo
A un taller mecánico llegan vehículos para el cambio de pastillas de freno, Los coches llegan a un promedio de 18 a la hora según un proceso de Poisson, El espacio físico del taller sólo permite que haya 4 vehículos, y las ordenanzas municipales prohíben esperar fuera, El taller puede servir a un promedio de 6 coches por hora de acuerdo a una distribución exponencial,
Parámetros del sistema: λ = 18 vehículos/h, µ = 6 vehículos/h, k = 4 vehículos
36
18 ==ρ
![Page 56: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/56.jpg)
Ejemplo
¿Cuál es la probabilidad de que no haya ningún vehículo en el taller?
( )0,00826446
1211
2422
31
31
1
11414
0
0 ≈=−−=
−−=
−−= ++ρ
ρρp
¿Cuál es el promedio de vehículos que hay en el taller?
( ) ( ) =−+−
−=
−+−
−= +
+
+
+
14
14
1
1
31
31431
3
1
11 k
kkL
ρρ
ρρ
vehículos3,5206611121426
2421215
23 ≈=
−−−
![Page 57: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/57.jpg)
Ejemplo
¿Cuánto tiempo pasa por término medio un coche en el taller?
( ) ( ) =
−
−−=−= +111
11 k
k
kef pρ
ρρλλλ
( )clientes/h 5,950413
121720
31
23118
5
4
≈=
−−−
horas 0,591666612071
720426
121720
121426
≈====ef
LW
λ
![Page 58: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/58.jpg)
Ejemplo
¿Cuánto tiempo esperan por término medio en la cola los coches?
horas 425,04017
61
120711 ==−=−=
µWWq
¿Cuál es la longitud media de la cola?
vehículos2,52893121306
4017
·121720 ≈=== qefq WL λ
![Page 59: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/59.jpg)
Redes de colas
![Page 60: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/60.jpg)
Redes de colas
Una red de colas es un sistema donde existen varias colas y los trabajos van fluyendo de una cola a otra
Ejemplos: Fabricación (trabajos=artículos) Oficinas (trabajos=documentos) Redes de comunicaciones (trabajos=paquetes) Sistemas operativos multitarea (trabajos=tareas)
![Page 61: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/61.jpg)
Enrutado de trabajos
Criterios para decidir a qué cola se dirige un trabajo que acaba de salir de otra: Probabilístico: se elige una ruta u otra en función
de una probabilidad (puede haber distintos tipos de trabajos, cada uno con sus probabilidades)
Determinista: cada clase de trabajo se dirige a una cola fija
![Page 62: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/62.jpg)
Tipos de redes de colas
Se distinguen dos tipos de redes de colas: Abiertas: Cada trabajo entra al sistema en un
momento dado, y tras pasar por una o más colas, sale del sistema, Dos subtipos: Acíclicas: Un trabajo nunca puede volver a la misma
cola (no existen ciclos) Cíclicas: Hay bucles en la red
Cerradas: Los trabajos ni entran ni salen del sistema, Por lo tanto permanecen circulando por el interior del sistema indefinidamente, Usualmente existe un número fijo de trabajos,
![Page 63: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/63.jpg)
Red abierta acíclica
![Page 64: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/64.jpg)
Red abierta cíclica
![Page 65: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/65.jpg)
Red cerrada
![Page 66: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/66.jpg)
Redes de Jackson abiertas
![Page 67: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/67.jpg)
Definición
Una red de colas abierta se dice que es de Jackson sii: Sólo hay una clase de trabajos Los enrutados son probabilísticos, donde rij ≥ 0 es la
probabilidad de ir al nodo j después de haber salido del nodo i, Por otro lado, ri0 es la probabilidad de abandonar del sistema después de haber salido del nodo i, donde ri0 = 1– ∑jrij
Cada nodo i es una cola .|M|ci
La tasa de llegadas externas al nodo i se notará γi
El número total de nodos de la red se notará K
![Page 68: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/68.jpg)
Ecuaciones de equilibrio
Dado que el flujo total de entrada a un nodo debe ser igual al flujo total de salida del nodo, tendremos que:
{ }1
, 1,...,K
i i j jij
r i K=
λ = γ + λ ∀ ∈∑
Las K ecuaciones anteriores forman un sistema lineal con solución única, que resolveremos para hallar las tasas de llegada a cada nodo λi
![Page 69: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/69.jpg)
Condición de no saturación
Para que ninguna de las colas del sistema se sature, es preciso que se cumpla la siguiente condición:
{ }ii
iii c
dondeKiµ
λρρ =<∈∀ ,1,,...,2,1
Nota: Se trata de la condición de no saturación del modelo M|M|c, aplicada a cada uno de los nodos por separado
![Page 70: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/70.jpg)
Teorema de Jackson para redes abiertas
Teorema: Sea una red de Jackson abierta que cumple la condición de no saturación, Entonces en el estado estacionario, la distribución del número de clientes en cada nodo es la que sigue:
11
( ) ( ), , , 0K
i i Ki
p p n n n=
= ∀ ≥∏n K
donde pi(ni) es la probabilidad de que haya ni clientes en el nodo i, calculada según las ecuaciones del modelo M|M|c
![Page 71: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/71.jpg)
Consecuencias del teorema
Corolario: Las medidas de rendimiento para cada nodo se calculan según las ecuaciones del modelo M|M|c, Además se tendrán las siguientes medidas: Tasa global de salidas del sistema (throughput),
que es el número medio de trabajos que salen del sistema por unidad de tiempo, Coincide con el número de trabajos que entran en el sistema:
∑=
=K
iired
1
γλ
![Page 72: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/72.jpg)
Consecuencias del teorema
Número medio de trabajos en el sistema, Lred, que es la suma de los número medios de trabajos en cada uno de los nodos:
∑=
=K
iired LL
1
Tiempo medio en el sistema, Wred, que es el tiempo medio que pasa una tarea desde que entra en la red hasta que sale de ella:
red
redred
LW
λ=
![Page 73: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/73.jpg)
Consecuencias del teorema
Razón de visitas al nodo i, Vi, que es el número medio de veces que un trabajo visita el nodo i desde que entra en la red hasta que sale:
{ }red
iiVKi
λλ=∈∀ ,,...,2,1
Nota: en una red acíclica habrá de cumplirse que Vi≤1 ∀i∈{1,2,,,,,K}, ya que cada tarea visitará cada nodo a lo sumo una vez
![Page 74: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/74.jpg)
Ejemplo (red acíclica)
11,5 2
0,8
3
0,2
60,5
40,6
50,4
1
{ }2 1,2,..,6i iµ = ∀ ∈
![Page 75: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/75.jpg)
Ejemplo (red acíclica)
En el ejemplo, γ1=1,5; r12=0,2; r13=0,8; r34=0,6; r35=0,4; γ6=0,5; r65=1; con lo cual la solución es:
1 2 31,5; 0,3; 1,2;λ = λ = λ =
4 5 60,72; 0,98; 0,5λ = λ = λ =
Ecuaciones de equilibrio:
1 1 2 1 12 3 1 13; ; ;r rλ = γ λ = λ λ = λ
4 3 34 5 3 35 6 65 6 6; ;r r rλ = λ λ = λ +λ λ = γ
![Page 76: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/76.jpg)
Ejemplo (red acíclica)
Medidas de rendimiento (ecuaciones del modelo M|M|1):
1 2 33; 0,1764; 1,5;L L L= ≈ =
4 5 60,5625; 0,9607; 0,3333L L L= ≈ ≈
Condición de no saturación (se cumple porque ρi<1):
ii
i
λρ = ⇒µ 1 2 30,75; 0,15; 0,6;ρ = ρ = ρ =
4 5 60,36; 0,49; 0,25ρ = ρ = ρ =
⇒−
=i
iiL ρ
ρ1
![Page 77: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/77.jpg)
Ejemplo (red acíclica)
⇒−
=ii
iW λµ1
1 2 32; 0,5882; 1,25;W W W= ≈ =
4 5 60,78125; 0,9803; 0,6666W W W= ≈ ≈
⇒−=i
iqi WWµ1
1 2 31,5; 0,0882; 0,75;q q qW W W= ≈ =
4 5 60,28125; 0,4803; 0,1666q q qW W W= ≈ ≈
![Page 78: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/78.jpg)
Red abierta cíclica
10,2 2
0,7
3
0,3
40,1
50,9
0,8
0,6
{ }{ }
3 1,2,4
4 3,5
i
i
i
i
µµ
= ∀ ∈
= ∀ ∈
![Page 79: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/79.jpg)
Ejemplo (red cíclica)
En el ejemplo, γ1=0,2; r12=0,3; r13=0,7; γ3=0,8; r53=0,6; r34=0,1; r35=0,9; con lo cual la solución es:
1 2 30,2; 0,06; 2,0434;λ = λ = λ ≈
4 50,2043; 1,8391λ ≈ λ ≈
Ecuaciones de equilibrio:
1 1 2 1 12 3 3 1 13 5 53; ; ;r r rλ = γ λ = λ λ = γ + λ + λ
4 3 34 5 3 35;r rλ = λ λ = λ
![Page 80: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/80.jpg)
Ejemplo (red cíclica)
Medidas de rendimiento (ecuaciones del modelo M|M|1):
1 2 30,0714; 0,0204; 1,0443;L L L≈ ≈ ≈
4 50,0731; 0,8511L L≈ ≈
Condición de no saturación (se cumple porque ρi<1):
ii
i
λρ = ⇒µ 1 2 30,0666; 0,02; 0,5108;ρ ≈ ρ = ρ ≈
4 50,0681; 0,4597ρ ≈ ρ ≈
⇒−
=i
iiL ρ
ρ1
![Page 81: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/81.jpg)
Ejemplo (red cíclica)
⇒−
=ii
iW λµ1
1 2 30,3571; 0,3401; 0,5111;W W W≈ ≈ =
4 50,3576; 0,4627W W≈ ≈
⇒−=i
iqi WWµ1
1 2 30,0238; 0,0068; 0,2611;q q qW W W≈ ≈ ≈
4 50,0243; 0,2127q qW W= ≈
![Page 82: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/82.jpg)
Redes de Jackson cerradas
![Page 83: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/83.jpg)
Definición
Una red de colas cerrada se dice que es de Jackson sii: Sólo hay una clase de trabajos Los enrutados son probabilísticos, donde rij ≥ 0 es la
probabilidad de ir al nodo j después de haber salido del nodo i,
Cada nodo i es una cola .|M|ci
Hay una cantidad constante M de trabajos en el sistema
El número total de nodos de la red se notará K
![Page 84: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/84.jpg)
Ecuaciones de equilibrio
Dado que el flujo total de entrada a un nodo debe ser igual al flujo total de salida del nodo, tendremos que:
{ }* *
1
, 1,...,K
i j jij
r i K=
λ = λ ∀ ∈∑
Las K ecuaciones anteriores forman un sistema lineal indeterminado con un grado de libertad, que resolveremos para hallar las tasas de llegada relativas a cada nodo λi*, Para ello fijaremos un valor positivo arbitrario para una incógnita, por ejemplo λ1*=1
![Page 85: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/85.jpg)
Análisis del valor medio
Hallaremos las siguientes medidas de rendimiento para M tareas en el sistema: Li(M)=Número medio de tareas en el nodo i
Wi(M)=Tiempo medio que cada tarea pasa en el nodo i cada vez que lo visita
λi(M)=Tasa real de salidas del nodo i
Se trata de un algoritmo iterativo que va calculando Li(m), Wi(m) para valores crecientes de m a partir de m=0
![Page 86: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/86.jpg)
Análisis del valor medio
Las ecuaciones son:
{ } { }
{ } { }*
*1
( 1)1( ) , 1,..., 1,...,
( )( ) , 1,..., 1,...,
( )
jj
j j j
j jj K
i ii
L mW m j K m M
c
W mL m m j K m M
W m=
−= + ∀ ∈ ∀ ∈
µ µ
λ= ∀ ∈ ∀ ∈
λ∑
{ }(0) 0, 1,...,jL j K= ∀ ∈
{ } { }( )( ) , 1,..., 1,...,
( )j
jj
L mm j K m M
W mλ = ∀ ∈ ∀ ∈
![Page 87: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/87.jpg)
Red cerrada
1
20,3
40,7
31
1
1{ }5 1,2,..,6i iµ = ∀ ∈
![Page 88: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/88.jpg)
Ejemplo (red cerrada)
En el ejemplo, r12=0,3; r14=0,7; r23=1; r31=1; r41=1; con lo cual la solución es, tomando λ1*=1:
* *1 21; 0,3;λ = λ =
* *3 40,3; 0,7λ = λ =
Ecuaciones de equilibrio:
* * * * *1 3 31 4 41 2 1 12; ;r r rλ = λ + λ λ = λ
* * * *3 2 23 4 1 14;r rλ = λ λ = λ
![Page 89: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/89.jpg)
Ejemplo (red cerrada)
{ }1 ( 1)( ) , 1,...,4
5j
j
L mW m j
+ −= ∀ ∈
11
1 2 3 4
( )( )
( ) 0,3 ( ) 0,3 ( ) 0,7 ( )
W mL m m
W m W m W m W m=
+ ⋅ + ⋅ + ⋅
22
1 2 3 4
0,3 ( )( )
( ) 0,3 ( ) 0,3 ( ) 0,7 ( )
W mL m m
W m W m W m W m
⋅=+ ⋅ + ⋅ + ⋅
33
1 2 3 4
0,3 ( )( )
( ) 0,3 ( ) 0,3 ( ) 0,7 ( )
W mL m m
W m W m W m W m
⋅=+ ⋅ + ⋅ + ⋅
44
1 2 3 4
0,7 ( )( )
( ) 0,3 ( ) 0,3 ( ) 0,7 ( )
W mL m m
W m W m W m W m
⋅=+ ⋅ + ⋅ + ⋅
![Page 90: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/90.jpg)
Ejemplo (red cerrada)
Primera iteración:
{ }(0) 0, 1,...,4jL j= ∀ ∈ ⇒ { }1 (0)(1) 0,2 1,...,4
5j
j
LW j
+= = ∀ ∈
1
0,2(1) 1 0,4347
2,3 0,2L = ⋅ ≈
⋅
2
0,3 0,2(1) 1 0,1304
2,3 0,2L
⋅= ⋅ ≈⋅
4
0,7 0,2(1) 1 0,3043
2,3 0,2L
⋅= ⋅ ≈⋅
3
0,3 0,2(1) 1 0,1304
2,3 0,2L
⋅= ⋅ ≈⋅
![Page 91: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/91.jpg)
Ejemplo (red cerrada)
m W1(m) W1(m) W1(m) W1(m) L1(m) L2(m) L3(m) L4(m)
0 -- -- -- -- 0 0 0 0
1 0,2 0,2 0,2 0,2 0,4348 0,1304 0,1304 0,3043
2 0,2870 0,2261 0,2261 0,2609 0,9483 0,2241 0,2241 0,6034
3 0,3897 0,2448 0,2448 0,3207 1,5360 0,2895 0,2895 0,8849
4 0,5072 0,2579 0,2579 0,3770 2,1913 0,3343 0,3343 1,1401
5 0,6383 0,2669 0,2669 0,4280 2,9065 0,3646 0,3646 1,3644
6 0,7813 0,2729 0,2729 0,4729 3,6737 0,3850 0,3850 1,5564
7 0,9347 0,2770 0,2770 0,5113 4,4852 0,3987 0,3987 1,7173
![Page 92: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/92.jpg)
0 2 4 6 8 10 12 14 16 18 200
2
4
6
8
10
12
14
16
Ejemplo (red cerrada)
m
L
Cola 1
Colas 2 y 3
Cola 4
![Page 93: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/93.jpg)
0 2 4 6 8 10 12 14 16 18 200
0.5
1
1.5
2
2.5
3
3.5
Ejemplo (red cerrada)
m
W
Cola 1
Colas 2 y 3
Cola 4
![Page 94: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/94.jpg)
0 2 4 6 8 10 12 14 16 18 2010
20
30
40
50
60
70
80
90
100
Ejemplo (red cerrada)Utilización del
servidor (%)
U=λ/µ=
L/(Wµ)
m
Cola 1
Cola 4
Colas 2 y 3
![Page 95: Teoria de Colas](https://reader035.vdocumento.com/reader035/viewer/2022062406/5597e5061a28ab130f8b485a/html5/thumbnails/95.jpg)
Cuellos de botella
Un cuello de botella en un sistema de colas es un nodo cuya capacidad de procesamiento determina el rendimiento de todo el sistema
Definición: Sea una red de Jackson cerrada. Diremos que el nodo j es un cuello de botella sii Lj(m)→∞ cuando m→∞
En el ejemplo anterior el nodo 1 es un cuello de botella. Trabaja al límite de su capacidad mientras que los otros no (se quedan al 30% o al 70%). Para mejorar el rendimiento global del sistema habría que aumentar la capacidad de procesamiento del nodo 1