11/58/58

Simulación por Eventos Discretos

Mg. Samuel Oporto Díaz Lima, 20 Septiembre 2005

SIMULACION DE SISTEMAS DISCRETOS

22/58/58

Objetivo de la Sesión• Identificar los elementos de un sistema de simulación por

eventos discretos asíncronos.• Identificar la relación que existe entre los elementos de un

sistema discreto.

33/58/58

Tabla de Contenido

1. Objetivo

2. Sincronización en modelos discretos

3. Simulación por eventos discretos

4. Diseño de Sistemas de Simulación Discreta

1. Gráfico del Sistema

2. Elementos del Sistema

3. Análisis del Sistema

4. Variables del Sistema

5. Diagramas de Flujo

6. Variables aleatorias

5. Bibliografía

44/58/58

Mapa Conceptual del Curso

Modelado y Simulación

Simulación X Eventos

Proyectos Simulación

Colas en Serie

Colas con un servidor

Colas en Paralelo

Inventarios Series de Nro. Aleato

Validación de Series

Generación de VA

55/58/58

Mapa Conceptual de la Sesión

síncrono

asíncrono

simulaciónpor eventos

discretos

e1

e3

e2

e4 e5

e6

Diagrama de relación de eventos

e1 e2 e1 e3 e3

Cola eventos

e1 e3e2 e1 e3

Simulación del Sistema

t t’

T T’

reloj

Flujo-grama

66/58/58

SINCRONIZACION EN MODELOS DISCRETOS

77/58/58

Simulación de Sistemas Discretos• Los SSD, evolucionan en el tiempo en forma discreta.• El estado del sistema sólo cambia en ciertos instantes de

tiempo, no de forma continua.

• Los cambios del sistema se traducen en el cambio de algún atributo de alguna entidad y ocurre en algún instante.

• Este cambio se denomina suceso o evento.• El tiempo entre dos instantes se denomina intervalo.

• Los objetos que operan en el sistema son las entidades.• El estado de una entidad se denomina actividad.• Un proceso describe la sucesión de estados de una entidad

88/58/58

Mecanismos de Reloj

Simulación Síncrona.• El tiempo de simulación avanza según pasos fijos Δt.

t, t + Δt, t + 2Δt, t + 3Δt, . . . . .

Simulación Asíncrona• El tiempo de simulación avanza del instante t al instante t’,

del siguiente suceso.

Δt Δt Δt Δt Δt Δt

tit tii tiii tiv tv

99/58/58

Simulación Síncrona

Basado en tiempo.

Inicializar

t = t + Δt

Generar Eventos

Evento 4

Evento 3

Evento 2

Evento 1

t < TmaxNoSi

1010/58/58

Simulación Síncrona• Se avanza en tiempo discretos Δt.• Cada vez que se incrementa el contador se verifica la cola

de eventos.• Sólo se puede detectar eventos que ocurren cada Δt.• Puede suceder que el tiempo para que ocurra el siguiente

evento sea muy grande en comparación de Δt.• Es usado frecuentemente en simulación de sistemas

dinámicos.

1111/58/58

Simulación Asíncrona

Basado en eventos.Inicializar

Determinar el siguiente evento

T = T( siguiente evento )

Evento 1

Cola de Eventos

caso = siguiente evento

Generar Nuevo Evento

Evento 4

Generar Nuevo Evento

Evento 3

Generar Nuevo Evento

Evento 2

Generar Nuevo Evento

Modificar Estadísticas

1212/58/58

Simulación Asíncrona• El cambio de estado del sistema se obtiene cuando ocurre

un suceso (evento).• Los periodos entre eventos son insignificantes, por lo que

no consumen tiempo de computo, aunque en la realidad consuman tiempo.

• Es la estrategia habitual de los lenguajes de simulación por eventos discretos.

1313/58/58

Ejercicio 1• Diga en el caso de un modelo de colas, ¿qué mecanismo

de reloj es recomendable?• En qué casos es recomendable usar el modelo síncrono.• En qué caso es recomendable usar el modelo asíncrono.

1414/58/58

SIMULACION POR EVENTOS DISCRETOS

1515/58/58

Simulación por Eventos Discretos• La simulación por eventos discretos es un paradigma de

