domingo, 20 de mayo de 2012

Petri Net

Carl Petri established in 1962, a mathematical tool for studying communications with controllers. Some of the most important applications of Petri Nets have been in the modeling and analysis of communication protocols, modeling and analysis of manufacturing systems. In this area, have been used to represent production lines, automated assembly lines, automotive production system, flexible manufacturing systems, systems just-in-time, etc..
 

Petri Nets are bipartite graphs consisting of three types of objects:
  • Places.
  • Transitions.
  • Oriented arcs

Petri nets are considered a tool for the study of systems. With your help we can model the behavior and structure of a system, and carry the model boundary conditions, which in a real system are difficult to get or very expensive.
The theory of Petri nets has become recognized as an established methodology in the literature of robotics to model flexible manufacturing systems.
Compared with other models of dynamic behavior charts, diagrams and finite state machines, Petri nets offer a way to express processes that require synchronization. And perhaps most importantly, Petri nets can be analyzed formally and learn the dynamic behavior of the modeled system.
To model a system using mathematical representations making an abstraction of the system, this is achieved with Petri nets, which can also be studied as automata and investigate its mathematical properties. 


Areas of application

  • Data Analysis
  • Software design
  • Reliability
  • Workflow
  • Concurrent programming

Example:

It has a single line to serve 100 clients. The arrival times of customers are successive values ​​of the random variable t, the service times are given by the random variable ts, and N is the number of servers. This model in its initial state the queue is empty and all servers in standby. The Petri net for this scenario is shown in Figure




The states are labeled with capital letters and lowercase transitions. The labels of the sites will also be used as variables whose values ​​are the tokens.

The edges have labels that could represent the transition functions, which specify the number of tokens removed or added when a transition is enabled.
The state A initially has the arrival of 100 customers, the site B prevents clients come more than once, the site is the row Q by customers when they have to wait to be answered. The state S is where the servers idle waiting for the opportunity to work, and site E counts the number of customers leaving the system. The initial state implies that the sites to have the following values:

  • A = 100
  • B = 1
  • Q = 0
  • S = N
  • E = 0 

The transition model is used for customers entering the system and the transition b models to customers when they are being served.
 
Classical Petri nets to model states, events, and conditions, synchronization, and parallelism, among other system features. However, Petri networks that describe the real world tend to be complex and extremely large. Furthermore, conventional Petri nets do not allow the modeling of data and time. To solve this problem, many extensions have been proposed. Extensions can be grouped into three categories: time extensions, color and hierarchies.

TIME EXTENSIONS
An important point in real systems is the description of the temporal behavior of the system. Because Casicas Petri nets are not able to manage time in a `` quantitative'' is added to the model the concept of time. Petri nets with time can be divided, in turn, into two classes: time Petri nets deterministic (or regular Petri nets) and Time Petri Nets Stochastic (or stochastic Petri nets).
The family of Petri nets with deterministic time include Petri nets associated with a given trip time in their transitions, places, or arcs.

The family of Petri nets with time include stochastic Petri nets associated with a trip time stochastic transitions, places and arcs.

Because this type of network associated with a delay time to execute a transition enabled, you can not establish a reachability tree because evolution is not deterministic. The analysis methods associated with such networks are Markov chains, where the probability of the emergence of a new state depends only on the previous state.

EXTENSIONS WITH HERARCHIES
The size problem with Petri nets when modeling real systems, can be treated with the use of hierarchical Petri nets. These networks provide, as its name implies, a hierarchy of subnetworks. A subnet is a set of places, transitions, arcs and even subnets. So that the construction of a large system, is based on a mechanism for structuring two or more processes, represented by subnets. Such that, at one level gives a simple description of the processes, and on another level we want to give a more detailed description of their behavior.
Extensions from hierarchies appeared as extensions to colored Petri nets However, we have developed types of hierarchical Petri nets that are not colored

EXTENSIONS WITH COLOR
Colored Petri nets are an extension of Petri nets that has built a modeling language. Colored Petri nets are considered a modeling language developed for systems in which, communication, synchronization and resource sharing are important. Thus, colored Petri nets combine the advantage of Petri nets and the classical languages ​​of high level programming. To make this statement clear, we will list the features of the graphical elements of such networks.
Bibliography:
http://homepage.cem.itesm.mx/vlopez/redes_de_petri.htm

http://www.mitecnologico.com/Main/RedesDePetri

1 comentario: