Sesión 17 SIMULACIÓN DE REDES DE PETRI

Contenido

Simulación y herramientas Procedimiento de simulación Redes coloreadas Ejemplos

Simulación y herramientas Un modelo de eventos discretos se compone de bloques de un sistema y una caledarización o reglas que gobiernan el flujo de trabajo en un FMS. La simulación de eventos discretos es un proceso en el cual se reproduce el comportamiento de un sistema que se rige por eventos discretos tal como los eventos de un FMS. Uno de los objetivos de la simulación es e de obtener datos cualitativos y cuantitativos de un proceso para predecir el comportamiento y rendimiento del sistema.

Simulación y herramientas La simulación tiene dos motivaciones principales: Prototipos rápidos para determinar el comportamiento del sistema, y predicción de rendimiento. Algunas medidas de interés son el flujo de material, utilización de recursos, capacidad de buffers, resistencia a fallas y efectos de las misma. El modelo de software debería de capturar toda la dinámica e interacciones del sistema real. Dado que los sistemas reales de manufactura son difíciles de construir, la simulación es un medio para predecir con precisión, y elegir el mejor diseño entre estas alternativas.

Procedimiento de simulación de eventos discretos En la simulación de eventos discretos, el modelo contiene entidades u objetos, atributos, eventos, actividades y relaciones entre ellos. La colección de entidades y su estado define el estado general del sistema. Los cambios son manejados por ocurrencias de eventos, generalmente asíncronas. El sistema de manufactura, una entidad puede ser una máquinas, un robot, material (trabajo en progreso), y un controlador con su itinerario.

Procedimiento de simulación de eventos discretos Los atributos de una máquina incluyen su ritmo de operación, la naturaleza de la operación y su confiabilidad. Ejemplos de eventos son la llegada de materia prima, carga, descarga, cambio de herramienta y el comienzo de una operación.

La simulación del sistema de eventos discretos se involucran los siguientes pasos: Definición de requerimientos ●

objetivos

y

especificación

de

Determinar la especificación de requerimientos y objetivos de simulación del sistema de manufactura que se estudia o diseña. ●

Los objetivos son para determinar el mejor sistema entre diversas alternativas y para investigar el comportamiento y rendimiento del sistema. ●

Se selecciona el nivel de detalle apropiado para empatar el objetivo de modelado. ●

Por ejemplo, podría optimizar el rendimiento un FMS individual o para mejorar la distribución de las celdas en una planta de fabricación. Ambientes de simulación y lenguajes relacionados podrían ser usados para formular requerimientos, aunque podrían diferir del lenguaje usado para construir el modelo de simulación.

Desarrollo del modelo Formular un modelo el cual podría ser una Red de Petri u otro modelo. Por ejemplo, un modelo de manejo de solicitudes, máquinas de estados y un modelo orientado a objetos. La construcción de un modelo puede ser una tarea difícil, requiendo el entendimiento del modelador del problema y experiencia en modelado. El modelo ha capturado la esencia del sistema real sin un detalle excesivo.

Desarrollo del modelo Los modelos jerárquicos que podrían representar los diferentes niveles de detalle son requeridos para un sistema FMS de gran escala. Los resultados de simulación pueden ser presentados a planeadores y administradores para la toma de decisiones y servir de base para el diseño y la implementación en tiempo real. Premisas y simplificaciones tienen que ser justificadas.

Construcción del modelo computacional Construir una representación computacional del modelo. Por ejemplo, programar una formulación matemática usando un lenguaje de simulación o algún lenguaje de programación de propósito general, o construir un modelo gráfico en un editor gráfico en el cual los algoritmos de simulación están empotrados y no aparente a un usuario.

Colección de datos

Analizar todos los parámetros involucran en el modelo y serie de especificaciones, y adquirir datos basados en conteos, experiencia y desde la simulación a bajo nivel. La calidad de datos tiene directo impacto en los resultados obtenidos desde la simulación. Es necesario tener cuidado en este proceso.

