Teoria De Colas I 1s6v6j

Investigación de Operaciones Teoría de Colas I Parte A: Introducción. Notación. Modelos M/M/1, M/M/s y M/M/s/K.

Introducción Teoría de Colas es el estudio de los fenómenos de espera bajo diferentes sistemas de atención. Esta teoría usa un modelo que consta principalmente de: - Proceso de llegadas - Proceso de atención - Número y tipo de servidores - Capacidad del sistema - Disciplina de atención

C5. TC – Teoría de Colas Investigación de Operaciones

Introducción Algunas medidas de interés son:

-

Tiempo medio de espera Tiempo medio de servicio Porcentaje de tiempo ocioso del sistema Número medio de personas en el sistema (tamaño de la cola)

C5. TC – Teoría de Colas Investigación de Operaciones

Introducción Gráficamente un sistema de espera se puede ver así: SISTEMA Servidor Cliente Fuente

Cola

C5. TC – Teoría de Colas Investigación de Operaciones

Cliente atendido

Proceso de llegadas Aún cuando no sean necesariamente personas las que hagan cola, vamos a llamar “clientes” a los individuos u objetos que esperan para ser atendidos.

- La población a ser atendida puede considerarse finita o infinita, lo más usual es considerarla infinita. - El supuesto más clásico es que las llegadas se realizan de acuerdo a un proceso de Poisson. OJO: el proceso de llegada debe determinarse empíricamente. - Hay modelos que consideran llegadas en grupos.

C5. TC – Teoría de Colas Investigación de Operaciones

Proceso de Atención y Nº de Servidores El mecanismo de servicio consiste en 1 o más “servidores”, los cuales pueden ser agrupados para atender a diferente clientes (como en los bancos). - El modelo más común asume un solo tipo de cliente y un número finito de servidores. - Es muy usual en los modelos asumir que todos los servidores atienden en un tiempo exponencial con igual parámetro. OJO: el tiempo de servicio debe determinarse empíricamente. - Otros modelos usuales de tiempos de atención son: Gamma y tiempo constante. C5. TC – Teoría de Colas Investigación de Operaciones

Capacidad del sistema y Disciplina de atención El sistema de atención consta de dos partes: la zona donde se espera (cola) y la zona de atención. - El tamaño del sistema es el número de clientes que pueden estar dentro, es decir, tanto clientes en atención como en espera. Si la capacidad del sistema es muy grande puede asumirse infinita para simplificar los cálculos. - Si el sistema está a capacidad completa, los clientes no entran al sistema. - La disciplina de atención indica la forma en que pasan los clientes desde “esperar” hacia “ser atendidos”. En general se asume FIFO, pero puede ser LIFO, Random o de prioridad. C5. TC – Teoría de Colas Investigación de Operaciones

Notación de Kendall La notación de Kendall es A/B/C/D/E, donde: A: se refiere al proceso de llegada. B: se refiere al proceso de atención. En ambos casos puede ser 1. M (Poisson o tiempo exponenciales entre llegadas o de atención según el caso. Se pone M de Markov), 2. Ek (Gamma de parámetro (λ,k)), 3. D (Determinista), 4. G (General).

C: Número de Servidores D: Capacidad del sistema (por defecto se supone ∞) E: Tamaño de la población (por defecto se supone ∞) C5. TC – Teoría de Colas Investigación de Operaciones

Notación en Modelos de Colas 1. Estado del sistema: Número de clientes en el sistema. 2. Largo de la Cola: Número de clientes esperando para ser atendidos. 3. s: número de servidores. 4. λn: tasa de llegada con n clientes en el sistema 5. μn: tasa de atención del sistema, como pasa de estar atendiendo n clientes a atender n-1.

(Existen pero no los usamos) 6. N(t): Número de clientes en el sistema en el instante t. 7. Pn(t): Probabilidad que el sistema se encuentre con n clientes en el instante t. C5. TC – Teoría de Colas Investigación de Operaciones

Notación en Modelos de Colas En régimen estacionario agregamos esta notación: 8. Pn: probabilidad que el sistema esté con n clientes. 9. L: número esperado de clientes en el sistema. 10. Lq: número esperado de clientes en la cola. 11. W: tiempo medio que el cliente permanece en el sistema. 12. Wq: tiempo medio que el cliente permanece en la cola. 13. ρ: factor de utilización (tasa de entrada/tasa de atención). 14. Ls: número esperado de clientes en atención. 15. Ws: tiempo medio de atención para un cliente.

C5. TC – Teoría de Colas Investigación de Operaciones

Modelos de Colas Vamos a revisar los modelos:

1. M/M/1 2. M/M/s 3. M/M/s/k 4. M/M/∞ Comentaremos: 1. M/M/s/N/N 2. M/G/1 3. M/D/1 4. M/Ek/1 C5. TC – Teoría de Colas Investigación de Operaciones

