Simulación de eventos discretos

El estado de un sistema es un conjunto de variables que captura las propiedades más relevantes del sistema que se va a estudiar. La trayectoria del estado a lo largo del tiempo, S(t), se puede representar matemáticamente mediante una función escalón cuyo valor puede cambiar cada vez que ocurre un evento.

La simulación debe registrar el tiempo actual de simulación, en las unidades de medida adecuadas para el sistema que se está modelando. En las simulaciones de eventos discretos, a diferencia de las simulaciones continuas, el tiempo avanza a saltos porque los eventos son instantáneos: el reloj avanza hasta el inicio del siguiente evento a medida que avanza la simulación.

La simulación mantiene al menos una lista de eventos de simulación. A esta se la denomina a veces conjunto de eventos pendientes, ya que enumera los eventos que están pendientes como resultado de un evento simulado previamente, pero que aún no se han simulado. Un evento se describe mediante el momento en que ocurre y un tipo, que indica el código que se utilizará para simularlo. Es común que el código del evento esté parametrizado; en ese caso, la descripción del evento también contiene parámetros para dicho código. La lista de eventos también se conoce como lista de eventos futuros (FEL) o conjunto de eventos futuros (FES). ^{[ 3 ] [ 4 ] [ 5 ] [ 6 ]}

Cuando los eventos son instantáneos, las actividades que se extienden en el tiempo se modelan como secuencias de eventos. Algunos marcos de simulación permiten especificar el tiempo de un evento como un intervalo, indicando la hora de inicio y la hora de finalización de cada evento.

Los motores de simulación de un solo hilo basados ​​en eventos instantáneos tienen un único evento actual. En cambio, los motores de simulación multihilo y los que admiten un modelo de eventos basado en intervalos pueden tener varios eventos actuales. En ambos casos, existen problemas importantes de sincronización entre los eventos actuales.

El conjunto de eventos pendientes se organiza típicamente como una cola de prioridad , ordenada por tiempo de evento. ^{[ 7 ]} Es decir, independientemente del orden en que se agregan los eventos al conjunto de eventos, se eliminan en orden estrictamente cronológico. Se han estudiado varias implementaciones de colas de prioridad en el contexto de la simulación de eventos discretos; ^{[ 8 ]} las alternativas estudiadas han incluido árboles splay , listas de salto , colas de calendario , ^{[ 9 ]} y colas de escalera. ^{[ 10 ] [ 11 ]} En máquinas masivamente paralelas , como CPU multinúcleo o de muchos núcleos , el conjunto de eventos pendientes se puede implementar basándose en algoritmos no bloqueantes , para reducir el costo de sincronización entre los hilos concurrentes. ^{[ 12 ] [ 13 ]}

Normalmente, los eventos se programan dinámicamente a medida que avanza la simulación. Por ejemplo, en el ejemplo del banco mencionado anteriormente, el evento LLEGADA DEL CLIENTE en el tiempo t, si la COLA DE CLIENTES estuviera vacía y el CAJERO estuviera inactivo, incluiría la creación del evento subsiguiente SALIDA DEL CLIENTE que ocurriría en el tiempo t+s, donde s es un número generado a partir de la distribución TIEMPO DE SERVICIO.

La simulación requiere generar variables aleatorias de diversos tipos, según el modelo del sistema. Esto se logra mediante uno o más generadores de números pseudoaleatorios . El uso de números pseudoaleatorios, en lugar de números aleatorios verdaderos, resulta ventajoso si se necesita repetir la simulación con el mismo comportamiento.

Uno de los problemas de las distribuciones de números aleatorios utilizadas en la simulación de eventos discretos es que las distribuciones de estado estacionario de los tiempos de los eventos pueden no conocerse de antemano. Como resultado, el conjunto inicial de eventos colocados en el conjunto de eventos pendientes no tendrá tiempos de llegada representativos de la distribución de estado estacionario. Este problema se suele resolver mediante el remuestreo del modelo de simulación. Solo se realiza un esfuerzo limitado para asignar tiempos realistas al conjunto inicial de eventos pendientes. Sin embargo, estos eventos programan eventos adicionales y, con el tiempo, la distribución de los tiempos de los eventos se aproxima a su estado estacionario. Esto se denomina remuestreo del modelo de simulación. Al recopilar estadísticas del modelo en ejecución, es importante o bien descartar los eventos que ocurren antes de que se alcance el estado estacionario o bien ejecutar la simulación durante el tiempo suficiente para que el comportamiento de remuestreo sea superado por el comportamiento de estado estacionario. (Este uso del término remuestreo puede contrastarse con su uso tanto en estadística como en informática ).

