Accroître la productivité en réduisant les coûts est, aujourd'hui, un objectif majeur dans toutes les entreprises, les systèmes de production sont caractérisés par leur dynamique et leur imprévision, les tâches souvent de caractère complexe et sont soumises à des contraintes de temps et d'exigence. Alors, le système de production se donne de nouveaux objectifs à atteindre.

Les modèles basés sur les approches distribuées ou décentralisés offrant des capacités d'adaptation et d'auto-organisation en utilisant, le plus souvent, les systèmes multi-agents ont fait leur preuve et ont donné des meilleurs résultats dans ce domaine.

Les métaheuristiques représentent une stratégie efficace pour la recherche des solutions approchées des problèmes d'optimisation combinatoire. L'hybridation de ces premières apparaît comme une alternative pour accélérer la recherche des solutions approchées. Cette hybridation est une issue qui permet d'intensifier la recherche de solutions et s'assurer de rester autour des zones les plus prometteuses.

L'avènement des systèmes multi-agents qui permettent de distribuer les problèmes sur des ensembles auto-organisés vers une gestion locale, favorisant réactivité et comportements émergent peut faciliter la mise en oeuvre du pilotage du système de production. En effet, le but principal d'un SMA et de faire collaborer et coopérer un certain nombre d'agents afin de résoudre un problème, nous nous proposons d'introduire au sein des agents les techniques évolutionnistes afin de leur permettre d'évoluer génétiquement dans le temps et déterminer une meilleure solution d'ordonnancement satisfaisant un certain nombre de critères.

Dans un contexte perturbé, le problème d'ordonnancement peut être envisagé comme un problème de Réordonnancement dont l'objectif est de respecter au mieux les plans pré-calculés par un ordonnancement initial, face à des aléas de production ou autres. Nous abordons cet objectif selon une approche de résolution coopérative faisant interagir l'ensemble des entités composant notre système nous conduisant à proposer des mécanismes de Réordonnancement coopératif (réactif).

Un problème d'ordonnancement consiste à affecter des tâches aux ressources et à décider de leur répartition dans le temps, de manière à optimiser un critère ou à trouver un compromis entre plusieurs critères. La résolution du problème d'ordonnancement commence par la modélisation du système de fabrication et son environnement. Alors, nous étions amenés à choisir une modélisation à base d'agents intégrant des techniques évolutionnistes.

Deux voies de résolution des problèmes d'ordonnancement sont considérées : donner une solution exacte selon une stratégie connue, ou bien donner des heuristiques qui permettent d'obtenir des solutions approchées ayant un écart raisonnable par rapport à la solution optimale ou par rapport à une borne inférieur calculée. Cependant, L'ordonnancement de production a fait l'objet d'un très grand nombre de travaux. De nombreuses approches ont été développées à base d'Algorithmes Génétiques (classiques et hybrides). Nous allons faire le point sur ces réalisations.

