Post on 10-Oct-2015
transcript
5/20/2018 Clase Redes Petri
1/36
5/20/2018 Clase Redes Petri
2/36
Qu son las redes de Petri?
Las redes de Petri son herramientas graficaspara la descripcin y anlisis de procesosconcurrentes que surgen de sistemasdinmicos con muchos componentes. Losgrficos, en conjunto con las reglas para surefinamiento, fueron inventadas en agosto de1939 por el alemn Carl Petri, a la edad de 13anos, con el propsito de describir procesosqumicos. Aunque en el mundo cientfico sepublico en su tesis doctoral en 1962.
En su tesis doctoral "kommunikation mit automaten"(Comunicacin con autmatas),establece los fundamentospara el desarrollo terico de los conceptos bsicos de lasRedes de Petri.
5/20/2018 Clase Redes Petri
3/36
Los procesos son representados mediante un
modelo matemtico para su estudio. Mediante
la manipulacin de este modelo se pueden
adquirir conocimientos del proceso modelado
sin los riesgos, costos e inconvenientes de
manipular el proceso real.
5/20/2018 Clase Redes Petri
4/36
Por otra parte, los sistemas a menudo exhibensituaciones de concurrencia o paralelismo. Lasactividades de una componente de un sistemapueden ocurrir simultneamente con las de otros
mdulos. Dado que las componentes de lossistemas interactan, es necesario que hayasincronizacin. Esto puede resultar en que unacomponente est esperando a otra. El
temporizado de acciones de distintos mdulospuede ser muy complejo y las interaccionesresultantes entre las componentes pueden serdifciles de describir.
5/20/2018 Clase Redes Petri
5/36
Caractersticas bsicas de una Red de
Petri
La teora de Redes de Petri puede ser aplicada adiversas reas.
Las Redes de Petri son una herramienta til parael estudio de sistemas. La teora permite que unsistema sea modelado por una Red de Petri, unarepresentacin matemtica del sistema. Elanlisis de la Red puede revelar importanteinformacin acerca de la estructura y el
comportamiento dinmico del sistema modelado,la que puede ser usada para evaluarlo y sugerirmejoras o cambios.
5/20/2018 Clase Redes Petri
6/36
Estructura de una Red de Petri
Una Red de Petri consta de cuatro partes: un conjunto de sitios o lugares o plazas P
un conjunto de transiciones T
una funcin de entrada I
una funcin de salida O.
Las funciones de entrada y de salida relacionan transiciones y plazas.
La funcin de entrada I es un mapeado desde una transicin tj a unacoleccin de plazas I(tj), conocida como las plazas de entrada de la
transicin.La funcin de salida O mapea una transicin tj en una coleccin de
plazas O(tj), conocida como las plazas de salida de la transicin.
5/20/2018 Clase Redes Petri
7/36
Representacin Formal de una Red de
Petri
Tomemos como ejemplo la siguiente estructura de Red de Petri:
C = (P,T,I,O)P = {p1, p2, p3, p4}
T = {t1, t2, t3}
I(t1) = {p1} O(t1) = {p2, p3}I(t2) = {p3} O(t2) = {p3, p4}
I(t3) = {p2,p3} O(t3) = {p4}
5/20/2018 Clase Redes Petri
8/36
Representacin Grficade una Red de
Petri
La mayor parte del trabajo terico sobre Redes
de Petri est basado en la definicin formal de
estructuras de Redes de Petri. Sin embargo, unarepresentacin grfica de una estructura de Red
de Petri es mucho ms til para ilustrar los
conceptos de la teora. Un grafo de Red de Petries una representacin de una estructura de Red
como un multigrafo dirigido bipartito.
5/20/2018 Clase Redes Petri
9/36
Representacin Grfica de una Red de Petri
Un grafo de Red de Petri tiene dos tipos de nodos:
Un crculo representa una plaza
Una barra o lnea representa una transicin.
Los arcos dirigidos conectan las plazas y las transiciones, con
algunos arcos dirigidos desde las plazas a las transiciones y otros
arcos dirigidos desde transiciones a plaza.
Un punto representa un tokens
5/20/2018 Clase Redes Petri
10/36
Representacin Grfica de una Red de Petri
Un arco dirigido desde una plaza pi a una transicin tj define a la
plaza como una entrada de la transicin.Las entradas mltiples a una transicin se indican por arcos
mltiples desde las plazas de entrada a la transicin.
Una plaza de salida se indica por un arco desde la transicin a la
plaza.
Nuevamente, las salidas mltiples se representan por arcos
mltiples.
5/20/2018 Clase Redes Petri
11/36
Representacin Grfica de una Red de
Petri
Una Red de Petri es un multigrafo, dado que permite
arcos mltiples desde un nodo del grafo a otro.
Adems, dado que los arcos son dirigidos, es unmultigrafo dirigido.
Dado que los nodos del grafo pueden ser particionados
en dos conjuntos (plazas y transiciones), tal que cada
arco est dirigido de un elemento de un conjunto a un
elemento del otro conjunto, es un multigrafo dirigido
bipartito.
5/20/2018 Clase Redes Petri
12/36
Representacin Grfica de una Red de
Petri
5/20/2018 Clase Redes Petri
13/36
= , , ,P = {p1, p2, p3, p4}
T = {t1, t2, t3}
I(t1) = {p1} O(t1) = {p2, p3}
I(t2) = {p3} O(t2) = {p3, p4}
I(t3) = {p2,p3} O(t3) = {p4}
5/20/2018 Clase Redes Petri
14/36
Marcas de las Redes de Petri
Una marca es una asignacin de tokens
(tambin llamados fichas o cospeles) a las
plazas de una Red de Petri.
El nmero y posicin de los tokens puede
cambiar durante la ejecucin de una Red de
Petri.
5/20/2018 Clase Redes Petri
15/36
Marcas de las Redes de Petri
En un grafo de Red de Petri, los tokens se representanpor puntos dentro de los crculos que representan lasplazas.
Dado que el nmero de tokens que puede serasignado a una plaza de una Red de Petri esilimitado, hay una infinidad de marcas para una
Red de Petri.
5/20/2018 Clase Redes Petri
16/36
5/20/2018 Clase Redes Petri
17/36
La sincronizacin o ensamble Ocurre cuando 2 o ms actividades se unen.
Se usa para unir o ensamblar tokens queprovienen de diferentes caminos.
Los 2 tokens se unen.
5/20/2018 Clase Redes Petri
18/36
La concurrencia o desensamble Equivale a los flujos que se ejecutan en
paralelo.
Equivale a una funcin de desensamble
Los 2 tokens se dividen.
5/20/2018 Clase Redes Petri
19/36
Representacin de una mquina
Esta mquina realiza una operacin dentro de
un proceso.
En un diagrama clsico se observa:
4 plazas : A, B, C , D
2 transiciones
6 arcos
5/20/2018 Clase Redes Petri
20/36
A - D que se ubican al inicio y final son espacios para almacenarunidades de trabajo (como materia prima y producto terminado)
BC equivalentes a la mquina. Representa los 2 estados posiblesde la mquina:
Cuando el token est en Bsignifica que la mquina est trabajando.
Cuando el token est en Csignifica que la mquina est libre o enestado inicial.
Las 2 transiciones indican el inicio y fin de la operacin.
5/20/2018 Clase Redes Petri
21/36
La mquina es usualmente representada con formade tringulo, compuesta por una sincronizacin yuna concurrencia.
Cuando el token que est en A pasa a B se sincronizacon C.
Luego al finalizar el evento u operacin ocurre unaconcurrencia retornando el token a C
5/20/2018 Clase Redes Petri
22/36
Represente grficamente a la siguiente RdP:
R1 = (P, T, F, M)P = { p1, p2, p3, p4, p5, p6, p7, p8, p9}T = {t1, t2, t3, t4, t5, t6}
O(t1) = { p2, p3}
O(t2) = { p1, p7}
O(t3) = { p6}
O(t4) = { p4}O(t5) = { p9 }
O(t6) = { p5, p8}
I(t1) = { p1}
I(t2) = { p8}
I(t3) = { p2, p5}
I(t4) = { p3 }
I(t5) = { p6, p7}
I(t6) = { p4, p9}
5/20/2018 Clase Redes Petri
23/36
p2
p1
t1
p3
t2
t3
p4
p5
t4
5/20/2018 Clase Redes Petri
24/36
5/20/2018 Clase Redes Petri
25/36
5/20/2018 Clase Redes Petri
26/36
5/20/2018 Clase Redes Petri
27/36
5/20/2018 Clase Redes Petri
28/36
5/20/2018 Clase Redes Petri
29/36
5/20/2018 Clase Redes Petri
30/36
5/20/2018 Clase Redes Petri
31/36
Simulacin de una operacin con RdP
Se desea realizar una simulacin de 10
operaciones de corte (Co) que sern realizadas
por una sola mquina (Mq1). Dicha operacin
requiere un tiempo exacto de 5 minutos porunidad procesada. Para llevar a cabo esta tarea se
necesitan 2 unidades de materia prima 1 (Mp1) y
1 unidad de materia prima 2 (Mp2).
Supuestos: La mquina solo podr procesar una
unidad de tiempo. Se omiten los transportes.
5/20/2018 Clase Redes Petri
32/36
5/20/2018 Clase Redes Petri
33/36
BOM (Bills of Materials)
El BOM describe el contenido de materiales
de un producto
5/20/2018 Clase Redes Petri
34/36
5/20/2018 Clase Redes Petri
35/36
C t
5/20/2018 Clase Redes Petri
36/36
Caso propuesto
Se desea realizar una simulacin de una lnea de
ensamblaje compuesta por 3 operaciones en serie (Corte,Fresado y Torneado), cada una realizada por una mquina
diferente (Mq1, Mq2 y Mq3) con tiempos equivalentes a
5, 7 y 3 minutos respectivamente. Para llevar a cabo esta
tarea, la operacin de corte requiere de 2 unidades demateria prima 1 (Mp1), 1 unidad de materia prima 2
(Mp2) y 3 unidades de materia prima 3 (Mp3). Se desea
producir 10 unidades de producto terminado.
Supuestos: Las mquinas solo podrn procesar una unidad
al tiempo. Incluya un almacenamiento entre operaciones
con capacidad igual a 10.