LIP6 2005/004

• Reports
  Une Condition Suffisante de Vivacité pour les Graphes d'événements généralisés
• O. Marchetti, A. Munier-Kordon
• 17 pages - 05/24/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
The aim of this paper is to develop a sufficient condition of liveness of a weighted event graph (in short WEG) computable in polynomial time. Many industrial problems may be modelled using WEG and a fast polynomial algorithm to decide if a system is live may be interesting in an optimization context. We prove that any unitary WEG may be transformed into a normalized WEG such that the values of the arcs adjacent to any transition depend on the transition. A simple sufficient condition of liveness can be expressed on this new WEG and polynomially computed. We also proved that this condition is necessary for a circuit with two transitions.
• Keywords : Petri-nets, Liveness, Scheduling, Manufacturing
• Publisher : Francois.Dromard (at) nulllip6.fr