Des approches à base d'AG ont été développées dans différents axes comme l'optimisation du lancement des produits, les problèmes à machines parallèles, ordonnancement des placements des tâches sur les jobs, etc. ( [3], [16], [22], [19], [5] [9] [17], ces recherches concernent l'utilisation d'une approche génétique classique dans le cadre de l'optimisation des problèmes d'ordonnancement des systèmes de production de différents types.

Vu les restrictions posées par les approches citées précédemment, d'autres chercheurs ont pensé à hybrider les AGs à d'autres méthodes telle que le Recuit Simulé, les Fouilles de Données, les Règles de Priorité et les méthodes de Recherche Locale…etc. [15][22][9][7] [11] [1].

Ces réalisations et travaux par lesquels nous nous sommes inspirés pour développer notre approche hybride de résolution (AG/RL) dans le but de l'amélioration de la performance du système paraissent une bonne tentative que nous avons développée au cours de notre travail.

Un Système Multi-Agents (SMA), est une structure composée d'un environnement et d'un ensemble d'agents artificiels. Ces derniers sont capables d'agir sur l'environnement et, de collaborer entre eux et / ou avec des agents extérieurs. Les SMA empruntent à l'intelligence artificielle distribuée les modes de communication et de concertation entre agents et reprennent les idées d'autonomie et d'émergence du résultat final à partir des interactions individuelles à la vie artificielle. [6].

Les recherches en SMA sont très actives et des systèmes opérationnels ont été déjà développés dans de nombreux domaines comme le diagnostic, l'enseignement, la conception, contrôle de réseaux de communication, etc. [2], [13], [6], [14], [18], [8], [4], [20], etc. Ces recherches concernent l'utilisation de l'approche multi-agents pour structurer des architectures pour le contrôle des processus. Les pricipales motivation sont de concevoir des application (non limitées à un domaine spécifique) pour en capsuler des systèmes experts existants en vue de la coopération. Pour notre part nous avons utilisé l'approche multi-agents pour la mise en oeuvre du pilotage d'un système de production (Flow Shop Hybride), nous développons dans cet article structure de pilotage générique basée sur des agents cognitifs et réctifs.

L'architecture hiérarchique présente quelques inconvénients qui nous poussent à opter pour les architectures hétérarchiques, en effet, l'architecture distribuée supervisée (hétérarchique) constitue un compromis entre les approches distribuée et supervisée. Ce choix est motivé par les avantages qui caractérisent cette approche et qui se résument dans :  Les caractéristiques de globalisation (en terme d'optimisation ou d'objectif) qui sont celles des approches hiérarchiques : la présence d'un niveau de supervision fournit une vision et une capacité de prise de décision globale, d'où la centralisation du contrôle ;  Les caractéristiques associées aux processus d'allocation dynamique des structures distribuées qui lui octroient une capacité satisfaisante en terme de réactivité et de flexibilité, notamment vis-à-vis les perturbations par la distribution des capacités de décision des agents. Cette structure a été utilisée et a montré son efficacité, citons par exemple les travaux de [21] et [10].

Dans ce papier, nous allons donner et justifier notre choix réalisé pour le problème d'ordonnancement des ateliers Flow-Shop hybride auquel nous allons appliquer les algorithmes génétiques hybrides au sein d'un système multi-agents organisé selon une architecture hétérarchique.

Notre contribution à la résolution des problèmes d'ordonnancement évolue selon deux axes.

Le premier axe concerne l'amélioration d'une des méthodes de résolution approchées de problèmes d'ordonnancement. Notre contribution concerne la modélisation et l'étude de la structure de ces problèmes afin de proposer et mettre en oeuvre des méthodes de résolutions des problèmes d'optimisation qualifiées d'hybrides, nous avons implémenté au niveau de l'agent Superviseur une approche génétique hybride et nous avons testé réellement le fruit qu'a donné cette hybridation. L'ordonnancement initial est calculé par l'agent Superviseur dès le lancement des centres de travail la première fois.

Les AGs et la RL présentent quelques inconvénients qui peuvent être palliés en les hybridant dans une seule architecture. Les AGs sont des algorithmes de recherche globale qui possèdent un parallélisme intrinsèque Néanmoins les AGs ne possèdent pas une preuve de convergence vers l'optimum global, et souffrent aussi du mécanisme de sélection centralisé et global qui rend une population vite homogène et peut conduire de ce fait à une convergence prématurée. La RL, et malgré son caractère séquentiel, peut être combinée à l'AG (recherche globale) pour l'aider à intensifier sa recherche dans les zones les plus prometteuses (autour d'une bonne solution), dans le but de l'amélioration de la performance de l'AG. L'idée principale de cette technique est de rendre plus agressif un algorithme génétique par l'ajout d'une recherche locale en plus de la mutation. Cette recherche sera appliquée à tout nouvel individu obtenu au cours de la recherche [13].

second axe concerne l'étude et la résolution de nouveaux problèmes d'ordonnancement issus de la prise en compte des imprévus (aléas de production). En ordonnancement, ces aléas concernent la présence de tâches imprévues (nouveau ordre de fabrication) à réaliser, la disponibilité incertaine des ressources. Pour traiter ces aléas, notre approche consiste à ne pas attribuer la fonction d'ordonnancement à un agent unique comme dans le premier axe (Agent superviseur), mais émerge d'un processus de négociation inter agents, ceci permet de diminuer la charge de l'agent superviseur. Cette approche suppose que des données sont connues au moment où l'ordonnancement initial est calculé par un premier algorithme, (approche génétique hybride) dit prédictif. Les aléas (ou modification des données) surviennent alors que l'ordonnancement ainsi pré-calculé est partiellement réalisé. Il devient alors nécessaire de déterminer rapidement un nouvel ordonnancement compatible avec les nouvelles données avec une seconde méthode, dit dynamique (réactif). Cette méthode de résolution est un processus de collaboration et négociation des agents interagissant pour résoudre la situation troublée. La qualité de la solution (de la résolution) mesure alors la capacité du processus de négociation à faire face de manière satisfaisante aux aléas. Par conséquent, nous nous proposons de mettre en évidence la relation qu'il peut y avoir entre les S.M.A. et les A.G. afin de définir une nouvelle propriété des S.M.A. : la notion D'AGENTS GENETIQUES.

Nous considérons un système de production composé d'un ensemble d'agents coopératifs sous le contrôle d'un superviseur. La figure ci-dessous présente notre architecture retenue où nous distinguons l'agent Superviseur et plusieurs autres agents simples consacrés chacun à un centre de travail (Agent Etage), chacun étant constitué de ses propres ressources (machines, stock, pièces, convoyeurs…). L'itération courante de l'algorithme se termine en remplaçant la solution courante, l'individu le plus mauvais (i.e., le plus coûteux) de la population, par l'enfant C à condition qu'il vérifie la condition de diversité.

