Systèmes à événements discrets

Sommaire

• Le début de l'histoire
• L'approche Max Plus en quelques mots
• L'équipe de recherche
• Quelques documents de présentation générale
• Autres sources d'information

Le début de l'histoire

La théorie des systèmes et de leur commande, alias l'Automatique, s'est intéressée dès ses origines à des systèmes physiques généralement décrits par les équations différentielles ou aux dérivées partielles auxquelles obéissent les phénomènes physiques correspondants. L'avènement des ordinateurs conduit à décrire parfois l'évolution de ces systèmes par des équations dynamiques en temps discret, ce qui ne remet pas en cause la nature continue de cette évolution.

Par ailleurs, la linéarité est une propriété mathématique intéressante qui simplifie beaucoup la manipulation de modèles mathématiques. Dans les années 70 et 80, l'Automatique non linéaire a commencé à se développer, après que les années 60 aient été l'âge d'or de l'Automatique linéaire. L'Automatique non linéaire s'adresse généralement à des équations dynamiques "lisses" ou "différentiables".

Avec les progrès de la technologie, l'Homme s'est mis à construire des systèmes de plus en plus complexes et complètement artificiels, du moins en ce qui concerne leur mode de fonctionnement considéré à un niveau de conceptualisation adapté à leur gestion ou à leur commande. Pour fixer les idées, citons les

• réseaux de transport,
• réseaux de communications et d'ordinateurs,
• unités centrales d'ordinateurs elles-mêmes,
• ateliers de production manufacturière, notamment dans leur version "ateliers flexibles" modernes.

Ce ne sont bien sûr que quelques exemples. Dans ces systèmes, l'essentiel de l'enchaînement dynamique des tâches provient de phénomènes

• de synchronisation (dont nous allons reparler),
• et d'exclusion mutuelle ou compétition dans l'utilisation de ressources communes, ce qui nécessite une politique d'arbitrage ou de priorité, questions généralement désignées sous le terme générique d'ordonnancement.

Ce type de dynamique échappe totalement à la modélisation par équations différentielles ou leurs équivalents en temps discret. C'est sans doute pourquoi ces systèmes, qui sont pourtant de réels systèmes dynamiques, ont longtemps été négligés par les automaticiens et ont plutôt été étudiés par les spécialistes de Recherche Opérationnelle, de Productique, d'Informatique, etc., en fonction des domaines d'applications traités, sans qu'une "théorie des systèmes" généraliste émerge véritablement. On peut quand même citer des théories d'inspiration graphique (réseaux de Petri), probabiliste (réseaux de files d'attente), etc., mais qui n'ont pas de forte parenté avec la théorie des systèmes en Automatique.

Ce qui s'est passé de nouveau au début des années 80, c'est la prise en compte de ces systèmes par le monde de l'Automatique. On les a alors appelés "Systèmes à Événements Discrets" (SED). Le mot "discret" ne signifie ni "temps discret", ni "état discret" (on verra que les variables d'état peuvent effectivement prendre des valeurs continues) mais ce mot réfère au fait que la dynamique est composée d'événements qui peuvent d'ailleurs avoir une évolution continue, mais ce n'est pas cela qui nous intéresse au premier chef : ce qui nous intéresse, c'est le début et la fin de ces événements, dans la mesure où les fins conditionnent de nouveaux débuts.

Pour en terminer avec ces généralités, disons que la théorie des SED peut être divisée actuellement en deux ou trois grandes approches :

• l'approche logique qui ne s'intéresse qu'à l'occurrence des événements ou l'impossibilité de cette occurrence ("impasse" ou "blocage", en Anglais "deadlock") et à la succession de ces événements, mais pas à la date précise de ces occurrences, autrement dit pas aux aspects de performances ; W.M. Wonham et P. Ramadge, et après eux de nombreux auteurs, ont étendu à la théorie des Automates et des Langages Formels la problématique de la commande, qui agit dans ce cas sur l'inhibition de certaines transitions d'état pour éviter les comportements non désirés (on cherche à faire en sorte que l'automate ne produise qu'un sous-langage "acceptable" du langage qu'il peut produire sans contrôle) ;
• l'approche quantitative qui s'adresse à l'aspect "évaluation de performance" (mesurée par le nombre d'événements survenant dans un laps de temps donné), voire à l'optimisation de ces performances ; dans ce contexte général, on peut distinguer deux écoles :
  • l'approche "perturbation analysis" inaugurée par Y.C. Ho (probablement le père de l'expression "Discrete Event Dynamic Systems") et toutes les variantes qui ont suivi et qui cherchent à résoudre toutes sortes de problèmes d'optimisation non classiques, en raison de l'aspect "événements discrets", et ce généralement dans un contexte stochastique ;
  • l'approche "Max Plus", qui fait l'objet de nos recherches, et dont il est donc essentiellement question dans la suite.

L'approche Max Plus en quelques mots

En quelques mots, cette approche se caractérise par

• l'utilisation d'une algèbre adaptée, l'algèbre "Max Plus" (essentiellement, l'addition de deux nombres devient le maximum de ces deux nombres et la multiplication de deux nombres est le plus habituel ; par exemple 3 plus 5 égale 5, et 3 fois 5 égale 8), ou plus généralement, l'algèbre des dioïdes (ou semi-anneaux idempotents) ;
• la limitation à certaines classes de SED, ceux qui ne mettent en jeu que des phénomènes de synchronisation (ce qui suppose la concurrence déjà arbitrée par une politique d'ordonnancement à un niveau plus élevé) ; essentiellement, ces systèmes se modélisent dans le paradigme des réseaux de Petri par la sous-classe des graphes d'événements ;
• l'aspect évaluation de performances (les graphes d'événements correspondants sont donc temporisés).

Dans ce cadre, les graphes d'événements temporisés deviennent des systèmes linéaires justiciables d'une théorie très analogue à la théorie des systèmes linéaires traditionnelle.

Ajoutons cependant que

• d'une part, nos recherches ne se limitent pas forcément aux SED qui sont linéaires dans les algèbres de dioïdes ;
• d'autre part, les algèbres de dioïdes ont d'autres utilisations que la théorie des SED, et ces applications nous intéressent aussi.

En savoir plus. . .

• votre navigateur supporte les cadres (frames) ;
• votre navigateur ne supporte pas les cadres (frames).

Petit glossaire

SED

système à événements discrets

Dioïde ou semi-anneau idempotent

structure algébrique munie d'une addition associative, commutative, avec élément neutre ("zéro"), et d'une multiplication associative, avec élément neutre ("un"), la multiplication étant distributive par rapport à l'addition, le zéro étant absorbant pour la multiplication (zéro fois a égale zéro pour tout a) ; enfin, l'addition est idempotente, c'est-à-dire que a plus a égale a pour tout a.

Graphe d'événements

réseau de Petri ne comportant pour chaque place qu'une seule transition amont (d'entrée) et une seule aval (de sortie), donc aucune compétition dans l'approvisionnement des places en jetons ni la consommation de jetons dans les places ; les transitions pouvant par contre comporter plusieurs entrées et sorties, les contraintes de synchronisation sont bien représentées par ces graphes.

---

retour au sommaire