(max, +) et quelques perspectives de recherche

 

Un grand nombre de processus peuvent être décrits par un modèle dynamique à événements discrets comme les ateliers flexibles, les systèmes multiprocesseurs ou les réseaux de transport. Ils se distinguent des systèmes continus par un espace d'état discret et un changement d'état produit par les événements. Leur comportement est caractérisé principalement par le parallélisme, la synchronisation et la concurrence.

Parmi les formalismes utilisables pour décrire les systèmes à événements discrets, les réseaux de Petri jouent un rôle important, présentant la caractéristique d'être un outil à la fois graphique et mathématique de modélisation. Les systèmes sont cependant complexes en raison de la taille des processus mais également de la variété de leur nature. Les réseaux de Petri recouvrent en réalité une famille de modèles qui chacune représente une vision particulière du système complexe. Il est bien connu que le graphe d'état représente le parallélisme et la concurrence mais pas la synchronisation et qu'il peut mettre facilement l'accent sur l'état du système ( défaillant, disponible, en marche,...). Chaque modèle est en réalité une simplification indispensable d'une réalité, celle-ci permettant une exploitation par un outil ou une théorie adaptée. Ainsi, les graphes d'état peuvent être utilisés par exemple, pour faire de la sûreté de fonctionnement tandis que la gestion de production est une application des graphes d'événement. Ce dernier modèle a une place importante car il représente naturellement les actions du système ( déplacement, saisie de pièce, usinage,..) et peut être intégré naturellement dans une méthodologie générale de conception du système. De ce fait, nous utiliserons de préférence ce type de modèle. Ce choix n'interdit pas l'utilisation d'autres modèles du moment que ceux-ci forment un tout cohérent dans une approche méthodologique.

Ces modèles pourront être analysés à travers des critères mettant en évidence des caractéristiques différentes du système. Elles pourront représenter :

les propriétés comportementales du système : vivacité, bornitude, réversibilité,... Ces critères permettent d'analyser un modèle quelconque.

la représentativité du processus : les modèles en réalité ne sont pas quelconques et représentent une réalité ou plus exactement un comportement donné d'un processus. On modélise le fait que des ressources sont partagées, que des priorités interviennent, la présence de gammes de fabrication,...

les objectifs de production : plus spécifiquement, le processus doit obéir à des critères liés aux coûts de fonctionnement et à sa rentabilité et devra être optimisé : ressources minimales nécessaires, taux moyen de production, production au plus tard pour limiter les stocks de pièces, périodicité du système,...

Notons que ces systèmes sont sujets aux défaillances qui sont à l'origine de coûts en termes de sécurité et de disponibilité. Un problème est donc d'intégrer les pannes dans la commande temporelle et de haut niveau du système et plus généralement d'avoir un système de commande robuste vis à vis des ruptures dans la continuité de la représentation du modèle. Ainsi, nous avons développé l'utilisation des équations "ARMA" dans l'algèbre (max,+).

Une algèbre exotique : l'algèbre (max,+)

Parmi les formalismes utilisés pour représenter les systèmes dynamiques à événements discrets, les réseaux de Petri temporisés intègrent explicitement le temps. La sous-classe des graphes d'événements joue un rôle important en raison de son comportement déterministe. L'évolution est décrite par des équations linéaires définies dans un dioïde. L'interprétation est que chaque variable est par exemple du type "dateur" pour l'algèbre (max,+) : chaque fonction xi(k) représente la date du k-ième tir de la transition xi .

Par exemple, considérons une unique machine pouvant traiter une seule pièce à la fois pendant T unités de temps. Soit u(n) la date d'arrivée de la n-ième pièce brute et y(n) sa date d'achèvement, on peut écrire l'équation suivante :

y(n) = max [ u(n) +T , T+ y(n-1) ]

Objectif

Un important objectif est la synthèse de contrôle temporel des systèmes. Les résultats peuvent être résumés par deux algorithmes qui donnent respectivement les instants au plus tôt et au plus tard des tâches. Utilisant l'algèbre des dioïdes, une équipe de l'INRIA a généralisé aux processus avec des tâches répétitives. Cette équipe a résolu le problème suivant : soit un système donné, comment calculer les dates au plus tard des entrées de pièces afin que les pièces soient produites au plus tard avant les dates désirées ? Il peut être prouvé que des équations analogues aux équations d'état (utilisant des opérateurs de maximisation et d'addition) donnent les dates au plus tôt alors que les dates au plus tard sont données par les "backward" équations (utilisant des opérateurs de minimisation et de soustraction). La différence entre ces instants donnent les temps disponibles pour le tir des transitions. L'existence d'une différence négative empêche le respect des dates limites.

Cette approche nécessite la connaissance d'un vecteur appelé "vecteur d'état" par analogie avec le vecteur d'état de l'automatique. La connaissance du modèle et des conditions initiales nous permet de caractériser ce vecteur d'état par une simple itération. Cependant, cette solution ne considère pas les erreurs de modélisation inévitables et doit partir d'une condition initiale connue. Pour surmonter ces difficultés, nous proposons d'utiliser un modèle différent composé d'équations appelées "ARMA" par analogie avec les équations ARMA utilisées en traitement du signal. Ces équations correspondent à la généralisation des chiens de garde sur des sous-systèmes. Nous montrons ainsi la possibilité d'utiliser ces équations pour faire la synthèse de contrôle temporel sans connaître le vecteur d'état. Le problème pratique se pose lorsque le processus subit une défaillance et doit être reconfiguré. Le modèle présente alors une rupture dans sa description générant une mauvaise estimation du vecteur d'état. Dans ce cas, le problème, est de calculer, après cette évolution du système, les dates au plus tard des tirs des transitions d'entrées afin que les tirs des transitions de sortie arrivent avant les dates désirées.

 

Mais, on peut aussi avoir une approche du type estimation !

 

Retour