Ejecuciones de simulación Se trata de ejecutar el modelo computacional o simulador para verificar que tan bien emula la realidad. El proceso de verificación del modelo asegura que la simulación modela apropiadamente al sistema. Si la estructura lógica, entradas y salidas son representadas correctamente en el modelo computacional, entonces es cuando se completa la verificación. Se usan casos simples y sentido común en el proceso. Técnicas de animación pueden facilitar el entendimiento de la dinámica. Finalmente, la validación asegura que el modelo es una buena representación de la realidad.

Evaluación de resultados de simulación Se trata de obtener y evaluar los resultados de la simulación. Este es una etapa de análisis estadístico aplicado a los resultados de la simulación y para validarlos. El sistema es simulado dentro de un rango aceptable de parámetros operacionales y configuración optima pueden ser determinados.

Documentación Documentar los datos de entrada, métodos , herramientas de simulación, tiempo computacional y los resultados. Los resultados deberán ser presentados en grafos para patrones y tendencias sobre los parámetros de interés. El uso de técnicas de descripción formal en la construcción de los modelos de simulación, permite la verificación de estos modelos, con respecto para sus propiedades de comportamiento, usando técnicas matemáticas estrictas. Por ejemplo, las redes de Petri permiten la construcción de modelos de simulación, de igual manera que su verificación formal a través de métodos de análisis.

Documentación Los resultados de simulación deben de ser comparados con los datos del mundo real, si están disponibles, para los sistemas existentes, o con los resultados producidos por modelos teóricos. Para sistemas complejos, obteniendo soluciones analíticas para modelos que involucran todas las caras de la funcionalidad de un sistema es, a menudo, difícil de hacer. Los modelos de la teoría de filas son usados, en la mayoría de los casos, para obtener los resultados de referencia. Estos efectos se deben al periodo de transición, lo cual sigue el inicio de la ejecución de la simulación,e influido por la naturaleza del sistema simulado tal como el ambiente de simulación.

Modelos de simulación, esquemas y herramientas

Hay tres tipos básicos de modelos de sistema de eventos discretos: Modelos de filas, modelos de transición de estados cuyos representantes son las máquinas de estados y redes de Petri, y los modelos orientados a objetos.

Modelos de filas En modelo de filas de un sistema de manufactura puede ser obtenido si se tratan los recursos tales como máquinas y robots como servidores, áreas de almacenamiento, bandas transportadoras como buffers (filas), y trabajos o partes como clientes. Cuando se tienen premisas estrictas, quizás no realistas o simplificadas, que se hacen para el modelo, los resultados analíticos pueden ser derivados de la evaluación del rendimiento. Cuando las premisas no pueden mantenerse, la simulación o los métodos de aproximación pueden ser usados para derivar los resultados deseados.

Modelos de transición de estados Los modelos típicos de transición de estados incluyen máquinas de estados finitos y redes de Petri. Cuando un sistema es complejo, la representación gráfica de una máquina de estados podría no ser práctica o posible debido a la explosión exponencial a que estaría sujeto el problema. Note que el número de estados está relacionado con un crecimiento exponencial con el número de componentes en el sistema.

Es posible incorporar el tiempo y efectos de retardo en la simulación. Hay dos formas de considerar el efecto del tiempo: El tiempo asociado con los eventos: por ejemplo, aquellos eventos que tienen un tiempo fijo de ejecución como las operaciones de mantenimiento programadas, cargas y descargas de material, etc. Tiempo y probabilidad asociado con los estados: tiempo fijo o aleatorio de retardo asignado a cada estado, implicando que el retardo en el momento en que el sistema entra al estado para pasar antes del disparo a eventos futuros.

