Un protocole de négociation pour l'ordonnancement distribué Multi-Agents d’un Atelier Job-Shop M.L. Berrandjia, S. Ourari Division Robotique et Productique Centre de Développement des Technologies Avancées Alger, Algérie mberrandjia@cdta.dz Résumé— Dans ce papier, nous nous intéressons à la résolution distribuée du problème d’ordonnancement d’atelier Job-Shop en utilisant les systèmes multi-agents. Nous considérons que chaque machine est assimilée à un agent autonome gérant son propre ordonnancement local (Ordonnancement à une machine) et coopérant avec les autres agents pour trouver une solution globale satisfaisante tout en gardant une certaine flexibilité séquentielle afin de faire face aux incertitudes. L'approche de résolution proposée est basée sur un mécanisme de coopération inter-ressources où les négociations sont initiées entre les agents afin d'assurer une cohérence entre tout couple de tâches liées par la gamme opératoire. Un protocole de négociation est proposé et sa mise en œuvre est réalisée sur la plateforme de développement des systèmes multi-agents JADE. Cette dernière permet de développer une solution portable fonctionnant sur plusieurs plateformes et supportant le standard FIPA-ACL pour la communication entre agents. Mots clés— Job-Shop, ordonnancement distribué, système multi-agents, coopération, flexibilité, JADE. I. INTRODUCTION Actuellement, le processus d’ordonnancement de la production occupe une place importante au niveau de l’entreprise qui évolue dans un environnement caractérisé par une hyper-concurrence visant à satisfaire à la fois les exigences et les contraintes imposées par les clients en termes de qualité, de coût et de délais de mise à disposition. Il est donc indispensable d’avoir un système assurant un ordonnancement robuste tenant compte de l’environnement perturbé de la production en exploitant au maximum la flexibilité existante lors de l’exécution du plan de production. Il existe dans la littérature plusieurs approches traitant le problème d’ordonnancement de la production. La plupart de ces approches sont centralisées et s’articulent essentiellement autour de méthodes de résolution exactes ou bien approchées [1]. La solution est alors donnée sous forme d’un ordonnancement prévisionnel unique satisfaisant les contraintes imposées par le client ainsi que par l’environnement de l’atelier. Notons toutefois, que le principal inconvénient de ces approches réside dans le fait que ces dernières considèrent que les problèmes d’ordonnancement R. Chalal Laboratoire de Méthodes de Conception des Systèmes Ecole Nationale Supérieure d’Informatique Alger, Algérie r_chalal@esi.dz sont déterministes, i.e. que les données du problème traité sont connues à l’avance. Seulement dans la réalité, l’environnement de production est de nature perturbé; en effet de nouvelles informations peuvent surgir pendant l’exécution du plan initial le rendant par la même occasion obsolète. La solution dans ce cas consiste donc à élaborer un nouvel ordonnancement global couteux en temps de calcul conduisant le plus souvent à des modifications radicales du plan initial ou bien dans le pire des cas à l’acceptation du retard engendré par la perturbation. Pour faire face au problème d’incertitudes, des approches dites robustes ont été développées. Ces approches sont classées en trois catégories : prédictives, proactives et réactives. Dans les approches prédictives, l’ordonnancement est calculé en se basant sur des données estimées sans tenir compte des perturbations. Les approches proactives quand à elles calculent un ordonnancement en utilisant des connaissances à priori sur les incertitudes probables. Enfin, les approches réactives effectuent un calcul de l’ordonnancement en temps réel en traitant les incertitudes lors de leur apparition. Il à noter que les approches précédentes peuvent être combinées afin d’exploiter les avantages que chacune de ces dernières offre. On retrouve dans [2] et [3] un état de l’art et une classification des approches robustes. D’autres approches exploitent la nature distribuée du problème d’ordonnancement, les décisions sont dans ce cas distribuées entre les différents acteurs, ayant chacun une autonomie, et coopérant entre eux de manière à converger vers un ordonnancement global avec une performance acceptable. Cette façon de faire permet de mieux absorber les incertitudes en ne modifiant que les ordonnancements locaux des ressources concernées par la perturbation. Notons que ce type d'approche distribuée peut être modélisé par les systèmes multi-agents (SMA) [4] en considérant que chaque agent représentant une ressource (machine) possède une autonomie décisionnelle et est capable de communiquer avec les autres agents moyennant un protocole de coopération pour la prise de décisions d'ordonnancement. L'intérêt de ces SMA s'est accru ces dernières années avec le développement rapide des réseaux et de l’informatique distribuée. Plusieurs chercheurs se sont intéressés au paradigme des systèmes multi-agents et à leur application dans le domaine de l’ordonnancement de la production. Dans [5], les auteurs décrivent un mécanisme d’appel d’offre permettant à une ressource de sous-traiter ses tâches avec d’autres ressources. Baker dans [6] a proposé une architecture basée sur le protocole Contract-Net. Dans [7], le système développé assigne à chaque ressource un agent permettant de forcer le respect des contraintes relatives à la capacité de cette dernière, et à chaque travail un agent s’assurant du respect des contraintes de précédence et des dates de disponibilités. Dans les articles [8] et [9], l’ordonnancement est réalisé avec deux agents qui détiennent un ensemble de tâches et sont en compétition pour l’utilisation des ressources. Dans [10], le problème d’atelier job-shop a été abordé dans un contexte coopératif et distribué pour la prise en compte des incertitudes. Dans [11], les auteurs présentent un SMA pour l’ordonnancement des ateliers job-shop où les agents définissent leurs plans de réalisation en utilisant des règles de priorité tout en minimisant les temps d’inactivité de la machine. Wei et Dongmei dans [12], proposent un SMA pour la résolution des problèmes job shop flexibles avec des stratégies de négociation inspirées du fonctionnement du système immunitaire humain. Dans [13], les auteurs proposent un SMA adaptatif permettant de faire face aux incertitudes et basé sur le Q-Learning, pour les systèmes de production à base de connaissances (Knowledge Manufacturing Systems). Enfin, dans [14] les auteurs présentent une approche multi-agents pour l’ordonnancement des workflows collaboratifs relatifs aux chaines d’approvisionnement en combinant le protocole Contract-Net, les modèles de workflow et les théories d’optimisation, et implémentée avec les standards de la FIPA et les modèles réseau de Pétri relatifs aux spécifications des workflows. Dans ce papier, nous nous intéressons à la résolution distribuée d'un problème d’ordonnancement multi-ressources et plus particulièrement à sa mise en œuvre en utilisant la plateforme JADE (Java Agent DEvelopment Framework) [15]. Cette dernière est organisée selon les spécifications de la norme FIPA (Foundation for Intelligent Physical Agents) appelée FIPA97 [16] qui décrit le modèle de référence d’une plateforme multi-agents ainsi que le langage de communication entre les agents (FIPA-ACL). Ce papier est organisé comme suit. Dans la section suivante, nous présentons la problématique d'ordonnancement étudiée. La troisième section est consacrée à la présentation de l’approche multi-agents proposée et une description du protocole de négociation y afférent. Nous expliquons le fonctionnement des étapes principales de l’approche proposée avec un exemple illustratif. Par la suite, nous décrivons la mise en œuvre du protocole proposé pour l'ordonnancement multiagents en utilisant la plateforme JADE. Enfin, nous terminons par une conclusion sur le travail réalisé et les perspectives futures en vue. II. PROBLEMATIQUE D’ORDONNANCEMENT JOB-SHOP Dans ce papier, nous étudions le problème d’ordonnancement de type Job shop noté Jn||Cmax et qui consiste à ordonnancer un ensemble de travaux T= {1,2,…, N} sur un ensemble de machines M = {1,2,…, m}. Chaque travail possède sa propre gamme opératoire et est composé d’un ensemble de tâches s’exécutant sur une des machines de l’ensemble M dans un ordre bien défini. Nous supposons que les tâches sont non-préemptives, et que les machines sont disjonctives. Notons aussi que chaque tâche i ne peut être exécutée que par une et une seule machine et que son exécution nécessite une durée opératoire pi connue à l’avance. La solution du problème consiste à trouver pour chaque machine un ordonnancement de manière à satisfaire les contraintes du problème et à converger au mieux vers un objectif qui est la minimisation de la durée totale de la réalisation des N travaux appelée Makespan et notée Cmax. Ce genre de problème est connu comme étant classé dans la catégorie des problèmes NP-Difficiles [17]. Se situant dans un contexte perturbé, nous exploitons, pour résoudre le problème, la nature distribuée de la fonction ordonnancement, en considérant chaque machine comme étant un centre de décision autonome disposant de toutes les informations nécessaires (connaissances locales) relatives aux tâches (date de disponibilité, date d’échéance et durée opératoire) devant être exécutées sur ce dernier. Ces connaissances locales sont utilisées par le centre de décision pour réaliser son propre ordonnancement local en définissant les dates de début des ses opérations. Le problème qui se pose alors est la cohérence des décisions prises par les différents centres de décisions sachant qu’ils sont interdépendants en raison des liens qui relient les différentes tâches d'un même produit (une date de fin d'une tâche ne pouvant excéder la date de début de la tâche qui la succède). En effet, en supposant que chaque centre prend ses décisions sans prendre en compte celles prises par les autres centres, il est clair que cela engendrerait des incohérences qu’il faudrait éliminer par la suite. On peut déjà en conclure que ces centres de décision sont dans l'obligation d'interagir les uns avec les autres pour assurer la cohérence entre leurs décisions et cela en utilisant un mécanisme de coopération bien précis. Un centre décision possède des relations avec des centres en amont qui lui fournissent des produits à transformer, et qu'il il transfère à son tour aux centres de décision en aval. Parmi les paradigmes les plus utilisés pour la résolution des problèmes distribués, les systèmes multi-agents en constituent le moyen le plus adéquat pour la modélisation distribuée du problème d’ordonnancement en offrant une multitude d’outils et de standards tels que ACL ou bien KQML. III. APPROCHE MULTI-AGENTS POUR L’ORDONNANCEMENT Comme nous l'avons introduit précédemment, nous considérons dans l'approche proposée pour la résolution distribuée du problème, que chaque machine est assimilée à un agent, et que ce dernier procède à l'établissement de son ordonnancement local en exploitant la technique d'ordonnancement à une machine basée sur le théorème de dominance décrite dans [18] et qui permet de caractériser un ensemble de solutions faisables au lieu d'une solution unique et fournit ainsi de la flexibilité séquentielle. Ainsi, chaque agent, définit pour chaque tâche i qu'il réalise, des dates de début et de fin au mieux et au pire et dispose d’une certaine flexibilité lui permettant de faire face aux incertitudes. Notons que chaque ordonnancement local déterminé par un agent donné est réalisé indépendamment des décisions prises localement par les agents en amont et en aval de ce dernier, engendrant ainsi des incohérences qu’il faudrait éliminer afin d’aboutir en finalité à un plan d'ordonnancement global réalisable. Afin d'assurer une cohérence entre les décisions prises localement, un mécanisme de coopération entre les agents est mis en œuvre à travers des primitives, permettant ainsi de négocier de nouvelles valeurs de début et de fin en jouant sur les dates de disponibilités et d’échéances des tâches. La phase de négociation est initiée par les deux agents ayant la plus grande incohérence. Pendant cette phase, les agents utilisent des primitives de négociation leurs permettant de faire des propositions ou bien des contrepropositions afin d’aboutir à la fin à une situation sans incohérences. Le ré-ordonnancement effectué au niveau d’un agent négociant nécessite une mise à jour des connaissances au niveau des autres agents à travers une coordination. Il est à noter qu’un couple d’agents peut faire l’objet de plusieurs négociations. On appelle donc une négociation déjà faite, une renégociation. A. Décomposition du Problème Initial Cette étape consiste à décomposer le problème d’ordonnancement job shop initial à plusieurs machines en plusieurs sous-problèmes à une machine. Il s’agit de déterminer une connaissance locale initiale en calculant pour chaque tâche i à exécuter par une ressource donnée, sa fenêtre d’exécution [ri, di] (ri, di représentent respectivement la date de disponibilité et la date d’échéance de la tâche i). Il faut noter que les données initiales du problème concernent seulement le nombre de travaux à réaliser, leurs gammes opératoires ainsi que les ressources, et les durées opératoire des tâches à exécuter. Les dates ri et di d’une tâche donnée sont calculées en utilisant le graphe disjonctif correspondant au problème [19]. Ainsi, chaque ressource (agent) disposera d’un ensemble de tâches à réaliser avec toutes les informations (ri, di et pi) requises pour procéder au calcul d’un ordonnancement local. B. Exemple illustratif sur la décomposition À titre d'exemple, considérons un problème job-shop à 3 machines 1, 2 et 3 et 4 travaux J1, J2, J3, J4. Tous les travaux sont disponibles à l'instant zéro. Le tableau I présente les données concernant les gammes et les durées opératoires. TABLEAU I. EXEMPLE D’UN PROBLEME JOB SHOP 4×3. Travail 1 1 1 2 2 2 3 3 3 4 4 4 Tâche 1 2 3 4 5 6 7 8 9 10 11 12 Durée 6 10 5 8 9 7 6 10 8 2 1 7 Machine 1 2 3 2 1 3 3 2 1 3 1 2 Le résultat de la décomposition du problème initial est donné sous forme de trois sous-problèmes relatifs aux machines 1, 2 et 3 et en calculant pour chaque tâche i sa date de disponibilité ri ainsi que sa date d’échéance di. Le tableau II illustre les données locales relatives aux tâches correspondantes à chacune des machines. TABLEAU II. Machine (Agent) 1 2 3 DECOMPOSITION DU PROBLEME INITIAL. Tâche 1 11 8 5 12 2 9 6 4 7 10 3 ri 0 2 6 8 3 6 16 17 0 0 0 16 di 9 17 16 17 24 19 24 24 8 6 16 24 Dans ce qui suit, nous donnons la manière dont est réalisé l’ordonnancement local au niveau des agents (machines) utilisant les données calculées précédemment. C. Ordonnancement local Le but de l'ordonnancent global étant la minimisation du Makespan, le problème job shop est décomposé en sousproblèmes plus faciles à résoudre, où chaque agent résout un sous-problème, et procède à l'établissement d'un ordonnancement local à une machine avec comme critère la minimisation du retard algébrique (problème noté 1|ri|Lmax). Comme nous supposons que chaque agent caractérise un ensemble d'ordonnancements possibles, ceci est réalisé en exploitant une condition de dominance [18] à travers les fenêtres temporelles d’exécution des tâches [ri, di] calculées précédemment. Il est possible ainsi de déterminer pour chaque tâche i ce qui suit :  La séquence favorable (resp. défavorable) avec le meilleur retard algébrique noté Limin (resp. Limax);   La date de début au mieux (resp. au pire) notée simin (resp. simax); La date de fin au mieux (resp. au pire) notée fimin (resp. fimax). Le calcul de Limin et de Limax est effectué en utilisant l’algorithme décrit dans [20] dont la complexité temporelle est en O (n log n). Les dates de début et de fin au mieux et au pire sont déduites des retards algébriques. D. Détermination des incohérences Dans la section précédente, nous avons montré que des intervalles temporelles spécifiant les dates de début et de fin au mieux et au pire de chaque tâche sont déterminés localement. Il faut toutefois noter que chaque agent procède à l'établissement de son ordonnancement local sans tenir compte des décisions prises par les autres agents avec qui il est lié au sens de la gamme opératoire des produits. Il en découle ainsi des incohérences entre les dates de début et de fin des tâches, dues aux contraintes de précédence liées aux gammes opératoires. En effet, les intervalles temporelles de début de réalisation déterminés par deux agents prenant en charge respectivement deux tâches successives i et i+1 d’un même produit doivent satisfaire les deux conditions suivantes : si+1min ≥ fimin et si+1max ≥ fimax (1) Les incohérences au mieux et au pire, entre deux tâches (i, i+1) sont données par les formules suivantes Δimin = si+1min – fimin et Δimax = si+1max − fimax (2) Ainsi, chaque agent gère deux ensembles de tâches incohérentes, au mieux et au pire, classés respectivement par ordre croissant des Δimin et Δimax. Le but étant d’arriver à trouver un ordonnancement global satisfaisant les conditions données dans (1), il est clair que seules les valeurs négatives des expressions données dans (2) constituent des incohérences, et feront par conséquent l’objet de négociations entre les agents. Notons que les agents se coordonnent par échange d’informations afin que le couple d’agents détenant l’incohérence la plus prioritaire (calculée à la base d’une règle de priorité) enclenche le processus de négociation. Nous signalons que dans le protocole de négociation que nous proposons, à un instant donné, seul un couple d’agents concernés est en phase de négociation, les autres agents entrent en état d’attente jusqu’à ce que la négociation prenne fin. E. Exemple illustratif sur l’ordonnancement local et le calcul des incohérences Le tableau III illustre les résultats obtenus au niveau des agents après la réalisation du premier ordonnancement local ainsi que les valeurs des incohérences calculées. TABLEAU III. ORDONNANCEMENTS LOCAUX ET DETERMINATION DES INCOHERENCES. Agent 1 2 3 Tâche 1 11 8 5 12 2 9 6 4 7 10 3 min si 0 6 6 17 3 6 20 28 6 0 14 16 fimin 6 7 16 26 10 16 28 35 14 6 16 21 simax 0 16 7 16 16 10 23 31 6 0 14 16 fimax 6 17 17 26 23 20 31 38 14 6 16 21 Δimin Δimax 0 -4 4 2 0 3 0 -10 - 4 -1 6 5 -4 3 1 0 - Les valeurs des incohérences (au mieux et au pire) sont obtenues à travers une coordination entre tout couple d’agents exécutant deux tâches successives (i, i+1) faisant partie du même travail. Le nombre total d’incohérences avant le début des négociations est de 4 (2 au mieux et 2 au pire). Dans ce qui suit nous présentons le protocole de négociation impliquant les agents à travers un schéma d’interaction afin d’éliminer les incohérences existantes entre ordonnancements locaux des agents. F. Protocole de négociation Afin d’assurer une cohérence lors des prises de décisions locales, les agents interagissent selon un schéma de coopération que nous décrivons dans cette section. Comme nous l’avons déjà signalé, il s’agit plus précisément d’amorcer une série de propositions et de contre-propositions entre les agents du couple ayant la plus grande incohérence. Pour ce faire, des primitives permettant d’agir sur les dates de début et de fin des tâches au mieux et au pire sont définies au niveau des agents, permettant à ces derniers de prendre des décisions locales, tout en négociant avec les agents amonts et avals. Dans ce qui suit, nous présentons ces primitives puis nous décrivons le schéma d’interaction adopté. 1) Primitives de gestion des incohérences: chaque agent dispose de deux types de primitives qu’il gère de manière autonome. La première règle les incohérences au mieux, alors que la seconde traite le cas des incohérences au pire. Le principe consiste à modifier les dates de début ou de fin au mieux et au pire de manière à ce que les valeurs Δimin et Δimax soient positives ou bien nulles, assurant ainsi la cohérence entre les tâches. Ces primitives agissent sur l’ordre de certaines tâches déjà préétabli en augmentant les dates de début ou bien en réduisant les dates de fin (au mieux et au pire) de la tâche faisant objet de l’incohérence la plus grande. Ces primitives sont :   Diminuer fimin (resp. fimax): cette primitive permet de diminuer la valeur de la date de fin au mieux (resp. au pire) de la tâche i ; Augmenter simin (resp. simax) : cette primitive permet d’augmenter la valeur de date de début au mieux (ou au pire) de la tâche i. 2) Schéma d’interaction : notre approche de résolution préconise, comme nous l’avons déjà signalé, la distribution des décisions sur un processus d’interaction en utilisant les SMA. En effet, une solution SMA sans interaction n’est guère différente d’une solution classique. Elle consiste à mettre en relation plusieurs agents afin de déclencher certaines actions au niveau de ces derniers. Dans notre cas, deux agents entrent en négociation pour éliminer l’incohérence liée aux tâches successives (i, i+1) de la même gamme, que chacun d’eux réalise. Durant cette phase de négociation, ces agents adoptent deux rôles différents ; l’agent réalisant la tâche i+1 est l’agent initiateur de la négociation alors que celui réalisant la tâche i est l’agent participant. Cette négociation se fait au moyen des primitives suivantes :     Propose : cette primitive permet à l’agent initiateur de demander à l’agent participant de diminuer sa date de fin au mieux ou au pire ; Contre-propose : cette primitive est utilisée par l’agent participant pour demander à l’agent initiateur d’augmenter sa date de début au mieux ou au pire, dans le cas ou la diminution de la date de fin n’a pas suffit à éliminer l’incohérence ; Accepte : cette primitive est utilisée par les agents négociants afin de confirmer l’acceptation de la proposition émanant du participant ou de la contre proposition émanant de l’initiateur ; Coordination : cette primitive est utilisée par les agents négociants pour informer les autres agents des modifications éventuelles opérées à leur niveau. La figure 1 représente un diagramme de séquence illustrant la négociation entre deux agents. La négociation commence par une proposition de l’agent initiateur (Agent réalisant la tâche i+1) demandant à l’agent participant de diminuer fimin (ou bien fimax). Ce dernier procède à un ré-ordonnancement local et informe les autres agents des modifications effectuées afin que ces derniers les prennent en considération. Dans le cas où l’action de l’agent participant a permit de régler le problème, alors il envoie un message d’acceptation à l’agent initiateur et la négociation est terminée. Dans le cas contraire, l’agent participant envoie à l’agent initiateur une contre-proposition lui demandant d’augmenter son si+1min (ou bien si+1max). Ce dernier après avoir procédé à un ré-ordonnancement local, informe les autres à travers un message de coordination des modifications faites à son niveau. A l’issue de cette étape un message d’acceptation sera envoyé à l’agent participant marquant ainsi la fin de la négociation. Les valeurs Cmaxfav(Aj) et Cmaxfav(Aj) représentent respectivement le makespan local au mieux et au pire de l’agent Aj. Rappelons que la solution globale est donnée sous forme d’un ensemble de solutions possibles (ordonnancements admissibles) avec les dates de livraison des jobs au mieux et au pire calculées à partir des expressions (3) et (4) données plus haut et qu’on note Cmaxfav et Cmaxdef : � � �� �� �� = = �� =1… (� �� =1… (� �� �� �� (� )) (5) (� )) (6) Puisque la solution au problème global est donnée sous fourme d’un ensemble d’ordonnancements possibles, alors le makespan global appartient à l’intervalle défini par les valeurs calculées dans (5) et (6), c'est-à-dire : Cmaxfav ≤ Cmax ≤ Cmaxdef :participant (Agent qui réalise i) :initiateur (Agent qui réalise i+1) D’autre part, il est clair que pour avoir plus de flexibilité au niveau de chaque agent, il faut que ce dernier propose un ensemble de solutions possibles au lieu d’une seule solution, et cela imposerait à ce que la valeur de Cmaxfav soit différente de celle de Cmaxdef. En effet, ceci permet de mieux gérer les perturbations, ou bien de mieux prendre en charge de nouvelles commandes qui peuvent surgir durant l’exécution des travaux sans dégrader la performance au pire, c’est-à-dire, en faisant avancer les travaux les plus prioritaires ou bien différer d’autres travaux par manipulation de l’ensemble des solutions proposées. Dans le cas où Cmaxfav est égale à Cmaxdef, alors cela voudrait dire que toutes les solutions proposées ont le même makespan, et ce qui implique une absence de flexibilité globale. Il est à noter que si s’il n’existe pas de flexibilité globale, cela n’implique pas que les agents ne disposent pas de flexibilité locale. Dans ce qui suit, nous illustrons à travers un exemple illustratif les négociations engagées entre les agents afin de parvenir à la fin à une situation sans incohérence. Propose min Diminuer f i (f max i ) Ré-ordonnancement Coordination Mise à jour des Δ Mise à jour des Δ Accepte alt [Δ min i (Δ max i ) ≥ 0] [else] Contre propose min Augmenter S i+1 max (S i+1 ) Ré-ordonnancement Coordination Mise à jour des Δ Mise à jour des Δ Accepte Fig. 1. Schéma d’interaction lors de la négociation. G. Evaluation de la solution La solution globale au problème initial est donnée sous forme d’un intervalle [Cmax] avec des dates de fin au mieux et au pire notées respectivement Cmaxfav et Cmaxdef. Nous savons que chaque agent caractérise un ensemble de solutions possibles lors de l’ordonnancement local, et définit pour chaque tâche i qu’il réalise un intervalle de début [si] ou de fin [fi] de réalisation. A partir de là, il est possible de calculer pour chaque agent Aj=1..m une date de fin de réalisation de toutes ses tâches, au mieux et au pire comme suit : � � �� �� �� � � = = �� � � �� � � �� , = 1… , = 1… (3) (4) H. Exemple illustratif sur les négociations Nous reprenons l’exemple précédent où la première étape de coordination a permis de déterminer l’existence de 4 incohérences. L’élimination de ces dernières nécessite une phase de négociations entre les agents qui procèdent en premier au traitement des incohérences au mieux pour passer ensuite aux incohérences au pire. Nous signalons aussi que le couple d’agents ayant la plus petite incohérence est celui qui enclenche le processus de négociation, cependant, d’autres règles peuvent être adoptées. Les actions adoptées au niveau des primitives Diminuer er Augmenter sont pour l’instant assez basiques puisque l’approche est en cours en de développement et se limitent simplement soit à l’augmentation ou bien à la diminution des dates de disponibilité et d’échéance afin de manipuler les dates de début et de fin au mieux et au pire de la tâche concernée et par la même occasion affecter la valeur de l’incohérence. L'application du schéma d’interaction donne des résultats regroupés dans le tableau VI où sont illustrées les étapes de négociation pour l’élimination de toutes les incohérences existantes. Chaque ligne du tableau est une étape de négociation (avant et après négociation) où (N, T, I, i+1, P, i) représentent respectivement le numéro de la négociation, le type de l’incohérence qu’elle soit au mieux (min) ou bien au pire (max), l’agent initiateur (numéro de la machine associée à l’agent), la tâche exécutée par ce dernier, l’agent participant et la tâche exécutée par ce dernier. Pour chaque agent, nous avons mentionné dans le tableau les dates des tâches incohérentes, la valeur de l’incohérence (Δi) ainsi que le nombre global des incohérences traitées avant et après la négociation (inc). TABLEAU IV. NEGOCIATIONS RELATIVES A L’EXEMPLE. Avant négociation Négociation (N, T, I, i, P, i+1) Initiateur (1, min, 2, 12, 1, 11) (2, min, 1, 11, 3, 10) (3, min, 1, 8, 3, 7) (4, min, 2, 9, 1, 8) (5, min, 1, 5, 3, 4) (6, max, 2, 6, 1, 5) (7, max, 3, 3, 2, 2) 3 2 6 16 8 17 16 d participant smin smax r d Initiateur participant smin smax 24 3 16 2 17 6 16 -4 5 2 6 0 16 14 14 -14 16 7 9 0 6 2 2 -1 24 20 23 8 18 17 18 -7 17 8 9 0 8 8 8 -8 24 20 23 16 25 18 19 -7 24 16 16 6 19 6 10 -4 4 3 2 5 3 3 1 Δi inc r d smin smax r 3 2 8 23 16 24 20 24 5 18 31 25 31 25 3 2 17 27 18 31 20 16 6 18 30 19 31 20 d smin smax 2 5 2 6 0 2 0 0 0 6 2 2 8 18 17 18 0 8 8 8 9 18 18 19 6 16 6 10 0 0 9 0 2 4 0 3 2 5 3 3 1 0 Il est à noter que inc représente ici le nombre d’incohérences global (au mieux + au pire) et que Δi correspond à une incohérence au mieux ou bien au pire, selon l’information indiquée dans la première colonne. Dans cet exemple, l’étape de négociation débute avec le couple d’agents (2, 1) ayant la plus petite valeur d’incohérence au mieux (en valeur absolue) car la priorité est donnée, en premier, au traitement des incohérences au mieux, pour ce schéma de coopération. On remarque d’après le tableau qu’après la troisième négociation, le nombre total d’incohérences est passé de 2 à 5 a cause du ré-ordonnancement local qui modifie aussi non seulement les dates de la tâche 8 mais aussi toutes les tâches affectées à l’agent 1, engendrant ainsi d’autres incohérences. Après le traitement des incohérences au mieux (après la cinquième négociation), les agents procèdent à des négociations visant la résolution des incohérences au pire. Il est à noter que, si la résolution d’une incohérence au pire génère une ou plusieurs incohérences au mieux, alors la prochaine négociation concernera le traitement de ces dernières. Le tableau V présente le résultat final après la fin de toutes les négociations. TABLEAU V. Tâche 1 11 8 5 12 2 9 6 4 7 10 3 Agent 1 1 1 1 2 2 2 2 3 3 3 3 Job 1 4 3 2 4 1 3 2 2 3 4 1 RESULTAT FINAL DES NEGOCIATIONS. ri 0 2 8 9 3 6 19 24 0 0 0 20 di 9 5 18 18 24 16 31 31 8 6 2 25 Dans cette section, nous nous intéressons à la mise en œuvre de la solution SMA proposée en mettant l’accent sur la plateforme utilisée (JADE) pour la modélisation comportementale des agents, la communication et la gestion des messages d’échange entre ces derniers. Il existe plusieurs plateformes logicielles permettant soit, la simulation des systèmes multi-agents, ou bien le développement et la mise en œuvre de ces derniers. Dans [21], les auteurs présentent une étude comparative des plateformes de développement des SMA les plus utilisées. Après négociation Δi inc r IV. MISE EN ŒUVRE simin 0 2 8 18 3 6 20 28 8 2 0 20 fimin 6 3 18 27 10 16 28 35 16 8 2 25 simax 3 6 9 19 16 10 23 31 8 2 0 20 fav Partant des résultats du tableau V, le calcul de [Cmax , se fait comme suit : Cmaxfav = max(f12min, f9min, f6min, f3min) = 35 Cmaxdef = max(f12max, f9max, f6max, f3max) = 38 fimax 9 7 19 28 23 20 31 38 16 8 2 25 Cmaxdef] A. Présentation de la plateforme JADE JADE (Java Agent DEvelopement framework) est une plateforme Open source gratuite, implémentée entièrement en JAVA et dédiée au développement des SMA conformément aux spécifications de la FIPA. Cette norme concerne aussi la communication inter-agents effectuée à travers le langage FIPA-ACL. JADE comporte aussi un ensemble d’outils et d’applications graphiques qui permettent le débogage, la supervision et l’administration du système développé, tels que : « Sniffer Agent » pour la visualisation des messages ACL circulants entre les agents du système, ou encore l’outil « Remote Monitoring Agent » qui permet l’administration à distance d’une ou de plusieurs plateformes JADE. B. Modélisation multi-agent du problème sous JADE Comme mentionné précédemment, chaque agent est autonome, possède des connaissances locales, et interagit avec les autres agents afin de mettre en cohérence les décisions prises localement. Au niveau de la plateforme JADE, chaque agent peut avoir un ou plusieurs réactions, selon la situation à laquelle il est confronté. La modélisation du comportement d’un agent est réalisée avec la classe Behaviour (offerte par JADE) à travers l’utilisation d’une machine à états finis (Finite State Machine). La figure 3 décrit le comportement général d’un agent, où chaque état correspond à une situation donnée :     Etat S1 (réception des données) : durant cet état l’agent reçoit les informations sur les tâches à exécuter nécessaires pour l’établissement de son ordonnancement local. A la fin de la réception des données, l’agent passe à l’état S2 ; Etat S2 (Ordonnancement local) : cet état permet à l’agent d’établir son ordonnancement local en définissant pour chaque tâche, ses dates de début et de fin au mieux et au pire. L’agent passe ensuite à l’état S3 pour la détermination des incohérences ; Etat S3 (Détermination des incohérences) : Il s’agit dans cet état du calcul ou de la mise à jour des incohérences à chaque fois que l’ordonnancement local est établi, suite à une négociation; Etat S4 (Détermination du couple d’agents négociants) : Cet état permet d’identifier le couple d’agents déclenchant la négociation. Ces deux derniers entrent en négociation (état S6) tandis que le reste des agents passent en attente (état S5) ;   Etat S5 (attente) : cet état est relatif aux agents qui ne sont pas concernés par la négociation. Si la négociation est finie alors les agents en attente passent à l’état S4 pour déterminer le nouveau couple d’agents négociants, sinon à l’état S3 pour une coordination et une mise à jour des incohérences ; Etat S6 (Négociation) : durant cet état, les agents ayant la plus grande incohérence négocient afin d’éliminer cette dernière. Le passage à l’état S2 se fait pour effectuer un ré-ordonnancement, à l’état S3 pour mettre à jour les incohérences (coordination) ou bien à l’état S4 après la fin de la négociation. moment, nous avons défini pour chaque état, un type de message qui lui correspond. Il s’agit ici d’ajouter un entête permettant d’identifier le type de message afin que l’agent puisse l’extraire à partir de la file d’attente et l’utiliser, ou bien de le placer en fin de la file d’attente et passer au message suivant s’il ne correspond pas à son état actuel. A partir de cela, nous avons défini les types de messages suivants :       Fig. 2. Machine à états finis d’un agent. C. Gestion de la synchronisation inter-agents Dans l’approche de résolution proposée, les agents sont distribués et interconnectés à travers un réseau informatique, où on ne dispose d’aucun contrôle sur l’acheminement et le routage des messages, et donc sur l’ordre d’arrivée des messages. D’un autre coté, on note que les agents s’exécutent à des vitesses différentes selon l’environnement où ces derniers sont hébergés. Ces deux derniers points posent le problème de synchronisation entre les agents. Il est donc important de procéder à une bonne gestion de la réception et de l’utilisation des messages reçus par chaque agent. Signalons que dans la plateforme JADE, chaque agent peut envoyer des messages d’une manière asynchrone. Il dispose également d’une file d’attente lui permettant la réception asynchrone de la part des autres agents. Afin d’assurer un fonctionnement correct du système, une bonne gestion de la file d’attente des messages doit prendre en considération le problème de synchronisation. En effet, durant son activité, l’agent passe par plusieurs états et pendant chaque état la lecture du message approprié est importante afin régler le problème de synchronisation lié aux deux points évoqués précédemment (Vitesse d’exécution et ordre d’arrivée des messages). Pour pallier au problème de synchronisation et afin de permettre à chaque agent de lire le bon message au bon   RCPT : désigne la réception des données relatives aux tâches et la décomposition du problème initial. Ce type n’est utilisé que dans l’état S1 (réception des données); DINC : message relatif aux communications interagents visant le calcul des incohérences. Ce type n’est utilisé que dans l’état S3 (Détermination des incohérences); DCAN : une catégorie de message associée à la phase de détermination du couple ayant la plus grande incohérence. Cette catégorie n’est utilisée que dans l’état S4 (Détermination du couple d’agents négociants) ; PROP : utilisé par l’agent initiateur pour faire une proposition à l’agent participant. Ce type est utilisé uniquement dans l’état S6 (Etat de négociation); CPRP : utilisé par l’agent participant pour faire une contre proposition à l’agent initiateur. Ce type est utilisé aussi dans l’état S6 ; ACPT : utilisé par l’agent participant (resp. initiateur) pour accepter la proposition (resp. contre-proposition) de l’agent initiateur (resp. participant). Ce type de message est utilisé uniquement dans l’état S6 ; CRNT : utilisé pour actualiser les valeurs des incohérences après ré-ordonnancement local. Ce type de message est utilisé par les agents en attente dans l’état S5 (Etat d’attente); FNGC : ce type exprime la fin d’une négociation, et permet aux agents en état d’attente (état S5) et aux agents négociants de passer à une nouvelle étape de détermination du couple ayant la plus grande incohérence (état S4) afin d’entamer une nouvelle négociation ou bien à l’état final (état SF) dans le cas où toutes les incohérences ont été éliminées. Le pseudo-code 1 illustre un exemple sur la gestion de la file d’attente des messages reçus durant l’état S5: Pseudo-code 1 : Gestion de la file d’attente dans l’état S5 1 : Do 2 : message = receive() ; 3 : if message.type ≠ FNGC and essage ≠ CRNT then 4: Mettre le message à la fin de la file d’atte te 5 : end if 6 : while (message.type ≠ FNGC and 7 : Traiter le message ; essage ≠ CRNT) ; Les messages qui seront traités dans cet exemple sont seulement les messages de fin de négociation FNGC (qui permettent au passage à prochaine négociation) et les messages de coordination CRNT (pour une mise à jour des connaissances après un ordonnancement local effectué par l’un des agents négociants). En effet, après la lecture du message depuis la file d’attente (Ligne 2), l’agent procède à une vérification de son type (Ligne 3). Si ce dernier ne correspond pas aux types FNG et CRNT alors l’agent le remet à la fin de la file d’attente (Ligne 4) et passe au message suivant, dans le cas contraire, l’agent procède à un traitement qui dépend du type de message lu (Ligne 7). V. CONCLUSION ET PERSPECTIVES Dans ce papier, nous avons présenté une approche multiagents pour la résolution distribuée du problème d’ordonnancement des ateliers job-shop. La démarche de résolution exploite au mieux la nature distribuée de la fonction ordonnancement en respectant l'autonomie des différents acteurs et en utilisant le paradigme des systèmes multi-agents. En effet, chaque machine est assimilée à un agent autonome qui gère son propre ordonnancement, et qui coopère avec les autres agents à travers un protocole de négociation de manière à assurer une cohérence entre les décisions prises localement. Nous avons montré le fonctionnement de l’approche à travers un exemple illustratif. Pour valider l’approche proposée, nous avons opté pour l'utilisation de la plateforme JADE afin de développer le système d'ordonnancement multi-agents. Une modélisation du comportement des agents sous forme d’une machine à état finis est proposée. Cette dernière permet aux agents d’adopter les actions appropriées selon la situation à laquelle ils sont confrontés. Nous avons aussi défini plusieurs types de messages servant d'échange lors des communications entre les agents ainsi qu’une règle de gestion des files d’attente des messages reçus au niveau d'un agent afin de résoudre les problèmes liés à la synchronisation et cela afin d’assurer un fonctionnement global correct du système. Actuellement, nous sommes en phase d’implémentation de l'approche pour sa validation à travers des tests expérimentaux sur des benchmarks tirés de la littérature. REFERENCES [1] Gotha, "Les problèmes d'ordonnancement", RAIRO Recherche Opérationnelle/Operations Research, vol. 27, no.1, pp. 77-150, 1993. [2] A.J. Davenport & J.C. Beck, "A survey of techniques for scheduling with uncertainty", http://www.eil.utoronto.ca/chris/chris.papers.html, 2000. [3] W. Herroelen & R. Leus, "Robust and reactive project scheduling: a review and classication of procedures", International Journal of Production Research, vol. 42, no. 8, pp 1599-1620, 2004. [4] J. Ferber, "Les systèmes multi-agents: Vers une intelligence collective", InterEdition, 1995. [5] M. J. Shaw and A. B. Whinston, "Distributed planning in cellular flexible manufacturing systems", Manage. Inform. Res. Center, Purdue Univ., West Lafayette, IN, Tech. Rep., 1983. [6] A. D. Baker, "Manufacturing control with a market-driven contract net", Ph.D. thesis, Rensselaer Polytechnic Inst., Troy, NY, 1991. [7] J. Liu and K. P. Sycara, "Distributed problem solving through coordination in a society of agents", presented at the 13th Int.Workshop on DAI, 1994. [8] A. Agnetis, P.B. Mirchandani, D. Pacciarelli, A. Pacifici, "Nondominated schedules for a job-shop with two competing agents", Computational and Mathematical Organization Theory, 6(2), pp. 191-217, 2000. [9] A. Agnetis, P.B. Mirchandani, D. Pacciarelli, A. Pacifici, "Scheduling problems with two competing agents", Operations Research, vol. 52, no.2, pp. 229-242, 2004. [10] S. Ourari, "De l'ordonnancement déterministe à L'ordonnancement distribué sous incertitudes", Thèse de Doctorat soutenue à l'Université Paul Sabatier de Toulouse, France, 2011. [11] A. Kouider, S. Ourari, B. Bouzouia, M. Mihoubi, "Approche Multi-Agents pour l’ordonancement dynamique d’atelier de production", 9ème Conférence Internationale de MOdélisation et SIMulation, MOSIM’12, 06 au 08 Juin, Bordeaux, France, 2012. [12] X. Weil & F. Dongmei, " Multi-Agent System for Flexible Jobshop Scheduling Problem Based on Human Immune System", Chinese Control Conference, Hefei, China, pages 2476-2480, 2012. [13] H. Wang & H. Yan, " An Adaptive Scheduling System in Knowledgeable Manufacturing Based on Multi-agent", International Conference on Control and Automation, Hangzhou, China, pages 496-501, 2013. [14] F. Hsieh & J. Lin, "A Multiagent Approach for Managing Collaborative Workflows in Supply Chains", IEEE 18th International Conference on Computer Supported Cooperative Work in Design, Hsinchu, China, pages 71-76, 2014. [15] F. Bellifemine, A. Poggi and G. Rimassa, "Developing Multiagent Systems with JADE", published in Intelligent Agents VII, LNAI 1986, pp. 89Ŕ103, 2001. [16] Foundation for Intelligent Physical Agents, "FIPA 97 Specification. Part 2, Agent Communication Language", 1997. [17] J.K. Lenstra, A.H.G. Rinnooy Kan & P. Brucker, "Complexity of machine scheduling problems", Annals of Discrete Mathematics, vol. 1, pp. 343-362, 1977. [18] J. Erschler, G. Fontan, C. Merce & F. Roubellat, "A new dominance concept in scheduling n jobs on a single machine with ready times and due dates", Journal of Operation Research, vol.1, pp. 114Ŕ127, 1983. [19] J.Adams, E.BAlas & D.Zawack, "The shifting bottleneck procedure for job shop scheduling", Management Science, vol. 34, n. 3, pp. 391-401, 1988. [20] L. Trung, "Utilisation d'ordre partiel pour la caractérisation de solutions robustes en ordonnancement", Thèse de doctorat, Laboratoire d'analyse et d'architecture des systèmes (LAAS),CNRS, Toulouse, France, 2005. [21] A. Singh, D. Juneja, A.K. Sharma, "Agent Development Toolkits", International Journal of Advancements in Technology, vol. 2, no. 1, pp. 158-164, January 2011.