Importante: Deducir Un modelo desde lo Básico!

Proceso de Nacimiento y Muerte Para resolver los modelos vamos a usar las cadenas de nacimiento y muerte. En el caso de las colas el estado representa el número de individuos en el sistema. λ0 0

λi-1

3

2

1

μ1

λ3

λ2

λ1

i

…

μ2

C5. TC – Teoría de Colas Investigación de Operaciones

μ3

λi

μ4

μi

…

μi+1

Proceso de Nacimiento y Muerte Recordemos que la solución general es:

aquí la suma es hasta R (o hasta ∞ según el caso) C5. TC – Teoría de Colas Investigación de Operaciones

M/M/1 Sistema de un banco con un cajero (cuyo tiempo de atención distribuye exponencial de media 1/μ) y donde el tiempo entre llegadas distribuye exp. de media 1/λ . λ

λ

λ

0

μ

μ

λ

λ

3

2

1

μ

λ

i

μ

…

μ

…

μ

Obs: Supone capacidad ilimitada (∞, o sea todos se ponen a la cola y nunca se van si está “muy lleno”) y población infinita (∞), por lo que no se especifican, de acuerdo a la notación de Kendall. C5. TC – Teoría de Colas Investigación de Operaciones

M/M/1 La solución a ese problema se basa en calcular la siguiente sumatoria infinita:

 Ci      i 0 i 0    



i

Sin embargo, la sumatoria no siempre converge…

C5. TC – Teoría de Colas Investigación de Operaciones

M/M/1 Si λ > μ entonces la sumatoria no converge. Estamos frente a una clase transiente, y el sistema colapsa. Si λ = μ entonces la sumatoria tampoco converge. Estamos frente a una clase recurrente nula y el sistema colapsa. Si λ < μ entonces la sumatoria converge a frente a una clase recurrente positiva y el sistema no colapsa.

C5. TC – Teoría de Colas Investigación de Operaciones

1

1 

. Estamos 

M/M/1 Así, si λ < μ , la solución del caso general es:       p1   

p0 

2

    p 2      3

    p3      . . i

    pi     

C5. TC – Teoría de Colas Investigación de Operaciones

M/M/1 Calculemos ahora las medidas de desempeño del este sistema: 1. Fracción del tiempo en que está ocupado el sistema

2. Número esperado de clientes en el sistema

3. Número esperado de clientes en la fila

Para calcular W, Wq y Ws necesitamos introducir la ley de Little. C5. TC – Teoría de Colas Investigación de Operaciones

Ley de Little La ley de Little o fórmula de Little es un principio de conservación de flujo aplicado a cualquier sistema de colas. La ley dice que si el sistema se encuentra en estado estacionario entonces las tasas de entrada y de salida del sistema deben ser iguales. Si no lo fueran, el sistema se estaría vaciando o llenando, pero no estaría en estado estacionario. 1.- Por un lado la tasa de llegada es λ. 2.- Por otro lado si hay un número esperado de L clientes en el sistema, y el tiempo medio de permanencia en el sistema es W, entonces la tasa de salida es L/W. Por lo tanto: Referencia: Queuing Systems (volume I: Theory), L. Kleinrock C5. TC – Teoría de Colas Investigación de Operaciones

Ley de Little La ley de Little se puede aplicar no sólo al sistema completo, también a la cola:

A los servidores:

Además se tiene que:

C5. TC – Teoría de Colas Investigación de Operaciones

M/M/1 Continuamos calculando las medidas de desempeño del sistema: 4.

Tiempo medio que pasa el cliente en el sistema:

5.

Tiempo medio que el cliente pasa en cola:

3.

(Nuevamente!) Número esperado de personas en la fila

C5. TC – Teoría de Colas Investigación de Operaciones

M/M/1 Cómo el modelo M/M/1 es el modelo más sencillo podemos conocer mejor el desempeño del sistema; sea ω la variable aleatoria que representa el tiempo que pasa un cliente en el sistema, es decir E(ω) = W. 6.

ω tiene distribución exponencial de parámetro μ(1-ρ).

7.

ωq tiene una distribución mixta:

C5. TC – Teoría de Colas Investigación de Operaciones

M/M/1 6. ω tiene distribución exponencial de parámetro μ(1-ρ). Demostración: Si un cliente llega a la cola verá que con probabilidad pn hay n clientes (además de él). Si hay n clientes tendrá que esperar un tiempo exponencial por él y por cada cliente, todos independientes entre si. Luego, el tiempo que debe esperar para salir del sistema, Sn+1, se distribuye como una Gamma (Erlang) de parámetros μ y n+1, por lo tanto:

C5. TC – Teoría de Colas Investigación de Operaciones

M/M/1 Dem. (continuación):

C5. TC – Teoría de Colas Investigación de Operaciones

M/M/1 7. ωq tiene una distribución mixta: Demostración: Es claro que la probabilidad que un cliente no espere en cola es la probabilidad de encontrar el sistema vacio. Luego la primera igualdad es directa.