Modelos orientados a objetos Un sistema de manufactura puede ser vista como una colección de objetos con reglas que gobiernan su dinámica e interacciona para generar los objetos deseados (producto). Los objetos pueden ser representados gráficamente y ser guardados en bases de datos como miembros de clase similar y compartir propiedades comunes. Tales objetos pueden ser construidos a partir de una base de datos para representar un modelo de sistema real. Estos modelos pueden crear librerías y ser reutilizadas como componentes de simulación.

Esquemas de simulación y herramientas Un sistema de simulación puede ser usado para la calendarización de eventos o para un esquema orientado a procesos. Un proceso puede ser tratado como una secuencia de funciones o eventos disparados por una entidad

En un esquema de calendarización de eventos, el proceso de simulación funciona con los siguientes pasos: 1. Se definen las variables iniciales de las variables, incluyendo los eventos posibles y sus tiempos de aparición en algo llamado 'Lista de eventos calendarizados'. Los eventos son ordenados por el sistema en base que el primero es que tienen menor calendarización. 2. Se remueve la primera entrada de la lista de eventos calendarizados. 3. Tiempo de reloj progresa para remover el tiempo calendarizado del evento.

4. Actualiza el estado del sistema debido a la ocurrencia del evento 5. Borra cualquier entrada correspondiente de eventos imposibles en el nuevo estado de la Lista. 6. Agrega nuevos eventos posibles y su calendarización de tiempos de ocurrencia. 7. Re-ordena La lista actualizada basado en el criterio de primero el de menor tiempo de calendarización y regresa al paso 2.

Unidades de tiempo Marcado

Función F Función Q Función A

0

(1,2,3,0,0)' (1,0)

(1,0)

(0,0)

1

(0,1,2,0,0)'

(0,1)

(0,2)

(1,0)

2

(0,1,2,1,0)'

(0,0)

(0,1)

(1,1)

3

(1,1,2,0,1)'

(1,0)

(1,0)

(1,2)

Descripción de las características de un paquete de simulación de redes de Petri Leer y almacenar una red de Petri Manejo de transiciones Resolución de conflictos Tiempo mínimo Marcado nuevo

Redes de Petri de alto nivel Las redes de Petri coloreadas son creadas para visualizar un cambio de estado de eventos al cambio de tokens a través de la red. Tales redes son útiles para el modelado de redes grandes, con múltiples tokens. Otras redes de alto nivel incluyen las asociaciones a redes de transición por predicado y redes orientadas a objetos con sus ambientes de desarrollo.

Redes coloreadas Las redes de Petri coloreadas (CPN) pertenecen a la familia de las PN, la diferencia viene marcada por las consideraciones en CPN de colores y de funciones lineales asociadas a sus arcos. Los tokens de color pueden representar un atributo o distintivo, si es necesario definir dos atributos entonces surge la idea de colores compuestos. Una transición en CPN está en estado ENABLED si todos sus nodos de entrada contiene en un número de colores igual o mayor que los definidos por fi donde fi es una función lineal asociada al nodo pi con la transición tj. Entonces además del concepto de color, estas redes manejan una función asociada para los elementos de las funciones I, O de la PN.

Ejemplo de una Red de Petri coloreada

Protocolo simple

Protocolo simple

Plazas Plazas

Protocolo simple

Transiciones Transiciones

Protocolo simple Place

Tipo Tipo (color) (color)

Protocolo simple Place

Marcado Marcado inicial inicial

Marcado para Envio INTxDATA

Send

8

1 ` (1,"Modellin") + 1 ` (2,"g and An") + 1 ` (3,"alysis b") + 1 ` (4,"y Means ") + 1 ` (5,"of Colou") + 1 ` (6,"red Petr") + 1 ` (7,"i Nets##") + 1 ` (8,"########")

Número Número de de tokens tokens Multi-set Multi-set de de Colores Colores de de tokens tokens

Protocolo simple

Inscripciones Inscripciones de de arco arco

Protocolo simple

Protocolo simple

Interface Interface de de las las plazas plazas de de buffer buffer