L'inclusion d'une recherche locale dans une métaheuristique permet d'intensifier la recherche autour d'une solution donnée. Une recherche locale nécessite la définition d'un voisinage N(x) pour toute solution x. En pratique, N(x) contient un petit ensemble de solutions dérivées de x par des transformations simples appelées mouvements. La procédure cherche une solution x' meilleure que x dans le voisinage N(x) de la solution actuelle x. Elle stoppe si x' n'est pas trouvée : x est alors localement optimal dans son voisinage. Sinon, x est remplacé par x' et on itère le processus.

Les systèmes de voisinage classique pour l'ordonnancement dans un problème de Flow Shop Hybride sont la p pe er rm mu ut ta at ti io on n et l l' 'i in ns se er rt ti io on n. Nous proposons d'utiliser ce type de système de voisinage pour un ordonnancement σ en entrée.

Le problème traité est celui de l'ordonnancement des N pièces en entrée du système et de l'affectation de ces pièces sur les machines. On recherche un ordonnancement et une affectation qui optimisent un critère de performance. Le critère à optimiser (minimiser) est le Cmax. Un codage spécifique de solutions est attribué à cette classe des FSH. Le génome de chaque solution est composé de deux chromosomes. L'un détermine l'affectation des jobs sur les machines et l'autre, l'ordre des jobs sur ces machines.

Les expérimentations ont été réalisées sur un PC standard, équipé d'un Pentium IV 3GHz, 512 Mo de RAM, fonctionnant sous Windows XP version 2002 SP2. Le modèle du système multi-agents est implémenté sur la plate forme SMA JADE réalisée en Java, les agents que nous avons crées sont inspirés du modèle Agent Management Reference proposé par FIPA. Ce modèle établit les règles normatives qui permettent à une société d'agents d'inter-opérer.

Afin de mieux cerner la portée de l'application des Algorithmes génétiques hybrides aux problèmes d'ordonnancement de la production et la nécessité d'améliorer les Algorithmes génétiques classiques, il convient de faire des expérimentation sur l'évolution du système dans ce champs, nous passerons après à une simulation globale du système réalisé en prenant en compte les aléas.

Pour mieux étudier le problème d'ordonnancement du FSH nous allons considérer deux problèmes du FSH et pour chacun nous varions le nombre de pièces à ordonnancer. Le premier est FH2 (P3, P2)Cmax et le deuxième FH3 (P4, P2, P3) Cmax (Figure 5). Le FH2 contient deux étages le 1 er est constitué de trois machines identiques et parallèles et le 2 eme contient deux machines identiques et parallèles, le FH3 contient trois étage, le 1 er étant composé de quatre machines identiques et parallèles, le 2 eme , deux machines identiques et parallèles et le 3 eme est composé de trois machines identiques et parallèles.

Nous avons pris le premier FSH qui est FH2 (P3, P2)Cmax, à chaque itération de simulation nous appliquons les deux algorithmes : l'AGH avec la recherche locale RL, l'AG et nous prenons les résultats donnés et ceci pour les différents nombre de pièces à ordonnancer (5,10,20,50,100). Nous fixons la recherche locale de l'AGH par l'une des trois méthodes (descente/ recuit simulé/ recherche taboue) et nous appliquons les deux algorithmes : AG avec une des méthode de la RL, Algorithme Génétique (AG), les résultats sont donnés par le graphe illustré par la figure 7 suivante : De ces constations, nous pouvons dire que l'hybridation des algorithmes génétiques avec des méthodes de recherche locale améliore clairement les performances des premiers en terme de solution.

Nous passons maintenant à présenter quelques exemples de scénarios de processus décisionnel développé ainsi que les résultats obtenus par la maquette informatique réalisée.

Rappelons que notre structure de pilotage est composée d'un agent Superviseur, Etage, Machine, Pièce, Perturbateur, Convoyeur et Stock.

Soit un Flow Shop Hybride à deux étages avec des stocks de capacité illimitée. Le 1 er étage est composé de trois machines identiques en parallèle et le second de quatre machines identiques en parallèle :

Cette phase déclenche le comportement qui concerne la recherche de la meilleure machine pouvant exécuter les tâches, et ceci en faisant appel au module génétique implémenté dans l'agent Superviseur (comme a été montré) pour déterminer les meilleurs ordonnancements et affectations des pièces aux différentes machines.

Ce plan contrôle le bon déroulement du processus en cours. Il est activé dés la détection d'une perturbation, l'ordonnancement émerge d'un processus coopératif des gents interagissant pour résoudre la situation troublée et préserver dans la mesure du possible une partie de l'ordonnancement pré-calculé. Point de vue général de la résolution La figure ci-dessous décrit les grandes étapes par lesquelles passent les agents. Cette figure permet d'identifier les points d'entrée et de sortie des flux de communication entre les agents ainsi que les actions effectuées par ces mêmes agents pour traiter les perturbations. En voici un extrait de ce processus interactif : Nous pensons à l'utilisation des systèmes distribués qui offrent des techniques de calculs performantes telles que les grilles de calcul. Ou encore l'utilisation du concept du parallélisme des AGH, et nous pensons également à l'utilisation de l'apprentissage par renforcement pour une optimisation en temps d'apprentissage et en qualité.