Sur la commande des systèmes flexibles de production manufacturière par l’algèbre des dioïdes

22/09/2017
Publication e-STA e-STA 2007-4
OAI : oai:www.see.asso.fr:545:2007-4:19884
DOI :

Résumé

Sur la commande des systèmes flexibles de production manufacturière par l’algèbre des dioïdes

Métriques

22
7
305.27 Ko
 application/pdf
bitcache://784872dbfed50efdd57ef3f63c9b104320b1ae55

Licence

Creative Commons Aucune (Tous droits réservés)
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/545:2007-4/19884</identifier><creators><creator><creatorName>Michel Alsaba</creatorName></creator><creator><creatorName>Jean-Louis Boimond</creatorName></creator><creator><creatorName>Sébastien Lahaye</creatorName></creator></creators><titles>
            <title>Sur la commande des systèmes flexibles de production manufacturière par l’algèbre des dioïdes</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2017</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Fri 22 Sep 2017</date>
	    <date dateType="Updated">Fri 22 Sep 2017</date>
            <date dateType="Submitted">Tue 13 Nov 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">784872dbfed50efdd57ef3f63c9b104320b1ae55</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>33795</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Sur la commande des systèmes flexibles de production manufacturière par l’algèbre des dioïdes Michel ALSABA, Jean-Louis BOIMOND, Sébastien LAHAYE Laboratoire d’Ingénierie des Systèmes Automatisés (LISA) 62 avenue Notre Dame Du Lac, 49000 ANGERS, France [alsaba, boimond, lahaye]@istia.univ-angers.fr Résumé—Cet article traite de la commande en juste-à-temps des systèmes flexibles de production manufacturière lorsque la trajectoire de l’entrée de référence est connue a priori. La commande est issue de résultats de base de la théorie de la résiduation dans l’algèbre des dioïdes, une règle d’ordon- nancement locale permet de résoudre les conflits éventuels. Mots-clés—Systèmes flexibles de production manufacturière, réseaux de Petri temporisés, graphes d’événements tempo- risés, graphes d’états temporisés, tas de pièces, ordonnan- cement, dioïde, résiduation, commande en juste-à-temps. I. Introduction Ce travail a trait à la commande en Juste-A-Temps (JAT) des Systèmes Flexibles de Production Manufactu- rière (SFPM). Il s’agit de retarder au plus tard les entrées du système telles que ses sorties se produisent avant les dates désirées, données par l’entrée de référence. La com- mande en JAT proposée nécessite de connaître a priori la trajectoire de l’entrée de référence. Les SFPM sont carac- térisés par : 1. La production de plusieurs types de pièces selon une séquence fixée de tâches à accomplir, 2. Certaines ressources (tels une machine ou un robot) par- tagées entre plusieurs tâches. Pour un tel système, chaque type de pièces passe succes- sivement par des étapes de traitement disposées de façon linéaire, comparable à une ligne de production. Une méthode de construction systématique d’un SFPM est proposée dans [1] en utilisant les réseaux de Petri. Comme exemple d’illustration, considérons le SFPM, décrit par la figure 1, dans lequel trois types de pièces (A, B, C) sont traités. Une pièce A suit la séquence de tâches sui- vante : elle passe dans la machine M1 (la présence de deux jetons dans la place P3 signifie que la machine peut traiter deux pièces simultanément et indépendamment), puis elle passe dans la machine M2 (également utilisée pour traiter des pièces B). Une pièce B suit la séquence de tâches sui- vante : elle passe dans la machine M3 (également utilisée pour traiter des pièces C), puis elle passe dans la machine M2. Enfin une pièce C est traitée par la machine M3. Il est connu que le calcul d’une commande optimale vis- à-vis du critère de JAT pour le type de systèmes consi- dérés n’est généralement pas possible du fait du problème d’ordonnancement des ressources partagées. Ce problème, analogue à celui de l’ordonnancement d’un atelier de type jobshop, est NP-difficile lorsqu’une ressource est partagée X5 X6 Y3 Y2Y1 P10 P11 P12 P7 P8 P9 X4 X1 X2 X3 U3U2U1 machineM1 Pièce A Pièce B Pièce C P1 P2 P3 P4 P5 P6 P13 X7 machineM2 machineM3 Fig. 1. Exemple d’un SFPM. par plus de trois tâches [2]. La solution alternative que nous utilisons pour gérer les ressources partagées, est basée sur une règle d’ordonnancement locale. La méthode proposée nécessite de décomposer les ré- seaux de Petri en différents graphes, de type graphe d’états ou graphe d’événements : • Nous utilisons les graphes d’états temporisés (GEtT) pour représenter des phénomènes de choix (voir la machine M2, ou M3, décrite dans la figure 1). Dans ce papier, on utilise la règle d’ordonnancement des tâches communément appelée Earliest Due Date (EDD), ou règle de Jackson [3]. Cette règle est reconnue pour sa simplicité et fournit des résultats généralement assez bons lorsque le critère porte sur le retard algébrique (lateness), ce qui est le cas dans cet article (le retard algébrique correspondant à Li = Ci − di où Ci est la date de fin d’exécution de la tâche i (completion time) et di est la date d’achèvement souhaitée de la tâche i (due date)). Appliqué sur le GEtT élémentaire décrit par la figure 3, où sont seulement représentées deux types de tâches pour des raisons de clarté, cette règle d’ordonnance- ment est obtenu en rangeant simplement les tâches (I1O1, (resp., I2O2) correspondant au traitement d’une pièce 1 (resp., pièce 2)) par ordre de dates croissantes d’achève- ment souhaitées (indiquées par une entrée de référence). Une fois cet ordonnancement fixé, nous proposons, à tra- vers une modélisation de type tas des GEtT saufs (un seul jeton à la fois dans une place), de calculer la commande optimale vis-à-vis du JAT, au sens où la ressource est at- tribuée le plus tardivement possible aux tâches (pour l’or- donnancement considéré). La commande obtenue est sous- optimale (en générale), mais son calcul est de complexité réduite, alors que le calcul de l’ordonnancement optimal est un problème NP-difficile. • Nous utilisons les graphes d’événements temporisés (GEvT) pour représenter des phénomènes de synchroni- sation. Des résultats bien connus sur la résiduation dans l’algèbre (max, +) permettent le calcul d’une commande optimale en JAT pour de tels graphes, voir [4], [5]. Il est important de noter que les GEvT ne sont pas nécessaire- ment saufs (voir la machine M1 décrite dans la figure 1), contrairement aux GEtT supposés saufs. Une telle approche de modélisation nous paraît préfé- rable à une transformation globale d’un réseau de Petri temporisé en un GEvT, comme proposée dans [6], [7]. En effet, la transformation d’un réseaux de Petri temporisé en un GEvT équivalent nécessite, pour chaque entrée de réfé- rence donnée, un arbitrage a priori des conflits, ce qui peut s’avérer coûteux en temps de calcul de par la dimension éventuellement importante du GEvT généré. Au contraire, la représentation d’un réseaux de Petri temporisé est in- dépendante de l’ordonnancement, et par conséquent, de l’entrée de référence, ce qui est particulièrement intéres- sant dans notre cas, au sens où n’importe quelle trajectoire d’entrée de référence peut être considérée. Cet article est organisé comme suit. Des rappels sur les dioïdes, la théorie de la résiduation, les réseaux de Petri et les modèles de type tas sont présentés dans la deuxième sec- tion. Nous traitons de la modélisation et de la commande des SFPM dans la troisième section, ce qui mène à décom- poser les réseaux de Petri en considérant deux types de graphes, à savoir les GEtT et les GEvT. L’algorithme de contrôle est appliqué au système représenté par la figure 1 à titre d’illustration. II. Préliminaires A. Dioïde Voir [4], [8, §4] pour une présentation exhaustive de la théorie des dioïdes. Définition 1: Un dioïde D est un ensemble muni de deux lois de composition internes, notées ⊕ (addition) et ⊗ (multiplication), associatives et ayant chacune un élément neutre, noté respectivement ε et e, telles que ⊕ est com- mutative et idempotente (i.e., a ⊕ a = a). De plus, la loi ⊗ est distributive par rapport à la loi ⊕, et l’élément neutre ε est absorbant pour le produit (i.e., ε ⊗ a = a ⊗ ε = ε). Notons que le symbole ⊗ est souvent omis. Définition 2: Un dioïde D est dit complet s’il est fermé pour les sommes infinies et si la multiplication est distri- butive sur les sommes infinies, c’est-à-dire, si : ∀c ∈ D et ∀A ⊆ D, c ⊗ x∈A x = x∈A c ⊗ x. La borne supérieure, notée , d’un dioïde complet est la somme de tous les éléments du dioïde, elle est absorbante pour l’addition (i.e., ∀a, ⊕ a = ). Une relation d’ordre, notée , peut être associée à un dioïde D de par l’équivalence suivante : ∀ a, b ∈ D, a b ⇔ a = a ⊕ b. Cet ordre confère au dioïde complet une structure de treillis complet. Ainsi, nous pouvons introduire un opéra- teur Inf, noté ∧, vérifiant : ∀ a, b ∈ D, a b ⇔ b = a ∧ b. L’ensemble R ∪ {±∞}, muni du maximum comme opé- rateur ⊕ et de l’addition classique comme opérateur ⊗, est un dioïde complet, habituellement noté Rmax, avec ε = −∞, e = 0 et = +∞. Si D est un dioïde, l’ensemble Dn×n constitué des ma- trices de dimension n×n à coefficients dans D, où la somme et le produit matriciels sont définis par : (A ⊕ B)ij = Aij ⊕ Bij , (A ⊗ B)ij = n k=1 Aik ⊗ Bkj, est un dioïde. B. Théorie de la résiduation Une présentation complète de cette théorie est proposée dans [9]. Voir [8, §4.4] pour son utilisation dans l’algèbre des dioïdes. La théorie de la résiduation fournit, sous certaines hy- pothèses, la plus grande solution à l’inégalité f(x) b, où f est une application isotone (i.e., a b ⇒ f(a) f(b)) définie sur des ensembles ordonnés. Définition 3: Soit l’application isotone f : D → F, avec (D, D) et (F, F ) deux ensembles ordonnés. L’applica- tion f est dite résiduable si pour tout y ∈ F, la borne supérieure du sous-ensemble {x ∈ D | f(x) F y} existe et appartient à ce sous-ensemble. Théoreme 1: [8, §4.4.2] Soit f : D → F une application isotone d’un dioïde complet (D, D) vers un dioïde complet (F, F ). Sont équivalents : (i) L’application f est résiduable. (ii) Il existe une unique application isotone f : F → D, appelée application résiduée de f, telle que f ◦ f F idF et f ◦ f D idD, où idF et idD sont respectivement les applications identités dans F et D. Les applications La : x → ax et Ra : x → xa définies sur un dioïde complet D sont résiduables. Leurs résiduées sont notées respectivement La(x) = a◦\x et Ra(x) = x◦/a. Soient A ∈ Dm×n , B ∈ Dm×p , C ∈ Dn×p , la résiduation matricielle en fonction de la résiduation scalaire est définie par : A◦\B ∈ Dn×p où (A◦\B)ij = m l=1 Ali◦\Blj, B◦/C ∈ Dm×n où (B◦/C)ij = p k=1 Bik◦/Cjk. De plus, on a les relations suivantes : B◦/(AC) = (B◦/C)◦/A ∈ Dm×m , (AC)◦\B = C◦\(A◦\B) ∈ Dp×p . C. Réseaux de Petri Voir [10] pour une présentation détaillée des réseaux de Petri. Les Réseaux de Petri Temporisés (RdPT) considérés ont des temporisations associées uniquement aux places. Définition 4: Un RdPT est un 5-uplet G = (T , P, F, M, τ), où T est un ensemble fini de tran- sitions, P est un ensemble fini de places, F ⊆ (P × T ) ∪ (T × P) est un ensemble d’arcs, M : P → N est le mar- quage initial des places et τ : P → N est le temps de séjour minimum d’un jeton dans les places. Nous notons x• (resp., • x) l’ensemble des successeurs (resp., prédécesseurs) immédiats d’un noeud (place ou tran- sition) x. Le langage du réseau de Petri G est l’ensemble L ⊂ T ∗ des séquences commençant par le marquage initial M et se terminant par un marquage atteignable, où T ∗ est l’ensemble des mots finis sur l’alphabet T . Les transitions sont franchies selon la règle suivante. Sup- posons que la transition Ti soit franchissable à l’instant t, le franchissement de Ti se déroule en deux étapes : 1. A l’instant t, un jeton est retiré de chaque place ∈ • Ti. 2. A l’instant t, un jeton est ajouté dans chaque place p ∈ T• i . Il peut ainsi contribuer au franchissement des tran- sitions dans p• après l’instant t + τp, où τp correspond au temps de séjour minimum d’un jeton dans la place p. Notons que cette règle de franchissement correspond à un fonctionnement au plus tôt des RdPT. D. Modèle et automate de type tas Une présentation exhaustive des automates de type tas est proposée dans [11] où il est notamment montré que les modèles de type tas sont particulièrement intéressants pour évaluer successivement un grand nombre d’ordonnan- cements possibles dans des RdPT saufs. Ces modèles sont vus comme des automates (max, +), lesquels permettent le calcul du makespan à travers le cal- cul de la hauteur dite de tas de pièces, ceci avec une com- plexité indépendante de l’ordonnancement. Les modèles de type tas sont utilisés ici pour modéliser les GEtT en vue de proposer une méthode de commande, en ce sens on s’in- téresse davantage au problème d’inversion lié à ce type de modèle. L’axe vertical permettant de représenter un tas de pièces indique la hauteur du tas, l’axe horizontal représente un nombre fini de slots. Une pièce est un bloc solide (éventuel- lement non connecté) qui occupe une partie des slots, avec des contours supérieur et inférieur, un exemple est donné dans la figure 2. Pour une séquence ordonnée de pièces est associé un tas correspondant à l’empilement des pièces. Une pièce occupe la position la plus basse possible par rapport au sol et aux pièces éventuellement déjà empilées. Définition 5: Un modèle de type tas est un 5-uplet H = (T , R, R, l, u), où : • T est un ensemble fini de pièces. • R est un ensemble fini de slots. • R : T → P(R) correspond au sous-ensemble des slots occupés par chaque pièce. temps temps temps slot slot slot 0 0 0 + pièce correspond au mot pièce correspond au mot pièce correspond au mot Fig. 2. Tas de pièces associés aux mots I1, O1 et I1O1. • l : T × R → R ∪ {−∞} donne la hauteur du contour inférieur de chaque pièce pour les différents slots. • u : T ×R → R∪{−∞} donne la hauteur du contour supé- rieur de chaque pièce pour les différents slots. Par construc- tion, nous avons : u ≥ l. Par convention, l(a, r) = u(a, r) = −∞ si r /∈ R(a) et minr∈R(a)l(a, r) = 0 (ce qui revient à dire qu’une pièce ne peut pas aller plus bas que le niveau du sol). Le mot ω = a1...ak ∈ T ∗ de longueur k est interprété comme le tas obtenu en empilant les k pièces a1, ..., ak (dans cet ordre). Nous définissons le contour supérieur du tas ω comme le vecteur ligne xH(ω), de dimension card(R) où xH(ω)r est la hauteur du tas relativement au slot r. Par exemple, on a relativement au tas de pièces correspondant au mot I1O1 représenté sur la figure 2 : xH(I1O1)P 1 = τ1, xH(I1O1)P = τ + τ1, xH(I1O1)P 2 = −∞. L’hypothèse d’un plan horizontal, correspondant au sol, im- pose que xH(e) = (0, ..., 0) où e est le mot vide. Ainsi, la hauteur du tas ω est yH(ω) = maxr∈RxH(ω)r. Définition 6: Un automate de type tas est un 4-uplet A = (Q, I, F, M), où : • Q est un ensemble fini (d’états) ; • I ∈ R1×Q max et F ∈ RQ×1 max sont les vecteurs initial et final respectivement ; • M est un morphisme (M(ab) = M(a)M(b)) défini par : M : T ∗ → R Q×Q max , a → M(a) = I ⊕ [˜l(a, .)] t u(a, .), (1) où I est la matrice identité définie par Iii = e = 0, Iij = ε = −∞, i = j, et ˜l(a, i) = −l(a, i) si l(a, i) = ε et ˜l(a, i) = ε autrement, et où ˜l(a, .), u(a, .) sont des vecteurs lignes. On vérifie qu’on a :    xH(e) = It R, xH(ωa) = xH(ω)M(a), yH(ω) = xH(ω)IR, (2) où IR est un vecteur colonne de dimension card(R) dont les éléments sont égaux à e. Théoreme 2: [11] Soit H = (T , R, R, l, u) un modèle de type tas. L’automate de type tas (R, It R , IR, M), associé au modèle de type tas H, reconnaît le contour supérieur xH et la hauteur yH, ce qui signifie que ∀ω ∈ T ∗ : • xH(ω) = It RM(ω), • yH(ω) = It RM(ω)IR, Une interprétation possible d’un RdPT par un modèle de type tas consiste à considérer les pièces comme des tâches et les slots comme des ressources. Chaque tâche "a" nécessite, pour être réalisée, un sous-ensemble de ressources (donné par R(a)) durant un certain temps (égal à u(a, r) − l(a, r) pour la ressource r ∈ R(a)). En fait, dans le cadre des RdPT, xH et yH correspondent à des dateurs au sens où xH(ω)r représente le temps d’achèvement de la tâche r à l’issu de l’application du mot ω. Théoreme 3: [11] Soit G = (T , P, F, M, τ) un RdPT sauf auquel est associé un langage L, alors le modèle de type tas H = (T , P, R, l, u), où : • ∀a ∈ T , R(a) = a• ∪ • a, • ∀a ∈ T , ∀p ∈ a• , u(a, p) = τp, • ∀a ∈ T , ∀p ∈ • a\a• , u(a, p) = 0, où ”\” est la soustrac- tion des ensembles, • ∀a ∈ T , ∀p ∈ R(a), l(a, p) = 0, est tel que : ∀ω ∈ L, xG(ω) = xH(ω), yG(ω) = yH(ω), ce qui signifie que les fonctions dateurs du vecteur xG et du scalaire yG du RdPT G coïncident respectivement avec le contour supérieur xH et la hauteur yH du tas associé au modèle H. Il résulte de ces deux théorèmes que les dates de fran- chissement des transitions d’un RdPT sauf sont reconnus par un automate de type tas. Par exemple, considérons le GEtT décrit par la figure 3, lequel peut correspondre aux machines M2 ou M3, repré- sentées dans la figure 1. I1 I2 O2O1 P P1 P2 t t2t1 Pièce 1 Pièce 2 Fig. 3. Un GEtT élémentaire. Le modèle de type tas associé est défini par : T = {I1, I2, O1, O2}, R = P = {P1, P, P2} ; R(I1) = R(O1) = {P1, P}, R(I2) = R(O2) = {P, P2} ; u(I1, .) = [τ1, 0, −∞], l(I1, .) = [0, 0, −∞], u(I2, .) = [−∞, 0, τ2], l(I2, .) = [−∞, 0, 0], u(O1, .) = [0, τ, −∞], l(O1, .) = [0, 0, −∞], u(O2, .) = [−∞, τ, 0], l(O2, .) = [−∞, 0, 0]. Les tas de pièces associés aux mots I1, O1 et I1O1 sont représentés dans la figure 2. Par exemple, nous pouvons dé- duire directement les valeurs xH(I1O1) = [τ1, τ1τ, −∞] et yH(I1O1) = τ1τ, où τ1τ correspond à τ1 + τ dans l’algèbre usuelle. L’automate de type tas correspondant est défini par le 4-uplet (P, (e e e), (e e e) t , M), où M est tel que (en uti- lisant l’équation (1)) : M(I1) = I ⊕   −e −e ε   τ1 e ε =   τ1 e ε τ1 e ε ε ε e   , M (O1) = I ⊕   −e −e ε   e τ ε =   e τ ε e τ ε ε ε e  , de la même manière, on a : M (I2) =   e ε ε ε e τ2 ε e τ2   , M (O2) =   e ε ε ε τ e ε τ e  . Il en résulte que M (I1O1) = M (I1) M (O1) =   τ1 e ε τ1 e ε ε ε e     e τ ε e τ ε ε ε e   =   τ1 τ1τ ε τ1 τ1τ ε ε ε e  , et M (I2O2) =   e ε ε ε τ2τ τ2 ε τ2τ τ2  . III. Modélisation et commande des SFPM Nous traitons de la commande en JAT des SFPM : étant données les dates de franchissement désirées des transitions de sortie, définie par la fonction dateur Z = {z(k)}k=0,...,kf , il s’agit de trouver les dates de fran- chissement au plus tard des transitions d’entrée U = {u(k)}k=0,...,kf telles que les franchissements des transi- tions de sortie Y = {y(k)}k=0,...,kf se produisent avant les dates désirées. Dans un contexte de production, une telle commande revient à satisfaire la demande des clients tout en minimisant les stocks internes. Ce problème de poursuite de sortie (classique en automatique) est résolu de façon op- timale par l’intermédiaire de la théorie de la résiduation dans le cas des GEvT [4], [5]. Dans la méthode que nous proposons, les RdPT sont décomposés en GEvT et en GEtT afin de séparer les phé- nomènes de synchronisation des phénomènes de choix. La modélisation et la commande de ces graphes sont décrites dans les deux sections suivantes. La loi de commande appli- quée dans le cadre des GEtT est telle que l’ordonnancement de la ressource partagée est obtenu en rangeant les tâches par dates croissantes d’achèvements souhaités indiqués par l’entrée de référence. Cette régle est appelée la règle EDD, ou la règle de Jackson [3]. A. Modélisation et commande des GEvT Les GEvT sont particulièrement adaptés pour modéliser les phénomènes de synchronisation et correspondent à des systèmes dynamiques linéaires dans l’algèbre des dioïdes (voir [4], [8]). Le comportement des GEvT est représenté, dans le cas présent, dans le dioïde Rmax. Aussi, pour un GEvT donné, correspondra, par la suite, la représentation d’état suivante : x(k) = Ax(k − 1) ⊕ Bu(k), y(k) = Cx(k). (3) Pour une entrée de référence Z définie a priori, la com- mande optimale en JAT, notée uJAT , pour le modèle décrit par les équations (3) est défini par les équations d’états- adjoints suivantes : ξ(k) = A◦\ξ(k + 1) ∧ C◦\Z(k), uJAT (k) = B◦\ξ(k), (4) où ξ représente le vecteur d’états-adjoints (voir [8, §5.6]). Une extension au cas des GEvT non-stationnaires est pro- posée dans [12]. B. Modélisation et commande des GEtT Un automate de type tas peut être vu comme un sys- tème (max, +)-linéaire dont la dynamique est pilotée par des lettres. Pour une séquence donnée de lettres a1...ak, nous posons x(k) = x(a1...ak), les équations (2) corres- pondent alors à la relation récurrente suivante à l’étape k : x(k) = x(k − 1)M (ak) , y(k) = x(k) ¯F, (5) pour k ≥ 1 et x(0) = (0, ..., 0) et ¯F un vecteur d’interface. Considérons le GEtT élémentaire de la figure 3 où I1, I2 sont des transitions d’entrée et O1, O2 sont des transitions internes (et de sorties) du graphe. Dans ce cas précis, et pour simplifier le raisonnement, on associe une lettre par tâche I1O1 ou I2O2. Les composantes du vecteur d’état x(k) sont les dates de disponibilité du k-ième jeton dans les places P1, P, P2. De telles équations d’état représentent un système non- stationnaire en posant A(k) = M(ak) la matrice associée à l’étape k, on aura ak = I1O1 ou I2O2 selon le choix de la séquence fait à l’étape k. Soient F = (ε, e, ε), F1 = (e, ε, ε), F2 = (ε, ε, e), les vecteurs d’interface qui per- mettent de relier les composantes des vecteurs d’états, de type dateurs de transitions, aux modèles de type tas, dont les composantes des vecteurs d’états sont des dateurs de places comme décrits précédemment. Finalement, en ajoutant des entrées au modèle, les équa- tions non-autonomes deviennent : x(k) = x(k − 1)A(k) ⊕ u(k)B(k), y(k) = x(k)C(k). (6) Où u = {u(k)}k=0,...,kf = (I1, I2), x = {x(k)}k=0,...,kf = (xP 1, xP , xP 2), y = {y(k)}k=0,...,kf = (O1, O2), B(k) = FM(I1O1), resp. FM(I2O2), C(k) = F t 1, resp. Ft 2, selon la séquence I1O1, resp. I2O2 réalisée à l’étape k. Partant de la première équation de (6) et d’une façon similaire à [12], le développement de la récurrence sur x(k) est tel que : x(k) = x(k − 1)A(k) ⊕ u(k)B(k) = x(k − 2)A(k − 1)A(k) ⊕ u(k − 1)B(k − 1)A(k) ⊕ u(k)B(k) = x(k − 3)A(k − 2)A(k − 1)A(k) ⊕ u(k − 2)B(k − 2)A(k − 1)A(k) ⊕ u(k − 1)B(k − 1)A(k) ⊕ u(k)B(k) ... = x(k − p)Φ(k − p, k) ⊕ p−1 i=0 u(k − i)B(k − i)Φ(k − i, k), ∀p ∈ N, où Φ(j, k) est la matrice de transition donnée par : Φ(j, k) =    non définie pour j > k, I pour j = k, A(j + 1)A(j + 2)...A(k) pour j < k. Remarque 1: La matrice de transition satisfait la pro- priété de composition : Φ(j, k) = Φ(j, i) ⊗ Φ(i, k), où k ≥ i ≥ j, et en particulier pour k ≥ i + 1 Φ(i, k) = A(i + 1)Φ(i + 1, k) = Φ(i, k − 1)A(k). En sachant que : ∃k0 = k − p | x(k0) = j≤k0 u(j)B(j)Φ(j, k0) (système relaxé), et en tenant compte de la remarque 1, nous avons à l’issue de l’événement k : x(k) = x(k0)⊕ k0≤j≤k u(j)B(j)Φ(j, k) = j≤k0 u(j)B(j)Φ(j, k0)⊕ k0≤j≤k u(j)B(j)Φ(j, k) = j≤k u(j)B(j)Φ(j, k). D’après la deuxième équation de (6), nous calculons : y(k) = j≤k u(j)B(j)Φ(j, k)C(k) = j≤k u(j)h(j, k) = [H(u)](k) où h est la réponse impulsionnelle du système telle que h(j, k) = B(j)Φ(j, k)C(k). Ainsi, nous déduisons la commande en JAT, notée uJATi , donnée par : uJATi (k) = k≤j Zi(j)◦/h(k, j) = k≤j Zi(j)◦/(B(k)Φ(k, j)C(j)), soit, uJATi (k) = k≤j Zi(j)◦/(FA(k)A(k + 1)..A(j)Ft i (j)), où l’entrée de référence Zi(j) correspond à Z1(j), resp., Z2(j) (c’est-à-dire, la sortie désirée Y1, resp. Y2) selon la séquence I1O1, resp. I2O2, réalisée à l’étape j. En posant ξ(k) = k≤j Zi(j)◦/(A(k)A(k + 1)..A(j)Ft i (j)) le vecteur d’états-adjoints, nous pourrons démontrer (en uti- lisant II.B) qu’il satisfait les équations d’états-adjoints sui- vantes : ξ(k) = ξ(k + 1)◦/A(k) ∧ Zi(k)◦/(A(k)Ft i (k)), uJATi (k) = ξ(k)◦/F, La règle de Jackson consiste à ordonnancer une ressource en fonction de l’ordre des dates croissantes indiquées par la référence d’entrée. Cette règle d’ordonnancement est obte- nue en rangeant simplement les tâches (I1O1, (resp. I2O2) correspondant au traitement d’une pièce 1 (resp. pièce 2)) par ordre de dates croissantes d’achèvement souhaitées. Il en résulte l’algorithme de commande suivant à l’étape k (avec k = l + h) : si Z1(l) Z2(h) alors    ξ(k) = (ξ(k + 1) ∧ Z2(h)◦/Ft 2)◦/M(I2O2), Ξ2(h) = ξ(k)◦/F, h = h − 1, sinon (7)    ξ(k) = (ξ(k + 1) ∧ Z1(l)◦/Ft 1)◦/M(I1O1), Ξ1(l) = ξ(k)◦/F, l = l − 1, où Ξ1(l)(resp. Ξ2(h)) correspond à la date de franchisse- ment de la transition d’entrée I1(l)(resp. I2(h)). Il apparaît clairement que la règle d’ordonnancement de la ressource partagée réalise une sélection parmi les séquences I1O1 et I2O2 à chaque étape k de l’algorithme. Notons que le test Z1(l) Z2(h) donne une priorité à la première ligne de pro- duction (I1, O1) quand la date de la consigne est la même pour les deux lignes. En fait, la commande obtenue est équivalente à la com- mande optimale en JAT du GEvT correspondant au RdPT obtenu en considérant l’ordonnancement utilisé. C. Modélisation et commande des SFPM Chaque ligne de production d’un SFPM est un assem- blage de GEtT et de GEvT. Considérons, par exemple, le SFPM de la figure 1, il est aisé de déduire sa correspon- dance en termes de sous-systèmes (cf. figure 4). Fig. 4. Diagramme correspondant au SFPM de la figure 1. Pour la mise en série des sous-modèles GEtT ou GEvT, il est supposé l’existence d’une zone de stockage de capa- cité infinie entre chaque sous-modèle (représentées par les places P1, P4, P5, P6, P13 dans le SFPM de la figure 1). Cette hypothèse permet alors de calculer la loi de com- mande par applications successives des algorithmes pro- posés pour chaque sous-modèle (à travers l’utilisation des équations (4) pour un sous-modèle de type GEvT et (7) pour un sous-modèle de type GEtT). La démarche permettant le calcul de la commande op- timale (au sens du JAT) est la suivante : étant donnés Z1, Z2, nous obtenons ξ4, ξ6 en appliquant l’algorithme (7) au GEtT2. Étant donné ξ4 (considérée comme une entrée de référence vis-à-vis du GEvT), nous obtenons U1JAT en appliquant l’algorithme (4) au GEvT. Finalement, étant donné ξ6, Z3 (considérés comme des entrées de référence vis-à-vis du GEtT1), nous obtenons U2JAT , U3JAT en ap- pliquant l’algorithme (7) au GEtT1. Notons que ξ2, ξ3 (resp., ξ5, ξ7) donnent les dates où la ressource de la ma- chine M3 (resp., M2) est assignée aux pièces. Ces dates sont les plus tardives possibles permettant de satisfaire la consigne. D. Application numérique Appliquons l’algorithme de commande précédent à l’exemple de la figure 1, en considérant l’entrée de réfé- rence suivante : Z =   Z1 Z2 Z3   =   14 32 33 34 35 41 ε ε ε 30 31 43 10 11 12 13 24 36   . Étant donnés Z1, Z2, nous obtenons, en appliquant l’algo- rithme (7) au GEtT2 : (ξ4, ξ6)t = 10 19 23 27 31 37 ε ε ε 16 18 42 . Puis, en considérant ξ4 et appliquant l’algorithme (4) au GEvT, nous déduisons l’entrée de commande : U1JAT = 5 14 18 22 26 32 . A présent, en prenant ξ6 et Z3, et en appliquant l’algo- rithme (7) au GEtT1, nous obtenons : (U2JAT , U3JAT )t = ε ε ε 7 11 35 0 2 4 6 20 32 . La sortie du système, induit par UJAT , est donnée par : Y =   14 23 27 31 35 41 ε ε ε 17 19 43 4 6 8 10 24 36   . Nous pouvons vérifier que Y Z. IV. Conclusion et Perspectives Nous avons considéré la commande en juste-à-temps des systèmes flexibles de production manufacturière. A présent, nous travaillons sur l’évaluation de la complexité et de de- gré de sous-optimalité de la méthode proposée, ce qui nous mène à considérer d’autres règles d’ordonnancement. En parallèle, nous cherchons à généraliser les classes de sys- tèmes pouvant être considérés par cette méthode de com- mande. Références [1] S. Amar, E. Craye, et J.C Gentina. A Method Of Hierarchi- cal Specification And Prototyping Of FMS. Proceedings of the IEEE-ETFA, volume 1, pages 44–49, 1992. [2] Y.N. Sotskov. The Complexity of Scheduling Problems with 2 and 3 Jobs. Eur. J. Oper. Res., volume 53, pages 326–336, 1991. [3] J.R. Jackson. Scheduling a Production Line to Minimize Maxi- mum Tardiness. Research Report 43, Management Science Re- search Project, University of California. Los Angeles., 1955. [4] G. Cohen, P. Moller, J-P. Quadrat, et M. Viot. Algebraic Tools for the Performance Evaluation of Discrete Event Systems. IEEE Proceedings : Special issue on Discrete Event Systems, 77(1) :39– 58, January 1989. [5] E. Menguy, J.-L. Boimond, L. Hardouin, et J.-L. Ferrier. Just- In-Time Control of Timed Event Graphs : Update of Reference Input, Presence of Uncontrollable Input. IEEE Trans. on Auto- matic Control, 45(11) :2155–2158, November 2000. [6] H. Hillion et J-M. Proth. Performance Evaluation of Job-Shop Systems Using Timed Event-Graphs. IEEE Trans. on Automa- tic Control, 34(1), January 1989. [7] B. Trouillet et A. Benasser. Cyclic Scheduling Problems with Assemblies : An Approach Based to the Search of Initial Mar- king in a Marked Graph. IEEE Trans. on Systems, Man and Cybernetics, 2002. [8] F. Baccelli, G. Cohen, G.J. Olsder, et J.-P. Quadrat. Synchroni- zation and Linearity : An Algebra for Discrete Event Systems. Wiley and Sons, 1992. [9] T.S. Blyth et M.F. Janowitz. Residuation Theory. Pergamon press, 1972. [10] T. Murata. Petri Nets : Properties, Analysis and Applications. Proceedings of the IEEE., volume 77(4), pages 541–580, 1989. [11] S. Gaubert et J. Mairesse. Modeling and Analysis of Timed Petri Nets Using Heaps of Pieces. IEEE Trans. on Automatic Control, 44(4) :683–697, April 1999. [12] S. Lahaye, J.-L. Boimond, et L. Hardouin. Optimal Control of (Min,+) Linear Time-Varying Systems, Petri Nets and Perfor- mance Models. Proceedings of PNPM’99, pages 170–178, Zara- goza Spain, 1999.