Metodos de Simulacion de Eventos Discretos

Autor: Prof. Marcelo Olivares

Ingenieria Industrial, U de Chile

Los modelos analiticos son una herramienta muy útil para evaluar estrategias y apoyar la toma de decisiones en temas relacionados a planificacion de capacidad, dotación de personal y manejo de inventario en una organización. Estos modelos permiten entender los mecanismos y los diferentes trade-off que se deben considerar en la toma decisiones, que permiten cuantificar los efectos de primer orden para optimizar la asignación de recursos.

Sin embargo, la implementación práctica de estas decisiones muchas veces requiere incorporar mayor nivel de detalle del funcionamiento del sistema, que no siempre es posible de capturar a través de un modelo analítico. Para esto, los modelos de simulación son muy efectivos, ya que permiten incorporar detalles idiosincráticos de un sistema que pueden ser importantes. Dentro de la familia de métodos de simulación, identificamos tres grandes categorías:

TipoDescriptionEjemplos
1. Simulación fisicaReplica un proceso real en un laboratorio- Operacion de proceso de votacion bajo medidas sanitarias.Paper plebiscito 2020
2. Simulación de MontecarloPermite medir algun resultado especifico de interés de un proceso estocástico.- Utilidad esperada del modelo Newsvendor. capsula de video
3. Simulación de eventos discretosModela el flujo de eventos detallado de un proceso estocastico.- Flujo de clientes en los cajeros de un supermercado (ver ejemplo adjunto).

En este documento, nos focalizamos en la tercera categoría, identificando sus principales elementos. Tambien discutimos aspectos mas generales de simulación, incluyendo el análisis estadístico de los resultados que estas simulaciones entregan.

Cuando usar simulación de eventos discretos vs. modelos analiticos?

Una herramienta frecuentemente utilizada para analizar distintas métricas de desempeño de un proceso son los modelos de colas y otros modelos analíticos. Estos modelos tienen la ventaja de entregarnos resultados de forma rápida y parametrizable, que permiten evaluar de forma eficiente distintas configuraciones del sistema. Sin embargo, para modelos mas complejos, resulta difícil (o a veces infactible) capturar detalles importantes de un sistema mediante este enfoque.

Tomemos como ejemplo un sistema de cajas en un supermercado. Un sistema de este tipo podria modelarse con los modelos de teoría de colas. Una alternativa es el modelo Erlang (conocido también como M/M/s), que se basa en los siguientes supuestos sobre el proceso:

Bajo estos supuestos, este modelo permite derivar analiticamente la distribución de probabilidad del número de unidades en el sistema (esperando para iniciar el servicio y en servicio), cuando el sistema lleva operando un tiempo suficiente y se encuentra en estado estacionario.

Relajar estos supuestos vuelve más complejo el análisis. Pero quizas la mayor limitación de los modelos de colas es que se orientan a analizar el sistema en estado estacionario y no son adecuados para estudiar efectos transcientes.

Consideremos por ejemplo una caja de un supermercado. Para efectos de la simulacion, consideramos una tiempo promedio de 40 s para procesar un cliente. Típicamente, las llegadas a un supermercado en días de semana siguen un patrón sinusoidal, con peaks a la hora de almuerzo y en lo horarios despues del trabajo. Consideramos 4 bloques de 4 horas cada uno:

Bloque (segs)Tiempo promedio entre llegadas ()
0-14.4K100 segs
14.4K - 28.8K50 segs
28.8K-43.2K75 segs
43.2K-57.6K42 segs

La siguiente figura muestra la evolución del numero de personas en fila de la caja para un dia simulado. Se puede apreciar que los largos de fila son sustancialmente mayores en los horarios peak, como es esperable.

MM1_example

Nos interesa estudiar los tiempos de espera de los clientes. En un primer enfoque es utilizar modelos de colas, para lo cual es necesario separar el modelo en al menos cuatro periodos, para capturar las diferencias en las tasas de llegada. Para cada bloque, se considera el tiempo promedio entre llegadas (), el tiempo promedio de servicio ( segundos) y se calcula la utlizacion para cada bloque. Luego se utiliza el modelo de colas para estimar el tiempo promedio de espera basado en la ecuación dada por el modelo Erlang:

El segundo enfoque -- mas preciso -- es generar simulaciones como la que se describe en la figura y promediar los tiempos de espera de clientes que llegaron en cada bloque. La siguiente tabla compara las estimaciones de tiempos de espera para cada bloque usando estas metodologías.