simulación.• Está soportado por una serie de técnicas y tecnologías.• En este paradigma el sistema posee el estado EE en

determinado momento.• El estado EE del sistema es actualizado sólo cuando ocurre

algún evento e, mientras tanto el sistema (modelo) permanece igual.

• Si ocurren dos o más eventos e al mismo tiempo, se atiende al primero de ellos y el resto se almacenan en una cola de eventos.

1616/58/58

SED

e1 e2 e3 e4 e5 e6 e7

EE11 EE22 EE33 EE44 EE55 EE66 EE77

1717/58/58

Ejercicio 2• ¿Qué es un evento?

• ¿Cómo identificar un evento?

• ¿Cómo nos enteramos de que evento ha sucedido?

• ¿Un evento puede desencadena otro evento?

• ¿Se puede programar un evento? Para que ocurra en determinado tiempo.

• El evento ¿tiene un tiempo de duración?

• ¿Se puede presentar la siguiente situación entre eventos?

e1

e2

e4 e3

e5

1818/58/58

Imagen del Sistema• La imagen del sistema refleja el estado del sistema E en

cualquier momento (valores).• El progreso o desarrollo de la simulación va ligado a la

imagen del sistema.• La simulación progresa realizando el siguiente ciclo:

1. Decidiendo, de la imagen del sistema, cuando ocurrirá el siguiente evento e y de qué tipo de evento se trata.

2. Verificando si el evento e puede ser ejecutado,

3. En caso que se pueda, ejecutando aquellos cambios, implicados por el evento, en la imagen del sistema.

1919/58/58

Ejercicio 3• Indicar qué las variables y parámetros se puede identificar

en el caso de una cola simple:

1. Parámetros

2. Variables de exógenas

3. Variables de estado

4. Variables de estado de salida

2020/58/58

Reloj Maestro• La imagen del sistema deberá tener un número que

represente el tiempo real de la simulación (Reloj Maestro); el avanza con la sucesión de eventos en el modelo.

Tiempo de reloj:• Paso del tiempo, número de unidades de tiempo simulado

que han transcurrido (t). 

Tiempo de simulación:• Tiempo de reloj indicado en el problema (unidades), no

tiempo de cómputo (T).

2121/58/58

Tiempo en la simulaciónActualización del tiempo de reloj:• Avanzar reloj en el momento en que ocurra el

siguiente evento principal - simulación orientada al evento. (periodo avance variable)

• Avanzar a intervalos fijos y determinar si ocurre un evento o no - simulación orientada a intervalos.(periodo de avance fijo)

2222/58/58

Calendario de Evento• El Calendario de Eventos o Cola de Eventos es un arreglo

en el cual se registran los eventos potenciales o programados para ocurrir.

• En el calendario de eventos se guardarán los tiempos de ocurrencia de los eventos potenciales.

• En el Calendario de Eventos el puntero de inicio TOP nos señalará, siempre cuál es el evento siguiente.

¿Es una cola FIFO o LIFO?

2323/58/58

Cola de Eventos

PUSH Cada vez que ocurre un evento principal este es ingresado a la cola de eventos.

POP Cada vez que se atiende un evento principal este es retirado de la cola de eventos y procesado por el programa.

2424/58/58

Calendario de Eventos

TIEMPO DE LLEGADA

TIPO DE CLIENTE

TIPO DE EVENTO

TIEMPO DE SERVICIO

TE TLL TPREVTP TS

TIEMPO DEL PROXIMO EVENTO

Estructura de datos con la cual podremos representar a un objeto en el sistema:

2525/58/58

DISEÑO DE SISTEMAS DE SIMULACION

DISCRETA

2626/58/58

Estructura del Sistema1. Gráfico del Sistema.

2. Elementos del Sistema.– Entidades.– Atributos.– Actividades.

3. Análisis del Sistema– Eventos.– Eventos Principales– DRE

4. Variables – Tiempo.– Contadores– Estado del Sistema

5. Diagrama de Flujo– Programa Principal– Eventos Principales

6. Variables Aleatorias– Distribución de

Frecuencias

GR EVEL VA FL VA

2727/58/58

Solicitar al profesor el caso 1.

Librería COPIAMOSLAS24HORAS

