Fundamentos de Teoría de Colas y Simulación de Eventos Discretos

Notación de Kendall: A / B / X / Y / Z / V

La notación de Kendall se utiliza para describir de forma estandarizada los modelos de colas:

• A: Modelo del tiempo entre llegadas:
  • M: Distribución exponencial (Markoviana)
  • D: Determinístico
  • G: General
• B: Modelo del tiempo de servicio (M, D y G)
• X: Especifica el número de servidores, procesadores o cajeros.
• Y: Capacidad del sistema (se omite si es infinita).
• Z: Refiere a la disciplina de la cola (FIFO, LIFO, etc.).
• V: Cantidad de canales (cantidad de colas).

La simulación de los eventos discretos se centra en modelar sistemas donde las variables de estado cambian solo en puntos específicos del tiempo.

Componentes del Sistema

• Entidad: Objeto de interés en el sistema.
• Atributo: Una propiedad de la entidad.
• Estado: Colección de variables necesarias para describir el sistema en cualquier momento.
• Evento: Suceso instantáneo que cambia el estado del sistema.
• Actividad: Período de tiempo de duración específica conocida al inicio.
• Demora: Duración de tiempo indefinida que no se conoce hasta que termina la simulación, ya que depende de condiciones del sistema.
• Lista / conjunto: Una colección de entidades asociadas y ordenadas lógicamente, como una cola de espera.
• Lista de eventos futuros: Registro de los eventos que ocurrirán próximamente.
• Tiempo / reloj: Banks sostiene que en la simulación de eventos discretos el tiempo se trata como una variable aleatoria continua que se observa únicamente en el instante discreto.

Mecanismos de Avance del Tiempo

• Intervalos de tiempo variable: El reloj salta al tiempo del evento próximo, no de forma continua.
• De tiempo fijo: El tiempo avanza en unidades constantes.

Simulación como Caja Negra: Inputs, Outputs y Variables de Estado

Prueba de Frecuencias

• Tamaño de muestra (N)
• Número de subintervalos (n)
• FE = N / n

Prueba de Series

FE = Cantidad de pares / Cantidad de celdas = (N - 1) / n²

Bloques de Simul8

1. Work entry point (Punto de entrada de trabajo): Genera arribos.
2. Storage bin (Área de almacenamiento): Repositorio o cola.
3. Work center (Centro de trabajo): Actividad o servidor.
4. Work complete (Punto de salida): Fin del proceso.
5. Work item type (Ítem de trabajo): La entidad que circula (no es un lugar de proceso, no es la entrada en sí).
6. Resource (Recurso): Algo compartido entre varios centros de trabajo (ejemplo: un operario para varias máquinas).

Metodología de Traducción de un Sistema Real a un Modelo Computacional usando VIMS

1. Sistema Real: Partís del sistema real dentro de un problema más amplio (alto nivel de abstracción).
2. Modelo Conceptual: Lo llevas a un modelo conceptual, usando herramientas de alto nivel como diagramas de ciclo de actividades o diagramas de flujo. Aquí describes el proceso en términos generales (colas, actividades, recursos).
3. Modelo VIMS: Ese modelo conceptual se traduce a un modelo VIMS. Aquí lo reformulas en términos de los constructores específicos que te da el paquete (en Simul8: work entry point, storage bin, work center, work complete).
4. Modelo Computacional: El software internamente traduce a un modelo computacional real, pero esa traducción queda oculta; el usuario no la ve ni la controla directamente.

El modelador debe acotarse al conjunto de constructores brindados por el paquete de software.

Ley de Little

Teorema fundamental en la teoría de colas que establece que el número promedio de entidades de un sistema estable (L) es igual a la tasa de llegada (λ) multiplicada por el tiempo promedio que cada elemento pasa en el sistema (w). Se expresa con la fórmula: L = λ · w.

Para que sea válida se requiere:

1. Estacionariedad: Sistema en equilibrio operativo.
2. Conservación de entidades: Todo lo que entra tiene que salir.

Función Hazard Rate

La función Hazard Rate (tasa de falla, riesgo o, en este caso, tasa instantánea de abandono) se define matemáticamente como: h(t) = f(t) / (1 - F(t)). Mide la probabilidad instantánea de que un evento (falla) ocurra en un momento específico T.

F(t): La función de distribución acumulada del tiempo de paciencia. Mide la probabilidad instantánea de que un cliente abandone la cola en el siguiente instante de tiempo, dado que ya sobrevivió (esperó) hasta el tiempo T.

Por lo general, el h(t) de una exponencial da como resultado una constante (cte) por la propiedad de falta de memoria de la exponencial; la probabilidad instantánea de irse es siempre igual (sin importar si recién llega o si lleva 3 horas esperando). En cambio, el h(t) de una distribución uniforme depende del tiempo y aumenta con el mismo.

Modelo M / M / 1

• Media de arribos (Tiempo promedio): E[A] = 1 / λ
• Tiempo de servicios: E[s] = 1 / μ

Ecuaciones de Balance de Flujo

• Por transición (balance local): λ P_n = μ P_{n + 1}
• Por estado (B. G.): Todo el flujo entrante a un estado n es igual a todo el flujo saliente de dicho estado.

Medidas de Rendimiento

• Intensidad de tráfico: ρ = λ / (k · μ) (donde k = 1)
• Probabilidad de sistema vacío: P₀ = (1 - ρ)
• Probabilidad de tener exactamente i entidades: P_i = ρⁱ (1 - ρ)
• Número esperado de entidades en el sistema: E[L] = ρ / (1 - ρ) = λ · W_s
• Tiempo total en el sistema: W_s = 1 / (μ - λ)
• Tiempo de espera en la cola: W_q = W_s - E_s = ρ / (μ - λ)

Modelo M / M / ∞ (Servidores Infinitos)

En este modelo hay infinitos recursos. Cada entidad que llega es atendida de inmediato por lo que no existe cola ni espera (W_q = 0 y E[L_q] = 0).

• Tasas del proceso de nacimiento-muerte: λ_n = λ y μ_n = nμ
• Probabilidad de estado (P_i): Siguen una distribución de Poisson de media ρ: P_i = (ρⁱ · e^-ρ) / (i!); donde ρ = λ / μ. Válido también para M / G / ∞.
• Medidas de rendimiento: E[L] = ρ; W_s = E_s = 1 / μ

Modelo M / M / K (Múltiples Servidores)

Posee k servidores en paralelo idénticos (con la misma tasa μ) y una única cola común.

Tasa de servicio del sistema (μ_n):

• nμ si 0 ≤ n ≤ k (donde n = clientes)
• kμ si n ≥ k (donde k = servidores)

r (Carga ofrecida): r = λ / μ. Mide la cantidad de trabajo que ingresa al sistema por unidad de tiempo (número de servidores promedio ocupados).

ρ (Intensidad de tráfico): ρ = λ / (k · μ). Representa la fracción de tiempo que cada servidor individual pasa trabajando. Para estabilidad (ρ < 1) se requiere que r < k.

QoS y Control de Tráfico