Sistemas de Eventos Discretos: Modelado, Simulación y Optimización de Colas

Sistemas de Eventos Discretos (SED): Modelado y Simulación

Un Sistema de Eventos Discretos (SED) es un modelo en el que el tiempo avanza de forma flexible, centrándose únicamente en los momentos en los que realmente sucede un cambio de estado. Los eventos son instantes específicos en el tiempo en los que ocurre un cambio de estado, aunque la duración real entre dos eventos consecutivos no implique un cambio en el sistema.

Principios de Gobierno de un SED

1. Condiciones de Ocurrencia: Se definen las circunstancias bajo las cuales un evento puede suceder.
2. Procedimientos de Cambio de Estado: Se especifican las acciones y transformaciones que el sistema experimenta como resultado de un evento.

Ventajas y Desventajas de los SED

• Ventajas:
  • Facilitan una mejor toma de decisiones al simular escenarios complejos.
  • Ilustran y simplifican la comprensión del comportamiento del sistema.
• Desventajas:
  • Su implementación puede ser peligrosa si no se realiza correctamente, llevando a resultados erróneos o modelos ineficientes.

Modelos Formales de Sistemas de Eventos Discretos

Los SED Formales se centran en describir el estado del sistema y el conjunto de relaciones lógicas que determinan la interacción entre sus entidades. Sus características clave incluyen:

• Independencia: Son independientes de los constructores y herramientas específicas de los entornos de simulación.
• Capacidad de Análisis: Deben permitir analizar el sistema y evaluar alternativas para simplificar el modelado.
• Facilidad de Traducción: Deben posibilitar una rápida traducción a las herramientas de los entornos de simulación.
• Modularidad: Deben soportar la división del modelo en subsistemas independientes.

Herramientas y Metodologías de Modelado

IDEF0: Integración de Definiciones para Modelado Funcional

IDEF0 es una metodología para representar de manera estructurada y jerárquica las actividades de un sistema. Aunque es útil para visualizar procesos y flujos de actividad antes de un modelado más detallado, no es completamente exhaustivo, al menos en su aspecto funcional.

• Utilidad: Es ideal para la fase inicial de diseño, permitiendo crear diagramas jerárquicos de actividades y flujos, lo que facilita la comprensión de los procesos.

Modelos de Flujos y Redes de Cola

Estos modelos permiten un estudio cuantitativo del sistema descrito, facilitando la obtención de resultados analíticos exactos en estado estacionario. Son fundamentales para evaluar el rendimiento de sistemas donde la espera y el servicio son críticos.

Grafos de Eventos

En los Grafos de Eventos, cada evento se representa por un nodo, y las conexiones entre ellos se indican mediante flechas. El proceso de simulación con grafos de eventos sigue estos pasos:

1. Inicialización: Establecer el estado inicial del sistema.
2. Avance del Tiempo: Mover el reloj de simulación hasta el inicio del próximo evento.
3. Ejecución de Postcondiciones: Realizar las acciones y cambios de estado asociados al evento.
4. Verificación y Bucle: Comprobar que el estado del sistema es correcto; si no, regresar al paso 2.

Diagramas de Ciclo de Actividad (ACD)

Los Diagramas de Ciclo de Actividad (ACD) son una representación gráfica del ciclo de actividades que realiza cada tipo de entidad en un sistema, así como de los estados pasivos (colas) por los que pasa.

Reglas para Dibujar un ACD

• Cada tipo de entidad tiene un ciclo de actividad propio.
• El ciclo consiste en una alternancia de actividades y colas.
• El ciclo debe ser cerrado.
• Las actividades se representan por rectángulos y las colas por círculos o elipses.
• Puede haber bifurcaciones para representar decisiones o caminos alternativos.

Formas de Representación en ACD

• La entidad está parada en un nodo, esperando iniciar una actividad.
• La entidad puede realizar actividades en una secuencia definida y cíclica.

Pasos para Modelar un SED Usando ACD

1. Definir las entidades que interactúan en el sistema.
2. Desarrollar un ACD para cada tipo de entidad.
3. Identificar los atributos relevantes de cada tipo de entidad.
4. Establecer la disciplina de las colas (ej., FIFO, LIFO, prioridad).
5. Definir la duración de cada actividad.
6. Definir los cálculos necesarios para los atributos y variables del sistema.
7. Especificar las estadísticas a recolectar durante la simulación.
8. Especificar las condiciones iniciales del sistema.