2828/58/58

1. GRAFICO DEL SISTEMA

2929/58/58

1. Gráfico del Sistema• Intenta representar mediante un diagrama las entidades del

sistema y los objetos o recursos a ser procesados.• Se intenta representar las entradas y salidas del sistema.• Se intenta representar los eventos y las colas que se

pueden formar.• Se indica la distribución de probabilidad de las variables

aleatorias.

GR EVEL VA FL VA

3030/58/58

Ejemplo

fotocopiadora

documentosa copiar

trabajosterminados

3131/58/58

2. ELEMENTOS DEL SISTEMA1. Gráfico del Sistema.

2. Elementos del Sistema.

– Entidades.

– Atributos.

– Actividades.

3. Análisis del Sistema

– Eventos.

– Eventos Principales

– DRE

4. Variables

– Tiempo.

– Contadores

– Estado del Sistema

5. Diagrama de Flujo

– Programa Principal

– Eventos Principales

6. Variables Aleatorias

– Distribución de Frecuencias

3232/58/58

2. Elementos de un Sistema• Se puede representar mediante formulas matemáticas,

símbolos o palabras, pero en esencia es una descripción de:– Entidades: parte importante del sistema, agente que

tiene algún significado en el sistema.

– Atributos: característica principal de una entidad para el estudio que se hace del sistema.

– Actividades: interacción principal de una entidad con otra entidad en el sistema.

GR EVEL VA FL VA

3333/58/58

EjemploElementos Atributos Actividades

Documentos a Copiar

Tiempo de Llegada Llegar a la fotocopiadora

Tiempo de espera máxima Esperar en la colaEntregar requerimiento de copias

Tamaño de la cola Salirse de la cola por sobrepasar el tiempo de espera máxima

Abandonos de la cola Recepcionar las copias

Fotocopiadora Tiempo de servicio (fotocopiado)

Iniciar el copiado

Tiempo de inicio de servicio Esperar nuevos requerimientos de copiado

Estado: Operativa, 1 = Ocupada, 0 = Desocupada

Terminar el copiado

Tiempo desocupada

GR EVEL VA FL VA

3434/58/58

3. ANALISIS DEL SISTEMA

e1

e3

e2

e4 e5

e6

3535/58/58

3. Análisis del Sistema• Eventos

• Eventos Principales

• Diagrama de Relación de Eventos

GR EVEL VA FL VA

3636/58/58

Sucesos (Eventos )• Los eventos son sucesos que marcan el inicio o fin de una

actividad.• Los eventos pueden:

– Crear una entidad.– Destruir una entidad.– Cambiar un atributo de una entidad.

GR EVEL VA FL VA

3737/58/58

Sucesos (Eventos )Los eventos se pueden clasificar en:

– Evento Principal: Es aquel evento que no necesita de otro evento para llevarse a cabo. Es un Evento independiente.

– Evento secundario: Es aquel evento que necesita la ocurrencia de por lo menos un evento para que pueda llevarse a cabo. Evento dependiente.

GR EVEL VA FL VA

3838/58/58

EjemploEventos del Sistema

1. Llegar al sistema

2. Ingresar a cola

3. Salir de cola

4. Iniciar el servicio

5. Fin del servicio

6. Inicio de espera de la fotocopiadora

7. Fin de espera

8. Salir del sistema

GR EVEL VA FL VA

3939/58/58

Ejemplo

Eventos Principales

1. Llegar al sistema (arribo) 2. Ingresar a cola

3. Salir de cola

4. Iniciar el servicio

5. Fin del servicio 6. Inicio de espera de la fotocopiadora

7. Fin de espera

8. Salir del sistema

GR EVEL VA FL VA

4040/58/58

Eventos Concurrentes• Eventos concurrentes son aquellos que se dan en una

misma unidad de tiempo.

– Entre Eventos Principales. Se producen eventos concurrentes simplemente por azar.

– Entre Eventos Secundarios. Se producen eventos concurrentes debido a que un cambio implica otros cambios que ocurren al mismo tiempo.

GR EVEL VA FL VA

4141/58/58

Eventos Concurrentes (Ejemplos)

• Entre eventos principales.– Llegada de dos elementos a la cola.– Llegada de un elemento a la cola y el fin de atención.