Si hay n clientes tendrá que esperar un tiempo exponencial por cada cliente, todos independientes entre sí (sin considerar su tiempo de atención). Luego, el tiempo que debe esperar, Sn, distribuye como una Gamma de parámetros μ y n. C5. TC – Teoría de Colas Investigación de Operaciones

M/M/1 Dem. (continuación):

C5. TC – Teoría de Colas Investigación de Operaciones

M/M/1 Con la distribución de ω y ωq podemos calcular su varianza:

También podemos calcular la varianza de N (número de clientes en el sistema):

C5. TC – Teoría de Colas Investigación de Operaciones

Resumen: M/M/1 N: número de clientes en el sistema. ω: tiempo del cliente en el sistema.

C5. TC – Teoría de Colas Investigación de Operaciones

M/M/s Sistema de un banco con s cajeros (cuyo tiempo de atención distribuye exponencial de media 1/μ) y donde el tiempo entre llegadas distribuye exp. de media 1/λ . λ

λ 1

0

μ

λ s-2

…

2μ

λ

(s-2)μ

C5. TC – Teoría de Colas Investigación de Operaciones

λ s1

(s-1)μ

λ s+1

s

sμ

λ …

sμ

sμ

M/M/s Así,

Para calcular las cantidades de interés se necesitan las siguientes igualdades:

C5. TC – Teoría de Colas Investigación de Operaciones

M/M/s Así, si λ < sμ, la solución es:

C5. TC – Teoría de Colas Investigación de Operaciones

M/M/s Luego la distribución estacionaria de la cola con s servidores es:

C5. TC – Teoría de Colas Investigación de Operaciones

M/M/s Al tener s servidores el sistema tiene la capacidad de vaciar la cola a una tasa sμ, luego el factor de utilización del sistema es:

El número esperado de clientes siendo atendidos, Ls, es:

C5. TC – Teoría de Colas Investigación de Operaciones

M/M/s El número esperado de clientes en la cola, Lq, se calcula como:

C5. TC – Teoría de Colas Investigación de Operaciones

M/M/s El número esperado de clientes en el sistema, L, se calcula como:

El tiempo medio que demora el cliente en el sistema se obtiene usando la ley de Little:

C5. TC – Teoría de Colas Investigación de Operaciones

Resumen: M/M/s

C5. TC – Teoría de Colas Investigación de Operaciones

Resumen: M/M/s

C5. TC – Teoría de Colas Investigación de Operaciones

M/M/s/K Sistema de un banco con s cajeros (cuyo tiempo de atención distribuye exponencial de media 1/μ) y donde el tiempo entre llegadas distribuye exp. de media 1/λ y con capacidad para que esperen K clientes. Asumimos K ≥ s.

λ 0

λ 1

μ

…

2μ

λ

λ

λ s-1

(s-1)μ

sμ

C5. TC – Teoría de Colas Investigación de Operaciones

…

s+1

s

sμ

sμ

λ

λ

λ

K

K1

sμ

sμ

M/M/s/K Así,

Para calcular las cantidades de interés necesitamos: a  1 a  1 C5. TC – Teoría de Colas Investigación de Operaciones

M/M/s/K (caso λ ≠ sμ) Luego, si λ ≠ sμ la solución es:

Llamando

(ojo: ¡no es el factor de utilización! ¿por qué?)

C5. TC – Teoría de Colas Investigación de Operaciones

M/M/s/K (caso λ ≠ sμ) Así, la distribución estacionaria de la cola con s servidores, capacidad K y ρ≠1 es:

C5. TC – Teoría de Colas Investigación de Operaciones

M/M/s/K (caso λ ≠ sμ) Como el sistema tiene una capacidad finita K, la tasa de entrada al sistema no es λ. ¿Cuándo los clientes deciden no entrar al sistema? Cuando está lleno, es decir en el estado K. Luego la tasa de entrada al sistema en régimen estacionario es

El número esperado de clientes siendo atendidos, Ls, es:

C5. TC – Teoría de Colas Investigación de Operaciones

M/M/s/K (caso λ ≠ sμ) El número esperado de clientes en la cola, Lq, se calcula como:

C5. TC – Teoría de Colas Investigación de Operaciones

Resumen: M/M/s/K (caso λ ≠ sμ)

El factor de ocupación es entonces ρ tal que: C5. TC – Teoría de Colas Investigación de Operaciones

M/M/s/K (caso λ = sμ) Ahora, si λ = sμ la solución es:

C5. TC – Teoría de Colas Investigación de Operaciones

M/M/s/K (caso λ = sμ) Así, la distribución estacionaria de la cola con s servidores, capacidad K y ρ=1 es:

C5. TC – Teoría de Colas Investigación de Operaciones

Investigación de Operaciones Fin C5 – Parte A