Redes de Petri (RdP)

Las Redes de Petri (RdP) son una herramienta de modelado gráfico y matemático para sistemas concurrentes, asíncronos y distribuidos. Sus componentes principales son:

• Nodos Lugar (P): Representan condiciones o estados del sistema (marcados con fichas).
• Nodos Transición (T): Representan eventos o acciones que pueden ocurrir.
• Arcos (A): Conectan lugares y transiciones, indicando el flujo de fichas.

La definición matemática de una Red de Petri se expresa como un quíntuplo: {P, T, A, W, M0}, donde W es la función de peso de los arcos y M0 es el marcado inicial. Además, se consideran las funciones de entrada E(Ti) y salida S(Ti) para cada transición.

Características y Beneficios de las Redes de Petri

• Definen qué eventos pueden ocurrir en un estado y cómo modifican el sistema.
• Establecen relaciones de causa y efecto entre eventos.
• Permiten modelar sistemas con procesos simultáneos (concurrencia).
• Utilizan un enfoque jerárquico para representar sistemas complejos.
• Son una herramienta visual con reglas de operación simples.
• Facilitan la actualización y el mantenimiento del modelo.

Arcos Inhibidores en Redes de Petri

Los arcos inhibidores son un tipo especial de arco que se habilita solo si el lugar conectado no tiene fichas. Son útiles para representar:

• Exclusión mutua (solo una actividad puede ocurrir a la vez).
• Condiciones de seguridad (evitar ciertos estados indeseables).

Medidas de Comportamiento y Teoría de Colas

Cálculos Analíticos Fundamentales

• R_i: Tiempo en cola de un cliente i.
• S_i: Tiempo de servicio de un cliente i.
• T_i = R_i + S_i: Tiempo total de un cliente i en el sistema.
• Q(t): Número de clientes en la cola en el instante de tiempo t.
• L(t): Número de clientes en el sistema (cola + servicio) en el instante t.

Teoría de Colas: Notación de Kendall

La notación de Kendall es un sistema estándar para describir las características de un sistema de colas, generalmente expresado como A/S/c/K/N/D. Un ejemplo sería M/M/3/20/1500/FIFO, donde:

• A: Distribución de los tiempos entre llegadas (ej., M para Poisson).
• S: Distribución del tiempo de servicio (ej., M para Exponencial).
• c: Número de servidores.
• K: Capacidad máxima del sistema (número total de clientes permitidos).
• N: Número de clientes en la población de origen (si es finita, si no se omite o se usa ∞).
• D: Disciplina de la cola (ej., FIFO para First-In, First-Out).

Fórmulas Clave en Sistemas de Colas M/M/1 (Ejemplos)

Para un sistema de cola simple M/M/1 (llegadas Poisson, servicio Exponencial, 1 servidor), algunas fórmulas importantes son:

• Tasa de Utilización (ρ):
  • ρ = λ / μ
  • Donde λ es la tasa media de llegadas (clientes por unidad de tiempo) y μ es la tasa media de servicio (clientes atendidos por unidad de tiempo).
  • μ se puede calcular como 1 / (tiempo medio de atención).
• Porcentaje de clientes que NO esperan en cola (P0):
  • P0 = 1 - ρ
• Número promedio de clientes en la cola (Lq):
  • Lq = ρ^2 / (1 - ρ)
• Tiempo promedio en cola (Wq):
  • Wq = ρ / (μ * (1 - ρ))
• Número promedio de clientes en el sistema (Ls):
  • Ls = λ / (μ - λ) = ρ / (1 - ρ)
• Tiempo promedio en el sistema (Ws):
  • Ws = 1 / (μ - λ) = Wq + 1/μ

Para calcular cuántos servidores se necesitan para que el tiempo de espera sea menor a un tiempo x, se utilizan las fórmulas específicas para sistemas M/M/c (múltiples servidores), donde la tasa de utilización se calcula como ρ = λ / (c * μ). La complejidad de estas fórmulas aumenta, y a menudo se recurre a tablas, software de simulación o métodos numéricos para su resolución.