• Entre eventos secundarios.– Fin de atención de una máquina, se inicia una nueva

atención si hay elementos en la cola.– Salida del cliente atendido del sistema, se iniciar la

atención de un nuevo cliente, si hay personas en la cola.

GR EVEL VA FL VA

4242/58/58

Eventos Concurrentes• Se debe tener especial cuidado en que la secuencia de

cambios (prioridad de elección del siguiente evento) esté de acuerdo como la secuencia deseada para dichos casos.

• En caso contrario podría alterarse el proceso.

GR EVEL VA FL VA

4343/58/58

Ejemplo• Llegada simultanea de dos personas.• Llegada y fin de servicio• Fin de servicio e inicio de servicio• Fin de servicio y salir del sistema• ..• ..• ..

GR EVEL VA FL VA

4444/58/58

Diagrama de Relación de Eventos

• Se elaboran solo para los eventos principales.• En un DRE un evento principal, no puede figurar otro

evento principal, ya que los eventos principales son independientes

• Los DRE, nos muestran la relación entre un evento principal y sus secundarios, así como la relación entre eventos secundarios.

• Un evento principal solo puede figurar en un DRE de otro evento principal, si la unión se realiza con una línea punteada que indica la realización a futuro de ese evento no en ese instante.

GR EVEL VA FL VA

4545/58/58

EjemploDiagrama de Relación de Eventos

1. Llegar al sistema (arribo)

1

7

2

4 6

1. Llegar al sistema (arribo) 2. Ingresar a cola3. Salir de cola4. Iniciar el servicio5. Fin del servicio6. Inicio de espera de la fotocopiadora7. Fin de espera8. Salir del sistema

1

4646/58/58

Ejemplo• Diagrama de Relación de Eventos

5. Fin del servicio

5

6

3 4 5

8 1. Llegar al sistema (arribo) 2. Ingresar a cola3. Salir de cola4. Iniciar el servicio5. Fin del servicio6. Inicio de espera de la fotocopiadora7. Fin de espera8. Salir del sistema

4747/58/58

4. VARIABLES

4848/58/58

Estadísticos de SalidaLos estadísticos más usados son los siguientes:a) Contador: Del número de entidades de cierto tipo, del

número de veces que ocurre algún evento, etc.b) Utilización: De una unidad del equipo (en términos de la

fracción de tiempo que está en uso).c) Ocupación: De un equipo de múltiples unidades (número

promedio de unidades en uso)d) Distribución: De las variables aleatorias como tiempos de

espera, tiempos en el sistema, junto con sus medias, des viaciones estándares e incluso máximos y mínimos observados.

¿PARA QUE NOS SIRVEN ESTOS DATOS?

4949/58/58

5. DIAGRAMAS DE FLUJO

5050/58/58

Inicializar

Inicio

Fin

siguiente evento

Arribo Fin Servicio

Estadísticas

Fin Corrida

Cálculos Parciales

Fin Simulación

Cálculos Finales

Reportes

Flujo-Grama Principal

5151/58/58

Flujo-Grama Arribo

N = N + 1

Arribo

Return

Programar Fin de Servicio (TS1)

Ocupado = 1

Programar Nuevo Arribo (TELL)

Cola > 0

Ocupado = 1

si

nosi

Cola = Cola + 1

no

5252/58/58

Flujo-Grama Fin Servicio

Fin Servicio

Return

Programar Fin de Servicio (TS1)

Ocupado = 1

Cola = Cola - 1

Cola > 0

Ocupado = 1

no

sisi

Ocupado = 0

no

5353/58/58

Estructura Programa de Simulación

Programa Principal

Generación estadísticas

Condiciones iniciales

Solución del modelo

Variables aleatorias

Números aleatorios

Generación reportes

5454/58/58

5. VARIABLES ALEATORIAS

5555/58/58

Variables Aleatorias• Indicar los parámetros para las curvas de distribución de

frecuencias asociadas a cada variable.

Exponencial(1)Poisson(3.5)

5656/58/58

BibliografíaSimulación de Sistemas Discretos. Shannon. Capítulo 1.

Simulación de Sistemas Discretos. Barceló. Capítulo 1.

5757/58/58

PREGUNTAS