La simulación suele registrar las estadísticas del sistema , que cuantifican los aspectos de interés. En el ejemplo del banco, interesa registrar los tiempos de espera promedio. En un modelo de simulación, las métricas de rendimiento no se derivan analíticamente de distribuciones de probabilidad , sino que se calculan como promedios de diferentes ejecuciones del modelo. Generalmente, se construyen intervalos de confianza para evaluar la calidad de los resultados.

Dado que los eventos se inician automáticamente, teóricamente una simulación de eventos discretos podría ejecutarse indefinidamente. Por lo tanto, el diseñador de la simulación debe decidir cuándo finalizará. Las opciones típicas son "en el tiempo t", "después de procesar n eventos" o, de forma más general, "cuando la medida estadística X alcance el valor x".

Pidd (1998) propuso un enfoque trifásico para la simulación de eventos discretos. En este enfoque, la primera fase consiste en saltar al siguiente evento cronológico. La segunda fase consiste en ejecutar todos los eventos que ocurren incondicionalmente en ese momento (denominados eventos B). La tercera fase consiste en ejecutar todos los eventos que ocurren condicionalmente en ese momento (denominados eventos C). El enfoque trifásico es un refinamiento del enfoque basado en eventos, en el que los eventos simultáneos se ordenan para optimizar el uso de los recursos informáticos. Este enfoque trifásico se utiliza en varios paquetes de software de simulación comerciales, pero desde la perspectiva del usuario, los detalles del método de simulación subyacente suelen estar ocultos.

Los métodos de simulación son especialmente útiles para diagnosticar problemas en entornos complejos. La teoría de las restricciones ilustra la importancia de comprender los cuellos de botella en un sistema. Identificar y eliminar estos cuellos de botella permite mejorar los procesos y el sistema en general. Por ejemplo, en las empresas manufactureras, los cuellos de botella pueden deberse a un exceso de inventario, sobreproducción , variabilidad en los procesos y variabilidad en el enrutamiento o la secuenciación. Al documentar con precisión el sistema mediante un modelo de simulación, es posible obtener una visión global del mismo.

Un modelo funcional de un sistema permite a la gerencia comprender los factores que influyen en su desempeño. Se puede crear una simulación que incluya diversos indicadores de desempeño , como la utilización de la mano de obra, la tasa de entregas a tiempo, la tasa de desperdicio, los ciclos de efectivo, etc.

Un quirófano suele ser compartido por varias especialidades quirúrgicas. Al comprender mejor la naturaleza de estos procedimientos, es posible aumentar el flujo de pacientes. ^{[ 14 ]} Ejemplo: Si una cirugía cardíaca dura en promedio cuatro horas, cambiar la disponibilidad del quirófano de ocho a nueve horas no aumentará el flujo de pacientes. Por otro lado, si una intervención de hernia dura en promedio veinte minutos, proporcionar una hora adicional tampoco generará un aumento en el flujo de pacientes si no se considera la capacidad y el tiempo promedio de espera en la sala de recuperación.

Muchas ideas para mejorar sistemas se basan en principios sólidos y metodologías probadas ( Lean , Six Sigma , TQM , etc.), pero no logran mejorar el sistema en su conjunto. Un modelo de simulación permite al usuario comprender y probar una idea de mejora del rendimiento en el contexto del sistema global.

La modelización mediante simulación se utiliza habitualmente para modelar posibles inversiones. Mediante la modelización de inversiones, quienes toman las decisiones pueden tomar decisiones informadas y evaluar posibles alternativas.

La simulación de eventos discretos se utiliza en redes informáticas para simular nuevos protocolos y diferentes arquitecturas de sistema (distribuidas, jerárquicas, centralizadas, P2P) antes de su implementación real. Es posible definir diferentes métricas de evaluación, como tiempo de servicio, ancho de banda, paquetes perdidos, consumo de recursos, etc.