Protocolo simple

Paquetes Paquetes aa enviar enviar

Protocolo simple

Contador Contador

Protocolo simple

Contador Contador

Protocolo simple

Recepción Recepción de de datos datos

Protocolo simple

Envía paquetes

p = "Modellin"

1`(1,"Modellin") + 1`(2,"g and An") 8 + 1`(3,"alysis b") + 1`(4,"y Means ") + 1`(5,"of Colou") + 1`(6,"red Petr") + 1`(7,"i Nets##") + 1`(8,"########")

INTxDATA ●

El enlace



se habilita.

Send (1,p) (n,p)

INTxDATA 



Cuando el enlace ocurre, agrega un token a la plaza A.

Send Packet

(n,p)

A 1

Esto representa que el paquete (1,"Modellin") es enviado a la red.

n 1



El paquete no es removido de la plaza INT Send y el contador NextSend no cambia.

NextSend

n=1

1 1`1

1`(1,"Modellin")

Envía paquetes

p = "Modellin"

1`(1,"Modellin") + 1`(2,"g and An") 8 + 1`(3,"alysis b") + 1`(4,"y Means ") + 1`(5,"of Colou") + 1`(6,"red Petr") + 1`(7,"i Nets##") + 1`(8,"########")

INTxDATA ●

El enlace



se habilita.

Send (1,p) (n,p)

INTxDATA 



Cuando el enlace ocurre, agrega un token a la plaza A.

Send Packet

(n,p)

A 1

Esto representa que el paquete (1,"Modellin") es enviado a la red.

n 1



El paquete no es removido de la plaza INT Send y el contador NextSend no cambia.

NextSend

n=1

1 1`1

1`(1,"Modellin")

Protocolo simple

Transmite paquete

r ∈ 1. .10 if Ok(s,r) then 1`(n,p) else empty

INTxDATA

Transmit Packet

(n,p)

A 1

B

1`(1,"Modellin")

s=8

s 8

n = 1, p = "Modellin"

●

INTxDATA

RP

1

1`8

Int_0_10

Todos los enlaces habilitados son de la forma: ●



●

donde

r ∈ 1. .10

Pérdida de paquetes

●

●

if Ok(s,r) then 1`(n,p) else empty

La función Ok(s,r) verifica que r ≤ s. ● para r ∈ 1. .8, Ok(s,r)=true. El token se mueve de A a B. Esto significa que el paquete se ha transmitido exitosamente en la red. ● Para r ∈ 9. .10, Ok(s,r)=false. Ningún token se agrega a B. Esto significa que el paquete se ha perdido El simulador CPN hace elecciones aleatorias entre los enlaces: 80% de posibilidad para una transferencia exitosa.

Protocolo simple

""

Recibe paquete

Received

1 1`""

DATA

●

El número de paquetes que llegan n y el número de paquetes esperados k se comparan.

INTxDATA

str (n,p)

B

if n=k andalso pstop then str^p else str

1 1`(1,"Modellin")

k 1

NextRec INT 1 1`1

if n=k then k+1 else k

C INT

Receive Packet if n=k then k+1 else k

Número correcto de paquetes ◆

El dato en el paquete es concatenado al dato que ya se ha recibido.

Received

1 1`"Modelling and An"

1 1`"Modelling and An"

1`(3,"alysis b")

B

1

str

(n,p)

if n=k andalso pstop then str^p else str

1 1`(3,"alysis b")

◆

◆

El contador NextRec se incrementa en uno. Un Reconocimiento es enviado. Contiene el número del siguiente paquete que el receptor desea obtener.

1

1`"Modelling and Analysis b"

k

1`3

1

1

NextRec 1 1`3

1`4

1

if n=k then k+1 else k

C

Receive Packet 1 1`4 if n=k then k+1 else k

Número de paquete equivocado ◆

Received 1 1`"Modelling and An"

1`(2,"g and An") (n,p) 1 B

