LIP6 2005/005

• Rapports de recherche
  Minimisation de la Capacité des Places d'un Graphe d'Evenenements Généralisé.
• O. Marchetti, A. Munier-Kordon
• 20 pages - 24/05/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
La minimisation de la taille des places d'un Graphe d'Evenements Généralisé (GEG en abrégé) est un problème crucial dans des domaines industriels tels que celui de la conception de systèmes embarqués ou pour les problèmes d'assemblage. L'objectif de cet article est d'exposer un algorithme polynomial qui résout ce problème. L'algorithme détermine aussi un marquage initial vivant. Dans un premier temps, nous caractérisons un borne inférieure de la capacité à affecter pour une place donnée. Nous détaillons ensuite une transformation du GEG initial G en un autre GEG Gr modélisant le fait que la capacité de chaque place de G est égale à la borne précédement calculée. L'analyse du problème de vivacité de Gr nous conduit à proposer une restriction sur les marquages initiaux possibles de Gr qui seront enviseagés par notre algorithme. Enfin, nous proposons un algorithme polynomial qui calcule un marquage initial vivant pour Gr.
• Mots clés : Réseaux de Pétri, Vivacité, Dimensionnement de mémoire, Problème d'assemblage.
• Directeur de la publication : Francois.Dromard (at) nulllip6.fr