BloqueapUtilTq (Erlang)Tq (Simulation)
0100400.4026.716.8
150400.80160.0115.4
275400.5345.760.7
342400.95800.0173.6

Los modelos de colas no capturan correctamente el tiempo de espera. Vemos, por ejemplo, que en el ultimo bloque el modelo sobreestima dramaticamente el tiempo de espera. Esto sucede porque el modelo Erlang predice lo que sucede cuando el sistema está estado estacionario, algo que no ocurre en este caso dado los cambios rápidos en el patrón de llegadas: el sistema "no alcanza" a llegar a estado estacionario. En el bloque 2, en cambio, el modelo Erlang subestima el tiempo de espera, esto debido a que este bloque arrastra clientes del peak alcanzado en el bloque anterior. En resumen, sistemas que no tienen una tasa homogenea de llegada hace que el analisis en estado estacionario sea menos util para predecir lo que sucede en la práctica.

Construyendo un simulador de eventos discretos

La implementación de un modelo de simulacion de eventos discretos considera lo siguientes elementos:

A modo de ejemplo, consideremos una cola con un unico servidor, donde los tiempos entre llegadas y el tiempo de servicio tienen alguna distribución conocida (no necesariamente exponencial). Este modelo es conocido como G/G/1 (el termino G indica una distribución general para llegada y tiempo de proceso). Definimos las siguiente variables:

El siguiente algoritmo describe la simulación:

Inicialización

En lo que resta, definimos como una variable aleatoria que describe el tiempo de servicio, i.i.d. para todas las llegadas. Definimos la v.a. para describir el tiempo entre llegadas, cuya distribución podria variar durante el tiempo. Finalmente, definimos como el tiempo de término de la simulacion (no hay llegadas despues de ). El sistema va iterando entre los siguientes casos hasta que se alcanza el fin de la simulación.

Caso 1: Proximo evento es una llegada al sistema. , .

Caso 2: Proximo evento es una salida. , .

Caso 3 : Se alcanzó el fin de la simulación, ,

Implementando un modelo de simulación

Los algoritmos antes descritos pueden ser implementados directamente en un lenguaje de programación, pero existen otras alternativas para acelerar la implementacion de estos modelos. Por ejemplo, hay software que combinan simulación con un despliegue gráfico que facilita la implementacion en base a modulos y permite "visualizar" los estados y procesos dentro de la simulacion. Algunas de las herramientas graficas son ProModel y Arena .

Otra alternativa es usar una API para distintos lenguajes de programación. Algunas recomendadas son Simpy que funciona en Python (y cubrimos en este curso) y Simulilnk para Matlab, pero existen muchos otros.

 

Analisis estadistico de los resultados de una simulación

La simulación nos entrega una muestra de valores de algun indicador del sistema que nos interesa evaluar. Dado que el sistema esta sujeto a variabilidad, este indicador varía de una simulación a otra. En general, nos interesa analizar la distribución de este indicador o alguna propiedad, como por ejemplo su valor esperado.

Consideremos el ejemplo de la cola con un servidor único, similar al que vimos anteriormente. Nos interesa estudiar el tiempo en que sale el n-esimo cliente del sistema. Esto se puede calcular de la siguiente manera:

El vector representa una muestra de los tiempos de salida del n-esimo cliente. Usando el teorema central del limite, tenemos que:

donde es el promedio de los y su desviación estándar. Con esto, podemos construir un intervalo de confianza dado por , donde es el percentil de la distribucion normal estandar correspondiente al nivel de confianza del intervalo que se busca lograr. Por ejemplo, para un intervalo de confianza 95% de confianza usamos .

Este resultado se puede utilizar para determinar cuantas corridas simular. Para esto, calculamos el número de simulaciones necesarias para obtener una precisión tal que el intervalo de confianza tenga un ancho , lo cual implica:

Para implementar esta regla:

Conclusiones

La simulacion de eventos discretos es una herramienta util para analizar procesos complejos que resultan dificil de modelar analiticamente. Estas permiten analizar sistemas con mayor detalle que lo que se puede lograr con los modelos de colas, pero tienen la desventaja que requieren mas trabajo para desarrollarlos y puede requerir mucho tiempo computacional correr simulaciones suficientes cuando se necesita evaluar muchos escenarios.