LIP6 2005/004

• Rapports de recherche
  Une Condition Suffisante de Vivacité pour les Graphes d'événements généralisés
• O. Marchetti, A. Munier-Kordon
• 17 pages - 24/05/2005- document en - http://www.lip6.fr/lip6/reports/2005/lip6-2005-004.pdf - 306 Ko
• Contact : olivier.marchetti (at) nulllip6.fr
• Ancien Thème : ASIM
L'objectif de ce papier est de developper une condition suffisante de vivacité pour les graphes d'événements généralisés (GEG en abrégé) qui soit calculable en temps polynomial. Beaucoup de problèmes industriels peuvent être modélisés par un GEG et dans un contexte d'optimisation, un algorithme qui décide de la vivacité d'un GEG s'avère d'une grande utilité. Nous prouvons que tout GEG unitaire peut être transformé en un GEG normalisé tel quetoutes les valeurs des arcs adjacents à chaque transition dependent de la transition. Une condition suffisante de vivacité peut alors être simplement exprimée sur ce nouveau GEG et être polynomialement calculée. Nous démontrons que cette condition est aussi nécessaire dans le cas à deux transitions.
• Mots clés : Réseaux de Pétri, Vivacité, Ordonnancement, Problème d'atelier
• Directeur de la publication : Francois.Dromard (at) nulllip6.fr