A Sufficient Condition for the Liveness of Weighted Event Graphs
Une Condition Suffisante de Vivacité pour les Graphes d'événements généralisés
Abstract
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.
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.
Origin : Files produced by the author(s)