Théorie algébrique des systèmes à événements discrets

Stéphane Gaubert
INRIA, Domaine de Voluceau, 78153 Le Chesnay Cédex.
Mèl: Stephane.Gaubert@inria.fr
Toile: http://amadeus.inria.fr/gaubert.

Le cours est commun au DEA ATS de l'Université d'Orsay et à l'Option Automatique de l'ENSMP

Dates et lieu du cours

Mon polycopié est disponible (sous forme postscript...)

OBJECTIF DU COURS Il s'agit de modéliser, d'évaluer les performances, et dans une certaine mesure, d'optimiser, des classes bien répertoriées de systèmes dynamiques à événements discrets (systèmes de production, réseaux de transports, etc). Le cours met l'accent sur les méthodes analytiques exactes (par opposition à des approches de type simulation): automates, algèbre linéaire et théorie des systèmes sur des semianneaux exotiques, programmation dynamique, asymptotiques de systèmes dynamiques monotones homogènes. Ce choix est fait pour trois raisons: -- ces méthodes sont mathématiquement formatrices, -- elles prolongent naturellement le cours d'Automatique de base, en montrant comment les idées de la théorie des systèmes sont encore pertinentes dans ce nouveau cadre, -- elle fournissent des algorithmes efficaces pour des sous-classes de systèmes, et souvent une compréhension intuitive des phénomènes.

PRÉSENTATION GÉNÉRALE La théorie des systèmes à événements discrets s'est constituée ces dernières années à partir de l'étude des systèmes de production, réseaux de transports, systèmes informatiques ... Elle s'intéresse à des problèmes d'évaluation de performance (calcul de taux de production, de débit), à des questions de vérification et de synthèse de commande (nécessité de satisfaire certaines contraintes logiques, comme l'absence de blocage, ou l'exclusion mutuelle), ainsi qu'à des problèmes d'optimisation (ex: nombre optimal de processeurs ou de machines pour réaliser une tâche donnée).

Le dénominateur commun est ici la présence de phénomènes de synchronisation, saturation ou concurrence liés à l'occurrence d'événements (arrivée d'un client, interruption d'une tâche, ...) qui semblent interdire l'emploi des outils familiers à l'automaticien (équations différentielles, équations récurrentes ``lisses''...).

On s'intéressera dans ce cours à une sous-classe bien repertoriée de Systèmes à Événements Discrets, dite classe des ``Graphes d'Événements'' (variété de réseaux de Petri). Cette classe a le mérite d'être déjà riche (elle couvre les phénomènes de saturation, synchronisation, assemblage), tout en admettant une théorie complète et algébrisée.

On montre en effet que ces systèmes sont linéaires à condition de se placer dans une nouvelle algèbre, à savoir le dioïde (ou semianneau idempotent) $({\mathbb R}\cup\{-\infty\},\max,+)$, structure dans laquelle $2\oplus 1=2$ ( $=\max(2,1)$) et $1\otimes 1=2$ (=1+1). Modulo ce changement d'algèbre, toutes les notions de l'Automatique classique s'étendent: représentation d'état, représentation entrée-sortie, séries de transfert ... Techniquement, le cur du cours est une théorie spectrale (max,+) ``à la Perron-Frobenius'' ainsi qu'une théorie des séries rationnelles ou séries de transfert à coefficients (max,+), qui fournissent des outils de calcul effectif (détermination du régime asymptotique, du taux de production) ainsi qu'une compréhension qualitative de ces systèmes.

Le cours contient quelques emprunts à la théorie des automates et aux réseaux de Petri. Aucun prérequis autre que l'Automatique de base n'est nécessaire.

MOTS-CLÉS EN FRANSCAIS Théorie des Systèmes, Systèmes dynamiques à événements discrets, évaluation de performance, ateliers flexibles, réseaux de transport, réseaux de Petri temporisés, algèbre max-plus, programmation dynamique, algorithmes de graphe, automate à multiplicité, séries rationnelles, théorie combinatoire des matrices, théorie de Perron-Frobenius, systèmes dynamiques monotones homogènes. MOTS-CLÉS EN ANGLAIS System Theory, Discrete Event Dynamical Systems, performance evaluation, manufacturing systems, transportation networks, timed Petri nets, max-plus algebra, dynamic programming, graph algorithms, automata with multiplicities, rational series, combinatorial matrix theory, Perron-Frobenius theory, monotone homogenous dynamical systems.

PLAN DU COURS 15 heures + 3 heures TD + 3 heures TP.

-- Petits exemples de systèmes à événements discrets, empruntés aux ateliers ou réseaux ferroviaires. Caractéristiques. Problèmes, approches et méthodes. Une nouvelle arithmétique pour la synchronisation: l'algèbre des dioïdes (ou semianneaux idempotents). Autres applications de cette algèbre.

-- Introduction aux réseaux de Petri. Graphe d'événements temporisés. Modélisation basée sur les ressources. Modélisation par empilements de pièces. Automates max-plus et diagramme de Gantt. Mise en équation des graphes d'événements temporisés. Points de vue dateur et compteur. Problème de l'évaluation de performance: temps de cycle, taux de production, grandeurs du second ordre (stocks, temps de séjour).

-- Graphes et matrices à coefficients dans des semianneaux. Application à la mise sous forme d'état des graphes d'événements temporisés.

-- Évaluation de performance via la théorie spectrale. Généralités sur les systèmes dynamiques monotones homogènes. Caractère non-dilatant de la dynamique. Théorème spectral max-plus. Valeurs propres, vecteurs propres. La valeur propre donne le débit, le vecteur propre fournit un horaire périodique (ex: chemins de fer).

-- Représentation entrée-sortie: séries de transfert; inf et sup-convolutions. Règles de simplification des expressions rationnelles commutatives. Calcul de séries de transfert. ``Décomposition en élements simples'' et forme canonique des séries en une lettre à cfficients $(\max,+)$. Version semianneau du théorème de Kleene-Schützenberger. Ce qui subsiste de la théorie de la réalisation minimale.

-- Pour finir. Stabilisation par feedback et optimisation des ressources. Dates aux plus tard. Représentation bi-dimensionnelle et algèbre $\mathcal{M}_{\text{\rm in}}^{\text{\rm ax}}[[\gamma,\delta]]$.

Références

1

F. Baccelli, G. Cohen, G.J. Olsder, and J.P. Quadrat.
Synchronization and Linearity.
Wiley, 1992.

2

V. Maslov and S. Samborski, editors.
Idempotent analysis, volume 13 of Adv. in Sov. Math.
AMS, RI, 1992.

3

V.K. Garg R. Kumar.
Modeling and control of logical discrete event systems.
Kluwer Acadamic Press, 1995.

4

P.J.G. Ramadge and W.M. Wonham.
The control of discrete event systems.
IEEE Proceedings: Special issue on Discrete Event Systems, 77(1):81-97, Jan. 1989.