LIP6 2005/005

• Reports
  Minimisation de la Capacité des Places d'un Graphe d'Evenenements Généralisé.
• O. Marchetti, A. Munier-Kordon
• 20 pages - 05/24/2005- document en - http://www.lip6.fr/lip6/reports/2005/lip6-2005-005.pdf - 357 Ko
• Contact : olivier.marchetti (at) nulllip6.fr
• Ancien Thème : ASIM
The minimization of the places capacities storage of a Weighted Event Graph (in short WEG) is a crucial problem in industrial area such as the design of embedded systems or manufacturing systems. The objective of this paper is to set out an algorithm for solving polynomially this problem. It also computes an initial live marking. Firstly, a lower bound formula for each place capacity storage is expressed. A simple transformation of the initial WEG G into another WEG Gr modelling that the limitation storage of each place of G is equal to these bounds is then detailed. Then, a restriction of the set of feasible initial markings of Gr is made by the analysis of the liveness problem. Finally, we develop a polynomial algorithm which computes an initial live marking of Gr.
• Keywords : Petri Nets, Liveness, Buffer Requirement, Manufacturing.
• Publisher : Francois.Dromard (at) nulllip6.fr