El dato en el paquete es ignorado

1 1`"Modelling and An"

if n=k andalso pstop then str^p else str

str

1 1`(2,"g and An")

◆

◆

El contador NextRec no cambia. Un Reconocimiento es enviado. Contiene el número del siguiente paquete que el recpetor desea obtener.

1

1`"Modelling and An"

k

1`3

1

1

NextRec

1`3

1 1`3

if n=k then k+1 else k

C

1

Receive Packet 1 1`3 if n=k then k+1 else k

Número de paquete equivocado ◆

El dato en el paquete es ignorado

◆

El contador NextRec no cambia.

◆

Un Reconocimiento es enviado. Contiene el número del siguiente paquete que el recpetor desea obtener.

Protocolo simple

Transmite Reconocimiento 8

RA

1 1`8

Int_0_10 s

D INT

●

●

if Ok(s,r) then 1`n else empty

Transmit Acknow.

n

C INT 1 1`2

Esta transición trabaja de manera similar como un paquete transmitido. El marcado de RA determina el ritmo de éxito.

Protocolo simple

Recibe Reconocimiento 1

NextSend INT 1 1`1 k

n

Receive Acknow.

n

D INT 1 1`2

Cuando un reconocimiento llega al origen, Este es usado para actualizar el contador NextSend. ●

En este caso, el valor del contador se convierte en 2, y por lo tanto se empezará a enviar el paquete número 2.

Modules

Tres módulos diferentes Receiver

Sender

I/O

Network



Out

In

Out

In

Out

In

In

Out

Las plazas de interface son usadas para intercambiar tokens entre módulos

Vista abstracta Protocolo

HS

HS

HS

Sender

Network

Receiver

 

Substitución de transiciones referidas a módulos Plazas de contacto se relacionan a las plazas de interface.

Módulos pueden ser reusados

Protocolo

HS Receiver HS

HS

Sender

Network HS Receiver

Protocolo con múltiples receptores Network Sender

Receiver I/O

Out In Out

In

Out In Out

In

Out In

Herramientas y aplicaciones

Herramientas ●

Design/CPN fue desarrollado a finales de los 80s y principios de los 90s. ●

●

●

Era uno de los paquetes mas usados para simular redes de Petri Fue reemplazado por CPN Tools

CPN Tools es la siguiente generación de soporte para redes de Petri coloreadas. ●

Es una herramienta para editar, simular y analizar redes de Petri coloreadas.

●

UPPAAL es una caja de herramientas para la verificación de sistemas en tiempo real desarrollado por la Uppsala University y Aalborg University ●

●

Está diseñado para modelar redes de automatas temporizados extendidos, con variables enteras, tipos de datos estructurados y canales de sincronización.

TAPAAL es una herramienta para el modelado, simulación y verificación de Redes de Petri con Arcos temporizados desarrollado también por el Departamento de Computación de la Universidad Aalborg en Dinamarca.

CPN Tools ●

La funcionalidad de CPN Tools es: ● ● ● ● ● ●

Editar y verificar sintaxis de Redes de Petri. Simulación interactiva y automática. Construcción y análisis de espacios de estado. Comunicación con otras herramientas. Simulación basada en análisis de rendimiento. Animación gráfica de resultados de simulación.

UPPAAL UPPAAL usa una arquitectura cliente-servidor, separando la herramienta en una interface gráfica de usuario y una máquina de verificación del modelo. La interface de usuario, o cliente, es implementada en java y el motor, o servidor, es compilado en las diferentes plataformas (Linux, Windows, Solaris) No está explicitamente diseñado para modelar redes de Petri

Conclusiones Hemos visto estrategias para preparar un modelo de una red de Petri para simulación Como se hace la construcción de un modelo computación de la red Se abordaron ejemplos de simulación Algunos paquetes que realizan simulación de sistemas discretos

Próxima sesión

Aplicaciones en Sistemas de Manufactura