Algorithmes Génétiques dans un Système Multi-Agents pour l

CARDON AlainVACHER Jean-Philippe

Rapport d'Activité du projet 1998045

Algorithmes Génétiquesdans un Système Multi-Agents

pour l’Ordonnancement.

Institut Universitaire de Technologie.Place Robert Schuman

BP 400676610 Le Havre

[email protected]

[email protected]

26 Novembre 1998

Algorithmes Génétiques dans un Système Multi-Agents pour l’Ordonnancement.Rapport d'activité 1998

& 1

SOMMAIRE

INTRODUCTION................................................................................................................................................. 4

L’ORDONNANCEMENT EN GESTION DE PRODUCTION........................................................................ 5

1. PRÉSENTATION............................................................................................................................................. 52. GESTION DE PRODUCTION. ........................................................................................................................... 5

2.1. Préambule. .......................................................................................................................................... 52.2. Planning. ............................................................................................................................................. 6

3. PROBLÈMES D’ORDONNANCEMENT .............................................................................................................. 63.1. Définition du problème........................................................................................................................ 73.2. Modélisation et types de problèmes. ................................................................................................... 7

3.2.1. Modélisation.................................................................................................................................................73.2.2. Types de problèmes. .....................................................................................................................................7

3.2.2.1. Open shop. ...............................................................................................................................................83.2.2.2. Job shop. ..................................................................................................................................................83.2.2.3. Flow shop.................................................................................................................................................8

3.3. Contraintes particulières..................................................................................................................... 83.4. Qualité de la solution. ......................................................................................................................... 8

4. MÉTHODES D’ORDONNANCEMENT. .............................................................................................................. 94.1. La méthode PERT................................................................................................................................ 94.2. Les Méthodes des potentiels. ............................................................................................................... 94.3. Simulation. .......................................................................................................................................... 94.4. Apports de l’I.A. ................................................................................................................................ 104.5. Méthodes exactes............................................................................................................................... 114.6. Heuristiques. ..................................................................................................................................... 11

5. ETAPES D’UN ORDONNANCEMENT.............................................................................................................. 116. CONCLUSION. ............................................................................................................................................. 12

DESCRIPTION DU PROBLEME CHOISI ..................................................................................................... 14

1. INTRODUCTION........................................................................................................................................... 142. REPRÉSENTATION DES ATELIERS. ............................................................................................................... 14

2.1. Composition d'un atelier. .................................................................................................................. 142.2. Le fichier texte de description d'un atelier. ....................................................................................... 152.3. Description de l'atelier correspondant au fichier texte précédent .................................................... 15

3. REPRÉSENTATION DES LOTS. ...................................................................................................................... 163.1. Composition du fichier texte pour les lots. ........................................................................................ 163.2. Exemple partiel d’un fichier texte de description des lots................................................................. 16

4. COMPARAISON DE DEUX GÉNÉRATEURS ALÉATOIRES D'EXEMPLES DÉVELOPPÉS. ....................................... 174.1. Explications....................................................................................................................................... 174.2. Le premier générateur réalisé. .......................................................................................................... 184.3. Le second générateur. ....................................................................................................................... 18

5. UN PREMIER NIVEAU DE RÉSOLUTION : LE PLACEMENT . ............................................................................ 195.1. Placement contre simulation. ............................................................................................................ 195.2. Choix du placement par lots.............................................................................................................. 225.3. Modélisation objet et fonctionnement du programme....................................................................... 22

6. UTILISATION DE L'INTERFACE GRAPHIQUE. ................................................................................................. 257. CONCLUSION. ............................................................................................................................................. 26

CINQ METHODES DE RECHERCHE D'OPTIMUM .................................................................................. 27

1. INTRODUCTION........................................................................................................................................... 272. CALCUL DE L'OPTIMUM POUR DEUX EXEMPLES À 10 LOTS DE MANIÈRE ITÉRATIVE. ................................... 28

2.1. Principe. ............................................................................................................................................ 282.2. Résultats. ........................................................................................................................................... 29


& 2

3. L'ALÉATOIRE TOTAL. .................................................................................................................................. 293.1. Principe. ............................................................................................................................................ 293.2. Résultats. ........................................................................................................................................... 30

4. LA MÉTHODE DU GRADIENT........................................................................................................................ 314.1. Principe. ............................................................................................................................................ 314.2. Résultats. ........................................................................................................................................... 31

5. LA MÉTHODE DU RECUIT SIMULÉ................................................................................................................ 325.1. Principe. ............................................................................................................................................ 325.2. Résultats. ........................................................................................................................................... 34

6. LES HEURISTIQUES. .................................................................................................................................... 356.1. Principe. ............................................................................................................................................ 356.2. Résultats. ........................................................................................................................................... 36

7. COMPARAISON DES RÉSULTATS. ................................................................................................................. 378. CONCLUSION. ............................................................................................................................................. 38

PRÉSENTATION DES ALGORITHMES GÉNÉTIQUES. ........................................................................... 39

1. LES ALGORITHMES GÉNÉTIQUES : AG. ...................................................................................................... 392. INTRODUCTION AUX ALGORITHMES GÉNÉTIQUES. ..................................................................................... 39

2.1. Historique.......................................................................................................................................... 392.2. Description des Algorithmes Génétiques. ......................................................................................... 41

3. ALGORITHME. ............................................................................................................................................ 424. LES SUJETS OUVERTS SUR LES AG.............................................................................................................. 435. RAPPEL MATHÉMATIQUE. ........................................................................................................................... 436. FONDEMENT MATHÉMATIQUE ET THÉORIE [GOLDBERG 1991]. .............................................................. 447. LES REPRÉSENTATIONS POSSIBLES DU PROBLÈME. ..................................................................................... 49

7.1. La représentation ADJACENTE ....................................................................................................... 497.2. La représentation ORDINALE. ......................................................................................................... 517.3. La représentation CHEMIN. ............................................................................................................. 52

8. CONCLUSION .............................................................................................................................................. 55

UTILISATION DES ALGORITHMES GÉNÉTIQUES POUR L’ORDONNANCEMENT. ...................... 56

1. MISE EN PLACE DES ALGORITHMES GÉNÉTIQUES. ....................................................................................... 561.1. Le codage. ......................................................................................................................................... 561.2. La reproduction................................................................................................................................. 571.3. La sélection. ...................................................................................................................................... 571.4. Le déblocage. .................................................................................................................................... 581.5. La mutation. ...................................................................................................................................... 60

2. LE CROSSOVER........................................................................................................................................... 612.1. Théorie des opérateurs de crossover PMX, CX et OX. ..................................................................... 612.2. Les crossovers permutation et TG-uniforme. .................................................................................... 622.3. Le crossover simple, bi et multi points. ............................................................................................. 64

3. CHOIX DE L’OPÉRATEUR DE CROISEMENT ET DES PARAMÈTRES. ................................................................ 654. LES RÉSULTATS. ......................................................................................................................................... 705. CONCLUSION. ............................................................................................................................................. 73

MODÉLISATION AGENTS EN ORDONNANCEMENT DE PRODUCTION DE TYPE JOB-SHOP .... 74

1. INTRODUCTION........................................................................................................................................... 742. L'INTELLIGENCE ARTIFICIELLE DISTRIBUÉE................................................................................................. 743. DE L'INTELLIGENCE ARTIFICIELLE À L'INTELLIGENCE ARTIFICIELLE DISTRIBUÉE. ...................................... 74

3.1. Un premier niveau de représentation : le chromosome. ................................................................... 743.2. Placement contre simulation. ............................................................................................................ 743.3. Choix du placement par lots.............................................................................................................. 763.4. La représentation chromosomique. ................................................................................................... 77

4. EVOLUTION VERS LES SYSTÈMES MULTI-AGENTS ....................................................................................... 774.1. Concept d'agent................................................................................................................................. 78

5. MODÉLISATION AGENT D'UN ORDONNANCEMENT DE TYPE JOB-SHOP ........................................................ 785.1. Modèle de systèmes d'IAD................................................................................................................. 78


& 3

5.1.1. Contract Net ...............................................................................................................................................785.1.2. Le système Contract Net.............................................................................................................................78

6. CONCLUSION .............................................................................................................................................. 82

CONCLUSION.................................................................................................................................................... 83

LEXIQUE ............................................................................................................................................................ 84

RÉFÉRENCE AG ............................................................................................................................................... 85

RÉFÉRENCE SMA ............................................................................................................................................ 87

ANNEXE 1 : INTERFACE GRAPHIQUE. ...................................................................................................... 88

ANNEXE 2 : LISTE DES PUBLICATIONS. ................................................................................................... 89


& 4

INTRODUCTION

De nos jours, les entreprises se doivent d’être compétitives et ont besoin pour cela d’outilsperformants pour gérer la complexité de leur organisation. La gestion de production assistée par ordi-nateur appartient à ces outils permettant le contrôle et la planification du processus de production.Parmi les fonctions d’une G.P.A.O., la résolution des problèmes d’ordonnancement est encore assezmal maîtrisée. Notre projet a donc pour but d’étudier l’application des Algorithmes Génétiques dansun Système Multi-Agents pour l’Ordonnancement d’atelier.

L’ordonnancement consiste à placer différentes opérations permettant la fabrication de pro-duits sur les machines d’un atelier de façon optimale. Ceci est un problème complexe qui a fait l’objetde nombreuses études en I.A. car on ne peut pas le résoudre efficacement avec des algorithmes classi-ques. Or il existe des algorithmes partiellement aléatoires qui permettent d’améliorer la recherched’optima dans des problèmes complexes, tels que la méthode du gradient ou du recuit simulé, et aussides algorithmes basés sur les lois de la génétique appelés ainsi algorithmes génétiques. Ceux-ci ontmontré leur efficacité dans plusieurs problèmes complexes et c’est pourquoi nous allons les appliquerà l’ordonnancement.

Dans ce mémoire, nous verrons tout d’abord en quoi consiste l’ordonnancement en gestion deproduction avec différents types de problèmes et différentes méthodes pour les résoudre. Nous décri-rons ensuite le problème que nous avons choisi au niveau de l’atelier et des lots ainsi que la méthodede résolution, à savoir le placement. Nous étudierons alors 5 méthodes de recherche d’optimum quinous permettront de faire des comparaisons avec les algorithmes génétiques. Nous regarderons enfinle principe de fonctionnement de ces algorithmes puis leur application à notre problèmed’ordonnancement.


& 5

L’ORDONNANCEMENT EN GESTION DE PRODUCTION

1. PrésentationLes systèmes d’ordonnancement utilisés jusqu’à maintenant construisent, en règle générale, des

ordonnancements imprécis à cause d’un manque de connaissance sur les particularités des ateliers etdes lots de fabrication qui y accèdent. Cette constatation reflète l’un des principaux problèmes querencontre tout atelier de fabrication : problème à gérer les en-cours de fabrication et les diverses res-sources de l’atelier tant humaines que matérielles.

La difficulté de tels problèmes n’est pas étrangère à cette relative incapacité à fournir au chefd’atelier ce qu’il désire réellement : un ordonnancement assez flexible pour tenir compte des diffé-rentes contraintes et des fréquentes remises en cause. Et l’on a vu surgir nombre de méthodes pourrésoudre les différents aspects de la gestion de production (qui comprend la fonction ordonnance-ment), afin de permettre la conduite en temps réel d’un atelier.

Nous allons donc introduire dans ce chapitre de manière informelle la gestion de productionafin d’accéder au domaine qui nous intéresse : l’ordonnancement. Nous verrons alors les différentsproblèmes d'ordonnancement, les méthodes qu'on peut leur appliquer et enfin les étapes d'un ordon-nancement. Nous détaillerons le problème choisi pour appliquer des algorithmes génétiques et lesraisons de ce choix dans le chapitre suivant.

2. Gestion de production.

2.1. Préambule.Une première définition consisterait à dire que c’est un ensemble de processus qui permet de

mener à bien la fabrication de produits à partir d’un ensemble de données et de prévisions. En fait, lagestion de production regroupe un ensemble de problèmes liés à la production tels que la gestion desdonnées, la planification et le contrôle (suivi) de la production, la gestion des stocks, la prévision, etc.L’ordonnancement, thème central de cette étude, est donc une fonction liée aux autres fonctions de lagestion de production et à tous les autres aspects inhérents au bon fonctionnement d'un atelier.

Les ordonnancements de production peuvent être vus comme un moyen de transcrire les ordresde fabrication en un tableau pour les activités de fabrication. La gestion de la capacité du système estprimordiale, car n’importe quel ordonnancement valable doit être au moins réalisable. Plus largement,la capacité du système étudié est déterminée par le type de l’atelier, l’ensemble des ressources pré-sentes et les heures où elles sont disponibles. Les ordonnancements de travaux ou "jobs" (un job (onparle aussi de lot) consiste en un ensemble d'opérations (ou de tâches) pour la fabrication d'un produitunique), doivent utiliser ces ressources efficacement tout en satisfaisant les impératifs de vente. Ce-pendant l’ordonnancement de produits demandant un assemblage complexe génère d'autres contrain-tes et impératifs pour les composants manufacturés ou achetés. Ainsi lorsque l’on fabrique une grandevariété de produits la coordination entre les différents ordres de production et la commande des res-sources nécessaires à leur assemblage est une tâche difficile.


& 6

2.2. Planning.En général, un ordonnancement de production est facilité en créant un planning hiérarchisé et

en spécifiant en détail ce qui doit être fait à l’instant présent. Selon Buxey [BUXEY 1989], un telplanning doit être composé des parties suivantes :

� Un planning des besoins d’équipements essentiels (pour une période de six mois);� Ressources (planning de matière et de travail) pour un horizon de deux ans, avec unplanning mensuel révisé tous les quatre mois;� Un plan directeur de production, MPS (Master Production Schedule). Il doit stipuler lerésultat de sortie des produits finis, par semaine, pour les douze prochains mois, et êtreremis à jour mensuellement;� M.R.P. (Materials Requirements Planning). Une extrapolation du MPS aux niveauxplus bas de fabrication et les commandes par ordinateur;� Décision journalière de la priorité des jobs sur les groupes de machines de manière àrespecter les dates échues et élever la productivité.

Deux autres étapes peuvent être rajoutées :� Vérifier que les plans �, � et � sont compatibles sinon faire les modifications né-cessaires;� Suivre la progression des jobs et des commandes, lancer les procédures nécessaires à�, ou faire les modifications nécessaires à � et �; c’est le contrôle de production.

C’est au niveau de l’ordonnancement détaillé que se situera notre étude.

Planification de la production (différentes étapes)

Calcul du plan directeur

Calcul des besoins nets

Approvisionnements Ordonnancement global Lancem ent

Ordonnancement détaillé

Long term e1-2 ans

Moyen term e1-2 mois

Court term e1 jour -1 semaine

Figure 1 : Planification de production.

3. Problèmes d’ordonnancementL’ordonnancement est une fonction essentielle en gestion de production. C'est un problème dif-

ficile en raison du nombre de calculs à effectuer pour obtenir un ordonnancement qui optimise le cri-tère retenu. En outre, il existe de nombreux problèmes d’ordonnancements et diverses méthodesexactes et ou approchées ont été proposées pour résoudre une partie d’entre eux. Nous allons définirle problème d’ordonnancement et décrire quelques types de problèmes existants, ainsi que les con-traintes qui peuvent exister.


& 7

3.1. Définition du problèmeParmi les diverses définitions du problème d’ordonnancement, on retrouve l’aspect commun de

l’affectation de tâches dans le temps et dans l’espace au moindre coût et en un temps raisonnable.Nous nous plaçons ici dans le cadre d'une production à flux discontinu, c'est-à-dire avec des lance-ments en petites et moyennes séries.

Il y a problème d’ordonnancement :− Quand un ensemble de travaux (jobs ou lots) est à réaliser,− Que cette réalisation est décomposable en tâches (ou opérations),− Que le problème consiste à définir la localisation temporelle des tâches et ou la ma-

nière de leur affecter les moyens nécessaires.

E. Bensana [BENSANA 1987] définit ainsi le problème d'ordonnancement d'une productiondiscontinue : "Le problème d'ordonnancement de la production consiste à fabriquer en même temps,avec les mêmes moyens un ensemble de produits différents".

Un ordonnancement détermine ce qui va être fait, quand, où et avec quels moyens; étant donnéun ensemble de tâches à accomplir, le problème d’ordonnancement consiste à déterminer quelles opé-rations doivent être exécutées et à assigner des dates et des ressources à ces opérations, de façon à ceque les tâches soient, dans la mesure du possible, accomplies en temps utile, au moindre coût et dansles meilleures conditions.

3.2. Modélisation et types de problèmes.

3.2.1. Modélisation.La résolution d’un problème d’ordonnancement commence par la modélisation du système de

fabrication et de son fonctionnement. Il faut donc définir un ensemble de paramètres représentant lesystème étudié, les liens existant entre ces paramètres et les critères qui permettront d’évaluer lessolutions obtenues. Il est clair qu’il existe diverses manières de modéliser chaque problèmed’ordonnancement et on est amené à choisir un mode de description. Parmi ces modes, on peut citerles équations mathématiques, les graphes potentiels-tâches, les réseaux de Pétri, etc.

3.2.2. Types de problèmes.En outre, parmi les problèmes d’ordonnancement, on peut distinguer ceux à court terme (hori-

zon inférieur à quelques semaines), qui regroupent donc des problèmes où la plupart des contraintes etles tâches à effectuer sont connues (le but est donc l’affectation de ces tâches et c'est à ce niveau quenous appliquerons les algorithmes génétiques), et les problèmes d’ordonnancement à long terme (ho-rizon supérieur à quelques semaines) qui font appel à des informations beaucoup moins précises, etqui peuvent subir des changements.

Il existe différentes définitions d’ateliers et ainsi on parle de flow shop, open shop et job shopselon la nature des contraintes de précédence entre les opérations élémentaires d’un même travail.Avant cela rappelons que la gamme de fabrication d’un produit est une liste d’opérations (tâches) quidoivent être effectuées pour réaliser ce produit. La gamme fournit en outre des renseignements prati-ques sur les ressources à utiliser, les temps opératoires, bref sur les conditions de fabrication. En gé-néral elle induit des relations de précédence entre les opérations.


& 8

3.2.2.1. Open shop.On parle de problème d’open shop si : "les gammes ne sont pas complètement spécifiées. Toute

machine doit pouvoir traiter n'importe quel type d'opération, l’ordre d’exécution des opérations élé-mentaires d’un travail est totalement libre. On se contente dans ce cas de donner l'ensemble des opé-rations à réaliser sans préciser leur enchaînement." [GALINHO 1994].

3.2.2.2. Job shop.Si par contre les opérations élémentaires sont liées par un ordre total, non nécessairement iden-

tique pour tous les travaux (donc chaque produit possède une gamme spécifique), on parle de pro-blème de job shop (on parle aussi de N x M Job-Shop où N est le nombre de jobs/lots et M le nombrede machines). Le cheminement des produits dans l'atelier est spécifique à chaque article et des pro-duits différents en cours d'usinage devront vraisemblablement se croiser. Les différents produits ontdes gammes totalement définies et différentes, et la fabrication répétée d'un même produit un certainnombre de fois est appelée lot ou job. C'est ce type de problème que l'on traitera avec des algorithmesgénétiques car il semble être le plus difficile et le plus répandu.

3.2.2.3. Flow shopSi enfin les opérations élémentaires des travaux sont liées par le même ordre total, c’est à dire

que tout produit suit le même chemin dans l’atelier, alors il s’agit de problème de flow shop avec deuxvariantes, selon que le dépassement est autorisé ou non (et d’autres variantes si les stocks d’en-courssont limités ou même interdits).

3.3. Contraintes particulières.Sur ces problèmes il existe des contraintes qui peuvent être obligatoires ou sujettes à des re-

laxations :− Des contraintes de précédence entre les opérations qui sont en général absolues et

fortes,− Des contraintes physiques qui reproduisent la capacité des diverses ressources de

l’atelier,− Des contraintes de disponibilité des ressources, qui concernent à la fois les ressources

consommables (utilisables une seule fois) et les ressources récupérables, indiquant lesressources pouvant être utilisées durant une période de temps donnée (comme les ma-chines et la main d’oeuvre).

Parmi les contraintes moins fortes figurent des contraintes de respect des livraisons,d’encombrement minimal, de lissage de charge, etc.

3.4. Qualité de la solution.Ainsi on parle d’ordonnancements admissibles ou réalisables pour un ordonnancement vérifiant

ces contraintes absolues, c’est-à-dire la réalité de l’atelier et de la vie courante. Cependant si un or-donnancement est admissible il faut encore pouvoir juger de sa qualité et s’il respecte les préférencesque l’on s’est assignées. On ne peut parler de bon ordonnancement que si on l’évalue par rapport à uncritère donné. Donc il faut donner des objectifs à atteindre, au mieux, car il est toujours difficiled’optimiser une fonction comprenant plusieurs critères. On s’efforcera de satisfaire des objectifs glo-baux représentant la vision du chef d’atelier.

On peut citer, parmi les objectifs les plus importants, le respect des dates de livraison, la qualitédes produits, la limitation des en-cours de fabrication. On peut aussi envisager de respecter un niveaude stock, maximiser la productivité, répartir au mieux la charge sur les différentes machines, éviter lesgoulots d’étranglement (sources de gêne pour l’atelier et des problèmes en cas de panne). Il existe


& 9

d’autres objectifs moins rigides comme la répartition au mieux du travail, les changements compli-qués d’outils.

Le coût d’une planification est affecté de manière plus ou moins forte par tous ces objectifs etl’on ne peut les inclure tous dans notre fonction de coût sous peine de rendre difficile, voire impossi-ble, l’obtention d’une solution. Il faut aussi s’efforcer de respecter au mieux les décisions passées, etéviter de trop remettre en cause les ordonnancements. Le difficile compromis entre les différentespréférences impose donc une échelle des objectifs à satisfaire en distinguant entre ceux qui ont lapriorité et ceux que l’on ne peut satisfaire qu’à moitié (relaxation des préférences), voire délaisser.

Pour notre problème, nous prendrons pour objectif la minimisation des retards de tous les lotspar rapport aux "dates au plus tard" fixées en théorie par le chef d'atelier en fonction des autres objec-tifs. Le choix de cet objectif a été fait pour permettre d'obtenir des solutions très rapidement car lescalculs sont très nombreux avec les algorithmes génétiques et aussi parce qu'il est suffisant pour com-parer ces algorithmes avec d'autres méthodes telles que le gradient ou le recuit simulé. Tout cela seradétaillé dans les chapitres suivants.

4. Méthodes d’ordonnancement.Parmi les méthodes utilisées en ordonnancement, on peut distinguer les méthodes anciennes

comme la méthode PERT, la méthode des potentiels, la simulation ainsi que les méthodes liées àl’I.A. ou l’emploi d’heuristiques. Cependant les méthodes PERT et des potentiels ne sont applicablesque pour l’ordonnancement d’un ouvrage unitaire ou de production unitaire et le passage à la petitesérie leur est fatal. Elles doivent passer le relais à des méthodes exactes issues des techniques del’optimisation combinatoire (programmation dynamique, procédure par séparation et évaluation, etc....), à des méthodes approchées (heuristiques) ou à des algorithmes génétiques.

Ces méthodes peuvent être classées en diverses familles; nous donnons brièvement la descrip-tion de quelques familles. Dans cette partie, on traite de l’ordonnancement d’atelier qui n’est qu’undes nombreux problèmes de l’ordonnancement (emplois du temps, problèmes de tournées, découpes,projets, etc...). On trouvera le détail des méthodes suivantes et de nombreuses autres dans [GALINHO1994] au chapitre 2 : "Construction d'ordonnancement".

4.1. La méthode PERT.La méthode PERT (Program Evaluation Review Technique) a vu le jour aux Etats-Unis vers la

fin des années cinquante et a été utilisée pour la première fois sur le programme militaire des fuséesPolaris. Elle travaille sur des graphes dont les arcs définissent des tâches et les noeuds des étapes(point de départ ou achèvement de tâches). Elle se prête mal à la représentation des contraintes poten-tielles. Elle s’adapte bien aux usages du bâtiment et des travaux publics et aux problèmes similaires.La description de la méthode, ainsi que celle des potentiels, pourra être vue dans Carlier et Chrétienne[CARLIER et CHRETIENNE 1987].

4.2. Les Méthodes des potentiels.Développée en France par l’équipe de B. Roy, elle ne connaît pas les problèmes de la méthode

PERT, car ceux sont les noeuds du graphe qui représentent les tâches et les arcs les contraintes. Elles’adapte mieux aux ateliers où le fractionnement des tâches est important [ROY 1970].

4.3. Simulation.L’idée de base de la simulation est de simuler le comportement d’un atelier en faisant avancer

le temps et en chargeant les machines libres par un choix sur les opérations disponibles. L’approchede la simulation intègre donc la notion de règles de priorité lors du chargement des postes de travail.Un grand nombre de ces règles ont été citées dans la littérature. Elles ne sont pas toutes efficaces et il


& 10

n’existe pas vraiment de règle donnant de bons résultats pour tous les types de problèmes et pour uncritère donné. La thèse de Canals [CANALS 1986] donne un aperçu sur les méthodes de simulation eton y trouve une étude sur une dizaine de règles de priorité.

On peut en citer quelques-unes comme FIFO (First in first out), EDD date de livraison la plusrapprochée, SPT temps opératoire minimal, LPT temps opératoire maximal, SLACK/OPN marge libreminimale. L’emploi d’une de ces règles conduit en général à l’amélioration d’un critère bien particu-lier et tout l’art de la simulation consiste à essayer de faire de l’optimisation multicritère en ne dégra-dant pas trop les autres critères, afin d’obtenir un planning raisonnable.

Diverses règles de priorités ont été utilisées comme parties de systèmes d’ordonnancement. Parexemple, un critère d’envoi du prochain job peut être basé sur les dates au plus tard. Cependantl’utilisation exclusive de règles de priorité peut engendrer une solution incomplète et rigide. On a puvoir que les règles de priorité sont adaptées à des circonstances spécifiques et doivent être choisiespour satisfaire à des buts. Aussi, plusieurs règles de priorité ne recouvrent-elles pas des facteurs parti-culiers. Ces facteurs, comme l’importance d’un client, la nature d’un ordre ou sa destination (pour unclient ou pour le stock de sécurité) sont difficiles à représenter et à incorporer aux techniques de rè-gles de priorité.

4.4. Apports de l’I.A.Plus récemment, des techniques d’intelligence artificielle ont été utilisées avec succès pour ré-

soudre les problèmes d’ordonnancement d’atelier. Les problèmes d’ordonnancement sont résolus soitpar un raisonnement à base de règles [KERR 1992], soit par une recherche dirigée par contraintes oupar une représentation à base de frames [KUSIAK 1988].

L’un des domaines de recherche les plus récents est l’ordonnancement à base de contraintes.Dans un atelier, il y a plusieurs contraintes en conflit. Pour obtenir un ordonnancement réalisable, ilfaut les relaxer de manière sélective. Ainsi, la stratégie de résolution du problème se doit de trouver lameilleure solution qui vérifie un sous-ensemble de ces contraintes. Les contraintes peuvent servir àrestreindre le nombre de possibilités et permettre la sélection de la meilleure solution.

Le raisonnement opportuniste permet aux activités les plus prometteuses d’être accomplies sui-vant l’état actuel du problème. Cette technique d’I.A. additionnelle a prouvé son efficacité lorsquel’on doit se concentrer de manière intelligente sur un problème, comme dans le cas del’ordonnancement.

Cependant modéliser le système d’ordonnancement d’après la vision de l’ordonnanceur nefournit pas la meilleure solution automatisée. Les décisions de l’homme sont souvent une réponse àun problème momentané, donc localement optimales ou résolvant seulement la situation immédiatesans se préoccuper des effets résultants. Un système d’I.A. ne doit pas chercher à reproduire ce quefait l’ordonnanceur mais s’efforcer de penser aux conséquences d’une décision immédiate.

Divers systèmes ont été développés en France comme OPAL [BENSANA 1987] ou SOJA [LE-PAPE 1985] ou aux USA comme ISIS [FOX 1983]. Cependant ces systèmes sont confrontés à diversproblèmes dont le temps de calcul assez grand pour obtenir une solution.

Parmi les nouvelles approches on peut citer l’utilisation de CHIP [DINCBAS 1988], développéà l’ECRC de Munich; il s’agit d’un langage de résolution de problèmes combinatoires en logique,utilisant la propagation des contraintes. CHIP utilise le concept de domaine fini d’entiers associé auxvariables. Il est basé sur l’utilisation active des contraintes et de leur interaction, afin de déduirel’ensemble des valeurs possibles de chaque variable (son domaine). Si, au cours du traitement, le do-


& 11

maine d’une variable est affecté, toutes les contraintes auxquelles elle participe sont examinées. De cefait les traitements sont dirigés par les données. Si l’on a vu naître quelques applications pour desproblèmes PARTICULIERS [CERVONI 1990], on a encore des problèmes pour des applications detaille industrielle où les méthodes de la recherche opérationnelle se révèlent mieux adaptées.

4.5. Méthodes exactes.Ce sont des méthodes garantissant que la solution fournie est optimale. On peut en citer deux

grandes approches: la programmation dynamique et les procédures par séparation et évaluation.

Ces deux techniques fournissent un algorithme, sous certaines conditions, qui converge versune solution précise. En fait on rejette ou on retient des sous-ensembles de solutions en faisant del’énumération implicite. Le défaut de ces méthodes, cependant, est que pour des exemples de grandetaille, on ne peut utiliser d’algorithme exponentiel, ce qui favorise l’emploi de méthodes approchéesou heuristiques.

Dans notre étude, nous utiliserons une méthode exacte (voir le chapitre sur les méthodes derecherche d'optimum, paragraphe 2) en parcourant toutes les solutions pour de petits exemples (2 fi-chiers à 10 lots). On se limite en effet à des petits fichiers à cause des temps de calculs.

4.6. Heuristiques.Quand on choisit la prochaine tâche pour une machine, les solutions optimales peuvent être

théoriquement trouvées en un nombre fini d’itérations. Il a été montré que plus la taille du problèmeaugmente pour devenir réaliste en terme de machines et d’ordres, plus le temps pour trouver la solu-tion optimale est long. La combinatoire impliquée dans la résolution d’un ordonnancement à courtterme rend le problème trop complexe pour être résolu avec ces seules techniques.

Pour améliorer ce point un travail considérable a été fait avec les heuristiques. Plusieurs plani-ficateurs les utilisent sur une base journalière pour résoudre les besoins d’ordonnancement ou de ré-ordonnancement. Le fait d’incorporer de telles règles assez simples dans des systèmesd’ordonnancement automatique a permis d’élaborer des méthodes mieux équipées pour affronter detels problèmes.

Quelques exemples d'heuristiques seront utilisés pour notre étude mais nous en montrerons leslimites quand elles sont utilisées seules. On pourra cependant s'en inspirer pour les améliorer ou lesutiliser avec d'autres méthodes dans une étude ultérieure.

5. Etapes d’un ordonnancement.Le choix des lots et opérations à placer s’effectue de diverses manières et ce choix est primor-

dial car il intervient fortement sur la qualité de l’ordonnancement final. Il s’agit donc de démarrer àpartir de la gamme d’opérations d’un lot de fabrication qui indique les opérations à réaliser successi-vement, dans quels centres de travail et combien d’unités de temps demande le traitement de ces opé-rations.

Vient ensuite le placement de chaque opération dans le temps d’abord en respectant les diffé-rentes dates au plus tôt et de disponibilité des opérations et dans l’espace en faisant un choix (s’ilexiste) parmi les postes de travail équivalents. Tout cela peut être visualisé en utilisant un diagrammede Gantt. C'est ce type de diagramme qui sera utilisé pour notre interface graphique. L'axe des abscis-ses représente l'échelle de temps et on représente en ordonné les postes de travail de l'atelier. On ré-partit ensuite les opérations sur le diagramme en fonctions des différentes contraintes existantes. Ci-dessous, un exemple de diagramme de Gantt avec 2 lots et 3 machines :


& 12

Lot 1 Opérations durée machine11 10 M112 10 M213 30 M114 20 M3

Lot 2 Opérations durée machine21 20 M322 10 M223 20 M124 30 M2

M1 0 10 50 100

M2 0 10 50 100

M3 0 10 50 100

Figure 2 : Exemple de diagramme de Gantt.

Le positionnement des opérations sur les centres de travail peut intervenir de deux manières. Lagamme peut être soit planifiée en avant, en calant la première opération de la gamme avec la date auplus tôt et en plaçant les autres opérations en avant dans le temps, soit être planifiée en arrière, encalant la dernière opération avec la date au plus tard et en planifiant les autres opérations en arrièredans le temps (ceci n'est pas toujours possible car il faut obligatoirement respecter la date au plus tôtet ne pas commencer d'opération avant celle-ci). L'exemple ci-dessus a été réalisé en marche avant.Un autre exemple des deux types de planification est donné dans le chapitre suivant au § 5.1 : "place-ment contre simulation".

6. Conclusion.Nous avons vu que l’ordonnancement de la production comporte différents niveaux qu’on peut

énoncer ci-dessous:− La prévision et la réception des commandes,− La création d’un plan directeur,− La commande en composants de base, et− Le chargement des machines.

Le problème d’ordonnancement est un problème difficile (NP-Difficile). Il existe différents ty-pes de problèmes (Open shop, Job shop, flow shop) et plusieurs méthodes adaptées à des situationsparticulières ont été développées. Elles diffèrent par leur approche de la construction d’un planning.

231311

22 2412

21 14


& 13

Les buts à atteindre sont une utilisation optimale et rationnelle des ressources respectant les en-gagements du service commercial ainsi que les différentes contraintes de l'atelier. Un moyen de repré-senter un ordonnancement est un diagramme de Gantt. En pratique, l’impératif temps de calcul resteun élément essentiel dans la construction d’un ordonnancement.

Nous allons maintenant détailler le problème choisi pour appliquer des algorithmes génétiqueset d'autres méthodes de recherche d'optimum, ainsi que les raisons des choix effectués pour notreétude.


& 14

DESCRIPTION DU PROBLEME CHOISI

1. Introduction.Dans ce chapitre, nous allons donner et justifier les choix réalisés pour le problème d'ordonnan-

cement auquel nous allons appliquer les algorithmes génétiques. Le problème que nous avons choisiest celui du Job-Shop constitué de M machines et N lots car c'est le plus complexe et le plus répandu.Nous verrons à chaque étape comment ces choix ont été implémentés. En premier lieu, nous montre-rons comment nous avons décidé de représenter les ateliers afin qu'ils soient représentatifs du plusgrand nombre de situations réelles possible. Ensuite, nous expliquerons la façon de décrire les lots etleurs opérations de façon simple, claire, générale et encore une fois proche de la réalité. Nous verronsalors différents générateurs aléatoires d'exemples réalisés pour respecter les descriptions précédentes.Nous expliquerons enfin la méthode de placement utilisée pour la résolution du problème à un pre-mier niveau qui n'est pas optimum mais que les cinq méthodes du chapitre suivant et que les algorith-mes génétiques utiliseront pour optimiser les résultats et nous verrons aussi le fonctionnement duprogramme ainsi que l'utilisation de l'interface graphique réalisée pour visualiser la répartition desopérations sur les machines.

2. Représentation des ateliers.Chaque problème d'ordonnancement auquel nous nous intéresserons sera lié à un atelier bien

précis que l'utilisateur pourra facilement décrire à l'aide d'un fichier de type texte dont le nom est de-mandé avant chaque calcul de placement ou d'optimisation. De même, la description des lots à placersera aussi saisie dans un fichier de type texte différent du fichier précédent dont les caractéristiquesseront expliquées dans la partie suivante (3. Représentation des lots). Pour chaque utilisation du pro-gramme de placement développé (dont les principales procédures sont décrites dans la partie 5 de cechapitre : Un premier niveau de résolution, le placement), l'utilisateur devra donc saisir deux noms defichiers textes.

2.1. Composition d'un atelier.Nous avons choisi de décrire un atelier de la manière la plus générale possible en suivant des

modèles réels d'entreprises. Un atelier est donc constitué de sections (endroits de l'atelier où l'ontrouve un type d'activité spécifique), chacune de ces sections étant divisées en sous-sections où l'ontrouve les machines. Dans une même sous-section, toutes les machines sont équivalentes et peuventdonc effectuer les mêmes opérations élémentaires. C'est pourquoi dans le fichier texte de la partiesuivante, chaque opération est liée à une sous-section et non à une machine (c'est le programme deplacement qui choisira la machine la plus adéquate pour effectuer le placement de chaque opération).De plus, une même machine appartient à une seule section mais peut appartenir à plusieurs sous-sections (et donc effectuer plusieurs tâches différentes). Pour illustrer cela, voir l'exemple ci-dessous(§ 2.3). Le rendement de chaque machine permet des calculs plus fins mais n'est pas utilisé dans laversion actuelle du programme (il est donc toujours de 1).

Pour les deux fichiers textes, il est possible d'insérer des lignes de remarques en commençantcelles-ci par : " // " (même principe qu'en C++) comme dans l'exemple ci-dessous (§ 2.2). On peutaussi sauter des lignes entre chaque groupe de description (entre atelier et les sections, entre les sec-tions et les machines...). En revanche, il ne faut pas sauter de ligne ni mettre de remarque à l'intérieurd'un même groupe (entre deux sections par exemple, ou entre deux machines).


& 15

2.2. Le fichier texte de description d'un atelier.

// **********************************************************// * FICHIER TEXTE DECRIVANT LA STRUCTURE D'UN ATELIER *// **********************************************************

// Nom de l'atelier et nombre de sections :Atelier1 3

// Description de chaque section (nom et nombre et noms des sous-sections) :Section1 3 Sous-section1 Sous-section2 Sous-section3Section2 1 Sous-section4Section3 2 Sous-section5 Sous-section6

// Nombre de machines dans l'atelier12

// Description de chaque machine (nom, rendement, nombre et noms des sous-sections)

M1 1 1 Sous-section1M2 1 2 Sous-section1 Sous-section3M3 1 2 Sous-section1 Sous-section2M4 1 1 Sous-section2M5 1 2 Sous-section1 Sous-section3M6 1 1 Sous-section4M7 1 1 Sous-section4M8 1 1 Sous-section5M9 1 2 Sous-section5 Sous-section6M10 1 1 Sous-section6M11 1 1 Sous-section5M12 1 1 Sous-section5

2.3. Description de l'atelier correspondant au fichier texte précédent

Figure 3 : Description d’un atelier.

ATELIER1

SECTION 1 SECTION 3SECTION 2

sous-section 1

sous-section 5

sous-section 6

sous-section 4

sous-section 2 sous-section 3

M12M11M6 M8M1

M9M5M2

M3 M7

M10

M4


& 16

3. Représentation des lots.Comme pour la description d'un atelier, l'utilisateur peut définir les lots et leurs opérations à

l'aide du même type de fichier texte que précédemment. C'est le deuxième fichier dont il faut saisir lenom lors de l'utilisation du programme d'ordonnancement. On a donc deux fichiers textes distincts cequi permet par exemple pour un atelier donné de calculer la meilleure solution pour différents lots, oualors pour un ensemble de lots donné, on pourrait aussi chercher la meilleure configuration d'atelier.

3.1. Composition du fichier texte pour les lots.Le fichier texte suit le même principe qu'au paragraphe précédent en ce qui concerne les re-

marques et le saut de lignes. Dans ce fichier, il faut tout d'abord indiquer le nombre de lots à traiterpour le placement. Un lot (on parle aussi de job) représente un ensemble d'opérations (ou tâches) àeffectuer pour produire un type de produit. Pour un lot, ces opérations représentent la gamme qui esttotalement définie dans le cadre où nous nous plaçons, à savoir le Job-Shop.

En général, un lot permet de fabriquer un certain nombre d'un produit spécifique en série. Ladifficulté du placement provient du fait que les entreprises produisent plusieurs types de produits enmême temps et sur les mêmes machines, or une machine ne peut pas gérer plusieurs opérations de lotsdifférents simultanément. Nous supposerons dans la suite qu'une machine ne peut traiter qu'une seuleopération à la fois pour n'importe quel lot. De plus, toutes les dates et durées s'expriment dans uneunité de temps dont le choix est laissé à l'utilisateur.

Une fois le nombre de lots saisi, l'utilisateur doit ensuite décrire chaque lot, c'est-à-dire donnerson nom, la date au plus tôt, la date au plus tard et la longueur de gamme (nombre d'opérations à réali-ser pour chaque lot). Il faut ensuite décrire chaque opération de la gamme (en respectant la longueurde gamme saisie précédemment), à savoir : le nom de l'opération, sa durée sur la machine et la sous-section sur laquelle elle doit s'effectuer. Comme nous l'avons dit précédemment, les machines d'unesous-section sont identiques au niveau des opérations qu'elles peuvent effectuer. C'est donc le pro-gramme qui choisit la meilleure machine (celle de la sous-section qui est disponible la première et quia le temps d'exécuter l'opération).

Dans l'exemple partiel ci-dessous (§ 3.2), on traite 10 lots d'environ 5 opérations chacun. Cetexemple a été généré par un générateur aléatoire dont le principe est expliqué dans la partie suivante(4ème partie). Le nom des lots et des opérations est donc choisi de manière automatique, c'est-à-dire sion appelle "i" le numéro d’un lot et "j" le numéro de l'opération dans le lot, le nom du lot est : "Lot i"et le nom de l'opération est : "Op i_ j" avec i variant de 1 à 10 et j variant de 1 à longueur de gamme.Mais l'utilisateur est libre de choisir les noms qu'il désire aussi bien pour les lots que pour les opéra-tions. La seule restriction est que chaque opération ait un nom différent (car pour le programme, cenom sert d'identifiant).

3.2. Exemple partiel d’un fichier texte de description des lots.// ***************************************************// * FICHIER TEXTE DECRIVANT UN EXEMPLE DE LOTS *// ***************************************************

// Nombre de lots à traiter :10

// Description de chaque lot// (nom, date_au_plus_tot, date_au_plus_tard, longueur_de_gamme) :

Lot1 0 87 6// Description de chaque opération (nom, durée, sous-section) :OP1_1 11 Sous-section1OP1_2 8 Sous-section4


& 17

OP1_3 11 Sous-section1OP1_4 7 Sous-section1OP1_5 11 Sous-section3OP1_6 9 Sous-section1

Lot2 0 78 6// Description de chaque opération (nom, durée, sous-section) :OP2_1 7 Sous-section2OP2_2 12 Sous-section1OP2_3 11 Sous-section3OP2_4 11 Sous-section1OP2_5 7 Sous-section1OP2_6 9 Sous-section1

......

Lot10 86 168 6// Description de chaque opération (nom, durée, sous-section) :OP10_1 8 Sous-section4OP10_2 8 Sous-section2OP10_3 9 Sous-section3OP10_4 9 Sous-section2OP10_5 7 Sous-section4OP10_6 12 Sous-section1

4. Comparaison de deux générateurs aléatoires d'exemples dévelop-pés.

4.1. Explications.Afin de réaliser des tests pour comparer les résultats obtenus par différentes méthodes telles

que le gradient, le recuit simulé ou les heuristiques (voir le chapitre suivant) avec ceux obtenus avecles algorithmes génétiques, il était nécessaire de se créer une base d'exemples pour les fichiers de lots.Initialement, nous avons donc créé nos fichiers de lots de façon totalement aléatoire, puis nous avonspensé qu'il serait plus judicieux de développer un générateur aléatoire car cela prendrait moins detemps (surtout pour les exemples à plus de 20 lots) et aussi pour que ce générateur crée le fichier delots de façon à ce qu'il y ait un ordonnancement possible qui optimise le temps de travail des machi-nes, à savoir qu'il y ait le moins de temps mort possible sur chaque machine de l'atelier.

Le critère d'optimisation que nous avons choisi étant la somme des retards de chaque lot (ceretard se calcule en faisant pour chaque lot la différence entre la date de fin de la dernière opérationdu lot et la date au plus tard du lot), le générateur fixera donc les dates au plus tard des lots de façon àavoir une somme des retards nulle. On connaît ainsi l'optimum (c'est 0) pour chaque fichier de lotsgénéré par notre générateur aléatoire.

En revanche, on sait que cet optimum sera difficilement atteint car, comme cela sera expliquédans la partie suivante (5. Un premier niveau de résolution, le placement), notre algorithme de place-ment est basé sur l'ordre dans lequel on place les lots et non sur les opérations elles-mêmes. C'est-à-dire qu'on choisit un premier lot par une des méthodes citées précédemment puis on place toutes lesopérations de ce lot. On prend ensuite un second lot et on place toutes ses opérations et ainsi de suiteavec tous les autres lots. L'optimum est donc difficilement atteint, car pour cela, il faudrait gérer lesopérations une par une.

Si cela n'a pas été réalisé de cette façon, c'est que les temps de calcul auraient été beaucouptrop longs, surtout pour les algorithmes génétiques. Mais, lorsque la puissance des machines le per-mettra, il sera sans doute fort intéressant de reprendre cette étude au niveau des opérations. Pour lemoment, seuls les générateurs aléatoires développés se situent au niveau des opérations (on pourradonc reprendre la base d'exemples).


& 18

Nous avons développé deux types (deux algorithmes) de générateurs aléatoires, mais ledeuxième est beaucoup plus performant (c'est-à-dire qu'il y a moins de temps morts pour les machi-nes) que le premier comme cela est expliqué ci-dessous. Il faut aussi préciser que le second générateurne demande plus le nombre de machines, mais qu'il se base directement sur le fichier d'atelier choisipar l'utilisateur.

4.2. Le premier générateur réalisé.Le premier générateur (voir listing en annexe : "Générateur d'exemples pour l'ordonnance-

ment, Version 1) est basé sur le principe que pour chaque opération de chaque lot, on choisit une ma-chine de manière aléatoire, on fixe aussi la durée aléatoirement et on place l'opération sur la machineà la suite de l'opération précédente sur celle-ci (ou à la date de début du lot s'il n'y en a pas).

L'utilisateur doit entrer le nom du fichier d'exemple à générer, le nombre de machines, lenombre de lots, le nombre moyen d'opérations par lot et la durée moyenne d'une opération. Le fichierest alors créé automatiquement avec des remarques explicatives permettant de le modifier facilementen cas de besoin.

Le placement des opérations sur chaque machine est réalisé en prenant les lots un par un. Pourchaque lot, on fixe la date de début aléatoirement, ainsi que le nombre d'opérations (en fonction dunombre moyen saisi par l'utilisateur). Puis, pour chaque opération du lot, on choisit une des machinesau hasard, on cherche la première place libre sur la machine, et on positionne l'opération à cette placeen respectant les contraintes de dates liées aux autres opérations (celles du même lot et celles de lamachine). La durée de l'opération est alors fixée aléatoirement (mais quand même en fonction de ladurée moyenne d'une opération saisie par l'utilisateur).

Si on dépasse le nombre moyen d'opérations + 2 sur une machine, alors on choisit une autremachine pour placer l'opération. Une fois toutes les opérations d'un lot fixées, on prend la date de finde la dernière opération comme date au plus tard du lot (d'où un retard et une avance nuls). On écritalors toutes les informations nécessaires dans le fichier.

Les résultats de ce placement sont moins bons que ceux du générateur suivant car il y a encoretrop de contraintes au niveau des dates pour que les machines n'aient pas de périodes d'inoccupation(c'est-à-dire pour qu'elles soient occupées au maximum). Nous avons donc décidé de développer unsecond générateur suivant un autre principe afin d'avoir moins de "temps morts" sur les machines.

4.3. Le second générateur.C'est ce second générateur qui a été utilisé pour construire notre base d'exemples. Les fichiers

d'exemples générés ont tous été construits sur la configuration du fichier : "atelier4.txt" et leur nomindique le nombre de lots et le nombre moyen d'opérations (par exemple l20o5m4.txt signifie 20 lotsde 5 opérations en moyenne avec les 4 machines de l'atelier). On trouvera la base d'exemples en an-nexe.

Le principe de ce second générateur est de commencer par placer des cases vides de duréealéatoire (mais proche de la durée moyenne d'une opération) sur les machines en ne laissant aucuntrou. Il reste alors à remplir ces cases avec les opérations de chaque lot qui auront ainsi pour durée lataille de la case dans laquelle on les place. On respecte là aussi les contraintes de précédence.

On trouvera en annexe le listing de ce générateur (Generateur d'exemples pour l'ordonnance-ment, Version 2). Comme précédemment, l'utilisateur entre le nom du fichier d'exemple à générer.Ensuite, il donne le nom du fichier où se trouve la description de l'atelier correspondant. Cela permetde compter le nombre de machines et de voir les sous-sections correspondantes. L'utilisateur saisit


& 19

ensuite le nombre de lots, le nombre moyen d'opérations par lot, la durée moyenne d'une opération,puis pour chaque machine, il doit donner le nombre de périodes de charge de la machine et la charge(en %) de ces périodes. Cela permet de prendre en compte les périodes où la machine est moins char-gée, voire inactive. Ces périodes de charge sont de durées identiques.Par exemple, si on veut représenter une machine chargée à 100% de 8h à 12h, inactive de 12h à 14h,chargée à 80% de 14h à 16h puis à 40% de 16h à 18h, il faut entrer :5 périodes (de 2 heures) avec comme charge : 1) 100%, 2) 100%, 3) 0%, 4) 80% et 5) 40%.

Le programme crée ensuite automatiquement le fichier d'exemple avec les remarques permet-tant une lecture simple de ce fichier. Il crée tout d'abord les cases vides sur chaque machine en res-pectant la durée moyenne d'une opération, ainsi que la charge des machines. Ensuite, pour chaqueopération de chaque lot, on choisit une machine aléatoirement et on regarde la première case sur cettemachine. Si la case n'est pas vide où ne convient pas (règle de précédence), on regarde la premièrecase de la machine suivante et ainsi de suite pour toutes les machines. Si aucune machine ne convient,on fait de même avec la deuxième case de chaque machine et ainsi de suite pour toutes les cases detoutes les machines.

Une fois qu'un lot entier a été placé, on remplit le fichier d'exemple avec comme date au plustôt, la date de début de la première opération du lot et comme date au plus tard, la date de fin de ladernière opération du lot.

Les résultats sont meilleurs car la durée des opérations n'est plus fixée au niveau des opéra-tions mais directement au niveau de chaque machine et on comble les cases en regardant la machinequi convient le mieux pour chaque opération (la machine n'est donc plus choisie totalement aléatoire-ment comme c'était le cas pour le premier générateur). On a ainsi très peu de périodes d'inactivité surles machines.

5. Un premier niveau de résolution : le placement .

5.1. Placement contre simulation.Pour générer des solutions au problème d'ordonnancement, nous avons choisi une méthode de

placement par lots et non de simulation. Le placement en général consiste à prendre les opérations unepar une, regarder les machines sur lesquelles elles peuvent être réalisées, choisir celle donnant lemeilleur résultat en "plaçant" l'opération au mieux, c'est-à-dire à un endroit où la machine est libre etqui respecte les contraintes de précédence (la Nième opération d'un lot ne peut commencer qu'après lafin de la (N-1)ième opération du même lot).

Le placement par lots consiste à prendre chaque lot les uns après les autres et à placer toutesleurs opérations d'un coup. Suivant l'ordre des lots que l'on choisit pour effectuer le placement, onobtient des solutions totalement différentes (voir l'exemple 2 ci-dessous qui compare la simulationavec le placement : suivant que l'on commence par le lot1 ou le lot2, on obtient pas le même résultat).Il existe de plus deux types de placement :

− en marche avant : on part de la date au plus tôt du lot et on prend les opérations dansl'ordre en partant de la première (op1 puis op2 puis op3 et op4 dans l'exemple 1 quisuit),

− en marche arrière : on part de la date au plus tard du lot et on place les opérationsdans l'ordre inverse, c'est-à-dire en partant de la dernière (op4 puis op3 puis op2 etop1 dans l'exemple 1 qui suit).


& 20

EXEMPLE 1Lot : date au plus tôt = 0 date au plus tard = 140

Opérations durée machineop1 30 M2op2 20 M1op3 20 M2op4 40 M1

Placement en marche avant :

M1

10 50 100 150M2

10 50 100 150

Placement en marche arrière :M1

10 50 100 150

M2

10 50 100 150

Figure 4 : Exemple 1.

La simulation quant à elle, procède instant par instant en regardant les opérations qu'elle doitet peut placer sur les machines. On avance ainsi progressivement dans le temps, mais le problème estqu'en plaçant une opération trop vite, on risque de bloquer un autre lot, entraînant ainsi de grandsretards du fait de grands décalages. En effet, dans certains cas, il est préférable de retarder le lance-ment d'une opération pour gagner du temps par la suite sur un autre lot. Pour bien comprendre ce phé-nomène regardons l'exemple simple qui suit :

op4op2

op3op1

op2 op4

op3op1


& 21

EXEMPLE 2

Soient les deux lots suivants à placer sur deux machines M1 et M2 :

Lot 1 date au plus tôt = 0 date au plus tard = 70Opérations durée machine

11 10 M112 10 M213 50 M1


21 50 M222 50 M1

La simulation donnerait :

M1

10 50 100 150M2

10 50 100 150

Ce qui fait un retard de 80 pour le lot 1 et 0 pour le lot 2 ⇒ retard = 80 au total.Le placement donnerait en commençant par le lot1 :

M1

10 50 100 150M2

10 50 100 150


Ce qui fait un retard de 0 pour le lot 1 et 20 pour le lot 2 ⇒ retard = 20 au total.Le placement est donc meilleur dans ce cas. De plus, le placement en commençant par le lot 2 donne-rait le même résultat que la simulation. On a donc plus de possibilités en utilisant le placement que lasimulation et le placement est mieux adapté à notre étude (voir le chapitre sur les algorithmes généti-ques).

132211

1221

221311

2112


& 22

5.2. Choix du placement par lots.Nous avons choisi le placement par lots (c'est-à-dire prendre les lots un par un et placer toutes

leurs opérations) et non par opérations (à savoir placer toutes les opérations sans tenir compte du lotauquel elles appartiennent) pour des raisons de temps de calcul comme cela a déjà été dit précédem-ment. En effet, les algorithmes génétiques sont basés sur des vecteurs appelés chromosomes (voir lapartie correspondante), et la taille de ces vecteurs détermine le nombre de possibilités et donc le tempsde calcul. En travaillant sur un fichier de 10 lots de 5 opérations chacun, on aura :

2 10 3 715 891 20010 × =! possibilités en traitant les lots et

2 50 342432247 1050 79× = ×! . possibilités en traitant les opérations pour le mêmefichier de lots.

On voit donc l'énorme différence. On est certes sûr de trouver l'optimum dans le second casmais on ne sait pas au bout de combien de temps. Alors que dans le premier cas, les temps de calculssont plus raisonnables et suffisent pour comparer les algorithmes génétiques aux autres méthodes.

Les deux formules précédentes indiquant le nombre de possibilités s'expliquent en considérantun vecteur de N lots : pour le choix du premier lot à placer, on dispose de N possibilités (parmi les Nlots) et on peut le placer en marche avant ou en marche arrière. On a donc 2N possibilités. De mêmepour le second lot, on a 2(N-1) possibilités (il reste N-1 lots à placer), et ainsi de suite. Au total, celadonne :

2 2 1 2 2 2 2 21 2N N N NN× − × − × × × = ×( ) ( ) ... . . !

Pour les opérations le principe est le même mais le vecteur a pour longueur le nombre d'opérations.

Remarque : le placement en marche avant est toujours possible alors que ce n'est pas le cas pour lamarche arrière car il se peut que l'on commence un lot avant sa date au plus tôt, ce qui est strictementinterdit. Dans un tel cas, on placera le lot obligatoirement en marche avant.

5.3. Modélisation objet et fonctionnement du programme.Le programme de placement a été développé en C++. On dispose donc d'un graphe d'héritage

de classes que l'on trouvera ci-dessous. Sur ce graphe figurent toutes les classes avec leurs attributs etles méthodes principales. On trouvera aussi tous les attributs et toutes les méthodes dans le fichier dedéfinition des classes : CLASSES.H et pour les algorithmes génétiques : ORDOGA.H .


& 23

MODELISATION OBJET

Entité-nom------------------------------ nommer- afficher_nom

Opération- duree- date_debut- date_fin- date_debut_ci- date_fin_ci- lot- sous_section- machine_cf- machine_ci- suivante_ci- suivante_cf-------------------------------------- init- dater_ci_plus_tot- dater_ci_plus_tard- afficher- lier_machine_ci- lier_machine_cf_plus_tot- lier_machine_cf_plus_tard- enlever_machine- mere- fille

- date_plus_tot- date_plus_tard-date_debut- date_fin- date_debut_ci- date_fin_ci- duree_operatoire- longueur_gamme- operation[ ]-------------------------- dater- creer_gamme- afficher_dates- placer_plus_tot- placer_plus_tard

Lot

- nbr_sections- nbr_sous_sections- nbr_machines- nbr_lots- section[ ]- sous_section[ ]- machine[ ]- lot[ ]-------------------------------------- afficher_sections- afficher_sous_sections- afficher_lots- afficher_machines- afficher_plan_de_charge- afficher_charge_machines- init_charge_machines- reinitialiser

Atelier

Machine- plan_de_charge- tab_charge[ ]------------------------------------ afficher_plan_de_charge- calculer_charge- ajouter- derniere_operation- precedente- enlever_operation

Section- nbr_sous_sections- sous_section[ ]-------------------------------------- afficher_sous_sections- donne_nbr_sous_sections- creer_sous_sections

- rendement- nbr_sous_sections- sous_section[ ]--------------------------------------- lire_rendement- lire_nbr_sous_sections- placer_operation_plus_tot- placer_operation_plus_tard- enlever_operation- init_charge- reinitialiser

MachineCF

------------------------- placer_operation- calculer_charge- afficher_charge- init_charge

MachineCI

SousSection

- nbr_lots- lot[ ]------------------------------ creer_lots- donne_nbr_lots- afficher_lots- placement- placement_plus_tot- placement_plus_tard- calculer_retard- calculer_avance- gradient- recuit_simule

Résolution

- sens_placement- tri_primaire_lots- tri_secondaire_lots- choix_place- pourcentage_placement----------------------------------- afficher- lire_fichier

Heuristique

- nbr_machines- machine[ ]- machine_generique----------------------------- donner_nom- inc_nbr_machines

---------------------------- simplecrossover- multicrossover- select- mutation- nb_mutation- statistique- reproduction- init

ga

Cette modélisation objet permet une bonne réutilisabilité car les objets créés sont explicites etproches de la réalité. Les seules méthodes que doit normalement appeler un utilisateur sont toutescontenues dans les classes Atelier et Résolution (voir l’explication de ces méthodes ci-dessous).


& 24

Pour certaines méthodes, "ci" signifie que l'on est à capacité infinie (une machine à capacitéinfinie peut traiter un nombre infini d'opérations simultanément, ce qui n'est pas du tout réaliste maispermet d'obtenir certains résultats intéressants, comme par exemple le fait d'avoir un retard à capacitéinfini permet de dire qu'on ne pourra jamais faire mieux à capacité finie). De même " cf " dans le nomd'une méthode signifie que l'on est à capacité finie (une telle machine ne peut traiter qu'une seule opé-ration à la fois).

Les deux classes principales sont Atelier et Résolution. En effet, la première chose que fait leprogramme est de créer l'atelier ("a1") en allant lire le fichier texte dont le nom est donné par l'utili-sateur. La création de l'atelier commence avec le nom de l'atelier et le nombre de sections. On cons-truit ensuite les sections (méthode creer_sections). Pour chaque section on lit le nom puis on crée lessous-sections (méthode creer_sous_sections de la classe section). Pour chaque sous-section, on lit lenom. On remplit ensuite l'attribut sous-section de la classe Atelier à l'aide de la méthodelier_sous_sections. Enfin, on créer les machines réelles à capacité finie (méthode creer_machines).Pour cela, on lit le nombre et le nom des machines, leur rendement (à 1 dans la version actuelle duprogramme), le nombre de sous-sections auxquelles elles sont rattachées et on lie ces sous-sectionsavec celles déjà existantes afin de ne pas avoir deux objets pour la même entité (on pointe ainsi sur lemême pointeur). On fait de même entre les sous-sections et les machines (méthodelier_sous_section_machines).

Une fois l'atelier "a1" créé, on initialise un objet heuristique (h1). Le rôle de cette heuristiquesera expliqué en détail dans le chapitre suivant. Elle ne sert que pour la méthode utilisant des heuristi-ques et dans les autres cas, elle est à sa valeur par défaut, c'est-à-dire un placement aléatoire (doncsans heuristique).

On créer ensuite un objet Résolution (r1) permettant d'initialiser les lots en allant lire le fi-chier de lots saisi par l'utilisateur et de résoudre ensuite le problème de placement par l'une des mé-thodes suivantes au choix :

- Placement à capacité infinie au plus tôt : on fait un seul placement sur les lots en marcheavant sur des machines à capacité infinie (pouvant traiter un nombre infini d'opérations simultané-ment) permettant d'obtenir certains résultats utilisables par d'autres méthodes. L'ordre des lots n'inter-vient pas car on est à capacité infinie.

- Placement à capacité infinie au plus tard : même principe mais en plaçant tous les lots enmarche arrière.

- Placement au plus tôt : on fait un placement sur les lots de manière aléatoire, en marcheavant pour tous les lots et à capacité finie.

- Placement au plus tard : on fait un placement sur les lots de manière aléatoire, en marchearrière pour les lots où cela est possible (en marche avant pour les autres) et à capacité finie.

- Placement : prend en paramètre un vecteur donnant l'ordre des lots à placer. Le signe desnombres du vecteur indique le sens du placement : s'il est positif, on fait un placement en marcheavant, s'il est négatif, on fait un placement en marche arrière (quand cela est possible, c'est-à-dire àcondition de ne pas commencer une opération avant la date au plus tôt du lot).Par exemple, pour un vecteur V sur 5 lots, si on a :

V[0]= 4, V[1]= 1, V[2]= -3, V[3]= 5 et V[4]= -2cela signifie que l'on place le lot 4 en premier en marche avant, puis le lot 1 en marche avant puis lelot 3 en marche arrière puis le lot 5 en marche avant et enfin le lot 2 en marche arrière.On ne peut pas placer deux fois le même lot.


& 25

− Gradient : on réalise plusieurs placements et on cherche l'optimum avec la méthode dugradient (voir chapitre suivant).

− Recuit Simulé : on réalise plusieurs placements et on cherche l'optimum avec la méthode

du recuit simulé (voir chapitre suivant). − Algorithmes génétiques : on réalise plusieurs placements et on cherche l'optimum avec dif-

férents algorithmes génétiques (voir chapitre correspondant).

Les autres méthodes de la classe Résolution permettent de faire des calculs (calcul du retardtotal ou de l'avance totale de tous les lots à capacité finie ou infinie). Ces calculs peuvent être réalisésaprès chaque placement. Enfin, les dernières méthodes de la classe Résolution servent à une visuali-sation textuelle des placements et calculs réalisés. On peut aussi visualiser la répartition des lots surles machines en utilisant les méthodes : "afficher plan de charge" de la classe Atelier. On dispose deplus de méthodes pour calculer la charge des machines à capacité infinie (calcu-ler_charge_machines_ci de la classe Atelier) donnant les résultats en pourcentage (100 % signifie uneseule opération, 200 % signifie 2 opérations simultanées ...).

Remarque : après tout calcul de placement, si on veut faire un autre placement, il faut obligatoirementréinitialiser le programme en utilisant la méthode réinitialiser de la classe Atelier (celle-ci faisantappel à toutes les méthodes réinitialiser nécessaires des autres classes).

Pour placer les opérations sur les machines (c'est-à-dire pour créer le plan de charge des ma-chines), on utilise des listes chaînées : toute opération possède un attribut "suivante" (qui peut être àcapacité finie ou infinie : on a en effet toujours 2 listes possibles) qui sert de pointeur sur l'opérationqui se réalise juste après sur la même machine. En revanche, les méthodes "mère" et "fille" de laclasse Opération permettent de connaître les opérations précédente et suivante pour le même lot.

6. Utilisation de l'interface graphique.Afin de visualiser comment les opérations sont réparties sur les machines après chaque pla-

cement, nous avons développé une interface graphique sous Unix utilisant XWindow et la bibliothè-que de widgets : MOTIF (un widget est un objet graphique possédant des fonctionnalités propres,comme les boutons, les menus déroulants, les fenêtres avec ascenseurs...).

L'utilisation du programme est simple et en voici la description. Tout d'abord, il faut choisirl'atelier concerné par le placement. Cela se fait en choisissant dans la première fenêtre le nom du fi-chier texte correspondant, à l'aide de la souris. On doit ensuite choisir de la même façon le nom dufichier de représentation des lots. Une fois ces choix réalisés, une deuxième fenêtre s'ouvre. Celle-cise décompose en trois parties :

• la première est une fenêtre avec deux ascenseurs (un vertical et un horizontal). C'est làque l'on représentera la répartition des lots sur les machines. Cette fenêtre contient deplus quatre boutons. Les deux premiers sont des boutons permettant de choisir un ni-veau de zoom. Il existe 5 niveaux de zoom pour voir le répartition des lots de façonplus ou moins précise. Le troisième bouton sert à réaliser le placement (notammentaprès avoir changé l'ordre des lots de la troisième partie). Le quatrième bouton (FIN)permet de quitter l'application. Pour faire apparaître le dessin (ou pour le rafraîchir), ilsuffit de cliquer n'importe où dans la fenêtre ou de cliquer sur le bouton : placement.


& 26

• la seconde est une fenêtre pour représenter la légende, c'est-à-dire la couleur associéeà chaque lot. Si on clique sur un des boutons de la couleur d'un lot, le dessin de la fe-nêtre précédente fait ressortir ce lot et une autre fenêtre s'ouvre avec les informationsdétaillées de ce lot (date de début et fin de chaque opération du lot, date au plus tôt /date au plus tard du lot, retard et avance).

• la troisième partie est une fenêtre avec un ascenseur vertical permettant de représenterune liste de vecteurs donnant chacun un ordre de placement aux lots. Pour changercette liste, il faut choisir dans la première fenêtre le nom d'un fichier texte où setrouve une liste de tels vecteurs. Il faut bien sûr que la taille de ces vecteurs corres-ponde avec le nombre de lots choisi. Une fois la liste affichée, il suffit alors de choisirl'un de ces vecteurs à l'aide de la souris, puis de cliquer sur le bouton placement de lafenêtre de représentation des opérations pour voir apparaître le placement correspon-dant.

Voir Annexe pour un aperçu de l’interface graphique.

7. Conclusion.Nous avons donc vu dans ce chapitre la façon dont nous avons choisi de représenter le pro-

blème au niveau des ateliers et des lots, à savoir un problème de Job-Shop à M machines et N lotsdont la description se fait à l'aide de deux fichiers textes. Les générateurs aléatoires réalisés vont per-mettre de créer une base d'exemples afin de pouvoir comparer les différentes méthodes d'optimisationdu chapitre suivant. Le programme C++ que nous avons implémenté pour résoudre le problème d'or-donnancement est basé sur le placement par lot. La partie de visualisation réalisée sous Unix à l'aidede la bibliothèque MOTIF permet de représenter la répartition des opérations sur les machines. L'al-gorithme principal du programme permet de réaliser un placement de tous les lots suivant un ordredéfini. Cet algorithme se contente de calculer les retards engendrés par le placement mais il n'optimisepas celui-ci. C'est le rôle des méthodes du chapitre suivant qui utilisent cet algorithme de nombreusesfois jusqu'à trouver l'ordre des lots donnant le retard cumulé le plus petit.


& 27

CINQ METHODES DE RECHERCHE D'OPTIMUM

1. Introduction.Pour les cinq méthodes qui suivent (itératif, aléatoire total, gradient, recuit simulé, et heuristi-

ques), le but est d'optimiser (minimiser) le retard total et l'avance totale, c'est-à-dire la somme desretards de tous les lots en effectuant un ou plusieurs placements successifs en changeant l'ordre deslots. Le retard de chaque lot se calcule de la façon suivante :

date de fin de la dernière opération du lot - date au plus tard du lot.Si ce nombre est négatif, on considère que le retard est nul. Les méthodes ont été réalisées sur lamême base d'exemples afin de pouvoir comparer les résultats obtenus. Cette base est constituée desfichiers :

- l10o3m4.txt : 10 lots, 3 opérations environ par lot- l10o5m4.txt : 10 lots, 5 opérations environ par lot- l10o10m4.txt : 10 lots, 10 opérations environ par lot- l20o3m4.txt : 20 lots, 3 opérations environ par lot- l20o5m4.txt : 20 lots, 5 opérations environ par lot- l20o10m4.txt : 20 lots, 10 opérations environ par lot- l50o3m4.txt : 50 lots, 3 opérations environ par lot- l50o5m4.txt : 50 lots, 5 opérations environ par lot- l50o10m4.txt : 50 lots, 10 opérations environ par lot- l50o10m10.txt : 50 lots, 10 opérations environ par lot- l100o10m4.txt : 100 lots, 10 opérations environ par lot- l100o10m10.txt : 50 lots, 10 opérations environ par lot

Le fichier d'atelier correspondant est : "atelier4.txt" et il correspond à l'atelier suivant :

// Nom de l'atelier et nombre de sections :Atelier4 3

// Description de chaque section (nom et sous-sections) :Section1 2 Sous-section1 Sous-section3Section2 1 Sous-section2Section3 1 Sous-section4

// Nombre de machines dans l'atelier4

// Description de chaque machine (nom, rendement et sous-sections)

M1 1 1 Sous-section1M2 1 1 Sous-section2M3 1 1 Sous-section3M4 1 1 Sous-section4

Cet atelier est donc très simple mais cela suffit pour comparer les résultats des différents mé-thodes et cela permet surtout d'avoir des calculs rapides. On peut simplement remarquer que plus il ya de machines dans l'atelier et meilleurs sont les résultats. Mais pour pouvoir faire des tests compara-tifs, il faut se baser sur le même atelier.


& 28

2. Calcul de l'optimum pour deux exemples à 10 lots de manière ité-rative.

2.1. Principe.Les méthodes qui suivent, ainsi que les algorithmes génétiques ne parcourent pas l'ensemble

de toutes les solutions pour trouver l'optimum. On n'est donc pas sûr de le trouver. Le meilleur moyenpour le trouver est de calculer le retard pour toutes les solutions possibles. C'est donc par cela quenous avons commencé pour avoir un point de repère. Le problème dans ce cas est le temps de traite-ment puisque, comme nous l'avons dit précédemment dans la partie 5.2 du chapitre précédent (choix

du placement par lots), la formule donnant le nombre de solutions est : 2N N× ! où N représentele nombre de lots. Ainsi, pour 10 lots, nous avons donc :

2 10 3 715 891 20010 × =! possibilités.Le temps de calcul prend alors plusieurs jours (ce nombre dépend de l'ordinateur utilisé et du nombred'opérations par lot). A titre d'exemple, il faut environ 7 jours sur une machine Sun pour le fichierL10O3M4.TXT (c'est-à-dire 3 opérations en moyenne par lot).

Pour réaliser ces calculs, nous avons tout d'abord utilisé le principe le plus simple, c'est-à-direparcourir réellement l'ensemble de toutes les solutions, en utilisant des boucles imbriquées. Pour unexemple à 5 lots, on parcourt pour le choix du premier lot toutes les possibilités, à savoir de -5 à +5(sauf 0). Pour chacune de ces possibilités, on choisit le second lot de -5 à +5 (sauf 0 et sauf le numérodu premier lot) et ainsi de suite pour les trois derniers lots.

Etant donné le nombre des solutions possibles, nous avons ensuite optimisé l'algorithme defaçon à être sûr de trouver quand même l'optimum. Pour cela nous avons repris l'algorithme précédent,mais au lieu de calculer le retard cumulé une fois tous les lots choisis, nous calculons le retard dechaque lot à chaque boucle, et nous le cumulons avec les retards des lots déjà placés. Si ce retard cu-mulé partiel est supérieur à l'optimum courant, on coupe l'algorithme, c'est-à-dire qu'on ne cherche pasà calculer le retard des lots restants puisque le retard cumulé sera de toute façon supérieur à l'opti-mum. On passe directement au chiffre suivant pour le lot courant. Prenons un exemple pour bien il-lustrer cela.

Soit un exemple à 5 lots. On suppose que l'optimum courant est de 100 (meilleur retard obte-nu). On se place à un moment du programme où le premier lot a déjà été choisi (-4 par exemple, cequi correspond au lot 4 placé en marche arrière) et où son retard est de 50. On doit maintenant choisirle second lot. On part de -5, cela donne un retard de 30. On est donc à un retard cumulé de 80 qui esttoujours inférieur à 100. On continue avec le troisième lot : -3 (car les lots 4 et 5 sont déjà pris). Ce-lui-ci donne un retard de 30. On est donc cette fois à un retard cumulé de 50+30+30=110 > 100. Onne calcule donc pas les quatrièmes et cinquièmes lots, mais on passe directement à -2 pour le troi-sième lot et ainsi de suite.


& 29

Au lieu de faire :

Nous n'avons fait que :

Dans l'exemple, on économise donc 12 calculs rien que pour la première branche. Pour accé-lérer encore le temps de calcul de cette méthode, nous fixons un optimum de départ à l'aide de la mé-thode du recuit simulé (voir §5). Il est en effet très important d'avoir un optimum de départ proche del'optimum réel pour gagner le plus de temps possible.

2.2. Résultats.Etant donné les temps de calculs, nous n'avons les optima que pour deux fichiers à 10 lots. La

solution n'est jamais unique et dans certains cas, l'optimum peut être obtenu pour un grand nombred'ordres de lots différents. Pour le fichier d'exemple : L10O3M4.TXT, l'optimum obtenu est de 20unités de temps (retard minimal). Celui-ci est obtenu 2879 fois alors que l'on a 3 715 891 200 possi-bilités ce qui fait un rapport de 1 pour 1 290 688. On a donc malgré cela peu de chance de trouver cetoptimum. Pour le fichier d'exemple : L10O5M4.TXT, l'optimum obtenu est de 70 unités de temps(retard minimal). Celui-ci est obtenu beaucoup moins de fois que précédemment. On a donc encoremoins de chances de le trouver de manière aléatoire.

3. L'aléatoire total.

3.1. Principe.Le principe de l'aléatoire total est de réaliser un grand nombre de placements en changeant à

chaque fois l'ordre des lots et leur sens de placement de manière totalement aléatoire. On regarde alorsà la fin le meilleur retard obtenu. Entre chaque placement, on mélange l'ordre des lots et on change lesigne d'un nombre de lots fixé aléatoirement.

-5

-4

-3

-3-1

-2

-1

-2

+1

+1

-2

-1

+1

+2

-1+1-2+2-2+2-1+1

STOP-5

-4

-3

-3-1

-2

-1

-2

+1

+1


& 30

Pour réaliser le mélange de l'ordre des lots, on utilise la procédure "mélange". On prend le loten première position et on l'échange avec le lot d'une position tirée au hasard. Par exemple, si on ainitialement (pour 5 lots) l'ordre suivant : 1 5 3 2 4 et que l'on tire au hasard la position 4, on auraensuite : 2 5 3 1 4. On recommence de même avec le lot en position 2 et ainsi de suite avec toutes lespositions.

Le changement de signe est très simple à réaliser avec la procédure changer_signe. En effet, ilsuffit de choisir une position de manière aléatoire dans notre vecteur donnant l'ordre des lots et demultiplier le nombre obtenu par -1. En reprenant l'exemple précédant : 2 5 3 1 4, si on tire la position3, on obtiendra alors : 2 5 -3 1 4. Cela signifie que l'on commencera par placer les opérations du lot 2en marche avant, puis celles du lot 5 en marche avant, puis celles du lot 3 en marche arrière, puis cel-les du lot 1 en marche avant et enfin celles du lot 4 en marche avant.

A chaque fois que l'on trouve un meilleur résultat, on affiche ce dernier, le nombre de place-ments déjà réalisés et le vecteur ayant permis de l'obtenir.

3.2. Résultats.Pour comparer les temps d'exécution de chaque méthode, nous avons réalisé des tests de

temps sur chaque fichier d'exemple. Voici ces temps en secondes pour 100 000 placements.

Nom du fichier Temps d'exécution en secondesl10o3m4.txt 16l10o5m4.txt 51

l10o10m4.txt 244l20o3m4.txt 52l20o5m4.txt 270


l50o10m4.txt 8700

Tableau 1: Temps de calculs nécessaire pour chaque fichier pour l’aléatoire total.

Pour chaque fichier d'exemples, nous avons réalisé une série de 10 tests dans chacun desquelson effectuait 200 000 placements. Nous allons donner la moyenne des optima et le meilleur vecteurobtenus à chacun de ces tests pour comparer les différentes méthodes entre elles.

Nom du fi-chier

Moyenne desmeilleurs retards

Meilleurretard

Meilleur vecteur obtenu

l10o3m4.txt 47.8 36 6 8 5 -9 4 -2 -3 -1 10 -7l10o5m4.txt 134 91 5 -2 -7 -3 -10 4 1 9 -6 -8

l10o10m4.txt 352 327 3 -4 1 5 -2 -8 7 -10 9 -6l20o3m4.txt 158 135 -5 -6 -8 -20 15 -12 -1 2 -17 14

-10 -16 -13 -4 -3 7 9 -18 19 -11l20o5m4.txt 519 461 2 -1 6 -12 15 -3 -9 7 14 -18

16 -10 -8 19 5 -4 17 11 -20 -13l20o10m4.txt 1131 931 -18 3 -4 2 -16 -6 -11 1 -13 8

-9 -14 7 -12 20 -15 -5 -17 -19 10l50o3m4.txt 1251 1083 -4 6 48 -37 16 40 2 -29 -18 -34 15 -14 44 -30 7 33 -17

21 -3 1 27 20 39 50 -31 10 26 45 28 -24 9 41 8 47 3825 23 49 -19 -32 -43 -46 -22 11 -13 36 -35 -42 5 -12

l50o5m4.txt 3144 3000 -7 -13 -43 32 48 36 44 -8 3 -40 -30 -17 19 21 50 18 414 -15 -45 -49 -47 -34 -25 39 9 1 16 38 12 11 -42 5 -31


& 31

-24 23 27 -37 14 -22 6 20 -26 33 -10 -35 -29 -46 -28 2l50o10m4.txt 6831 6418 -29 -18 36 -37 -40 -21 38 2 3 7 -34 5 -16 47 20 22 -12

42 -26 19 25 -31 -27 -4 -13 6 46 -41 -44 -9 -15 24 10 -48-33 14 -45 -49 8 35 -28 -1 -11 -43 -50 -32 39 -17 30 23

Tableau 2 : Résultats de l'ordonnancement pour les différents fichiers pour l’aléatoire total.

4. La méthode du gradient.

4.1. Principe.Le principe de cette méthode est très proche de l'aléatoire total. On procède de même que pour

la méthode précédente, mais au lieu de tout mélanger entre chaque placement, on se contente d'échan-ger 2 lots de place et d'effectuer un seul changement de signe sur le vecteur ayant donné le meilleurrésultat et non plus sur le dernier vecteur obtenu. On garde ainsi la trace des vecteurs ayant donné debons résultats et on les modifie pour obtenir des résultats encore meilleurs. Le problème de cette mé-thode est que l'on peut rester bloqué sur un optimum local et donc ne jamais trouver l'optimum réel. Sion veut tracer le résultat obtenu en fonction du temps, on aura une courbe du type suivant :

Figure 6 : Evolution du gradient au cours du temps.

Dans le programme de placement, le gradient est une méthode de la classe Résolution. v_minest le meilleur vecteur obtenu à chaque instant, et v est le vecteur sur lequel on effectue les opérationsd'échange et de changement de signe. Le critère d'arrêt est le nombre de placements réalisés. A chaquefois que l'on trouve un meilleur résultat, on affiche ce dernier, le nombre de placements déjà réaliséset le vecteur ayant permis de l'obtenir.

4.2. Résultats.Tests de temps pour 100 000 placements :




retard

temps


& 32

l50o10m4.txt 5400

Tableau 3 : Temps de calculs nécessaire pour chaque fichier pour le gradient.

Ces temps sont meilleurs que pour l'aléatoire total car on ne fait pas de mélange complet deslots à chaque placement, or le temps d'exécution de l'algorithme de mélange est assez long.

Pour chaque fichier de la base d'exemples, nous avons aussi réalisé une série d'une dizaine detests de 20 000 placements chacun. Pour les résultats, nous mettrons là aussi la moyenne des meilleursretards obtenus à chacun de ces tests et le meilleur vecteur (ordre des lots) obtenu.

Nom du fi-chier

Moyenne desmeilleursretards

Meilleurretard


l10o3m4.txt 45.4 36 6 -4 5 8 -9 2 -3 -7 -10 1l10o5m4.txt 140 84 -4 5 1 6 9 -2 7 -3 -10 8

l10o10m4.txt 370 337 -9 1 -2 -6 5 4 -3 -8 -10 7l20o3m4.txt 124 28 -5 -1 -11 20 2 3 7 -18 -15 10 6 16 -8 9 -14 19 13 4 17 12l20o5m4.txt 388 323 9 14 16 3 15 6 -11 -12 17 -10 -4 -1 8 -13 -2 -18 19 -5 -20 7

l20o10m4.txt 957 739 3 -11 4 -15 13 2 -6 -12 16 -1 -7 -9 17 5 -8 14 -10 18 19 -20l50o3m4.txt 924 755 -35 16 4 18 -41 -7 19 1 6 10 -22 28 -17 -46 23 29 9 48 -5

-38 27 13 -25 24 -12 31 3 -39 -45 20 -26 -43 37 -21 40 4442 -47 -50 15 32 -2 30 33 8 -36 -11 34 -49 -14

l50o5m4.txt 2394 1876 35 17 -15 3 4 -10 -24 13 1 -34 12 16 33 25 27 32 48 4345 18 -14 36 26 -23 -30 19 40 29 -22 6 -31 20 -2 -9 39

42 11 28 44 37 -5 38 41 -47 -46 -7 -8 21 50 49l50o10m4.txt 5300 4631 18 -27 -36 -42 22 -28 -20 -50 -16 6 39 -44 21 -29 2 45 -1

-19 -48 40 -17 -49 -24 14 -25 -3 41 -32 -31 26 -15 -33 -5-8 -10 34 -4 -23 -35 7 43 -47 -13 30 9 12 -38 37 46 -11

Tableau 4 : Résultats de l'ordonnancement pour les différents fichiers pour le gradient.

5. La méthode du recuit simulé.

5.1. Principe.Le principe du recuit simulé nous vient de la cristallographie. Pour obtenir un cristal très pur à

partir d'un cristal quelconque, on commence par le chauffer, puis on le refroidit très lentement. L'in-terprétation de cela est que : "le cristal initial est dans un état d'énergie minimale, mais il s'agit d'unminimum local. En chauffant, il peut s'élever, quitter le minimum local, et se diriger vers un autreminimum. On va s'efforcer d'obtenir un minimum global." [ZOONEKYND 1994]. Pour tenter d'éviterde rester bloqué dans un minimum local (comme c'est souvent le cas avec la méthode du gradient), lerefroidissement doit être très lent. Un refroidissement brusque correspondrait à une descente rapidevers le minimum local le plus proche. Pour plus d'informations sur cette méthode ainsi que les dé-monstrations mathématiques de convergence, voir [ZOONEKYND 1994]. Nous allons maintenantappliquer ce principe à notre problème en utilisant l'algorithme de Métropolis :

Soit E0 l'énergie de l'état courant;Répéter

Choisir un nouvel état d'énergie E1 ;Soit P la probabilité : ð 1 si E1 < E0


& 33

ð expE E

kT0 1−

si E0 < E1 (k représentant la

constante de Boltzmann).L'état courant devient alors le nouvel état (E0 prend la valeur de E1) avec la probabilité P, et

dans le cas contraire, l'état courant reste inchangé.Fin.

Dans notre problème, les énergies représentent la valeur du retard total après placement, doncE0 représente le retard minimal courant et E1 le retard qui vient d'être calculé pour le placement cou-rant. Nous prendrons de plus la constante de Boltzmann égale à 1. Pour nous, la température T sera unparamètre de contrôle de l'algorithme.

On explique l'algorithme de Métropolis pour notre problème en se basant sur la méthode dugradient : quand E1 < E0 , on a P=1, c'est-à-dire que l'on a trouvé une meilleure solution donc on lagarde. En revanche, quand E1 > E0 , la méthode diffère du gradient puisque on accepte de dégrader lasolution avec une probabilité égale à P. Mais il ne faut pas que cette probabilité reste constante, sinonon dégraderait toujours et on aurait peu de chance d'obtenir l'optimum. C'est pourquoi il convient debaisser la température pour que P tende vers 0. Mais il faut aussi faire attention à ce que T ne baissepas trop vite sinon on risque de rester bloqué sur un minimum local (donc sous-optimal).

Il existe donc différentes procédures de refroidissement. Celle que nous avons choisi pournotre algorithme consiste à baisser la température par plateaux (elle reste constante pendant un nom-bre fixe d'itérations), puis on utilise un refroidissement exponentiel (c'est le cas dans la plupart desimplémentations pratiques du recuit simulé), c'est-à-dire du type :Tn = T0 . an, avec a<1 et proche de 1 (dans notre algorithme, a = 0.95).La convergence de ce type de refroidissement est plus rapide que pour un refroidissement logarithmi-que ( Tn = R / log n ) mais la convergence n'est plus certaine.

Voici le type de courbe que l'on obtient :

Figure 7 : Evolution du recuit simulé au cours du temps.

retard

temps


& 34

Dans notre programme, le recuit simulé est une méthode de la classe Résolution. Le vecteur vreprésente le nouvel état et le vecteur v_min l'état courant (meilleur vecteur trouvé). Les énergiesassociées à ces deux vecteurs sont retard et retard_min. Une difficulté de ce type d'algorithme est detrouver la valeur de T0. Pour la déterminer, on cherche à atteindre au moins 80% de dégradation durésultat initialement (sur 200 essais, il faut que l'on garde une solution moins bonne au moins 160fois). Si c'est le cas, on garde la valeur de T0 , sinon on multiplie cette valeur par 2 et on recommence.

Ensuite, on passe à l'algorithme du recuit simulé lui-même. On fixe un nombre de placementsquelconque pour le critère d'arrêt (de l'ordre d'au moins 10 000) et on utilise l'algorithme de Métropo-lis adapté à notre problème. Chaque fois que l'on trouve une solution meilleure, on la garde et on affi-che le retard correspondant, le nombre de placements réalisés et le vecteur v_min. Sinon, on calcule laprobabilité (fonction proba), on tire un nombre au hasard entre 1 et 100 et si la probabilité est supé-rieure à ce nombre, on dégrade la solution.

La taille des plateaux pendant lesquels notre température reste constante est : nombre de lotsau carré. Le refroidissement est exponentiel : T T= ×0 95. .

5.2. Résultats.Tests de temps pour 100 000 placements :



l20o10m4.txt 3845l50o3m4.txt 1457

Tableau 5 : Temps de calculs nécessaire pour chaque fichier pour le recuit simulé.

Ces temps sont plus longs que pour les autres méthodes car on doit effectuer le calcul de T0 etle calcul de probabilités à chaque placement. Pour chaque fichier de la base d'exemples, nous avonsaussi réalisé une série d'une dizaine de tests de 20 000 placements chacun. Pour les résultats, nousmettrons là aussi la moyenne des meilleurs retards obtenus à chacun de ces tests et le meilleur vecteur(ordre des lots) obtenu avec le meilleur retard correspondant.

Nom du fi-chier

Moyenne desmeilleursretards

Meilleurretard


l10o3m4.txt 22.6 20 5 -3 -2 6 -1 -7 8 -104 -9

l10o5m4.txt 111 91 -7 5 -10 -2 -1 -3 -4 -69 8

l10o10m4.txt 348 322 1 3 -5 4 -2 7 -8 610 -9

l20o3m4.txt 159 98 -10 -5 4 -13 -6 -1 -18 14 2 16-11 -3 20 19 17 7 8 -15 -12 9

l20o5m4.txt 484 416 5 -14 1 -2 9 16 -20 -15 -4 12-11 3 -8 6 -18 -10 -17 -19 -13 -7

l20o10m4.txt 1117 1067 13 4 -16 6 -7 12 -9 1 8 15-3 -11 -17 -18 -14 20 19 2 -5 -10

l50o3m4.txt 1226 1121 31 30 -26 40 46 41 34 -14 -5 -28 -11 -27 4 6 32 1 36 25


& 35

39 13 -47 18 16 49 20 35 50 -2 15 -9 -12 33 3 23 7 -42-21 22 45 17 -44 -38 24 29 19 -43 8 -37 10 -48

l50o5m4.txt 3120 2895 -11 10 40 6 -35 16 -29 34 41 28 4 39 -43 -9 50 -15 -26-24 -38 -5 -20 -3 46 -33 -8 -1 -48 -7 37 44 47 23 30 -4213 -45 -12 -2 -32 -49 27 -17 -21 -14 -18 36 -31 19 22 25

l50o10m4.txt 6820 6674 -43 -46 -44 41 2 13 -40 20 -11 48 16 22 1 -14 36 34 5 -647 4 -30 28 -8 -9 -29 35 -50 25 -12 -31 -32 -3 7 -19 45 -15

37 -24 -18 -38 -39 -17 21 -42 -10 -23 33 -26 -27 -49

Tableau 6 : Résultats de l'ordonnancement pour les différents fichiers pour le recuit simulé.

6. Les heuristiques.

6.1. Principe.Cette méthode diffère des autres car elle ne fait pas une recherche systématique de l'optimum

en effectuant plusieurs placements. Elle permet juste d'obtenir des résultats en utilisant différentesheuristiques. Chacune de celles-ci permet d'obtenir un ordre de priorité entre les lots en effectuant unseul placement. Les résultats obtenus serviront donc de comparaison, surtout au niveau de l'ordre deslots obtenus, et non simplement au niveau des retards cumulés. En effet, les heuristiques sont desméthodes permettant de guider le choix de l'ordre des lots en se basant sur une évaluation des résultatsfuturs de ce choix. Pour notre problème d'ordonnancement, il en existe un grand nombre et on peutmême les combiner entre elles. Nous nous contenterons ici d'en présenter douze. Pour plus d'informa-tions sur ces heuristiques (pour l'ordre de priorité des lots), voir [PANWALKER 1977].

Pour l'utilisation des heuristiques, nous utilisons là aussi un fichier texte, mais qui est uniquecette fois : "HEURISTI.TXT". Dans celui-ci, les douze heuristiques sont nommées et l'utilisateur secontente d'en choisir une avec un numéro. Pour utiliser les autres méthodes précédentes, il faut choisirl'heuristique 13 (c'est-à-dire aléatoire). Ci-dessous, le détail de ce fichier :

// **********************************************************// * FICHIER TEXTE DECRIVANT LES HEURISTQUES A UTILISER *// **********************************************************

// Sens du placement ( 1)avant - 2)arrière )1

// Tri primaire des lots :// ---------------------// 1) date_au_plus_tard_croissante 2) date_au_plus_tard_decroissante// 3) duree_operatoire_croissante 4) duree_operatoire_decroissante// 5) longueur_gamme_croissante 6) longueur_gamme_decroissante// 7) duree_moyenne_ci_croissante 8) duree_moyenne_ci_decroissante// 9) retard_previsionnel_croissant 10) retard_previsionnel_decroissant// 11) marge_moyenne_operatoire_croissante 12) decroissante// 13) aleatoire12

// Tri secondaire des lots :// -----------------------// Memes criteres que precedemment13

// Pourcentage de temps reclame au placement100

L'utilisateur doit donc choisir quatre critères :

1) le sens de placement : marche avant ou marche arrière,


& 36

2) le tri primaire des lots : c'est à ce niveau que l'utilisateur choisit une des douzeheuristiques (la treizième est utilisée pour les autres méthodes). Voir le détailde celles-ci ci-dessous.

3) le tri secondaire des lots : choix d'une seconde heuristique pour départager leslots qui n'ont pu l'être avec le premier tri. Cela permet donc la combinaison dedeux heuristiques.

4) pourcentage de temps réclamé au placement : cela permet de réaliser un place-ment plus fin en autorisant certaines opérations qui n'ont pas la place d'être pla-cés sur une machine à être placés quand même en décalant les autres opérations(limité à un certain pourcentage de temps de "débordement"). Pour le détail dece principe, voir [GALINHO 1994], chapitre 5, pp 245-255.

Les deux derniers critères n'ont pas été implémentés mais ont été placés pour réaliser un pla-cement plus fin dans les versions futures du programme. Pour le pourcentage de temps réclamé auplacement, on mettra donc 100 dans la version actuelle du programme.

La plupart des heuristiques sont tirées de [GALINHO 1994], chapitre 5 et voici leur signifi-cation :

- 1 et 2 : on se base sur la date au plus tard de chaque lot.- 3 et 4 : on regarde la durée opératoire (ou temps de traitement) des lots (somme

des durées de toutes les opérations d'un lot). Une variante consiste à regarder la durée moyenne opé-ratoire qui est la durée opératoire divisée par le nombre d'opérations.

- 5 et 6 : le tri est réalisé sur la longueur de gamme de chaque lot (nombre d'opé-rations de chaque lot).

- 7 et 8 : on utilise la durée moyenne à capacité infinie qui se calcule après avoir

réalisé un placement à capacité infinie avec la formule suivante : duree du lot

longueur gamme .

- 9 et 10 : on prend le retard prévisionnel : là aussi il faut effectuer un placement àcapacité infinie. Ce retard représente alors le retard algébrique à capacité infinie, c'est-à-dire l'écartentre la date échue (date au plus tard) et la date de fin de traitement à capacité infinie.

- 11 et 12 : on utilise la marge moyenne opératoire qui correspond à la différenceentre la date au plus tard et celle au plus tôt (temps alloué), divisée par la longueur de gamme.

6.2. Résultats.Cette méthode ne calculant pas l'optimum en effectuant plusieurs placements, nous allons

donner le résultat obtenu pour chaque fichier d'exemple et pour chaque heuristique. Nous donneronssimplement le retard obtenu à chaque fois. Pour le détail des résultats, voir en annexe.Aucune des heuristiques ne s'occupant du sens de placement, on a deux tableaux de résultats : le pre-mier correspond aux lots placés en marche avant et le second en marche arrière. Les résultats pour-raient donc être améliorés en mélangeant cette méthode avec les précédentes.

Retards en marche avant :Heuristiques

Nom du fichier 1 2 3 4 5 6 7 8 9 10 11 12l10o3m4.txt 161 144 156 124 147 124 139 125 110 128 127 173l10o5m4.txt 131 326 232 431 185 431 258 378 338 235 235 305

l10o10m4.txt 711 945 657 717 617 639 770 586 994 507 776 878l20o3m4.txt 281 658 517 625 260 625 476 441 761 381 463 387l20o5m4.txt 662 1590 988 1692 793 1743 1569 1673 1275 1039 1104 1526

l20o10m4.txt 1460 2890 1865 2470 1971 2495 2265 2302 2056 1838 2093 2378


& 37

l50o3m4.txt 1188 3005 1993 2603 2103 2603 2662 2908 2665 1873 1822 2592l50o5m4.txt 2535 7342 4539 6274 4528 6441 6298 4843 7498 6092 4979 5700

l50o10m4.txt 6694 15256 9026 11428 9114 11625 10553 12566 11178 9878 9150 12513Moyenne 1536 3573 2219 2929 2191 2970 2777 2869 2986 2441 2305 2939

Retards en marche arrière :Heuristiques

Nom du fichier 1 2 3 4 5 6 7 8 9 10 11 12l10o3m4.txt 109 156 121 53 112 64 123 130 176 74 77 159l10o5m4.txt 235 395 197 438 192 283 314 304 403 252 206 399



l50o10m4.txt 6661 16553 7920 11296 8133 10051 8596 7931 9587 8846 10657 9064Moyenne 1400 3416 1976 2724 1914 2429 2111 1911 2490 2344 2388 2320

Tableau 7 : Résultats de l'ordonnancement pour les différents fichiers avec les méthodes heuristiques.

Pour chaque fichier d'exemple, le meilleur retard obtenu est mis en gras. On remarque queglobalement, les placements en marche arrière donnent de meilleurs résultats, surtout quand on a plusde 100 opérations, ce qui est tout a fait normal puisque l'on part de la date au plus tard des lots. Onremarque aussi que pour les exemples de taille importante, c'est la première heuristique qui donnetoujours le meilleur résultat. Ceci s'explique par le fait que cette heuristique se base sur la date au plustard dans l'ordre croissant, ce qui permet de caser les lots dans le bon ordre (la seconde heuristiqueconfirme cela, puisque dans l'ordre inverse, les résultats sont les plus mauvais). On remarque enfinque les heuristiques dans l'ordre croissant donnent de meilleurs résultats que dans l'ordre décroissant.

7. Comparaison des résultats.Au niveau des tests de temps, c’est la méthode du gradient qui est la plus rapide pour un

même nombre de placements. Ensuite, c’est l’aléatoire total puis le recuit simulé. Cela s’explique parle fait que l’aléatoire total demande de mélanger les lots avant chaque placement et que le recuit si-mulé calcule des probabilités à chaque placement et accepte des dégradations du résultat contraire-ment à la méthode du gradient.

Mais, pour notre problème, ce n’est pas la vitesse de calcul qui importe le plus entre ces troisméthodes car les temps sont assez proches , c’est surtout le meilleur retard obtenu qui est important.

L’aléatoire total donne les moins bons résultats parmi les trois méthodes. Cela respecte bienles prévisions que nous pouvions faire. On remarque ensuite que le recuit simulé est bien la meilleureméthode des trois pour les fichiers à 10 lots. En revanche, pour les autres fichiers, c’est la méthode dugradient qui est la meilleure. Cela peut s’expliquer par le fait que la décroissance en température (durecuit simulé) T=0.95*T doit être fonction du nombre de lots.On pourrait aussi essayer une décroissance logarithmique à la place de la décroissance exponentielleutilisée pour s’assurer de la convergence comme cela est expliqué au paragraphe 5.1. Mais avec unetelle décroissance, les temps de calcul deviennent extrêmement longs.

Les résultats obtenus avec les heuristiques sont beaucoup moins bons qu’avec les méthodesprécédentes (sauf pour la première heuristique qui donne de bons résultats avec les fichiers où lenombre de lots est important). Cela s’explique en effet car on ne réalise qu’un seul placement à cha-que fois et les lots sont soit tous placés en marche avant, soit tous placés en marche arrière. Pour ob-tenir de meilleurs résultats avec les heuristiques, il faudrait utiliser une méthode mélangeant marche


& 38

avant et marche arrière, voire utiliser une des trois méthodes précédentes ou les algorithmes généti-ques avec cette méthode. Il serait intéressant d’utiliser de telles méthodes pour une étude plus appro-fondie.

8. Conclusion.D’après les résultats précédents, la méthode du gradient donne les meilleurs résultats globa-

lement. Mais pour les exemples à 10 lots, c’est le recuit simulé qui est la meilleure méthode. Commeexpliqué précédemment, le recuit simulé devrait donner les meilleurs résultats même pour les grandsexemples mais il faut déterminer correctement la décroissance en température ce qui demande ungrand temps de calcul.

Pour ce qui est des optima pour les fichiers l10o3m4.txt et l10o5m4.txt, seul le recuit simulé apermis d’atteindre celui du fichier l10o3m4.txt. La méthode de l’aléatoire total donne les moins bonsrésultats comme le prévoyait la théorie et les méthodes heuristiques demandent à être approfondiespour les utiliser avec d’autres méthodes.

Pour un aperçu global des résultats de ces méthodes et des algorithmes génétiques, voir les fi-gures 22 à 25 en fin du dernier chapitre.


& 39

Présentation des algorithmes génétiques.

1. Les Algorithmes Génétiques : AG.Les algorithmes génétiques font partie des techniques d’optimisation se basant sur

l’exploration aléatoire de l’espace des solutions. Les travaux de fondation dans ce domaine sontl’oeuvre d'Holland [HOLLAND 1975]. Ce sont des méthodes simulant le processus d’évolution bio-logique. Pour faire le parallèle entre la nature et les algorithmes génétiques, voici les termes que nousutiliserons :

Nature Algorithme Génétiquechromosome chaîne ou chromosome

gène trait, caractéristique ou détecteurallèle valeur de caractéristiquelocus position dans la chaîne

génotype structurephénotype ensemble de paramètres

une structure décodéeépistasie non linéarité

Une population est composée d’un ensemble d’individus où chaque individu (membre) est ca-ractérisé par un seul chromosome (tous les AG réalisés jusqu'à maintenant utilisent cette caractéristi-que). Un chromosome correspond à une chaîne de caractères (gènes) qui sont caractérisés par uneposition sur le chromosome (locus) et une valeur du gène (allèle). Chaque gène a la possibilité de semouvoir de façon non linéaire (épistasie) sur un chromosome après une opération de croisements.

L’ensemble des chromosomes constituant une population représente le génotype et il peut agirsur son environnement (phénotype).

Les algorithmes génétiques font appel à l’approche où les paramètres naturels du problèmed’optimisation se codent comme une chaîne ayant une longueur finie. Les algorithmes génétiques ontdéjà un vaste champ d’application dans divers domaines, aussi variés que l’automatique, la chimie, laphysique statistique, l’intelligence artificielle, etc.. A l’heure actuelle, ces techniques sont en périodede maturation et de mutation.

Un des problèmes rencontrés lors de l’utilisation des AG de même que pour les méthodes dugradient ou du recuit simulé est la “convergence prématurée”. Par ces termes, nous entendons la con-vergence vers une solution nettement sous optimale.

2. Introduction aux Algorithmes Génétiques.

2.1. Historique.Les techniques d’optimisation bénéficient d’un intérêt constant de part leur capacité à amélio-

rer de façon sensible les performances et ou la conception des systèmes auxquels on les applique. Lalittérature est riche en méthodes généralistes qui, tout en restant très efficaces dans beaucoup de si-tuations, ne permettent pas d’aboutir à une solution pratique lorsque les problèmes abordés atteignentune taille et ou une complexité importante. Afin de répondre à ces problèmes, des approches heuristi-ques spécifiques à chacun de ces problèmes ont été développées. Une alternative à ces méthodes peut


& 40

être trouvée dans le développement des algorithmes basés sur des méthodes aléatoires de recherche desolutions : gradient, recuit simulé, algorithmes génétiques, ...

Caractérisés par leur propre théorie et structure, les AG se sont différenciés des autres tech-niques d’optimisation traditionnelles. Divers problèmes reconnus difficiles ont été résolus par les AG,tel que le problème du Voyageur de Commerce, celui de la Classification, celui d’Ordonnancement ...

La théorie de base des AG a été développée par Holland et à sa suite par d’autres chercheursde l’Université du Michigan. Leurs recherches ont abouti à la fondation de la théorie des techniquesgénétiques adaptives. Après plusieurs années de recherche dans ce domaine pour créer et compléter lathéorie des AG, Holland a publié en 1975 [HOLLAND 1975]le premier ouvrage qui constitue encoreaujourd’hui la référence dans ce domaine.

Leurs recherches avaient deux objectifs principaux :• mettre en évidence et expliquer les processus d’adaptation des systèmes natu-

rels,• concevoir des systèmes artificiels qui possèdent les propriétés importantes des

systèmes naturels.

Les algorithmes génétiques sont des algorithmes d’exploration basés sur les mécanismes de lasélection naturelle et de la génétique. Ils utilisent d’une part les principes de la survie des structuresles mieux adaptées, et les échanges d’information pseudo-aléatoires, pour former un algorithmed’exploration qui possède certaines des caractéristiques de l’exploration humaine[HOFSTADTER1979]. A chaque génération, un nouvel ensemble de créatures artificielles (des chaînes de caractères)est créé en utilisant des parties des meilleurs éléments de la génération précédente ; ainsi que des par-ties innovatrices, à l’occasion. Bien qu’utilisant le hasard, les algorithmes génétiques ne sont pas pu-rement aléatoires. Ils exploitent de manière efficace l’information obtenue précédemment pour spé-culer sur la position de nouveaux points à explorer, avec l’espoir d’améliorer la performance. Desdécouvertes importantes à la fois dans la science des systèmes naturels et dans celles des systèmesartificiels ont été faites.

Les algorithmes génétiques sont des procédures robustes d’exploration d’espaces complexes.L’ouvrage originel sur ce thème est celui de John Holland Adaptation in Natural and Artificial Sys-tems [HOLLAND 1975]. Un grand nombre d’articles et de thèses de doctorat établissent la validité dela technique pour les applications d’optimisation de fonctions et de contrôle. Ayant été reconnuscomme une approche valide des problèmes nécessitant une exploration performante et économique dupoint de vue du calcul, les algorithmes génétiques sont maintenant appliqués plus largement, aux do-maines des affaires, à la recherche scientifique en général, ainsi que pour l’ingénierie. Les raisons dece nombre grandissant d’applications sont claires. Ces algorithmes sont simples d’un point de vue decalcul, mais sont cependant très performants dans leur recherche d’amélioration. De plus, ils ne sontpas fondamentalement limités par des hypothèses contraignantes sur le domaine d’exploitation (hy-pothèses concernant la continuité, l’existence de dérivées, etc).

Un AG peut être considéré à la base comme un processus aléatoire. Cependant, les informa-tions qui viennent de fonctions objectifs sont toujours utilisées pour paramétrer ce processus. Le tra-vail de recherche commence en plusieurs points dans l’espace des solutions, c’est-à-dire sur une po-pulation de points et non pas en un point singulier comme dans la plupart des techniquesd’optimisation. Par les opérations de sélection, mutation et croisement, ce sont les bons membres decette population qui survivent. Donc, ils peuvent passer à la prochaine génération. A la fin del’algorithme, une meilleure solution est engendrée parmi les membres suivants. Les caractéristiquesdes algorithmes génétiques peuvent se résumer par les aspects fondamentaux suivants :


& 41

♦ Les AG travaillent sur un codage de l’ensemble des paramètres et non pas avec les pa-ramètres eux-mêmes;

♦ Les AG cherchent l’optimum à partir d’une population de points et non à partir d’unseul point;

♦ Les AG utilisent l’information (ou le coût ) de la fonction objectif et non pas les in-formations provenant des fonctions dérivées de quelque ordre que ce soit;

♦ Les AG font appel à des règles de transition probabilistes et non pas à des règles dé-terministes.

2.2. Description des Algorithmes Génétiques.Un algorithme génétique est une procédure itérative basée sur une évolution des populations

de solutions candidates. Un algorithme génétique simple, dénoté SAG, qui engendre de bons résultatssur des problèmes pratiques, comporte quatre opérations fondamentales :

Ä Codage (générer une population);Ä Reproduction de populations selon leurs héritages de valeurs;Ä Croisement entre deux ou plusieurs membres de la population;Ä Mutation de la population.

Chaque itération complète est appelée une Génération. Une population est un groupe de can-didats de solutions sur lequel on applique les opérations de reproduction, mutation, croissement. Achaque génération correspond une nouvelle population.

Le codage génère aléatoirement une population de solutions candidates en code binaire oudécimal.

La reproduction (ou sélection) est un processus où les membres sont copiés selon les valeursde la fonction objectif. Un membre ayant une grande valeur de la fonction objectif aura plus dechance de passer à la prochaine génération et ainsi de se reproduire.

Le croisement s’effectue en deux temps : premièrement, choisir aléatoirement les membres etla position d’un croisement ; deuxièmement, échanger les parties entre les membres. La position decroisement (matérialisée dans l’exemple suivant par le signe ‘_’) est la position à partir de laquelle onéchange les éléments de chacun des membres.

Par exemple, en codage binaire, S1 et S2, deux membres choisis aléatoirement pour un croi-sement sur le bit ou la position 3 des membres (de gauche à droite), qui est également choisie aléatoi-rement.

S1=(011_1010);S2=(110_0100);

Le croisement génère deux nouveaux membres S1’ et S2’.S1

’=(011_0100);S2’=(110_1010);

La mutation faisant changer la valeur d’un gène permet d’éviter une solution de blocage enrestant dans un optimum local. Elle joue un rôle secondaire mais non négligeable dans les AG. C’estune politique contre la prématurité des AG. Soit un exemple en binaire avec mutation du gène dont lavaleur est 1 à la position 2 :

SS

1

1

==

1 1 0 1 0 0 11 0 0 1 0 0 1'


& 42

La mutation, en binaire, permet de changer le 1 en 0 et vice-versa.

3. Algorithme.Le principe général [GOLDBERG 1994] peut se ramener à :

Engendrer la population initialeCalculer l’aptitude de chaque individurépéter

répéterChoisir deux individus de la génération courante (sélection)Engendrer deux descendants correspondant à ces deux parents (crossover)Calculer l’aptitude de chacun des descendantsMettre ces deux nouveaux individus dans la nouvelle génération

jusqu'à ce que la nouvelle génération soit complètetant que la population n’a pas convergé.

Gen :=0

Création aléatoire d’unepopulation initiale

Fin du programmeOui

Non

Affichage résultat

FinEvaluation du Fitness de chaque individude la population

i:=0

Non

Oui

Gen:=Gen+1

Sélection de l’opérateurgénétique

Sélection de 2 individusen fonction du Fitness

i:=i+1

Réalisation du crossover

Pm

Pc

Pr

i:=M?

Sélection d’un individuen fonction du Fitness

Sélection d’un individuen fonction du Fitness

Réalisation de la reproduction Réalisation de la mutation

Copie dans la nouvellepopulation

Insertion des deuxenfants dans la

nouvelle population

Insertion du mutant dansla nouvelle population

i:=i+1

Figure 8 : Schéma de principe d’un algorithme génétique [KOZA 1992].

Le Fitness correspond à la valeur moyenne du retard pour un chromosome donné.


& 43

4. Les sujets ouverts sur les AG.Un problème que l’on rencontre souvent dans les AG est la convergence prématurée. Pour

surmonter ce handicap, nous nous devons d’étudier de nouvelles techniques de mutation, de croise-ment et de reproduction dans les AG. Il existe plusieurs facteurs qui influencent la convergence d’unalgorithme génétique. Les solutions proposées sont les suivantes:

°Amélioration des méthodes de sélection pour reproduction.A cause de l’influence essentielle de la méthode de sélection sur la convergence des AG, des

études sur des techniques de sélection sont naturellement importantes. Ici, on énumère quelques mé-thodes qui ont été proposées :

Sélection proportionnelle ;Probabilités des opérateurs adaptatifs ;Reproduction avec l’état stable;Sélection avec taux linéaire.

°Amélioration de la technique de croisement.Les nouveaux membres se génèrent par un croisement durant les algorithmes génétiques. Mais

le croisement entraîne un risque de perte des schémas critiques contenant une tendance vers une solu-tion optimale. Plusieurs méthodes de croisement ont été proposées et pratiquées pour diminuer lapossibilité de perte des schémas critiques. Parmi ces méthodes, on peut citer :

Un point de croisement et deux points de croisement;Croisement uniforme;Croisement multipoints.

Chaque technique a ses propriétés et ses avantages pour résoudre une certaine classe de pro-blèmes.

°Techniques de codage.Les techniques de codage ont aussi une influence significative sur la convergence des AG.

Dans la littérature, une condition suffisante est proposée et le code uniforme est défini. En règle géné-rale, le code binaire est utilisé dans les AG. Cependant pour des raisons de convergence de calcul etde temps de calcul, le code décimal peut être utilisé.

Face aux problèmes les plus délicats et complexes, il est indispensable d’essayer de trouverdes stratégies génétiques qui peuvent régler les problèmes d’une manière efficace.

5. Rappel mathématique.Certains problèmes sont de complexité supérieure à l’exponentielle : les problèmes NP, il

s’agit d’une classe de problèmes dont la nature polynomiale ou exponentielle n’a pas été montréemais pour lesquels on ne connaît pas d’algorithmes polynomiaux. De plus, ils sont polynomiaux équi-valents, c’est-à-dire que si un seul est résolu par un algorithme polynomial, alors tous peuvent êtrerésolus par des algorithmes polynomiaux. L’abréviation NP signifie non-déterministe polynomial.

Un problème Q est réductible à un problème R, si pour toute solution s de R, il existe unefonction polynomiale g(s), telle que g(s) est une solution de Q. On écrit alors :

Q ∝ RLa relation ∝ est transitive mais pas forcément symétrique. Si la relation

R ∝ Qest vérifiée, alors Q et R sont dites polynomialement équivalentes.

Un problème R est dit NP-dur si tout problème NP est réductible au problème R.Un problème est dit NP-Complet si tout problème NP est réductible à R et si R est NP (R est

donc NP et NP-dur).


& 44

6. Fondement mathématique et théorie [GOLDBERG 1991].La mise en œ uvre des algorithmes génétiques est aisée. On commence avec une population

aléatoire de n chromosomes, on copie les chromosomes avec l’intention de choisir les meilleurs, onles apparie et on échange partiellement des sous chromosomes, puis on fait muter certaines valeurs debits pour terminer le travail.

Bien que les algorithmes génétiques manipulent directement une population de chromosomesde cette manière simple, nous avons aperçu que le traitement explicite des chromosomes produit réel-lement le traitement implicite d’un grand nombre de schèmes ( ensemble correspondant aux motifs desimilarité pouvant conduire à la représentation d’un chromosome) à chaque génération. Pour analyserle développement et le dépérissement du grand nombre de schèmes contenus dans la population, ilnous faut des notations simples pour donner de la rigueur au problème. Nous allons considérer l’effetdes opérations de reproduction, de crossover et de mutation sur les schèmes contenus dans une popu-lation.

Nous supposerons, que les chromosomes sont construits sur l’alphabet binaire }{0 1 . Pourdes raisons pratiques, nous désignerons les chromosomes par des lettres majuscules et les caractèrespar des lettres minuscules indicées par leur position. Par exemple, le chromosome de sept bits A =01110000 peut être représentée symboliquement ainsi :

A = a1a2a3a4a5a6a7

Ici, chacun des ai représente une variable ou un détecteur binaire simple (en accord avecl’analogie naturelle, on nomme parfois les ai des gènes). Pour le chromosome 0111000, a1 vaut 0,a2

vaut 1, a3 vaut 1,etc. Il est possible d’avoir des chromosomes pour lesquels les détecteurs ne sont pasordonnés séquentiellement comme pour le chromosome A. Par exemple, un chromosome A’ pourraitêtre ordonné de façon suivante :

A’= a2a6a4a3a7a1a5.Supposons que la fonction d’une variable puisse être déterminée par sa position.Une exploration génétique conséquente nécessite une population de chromosomes. Nous con-

sidérons un ensemble de chromosomes }{A Nj avec j ∈ 1 K , qui forme la population A(t) à ladate (ou à la génération) t. L’utilisation de caractères gras différencie les populations des chromoso-mes individuels. En plus de notations pour décrire des populations, des chromosomes, des positionsde bits et des allèles, il nous faut une notation pratique pour décrire les schèmes contenus dans unchromosome ou une population particulière. Considérons un schème H défini sur l’alphabet

}{V + = 0 1 * .

Le symbole supplémentaire, l’astérisque ou l’étoile * est le joker ou le symbole indifférent quicorrespond à un 0 ou à un 1 à une position particulière. Par exemple, si l’on considère le schèmeH=*11*0** de longueur 7, on peut remarquer que le chromosome A=0111000 présenté au-dessus estun exemple du schème H, car les allèles ai du chromosome correspondent aux bits hi du schème auxpositions 2, 3 et 5. Il y a 3l schèmes ou similarités définies à partir d’un chromosome de longueur l. Engénéral, pour un alphabet de cardinal k, il y a (k+1)l schèmes. Dans une population de N chromoso-mes, il y a au plus N2l schèmes, car chaque chromosome est elle-même représentante de 2l schèmes.Ces quantités donnent une idée de l’importance de l’information traitée par les algorithmes généti-ques ; cependant, pour bien isoler les briques élémentaires des solutions futures, nous devons faire ladistinction entre les différents types de schèmes.

Tous les schèmes ne sont pas créés égaux. Certains sont plus spécifiques que d’autres. Parexemple, le schème 011*1** dit plus sur une importante similarité que le schème 0******. De plus,certains schèmes couvrent une plus grande partie de la longueur totale du chromosome que d’autres.


& 45

Par exemple, le schème 1****1* couvre une plus grande portion du chromosome que 1*1****. Pourquantifier ces notions, il est nécessaire de définir deux caractéristiques propres au schème :

son ordre,sa longueur utile.

L’ordre d’un schème H, noté o(H), est tout simplement le nombre de positions instanciées(pour un alphabet binaire, le nombre de 1 et de 0) dans le modèle. Pour les exemples précédents,l’ordre du schème 011*1** est 4.

oo

( * **)( ******)011 1 40 1

==

La longueur utile d’un schème H, noté δ( )H , est la distance entre la première et la dernièreposition instanciée dans un chromosome. Par exemple, le schème 011*1** a une longueur utile d=4car la dernière position instanciée est 5 et la première est 1, et la distance qui les sépare estδ( )H = − =5 1 4

Les schèmes et les propriétés que nous venons de définir sont des outils intéressants qui per-mettent d’étudier rigoureusement et de classer les similarités entre chromosomes. De plus, ils per-mettent d’analyser l’effet de la reproduction et des autres opérateurs génétiques sur les briques élé-mentaires contenues dans la population. L’effet de la reproduction sur le nombre attendu de schèmesdans la population est particulièrement facile à déterminer. Supposons qu’à une date t donnée, il y aitm exemplaires d’un schème H contenus dans la population A(t), ce que nous notons m=m(H,t).Lors de la reproduction, un chromosome est copié en fonction de son adaptation, ou plus précisément,un chromosome Ai est sélectionné avec une probabilité pi.

pf

fi

i

i= ∑

Après avoir choisi une population de taille N, nous nous attendons à avoir

m H t m H t Nf H

fi( , ) ( , ). .

( )+ = ∑1

représentants du schème H dans la population t+1, où f(H) est l’adaptation moyenne des chromoso-mes représentants le schème H à la date t. En s’apercevant que l’adaptation moyenne de la populationpeut être écrite :

ff

Ni

= ∑ ,

on peut reformer l’équation de développement par reproduction des schèmes par :

m H t m H tf H

f( , ) ( , ).

( )+ =1

Explicitement, un schème quelconque se développe à une vitesse égale au rapport del’adaptation moyenne du schème sur l’adaptation moyenne de la population. Les schèmes ayant unevaleur d’adaptation supérieure à la moyenne de la population recevront davantage de copies à la géné-ration suivante, tandis que les schèmes dont les valeurs d’adaptation sont au-dessous de la moyenneseront moins copiées. Il est important de noter que ce phénomène attendu à lieu en parallèle pour cha-que schème H contenu dans une population A. Tous les schèmes d’une population se développent oudépérissent en fonction de leur moyenne de schème du fait de l’opérateur de reproduction unique-ment.

Les schèmes qui sont au-dessus de la moyenne se développent et ceux qui sont en dessouss’éteignent. Peut-on apprendre davantage à propos de la forme mathématique de ce développement àpartir de l’équation d’évolution des schèmes ? Supposons qu’un schème quelconque H reste au-dessus


& 46

de la moyenne d’une quantité cf, où c est une constante. Il est possible de réécrire l’équationd’évolution des schèmes pour obtenir :

m H t m H tf cf

fm H t c( , ) ( , ).

( )( , ).( )+ =

+= +1 1

En commençant à t=0 et en supposant une valeur de c stationnaire, on obtient :m H t m H c t( , ) ( , ).( )= +0 1

C=0.8

C=0.6

C=0.4

C=0.2

Figure 9:Variation de ( )1 + c t pour c=0.2, c=0.4, c=0.6 et c=0.8.

L’effet de la reproduction alloue une place exponentiellement croissante aux schèmes qui sontau-dessus de la moyenne. Un très grand nombre de schèmes sont échantillonnées en parallèle à traversl’utilisation de N opérations de reproductions simples. Toutefois la reproduction en elle-même ne faitrien afin de promouvoir l’exploration de nouvelles régions de l’espace de recherche, puisque aucunnouveau point n’est exploré. Si nous ne faisons que copier les anciennes structures sans changement,comment obtiendrons-nous quelque chose de nouveau ?

Le crossover est un échange d’informations entre les chromosomes qui est à la fois structuréet aussi en partie aléatoire. Le crossover crée de nouvelles structures en évitant autant que possible detroubler la stratégie d’allocation dictée par la reproduction seule. Il en résulte des proportions deschèmes exponentiellement croissantes dans la population. Pour voir quels schèmes sont affectés parle crossover et lesquels ne le sont pas, considérons un chromosome particulier de longueur l=7 et dedeux schèmes représentatifs de ce chromosome.

A = 0 1 1 1 0 0 0H1= * 1 * * * * 0H2= * * * 1 0 * *

Il apparaît que les schèmes H1 et H2 sont représentés dans le chromosome A. Pour voir l’effetdu crossover sur ces schèmes, il faut d’abord se souvenir que le crossover simple se réalise par sélec-tion aléatoire d’un autre chromosome, et sélection aléatoire d’un point de crossover, puis parl’échange des sous chromosomes depuis le début du chromosome jusqu’au point de crossover inclusavec le partenaire choisi. Supposons que le chromosome A ait été choisi pour appariement et crosso-ver. Sur ce chromosome de longueur 7, supposons que nous lancions un dé pour choisir le point decrossover. Imaginons que le dé propose un 3, c’est-à-dire que le point de coupure prend place entre les


& 47

positions 3 et 4 dans le chromosome. L’effet de ce croisement sur les deux schèmes H1 et H2 peut êtrevu dans l’exemple qui suit avec le symbole | comme séparateur.

A = 0 1 1 | 1 0 0 0H1= * 1 * | * * * 0H2= * * * | 1 0 * *

A moins que le chromosome apparié avec A ne lui soit identique aux positions instanciés duschème, le schème H1 sera détruit, car le 1 en position 2 et le 0 en position 7 seront placés dans deuxdescendants distincts. De même, le schème H2 survivra, car le 1 en position 4 et le 0 en position 5seront tous deux préservés dans le même descendant. Bien que n’ayant utilisé qu’un point de coupure,il est facile de remarquer que le schème H1 a moins de chance de survivre au crossover que le schèmeH2 parce que le point de coupure a plus de chance de tomber entre les positions instanciées extrêmes.Pour quantifier ces observations, le schème H1 a une longueur utile de 5. Si le point de crossover estchoisi uniformément au hasard parmi les l-1=7-1=6 points possibles, alors il est évident que le schèmeH1 a une probabilité de destruction

pH

ld = − =δ( )1

156

La probabilité de survie

p ps d= − =116

De la même façon le schème H2 a une longueur utile δ( )H 2 1= , et il est détruit lors del’unique événement parmi les 6 possibles pour lequel le point de coupure est choisi entre les positions4 et 5, d’où

p16

et p 1 p56d s d= = − =

Une borne inférieure de la probabilité ps de survie au crossover peut être calculée pour unschème quelconque. Un schème survit quand le point de crossover se trouve à l’extérieur de sa lon-gueur utile, la probabilité de survie lors d’un crossover simple est :

pH

ls = − −11

δ( ),

puisque le schème a de grandes chances d’être perdu quand un point compris dans sa longueur utileest choisi parmi les l - 1 points possibles.

Si le crossover a lieu avec une probabilité pc lors d’un appariement quelconque, la probabilitéde survie devient :

p pH

ls c= − −11

δ( )

ce qui revient à l’expression précédente lorsque pc=1.

L’effet de la reproduction et du crossover peut ainsi être considéré. Nous nous intéressons aucalcul du nombre de schèmes H attendu pour la génération suivante. En supposant l’indépendance desopérations de reproduction et de crossover, on obtient :

m H t m H tf H

fp

Hlc( , ) ( , )

( ) ( )+ ≥ ⋅ − −

1 11

δ

En comparant ceci à l’expression obtenue précédemment, l’effet combiné de la reproductionet du crossover s’obtient en multipliant le nombre attendu de schèmes lors de la reproduction seulepar la probabilité ps de survie lors d’un crossover. Le schème H se développe ou dépérit en fonctiond’un facteur multiplicatif.

Avec le crossover et la reproduction mis ensemble, ce facteur dépend de deux choses :le fait que le schème soit au-dessus ou au-dessous de la moyenne de la population,le fait que le schème ait une longueur utile relativement courte ou longue.


& 48

Les schèmes ayant à la fois une performance observée au-dessus de la moyenne et une courtelongueur utile vont être échantillonnés à une fréquence croissante exponentiellement.

Le dernier opérateur à prendre en compte est la mutation. La mutation est la modificationaléatoire de probabilité pm d’une position quelconque du chromosome. Pour qu’un schème H survive,toutes ses positions instanciées doivent survivre. Puisqu’un allèle quelconque a une chance de surviede ( )1 − pm , et puisque chaque mutation est statistiquement indépendante des autres, un schème quel-conque survit quand chacune des o(H) positions instanciées dans le schème survit. En multipliant laprobabilité de survie ( )1 − pm par elle-même o(H), on obtient la probabilité de survie à la mutation :

probabilité de survie à la mutation = −( ) ( )1 pmo H

Quand pm est petit (pm<<1), la probabilité de survie du schème peut être approximée parl’expression :

p p o H pm mo H

m<< ⇒ − ≅ − ⋅1 1 1( ) ( )( )

Nous pouvons donc conclure qu’on peut s’attendre à ce que le schème H quelconque reçoive,du fait de la mutation, du crossover et de la reproduction, un nombre de copies donné par l’équationsuivante :

m H t m H tf H

fp

Hl

H pc m( , ) ( , )( ) ( )

( )+ = ⋅ ⋅ − − − ⋅

⋅1 11

δ ο

L’ajout de la mutation affecte peu nos conclusions précédentes. Les schèmes courts, d’ordrefaible et de performance au-dessus de la moyenne de la population font l’objet d’un nombre de testsexponentiellement croissants dans les générations suivantes. Cette conclusion correspond à ce qu’onappelle :Le Théorème des schèmes ou Théorème Fondamental des Algorithmes Génétiques.

Vu la théorie des schèmes, quel est le nombre de schèmes traités utilement ?Dans une population de taille N dont les chromosomes ont une longueur l, il y a entre 2l et n.2l

schèmes manipulés. Certains schèmes n’ont pas une probabilité élevée d’être traités car le crossoverdétruit ceux ayant des longueurs utiles importantes. La méthode de comptage du nombre de schèmesefficacement traités qui est utilisée est l’estimateur O(n3) de Holland [GOLDBERG1985][GOLDBERG 1991][HOLLAND 1973]. Cet estimateur traduit le fait que au delà du traitementde N structures à chaque génération, un algorithme génétique traite en fait un nombre de N3 schèmes.Ce résultat a le nom de parallélisme implicite. A chaque génération, le calcul effectué est d’une com-plexité proportionnelle à la taille de la population, on réalise un traitement utile d’environ N3 schèmesen parallèle sans utiliser de mémoire autre que celle constituée par la population.

Démonstration.Considérons une population de N chromosomes binaires de longueur l. Nous ne prenons en

compte que les schèmes qui ont une probabilité de survie supérieure à une constante ps. Si l’on sup-pose la mise en œ uvre d’un crossover simple et d’une petite fréquence de mutation, nous ne prenonsque les schèmes dont le taux d’erreur est :

taux d' erreur e = −1 ps

Cela nous conduit à ne considérer que les schèmes de longueurl e ls < − +( )1 1

Pour une longueur de schème particulière, on peut estimer une borne inférieure du nombre deschèmes traités par une population de chromosomes définie initialement au hasard. Pour cela, oncompte le nombre de schèmes de longueur ls ou moins. Puis, on multiplie ce nombre par la taille de lapopulation, choisie de façon à n’avoir, en moyenne, pas plus d’un représentant de chacun des schèmesde longueur ls/2. Supposons par exemple que nous compter les schèmes de longueur ls dans le chro-mosome de longueur l=10.

1 0 1 1 1 0 0 0 1 0


& 49

On calcule le nombre de schèmes dans la première partie de 5 caractères de façon à avoir ledernier bit du groupe fixé. On veut donc avoir l’ensemble des schèmes de la forme :

% % % % 1 * * * * *où les étoiles * sont les signes jokers les signes de pourcentages % peuvent prendre soit la valeur ins-tanciée, soit *. Il y a 2 1( )ls − schèmes de cette forme, car ls - 1 = 4 positions pouvant être instanciéescomme dans le chromosome ou être indifférentes. Pour compter le nombre total de ces schèmes, ilsuffit de faire glisser la fenètre le longueur 5 caractère par caractère.

1 0 1 1 1 0 0 0 1 0Cette opération est réalisée au total l ls− + 1 fois. On peut donc estimer le nombre total de

schèmes de longueur ls ou moins à( ). ( )l ls

ls− + −1 2 1

Afin d’estimer un majorant du nombre de tels schèmes dans la population totale, il est possi-ble de multiplier l’expression précédente par la taille de la population, d’où :

N l lsls.( ). ( )− + −1 2 1

Il y a plusieurs exemplaires de certains schèmes d’ordres faibles dans une population impor-tante d’ou une surestimation du nombre total de schèmes. Pour affiner cette valeur, on se limite à une

taille de population Nls

= 2 2 . En choisissant cette valeur, on suppose avoir au plus un exemplaire de

tous les schèmes d’ordres ls2

ou plus. La moitié des schèmes sont d’ordre supérieur à ls2

et la moitié

d’ordre inférieur. Si l’on ne compte que les schèmes d’ordre supérieur à ls2

, on peut donner une esti-

mation de la borne inférieure du nombre de schèmes :N N l ls s

ls≥ − + −.( ). ( )1 2 2

Cela diffère du minorant précédent par un facteur 12

. Le choix de la taille de la population

permet de reformuler l’expression précédente :

Nl l N

ss=

− +( ).14

3

Puisque N C ns = . 3 , on conclut que le nombre de schèmes est proportionnel au cube de lataille de la population et est donc de l’ordre de n3, O(n3). Bien que le crossover et la mutation détrui-sent les schèmes longs et d’ordre élevé, les algorithmes génétiques traitent un grand nombre de schè-mes tout en ne manipulant qu’une quantité relativement faibles de chromosomes.

7. Les représentations possibles du problème.

7.1. La représentation ADJACENTE .La représentation adjacente [MICHALEWICZ 1994] représente un ordonnancement comme

une liste de N lots. Le lot j est listé à la position i si et seulement si l’ordonnancement se dirige du loti au lot j. Soit par exemple le vecteur

(2 4 8 3 9 7 1 5 6)Représentant l’ordonnancement : 1-2-4-3-8-5-9-6-7.Chaque ordonnancement a seulement une représentation adjacente ; toutefois, quelques listes

adjacentes représentent des ordonnancements illégaux.(2 4 8 1 9 3 5 7 6)


& 50

Ce qui conduit à l’ordonnancement 1-2-4-1, celui-ci n’étant qu’un ordonnancement partielavec le cycle. Mais le principal problème est que la représentation adjacente ne supporte pasl’opérateur de crossover classique. Pour cela un algorithme de réparation est nécessaire. Ainsi troisopérateurs de crossover furent définis et implémentés pour la représentation adjacente :

Le crossover heuristique,Le lancement de tour partiel,et l’excitation alternative.

• Le crossover par excitation alternative conduit à produire un parent par choix aléatoired’une coupure dans le premier parent, puis une coupure appropriée dans le second parent, etc.L’opérateur prolonge l’ordonnancement par choix des coupures parmi les parents successifs. Si lanouvelle coupure, provenant d’un des parents, engendre un cycle dans l’ordonnancement courant,l’opérateur sélectionne cette partie au lieu d’une coupure parmi les coupures restantes quin’engendreront pas de cycles. Par exemple, le premier enfant issu de deux parents

p1=(238791456)p2=(751692843)

peut êtree1=(258791643)

Pour obtenir ce résultat, le processus commence par une coupure (1,2) dans le parent p1 et uneseule coupure aléatoire fut introduite dans le processus (7,6) au lieu de (7,8), laquelle donne un nou-veau cycle.

• Le crossover par lancement d’ordonnancement partiel engendre des enfants par choix d’unelongueur aléatoire d’un ordonnancement partiel parmi un de ses parents, puis le choix d’une longueuraléatoire d’un ordonnancement partiel d’un autre parent et ainsi de suite. L’opérateur engendre unordonnancement par le choix des coupures issues de ses parents successifs. De plus, si une coupureissue d’un des parents introduits un cycle dans l’ordonnancement courant, l’opérateur sélectionnecette partie au lieu d’une coupure parmi les coupures restantes qui n’engendreront pas de cycles.

• Le crossover heuristique donne un enfant par le choix d’un lot, aléatoirement, comme pointde départ pour l’ordonnancement enfanté. Puis, on compare les deux coupures issues de deux parentsdonnant ce lot. La partie sélectionnée est la plus petite coupure. Le lot, sélectionné par la coupure, sertde point de départ dans la sélection de la plus petite de deux coupures donnant ce lot, etc. Si, à unmoment, une nouvelle coupure engendre un cycle dans l’ordonnancement courant, l’opérateur sélec-tionne cette partie au lieu d’une coupure parmi les coupures restantes qui n’engendreront pas de cy-cles. Le but de cet opérateur est de coller ensemble de petits morceaux d’ordonnancements partielsissus des ordonnancements parents. Toutefois, un ensemble d’enfants indésirables peut apparaître. Lecrossover heuristique n’est donc pas forcément adapté. Suh et Gucht [SUH et GUCHT 1987] ont in-troduit un opérateur d’addition heuristique pour les ordonnancements partiels.

L’opérateur sélectionne arbitrairement deux coupures, (i j) et (k m) puis compare tel que :dist(i,j) + dist(k,m) > dist(i,m) + dist(k,j).

dist(a,b) représentant la « distance » entre les lots a et b. Si cette inégalité est vérifiée, lescoupures (i j) et (k m) dans l’ordonnancement sont remplacées par les coupures (i m) et (k j). Unavantage de la représentation adjacente est que le schéma d’analyse est similaire à la manipulation dechaîne binaire. Le schéma correspond donc à une construction, à un agencement naturel de blocs ( decoupures). Par exemple, le schéma

(* * * 3 * 7 * * *)correspond à l’ensemble de tous les tours avec les coupures (4 3) et (6 7). Toutefois, le principalavantage de la représentation adjacente est qu’elle fournit des résultats très épurés pour l’ensembledes opérateurs. Le crossover heuristique est le meilleur opérateur, car le premier des deux crossoversest aveugle, c’est-à-dire qu’il ne prend pas en compte les longueurs actuelles des coupures. De plus, le


& 51

crossover heuristique sélectionne la meilleure coupure issue de deux coupures possibles : pour cetteraison, les performances sont meilleures que les deux autres opérateurs.

Malgré tout, cette représentation reste complexe et ne donne pas toujours des solutions via-bles. C’est pourquoi nous ne l’avons pas choisie.

7.2. La représentation ORDINALE.La représentation ordinale [MICHALEWICZ 1994] représente un ordonnancement comme

une liste de N lots; le ième élément de la liste est un nombre compris entre 1 et N-i+1. L’idée consisteen ce que la représentation ordinale est une suite. Il existe une liste ordonnée de lots C, laquelle sertde référence pour les autres listes dans la représentation ordinale. Par exemple, considérons la listeordonnée suivante comme point de départ.

C=( 1 2 3 4 5 6 7 8 9).Un ordonnancement

1-2-4-3-8-5-9-6-7qui est représenté comme une liste l de références,

l=(1 1 2 1 4 1 3 1 1),et peut-être interprétée comme suit :

• Le premier nombre de la liste l est 1, prendre le premier lot de la liste C comme premier lotde l’ordonnancement (lot numéro 1) puis l’enlever de C. L’ordonnancement partiel est

1.• Le nombre suivant de la liste l est aussi 1, prendre le premier lot de la liste courante C

comme prochain lot de l’ordonnancement (lot numéro 2) et l’enlever de la liste C.L’ordonnancement partiel est

1-2.• Le nombre suivant de la liste l est 2, prendre le second lot de la liste courante C comme pro-

chain lot de l’ordonnancement (lot numéro 4) et l’enlever de la liste C. L’ordonnancement partiel est 1-2-4.

• Le nombre suivant de la liste l est 1, prendre le premier lot de la liste courante C commeprochain lot de l’ordonnancement (lot numéro 3) et l’enlever de la liste C. L’ordonnancement partielest

1-2-4-3.• Le nombre suivant de la liste l est 4, prendre le quatrième lot de la liste courante C comme

prochain lot de l’ordonnancement (lot numéro 8) et l’enlever de la liste C. L’ordonnancement partielest

1-2-4-3-8.• Le nombre suivant de la liste l est 1, prendre le premier lot de la liste courante C comme


1-2-4-3-8-5.• Le nombre suivant de la liste l est 3, prendre le troisième lot de la liste courante C comme


1-2-4-3-8-5-9.• Le nombre suivant de la liste l est 1, prendre le premier lot de la liste courante C comme


1-2-4-3-8-5-9-6.• Le nombre suivant de la liste l est 1, prendre le premier lot de la liste courante C comme

prochain lot de l’ordonnancement (lot numéro 7) et l’enlever de la liste C. L’ordonnancement final est 1-2-4-3-8-5-9-6-7.


& 52

Le principal avantage de la représentation ordinale est que le crossover classique fonctionne.A deux ordonnancements dans la représentation ordinale, le fait de couper après chaque position et decroiser ensemble, cela produit deux enfants dont l’un correspond à un ordonnancement valide. Parexemple, soit deux parents

p1=(1 1 2 1 4 1 3 1 1)p2=(5 1 5 5 5 3 3 2 1)

qui correspondent aux ordonnancements1-2-4-3-8-5-9-6-75-1-7-8-9-4-6-3-2.

représentent le crossover.Ceci produit les enfants suivants

e1=(1 1 2 1 5 3 3 2 1)e2=(5 1 5 5 4 1 3 1 1)

qui correspondent aux ordonnancements1-2-4-3-9-7-8-6-55-1-7-8-6-2-9-3-4

Il est évident de voir que la partie gauche du crossover ne change pas. La partie droite parrapport au point de crossover qui correspond à des ordonnancements partiels est transformée en unautre chemin. Cette représentation demande aussi un algorithme de conversion entre les listes et lesordonnancements réels, ce qui augmente les temps de calculs. Nous ne l’avons donc pas gardée.

7.3. La représentation CHEMIN.La représentation par chemin [MICHALEWICZ 1994] est, pour ainsi dire, la représentation la

plus naturelle pour un ordonnancement. Par exemple, un ordonnancement5-1-7-8-9-4-6-2-3

est représenté simplement par le vecteur(5 1 7 8 9 4 6 2 3)

Trois crossovers utilisant cette représentation ont été définis pour conserver la viabilité desenfants après croisement :

Le crossover partiellement tracé PMX partially mapped,Le crossover ordonné OXLe crossover circulaire CX

• PMX fut proposé par Goldberg et Lingle [David E. GOLDBERG & R. LINGLE 1985]. Lebut était de construire un enfant par choix de sous séquences d’un ordonnancement d’un des parentset de préserver l’ordre et la position d’autant de lots que possible des autres parents. La sous séquencede l’ordonnancement est sélectionnée par choix de deux points de coupure aléatoire, lesquels serventde frontière pour l’opération de remplacement. Considérons par exemple les deux parents :

p1=(1 2 3 4 5 6 7 8 9)p2=(4 5 2 1 8 7 6 9 3)

Ces deux parents vont produire deux enfants. Premièrement, les segments compris entre lespoints de coupures sont échangés:

e1=(x x x 1 8 7 6x x)e2=(x x x 4 5 6 7x x)

L’échange définit ainsi une série de permutations pour les autres lots :1↔ 4, 8↔ 5, 7↔ 6, 6↔ 7.

Certains lots sont donc inchangés.e1=(x 2 3 1 8 7 6x 9)e2=(x x 2 4 5 6 7 9 3)

Les deux enfants obtenus sont donc toujours viables (pas deux fois le même lot dans le vec-teur) et on évite ainsi l’utilisation d’un opérateur de réparation.


& 53

Finalement, le premier x du vecteur enfant e1 est remplacé par 4 en raison de la permutation1↔ 4. De la même manière, on réalise les permutations pour les autres x. Les vecteurs enfants finauxsont donc :

e1=(4 2 3 1 8 7 65 9)e2=(1 8 2 4 5 6 7 9 3).

algorithme du crossover PMX.

{ }{ }

[]

[] [] [] [][]

[] [] [] [][]

[]

k k l

kk kk l

k kkend kk start kstart kk end k

C A

T i

A i B jC i A j

T j

A i B jC i A j

T j

T i

i start

i end

j start

j end

i

i start

j start

j end

i end

i l

∈ ∈

∈ ∈

<⇒ ← ←/⇒ ← ←

=

=

= ⇒=

=

= ⇒=

=

=

=

=

<=

=

<

=

=

= +

=

∑

∑∑

∑∑

Ν

Ν

/ ;

/ ;

,,

;

;

;

;

;

1

1

1

0

0

0

1

K

K

[] []( )= ⇒ ==

<=

∑ 0 C i B ii start

i end

;

• Le crossover OX, proposé par Davis [DAVIS 1985], construit un enfant par choix de sous-séquences d’un ordonnancement d’un des parents et préserve l’ordre relatif des lots des autres pa-rents. Par exemple, soit deux parents

p1=(1 2 3 4 5 6 7 8 9)p2=(4 5 2 1 8 7 6 9 3)

Ces deux parents vont produire deux enfants. Premièrement, les segments entre points decoupures sont copiés.

e1=(x x x 4 5 6 7x x)e2=(x x x 1 8 7 6x x)

Ensuite, il suffit de partir du point de coupure d’un des parents, les lots de l’autre parent sontcopiés dans le même ordre, omettant les symboles déjà présents. Lorsque l’on atteint la fin du vecteur,on continue depuis le premier emplacement de la chaîne. La séquence de lots issue du second parentest donc :

9 3 4 5 2 1 8 7 6Ensuite, on enlève les lots 4, 5, 6 et 7 qui sont déjà dans le premier enfant. La chaîne obtenue

est9-3-2-1-8.

Cette séquence est placée dans le premier enfant. Le point de départ est la seconde coupure.e1=(2 1 8 4 5 6 7 9 3)

De la même manière, on obtient le deuxième enfant :e2=(3 4 5 1 8 7 6 9 2)

Là aussi, les enfants sont toujours viables.

Algorithme du crossover OXChoisir deux chromosomes sélectionnables


& 54

Définir deux points de coupuresConstruire un nouveau chromosomePrendre la troisième sous séquencePrendre la première sous séquencePrendre la partie centralePermuter les parties centralesRetirer de ce chromosome les lots compris dans la partie centraleCompléter le chromosome à partir des lots restants

• Le crossover CX, proposé par Oliver [OLIVER, SMITH, HOLLAND 1987], engendre unenfant dans tous les cas tel que chaque lot provient d’un des parents.

p1=(1 2 3 4 5 6 7 8 9)p2=(4 1 2 8 7 6 9 3 5)

L'enfant engendré est obtenu en prenant le premier lot du premier parente1=(1 x x x x x x x x )e2=(4 x x x x x x x x )

Ensuite, chaque lot doit être pris dans un des parents, à la même position. Il n’y a pas de choixpossible. Le prochain lot à considérer est le lot 4.

e1=(1 x x 4 x x x x x)e2=(4 x x 8 x x x x x )

Le lot 4, dans le parent p1, implique le lot 8 dans le parent p2.e1=(1 x x 4 x x x 8 x)e2=(4 x x 8 x x x 3 x )

On continue ainsi jusqu'à la fin du cycle et on obtient :e1=(1 2 3 4 x x x 8 x)e2=(4 1 2 8 x x x 3 x )

On complète alors en échangeant les lots restants des deux parents, on obtient :e1=(1 2 3 4 7 6 9 8 5)e2=(4 1 2 8 5 6 7 3 9)


& 55

Algorithme du crossover CX.

[][]

[][]

[][]

[]

[] [] []( )

C A

T i

T

first A

k BTantque vr

A jk B jT j

breakfirst k break

T i C i B i

i

l

i

i l

=

=

←←

←

= ⇒←

←

= ⇒

= ⇒ ←

=

=

<

∑

∑

∑

;

;

;

;

;

;

;

0

0 0

0

0

0

1

1

0

ai

k

fin tant que

j=1

j=l

Cet algorithme produit un chromosome fils toujours viables à partir de deux parents sélec-tionnables. Cette représentation étant la plus naturelle et ne demandant pas de conversion ou de répa-ration, c’est celle que nous avons choisie pour notre problème.

8. ConclusionLes algorithmes génétiques correspondent à des méthodes d’optimisation nouvelles, leur pro-

cessus permet d’atteindre une solution optimale en se basant sur le principe de l’évolution humaine.Le calcul pour obtenir une nouvelle génération avec les AG se décompose couramment en 4 parties :la sélection, le croisement, la mutation et la reproduction.

Les opérateurs dans les algorithmes génétiques n’ont pas la même importance. Ainsi,l’opérateur de crossover a une place importante dans le processus d’exploration de l’espace des solu-tions comme le prouve la théorie. La mutation quant à elle ne joue qu’un rôle secondaire par rapportau crossover mais son influence sur l’exploration de l’espace des solutions n’est pas à négliger.

Parmi les représentations possibles du problème, la représentation chemin correspond à unereprésentation naturelle et les opérateurs qui y sont définis donnent des individus toujours viablesaprès croisement. N’ayant pas à utiliser d’opérateur de décodage du binaire vers le décimal et vice-versa, cette représentation a été adoptée.


& 56

Utilisation des algorithmes génétiques pour l’ordonnancement.

1. Mise en place des algorithmes génétiques.

1.1. Le codage.Par rapport au génome humain, les caractéristiques d’un individu dans un algorithme généti-

que sont codées par une chaîne de caractères, appelée chromosome. Un individu est représenté par unet un seul chromosome. Le codage traditionnellement utilisé pour les algorithmes génétiques est lecodage binaire. Toutefois, cette forme de codage ne permet pas de mettre en évidence les lots de ma-nière claire mais aussi leurs modes de placements. Comment représenter :

? un lot,? un mode de placement en marche avant,? un mode de placement en marche arrière.

La représentation d’un lot en forme binaire n’est pas explicite tandis qu’un lot dont on a attri-bué une valeur décimale entière correspondant au numéro du lot donne une idée plus facile à com-prendre pour tout un chacun.

[ ]Un lot numéro de lot= ∈ ∞1Pour représenter la notion de placement en marche avant et la notion de placement en marche

arrière, il a été adopté la notation suivante :− ⇒+ ⇒

numéro de lot placement en marche arrièrenuméro de lot placement en marche avant

donc le codage permet de représenter rapidement un chromosome représentant un ordonnancementd’un ensemble de lots. Soit par exemple le chromosome suivant :

1 4 3 2 5 6 9 8 7 10− − − −Ce chromosome représente un ordonnancement de 10 lots dont les lots 4, 2, 8 et 7 sont placés

en marche arrière. On a donc une représentation chemin. Le codage d’un problème pour l’explorationgénétique ne pose pas de problème. Les algorithmes génétiques exploitent les similarités dans lescodages quelconques tant que les briques élémentaires (les schèmes courts et très performants) con-duisent à un quasi optimum. Les méthodes de codages sont variées, toutefois, il existe un principe debase pour choisir un codage d’algorithmes génétiques : le principe des alphabets minimaux qui sedéfinit ainsi :

L’utilisateur doit choisir le plus petit alphabet qui permette une expression natu-relle du problème.

Ce principe peut facilement être mis en œ uvre. Il aurait été possible de représenter un chro-mosome par une chaîne de nombre binaire signé sur 8 bits . Par exemple,

1 4 3 2 5 6 9 8 7 10− − − −devient0000000111111100000000111111111000000101000001100000

1001111110001111100100001010K

Ce type de codage respecte bien le principe sur l’alphabet minimum }{0 1 mais n’est pasexplicite pour le néophyte. De plus, ce type s’apprête bien aux opérations de crossover et de mutation.La conversion en binaire est donc inadéquat dans notre cas en raison de la place importante en mé-moire que cela prendrait.


& 57

Population avec chromosome de longueur 1010 20 50 100

Décimal 100 cases mémoi-res

200 cases mémoi-res



Binaire signé sur8 bits





Tableau 8: Place mémoire occupée en fonction de la population et du codage.

De plus, lors des opérations de crossovers et de mutations, il y a de fortes présomptions pourque le nouveau chromosome ne soit pas valide :

• le point de croisement fait apparaître un nouveau lot d’où erreur génétique.Par exemple, soit un chromosome A= ... 4 ... et un chromosome B= ... -4 ... avec :

− 4 et -4 à la même position ;− un chromosome de longueur l=10 ;− lot numéroté de 1 à 10 ;− | comme point de coupure.

K KK K

K K K K000 0010011111100

11100100 28

⇒ ⇒ −

On voit sur cet exemple un lot nouveau : le lot 28 qui n’existe pas.Donc le codage binaire entraîne un nombre important de chromosomes non viables. Le pro-

gramme d’ordonnancement nécessitant des nombres décimaux, il n’était pas nécessaire de réaliser uneconversion du binaire signé vers le décimal et vis et versa. Donc nous adopterons la convention sui-vante :

Nombres décimauxSigne placement en marche avantSigne placement en marche arrière

+ ⇒− ⇒

1.2. La reproduction.Lorsque les deux parents sont sélectionnés, ils vont donner naissance à deux nouveaux indivi-

dus, en recombinant leurs gènes. Pour cela, ils utilisent divers opérateurs génétiques, en particulier lecrossover et la mutation. Le crossover consiste à prendre les deux chromosomes parents, à les couperen un endroit quelconque et à recoller les morceaux, mélangeant ainsi l’information génétique desdeux parents.

L’information contenue dans les gènes pouvant être altérée, le crossover n’est pas toujoursappliqué de manière systématique. L’autre opérateur génétique, la mutation, est appliqué aux enfants.Afin de créer des individus vraiment nouveaux, il faut explorer l’espace des chromosomes et ne pas secontenter d’utiliser l’information des parents.

1.3. La sélection.La sélection est l’opération qui consiste à prendre les meilleurs individus d’une population à

un instant t pour qu’ils puissent se croiser entre eux. A la génération N , l’opérateur de sélection[MUHLENBEIN] doit calculer le Fitness de chaque chromosome pour déterminer les meilleurs élé-ments.


& 58

FF x

uPopSize

Ni

i

uPopSize

=∑ ( )

CF x

FNi

Ni=

( )

avec les notations suivantes :uPopSize représente la taille de la population, c’est-à-dire le nombre de chromosomesdans la population,

x Ni représente le chromosome i de la population uPopSize à la génération N,

F x Ni( ) représente le retard pour le chromosome i de la population uPopSize à la géné-

ration N,F représente le retard moyen sur la population uPopSize à la génération N,

C Ni représente la valeur normalisée du Fitness associée au chromosome i de la popula-

tion uPopSize à la génération N.

C p g sélectionable

C p g non_ sélectionnable

Ni c n

Ni c n

≥ ∗ ⇒

< ∗ ⇒

avec les notations suivantes :

pc est la probabilité de crossover,gn est le gain en génération.

1.4. Le déblocage.Suite aux premiers tests effectués, il est apparu que la méthode de sélection pouvait rendre

tous les chromosomes d’une population à un instant t non sélectionnable. Donc, le processusd’exploration de l’espace des solutions était bloqué.

}{∀ ∈ = ⇒i uPopSize non sélectionnable blocageNi1,.., _ , x

Le problème principal des algorithmes génétiques est une convergence prématurée vers unesolution qui est un sous optimum. Le blocage correspond à un sous optimum mais les chromosomesde la population n’ont plus une valeur de Fitness suffisante pour être sélectionnée. N’étant pas à unoptimum, le processus itératif ne doit pas rester dans une phase d’échec donc une fonction dite dedéblocage peut intervenir.

Le déblocage fut envisagé de différentes manières :⇒ Un déblocage systématique,⇒ Un déblocage par fonction,⇒ Un déblocage aléatoire,⇒ Un déblocage en fonction d’un seuil.

L’algorithme des fonctions est le suivant


& 59

Calcul du nombre Nb de chromosomes non sélectionnables.Si Nb > seuilAlors

Pour i variant de 1 à uPopSizeSi chromosomei non sélectionnableAlors chromosomei sélectionnable.

Nb x non sélectionnableNi

i

uPopSize

= ∑ _

Si }{Nb seuil i uPopSize x non sélectionnable x sélectionnableNi

Ni≥ ⇒ ∀ ∈ =1,.., , _

avec les notations suivantes :Nb correspond au nombre de chromosomes non sélectionnables,seuil représente une valeur placée en paramètre ou la valeur d’une fonction à un instantdonné.

Différentes méthodes de déblocage furent testées. La méthode la plus simple est le déblocagesystématique et par seuil. Mais le processus itératif des algorithmes génétiques conduit à obtenir unesolution se rapprochant de l’optimum. Donc au début du processus, les chromosomes d’une popula-tion ont des Fitness très différents mais en fin de processus, les chromosomes se rapprochent de lasolution optimale. Donc le nombre de chromosomes ayant un mauvais Fitness est faible. Par consé-quent, le déblocage ne doit presque pas intervenir afin de ne pas modifier de manière sensible la po-pulation.

D’où le choix de fonctions dont la limite tend vers zéro quand le nombre de générations aug-mente.

Figure 10 : Graphe de f tt

t:

log→ .

log xx

x→ + ∞ → 0

Figure 11 : Graphe de f tt

t: → .

xx

x→ + ∞ → 0


& 60

L’emploi de ces deux fonctions pour réaliser un seuil de déblocage a des avantages :• Déblocage que si nécessaire en fin du processus d’itération,• Evite de modifier les caractéristiques de la population.

1.5. La mutation.Les étapes de reproduction et de croisements explorent et recombinent efficacement les chro-

mosomes d’une population cependant la mutation est nécessaire, car certains chromosomes peuventdevenir trop prédominant par rapport à d’autres et perdre de la matière génétique potentiellement utile(un signe plus ou un signe moins à un lot précis). Dans un algorithme génétique simple, la mutationest la modification occasionnelle (de faible probabilité pm) de la valeur d’un caractère dans le chromo-some [GOLDBERG 1994].

Variation du retard en fonction du taux de mutation pour le fichier L10o5m4.txt avec FlXRate=1, FlGap=0.8, FlDRate=0.66, uPopSize=10 et Nb de génération=5000.

70

80

90

100

110

120

130

1 0,8 0,6 0,4 0,2

Probabilité de mutation

Ret

ard

Pour crossover Mutation SimplePour crossover Bi-PointPour crossover PermutationPour crossover PMXPour crossover CXPour crossover OXPour crossover UniformePour crossover TG Uniforme

Figure 12 : variation du retard en fonction du taux de mutation.

Les taux de mutation sont faibles dans les populations naturelles, ce qui nous conduit à penserque la mutation est considérée à juste titre comme un mécanisme d’adaptation secondaire pour lesalgorithmes génétiques.

? La probabilité de mutation pm que nous utiliserons sera donc faible.De plus, les expériences ont montré qu’une grande probabilité de mutation ne conduisait pas à

de meilleurs résultats. Sur la figure ci-dessus, la variation de la probabilité de mutation n’ayant pas derépercutions significatives sur la valeur du retard, nous utiliserons par la suite une probabilité de mu-tation pm faible. Nous retiendrons que la fréquence de mutation conseillée pour obtenir de bons résul-tats dans les études empiriques se situe autour d’une mutation toutes les 1000 positions.

pm = 0 001.Pour l’opérateur de mutation, deux méthodes furent employées :

• Une mutation systématique,• Une mutation aléatoire.

La mutation systématique consiste à choisir deux places aléatoirement sur un chromosomesélectionnable et à permuter les deux valeurs en changeant leur signe. (Cela permet de conserver laviabilité.)


& 61

Algorithme de la mutation systématique.Choisir aléatoirement un chromosome sélectionnable,Choisir deux emplacements aléatoirement sur le chromosome,Permuter les valeurs se trouvant aux deux emplacements et changer le signe.

La mutation aléatoire consiste à choisir deux places aléatoirement sur un chromosome sélec-tionnable et de permuter les deux valeurs mais en changeant aléatoirement le signe :

− d’une des deux valeurs,− des deux valeurs (revient à appliquer la mutation systématique).

Algorithme de la mutation aléatoire.Choisir aléatoirement un chromosome sélectionnable,Choisir deux emplacements aléatoirement sur le chromosome,Permuter les valeurs se trouvant aux deux emplacements,Choisir aléatoirement une méthode de changement de signe :

changement de signe sur l’emplacement 1 ;changement de signe sur l’emplacement 2 ;changement de signe sur les deux emplacements.

2. Le crossover.

2.1. Théorie des opérateurs de crossover PMX, CX et OX.Quelques valeurs intéressantes sur les réorganisations des gènes dans les chromosomes furent

calculées par Frantz [FRANTZ 1972][GOLDBERG 1989]. Le calcul définit la probabilité du mouve-ment d’un gène en fonction des spécificités du chromosome (ordre et longueur). Ceci permet de dé-terminer la probabilité de mouvement d’un gène placé à une position particulière. La probabilitéqu’une permutation aléatoire se déroule, avec o allèles et une longueur utile égale à δ est donnéepar :

}{P Dl

ol= =

− +−−

δδ

δ

δ

( ).122

La distribution cumulée correspondante fut aussi calculée :

}{P D

ll

l≤ =

⋅

− +

δ

δο

δ οδ δ

δLa probabilité d’un gène de se mouvoir pour un gène se trouvant la position k dans une

chaîne de longueur l est donnée par :

}{ ( )[ ]P

k l kl

mouvement d' un gène =+ − +2 1 12

2

Pour des chaînes (chromosomes) de grandes longueurs, l’expression ci-dessus peut être ré-duite à :

}{ ( )P mouvement x x= −2 2

où x représente le nombre sans dimension xkl

= . Cette fonction donne un maximum P=0.5 pour

x=0.5.


& 62

Figure 13 : Graphe de f : .( )t x x→ −2 2

Bien que les algorithmes de crossover tels que le PMX, OX et CX furent principalement dé-veloppés pour résoudre le problème du voyageur de commerce (T.S.P. =Travelling Salesman Pr o-blem), ils peuvent facilement être adaptés à l’ordonnancement d’ateliers.

En fonction des différents opérateurs de croisements, après avoir réalisé un certain nombre detests, il est apparu que les crossovers PMX, OX et CX donnaient de meilleurs résultats que les opéra-teurs classiques.

2.2. Les crossovers permutation et TG-uniforme.Le crossover Permutation donne obligatoirement un individu viable car correspond à un opé-

rateur de croisements hermaphrodites. Pour se faire, il utilise un chromosome sélectionnable et unpoint de coupure pour obtenir un nouvel individu. Le mécanisme correspond à permuter les souschromosomes par rapport au point de coupure.

Le crossover TG-Uniforme se base sur l’algorithme du crossover uniforme. Ce dernier réaliseun crossover à partir de deux parents sélectionnables pour obtenir un nouveau chromosome qui seraensuite inséré dans la nouvelle population dans la mesure où celui-ci est viable.


& 63

Algorithme du crossover uniforme.Choisir deux parents sélectionnables A et B.

{ }( )

[]( )

[] [][ ] [ ][ ] [][ ]( )

V i x x

C Acntcnt

V i T cnt cnt i

B i A T j C T cnt cnt A T j

i

l

i

l

j

cnt

i

l

[ ] ; ;

;;

;

[ ] ;

=

===

= ⇒ ← + =

= ⇒ ← + ←

=

=

==

∑

∑

∑∑

1

1

11

0 1

02 0

0 1

2 2 1

a

C est le chromosome fils

Un chromosome issu de deux parents peut avoir une ou plusieurs erreurs génétiques, dans no-tre cas :

• un ou plusieurs lots identiques dans le même chromosome ; 1 2 3 4 5 6 4 8 9 10

• un lot avec un placement en marche avant et le même lot avec un placement enmarche arrière.

1 2 3 4 5 6 - 4 8 9 10Donc pour obtenir plus de chromosomes viables après le crossover uniforme, un algorithme

de réparation a été greffé après le crossover uniforme. Cet algorithme n’opère que dans le cas où lechromosome n’a qu’une erreur génétique. Cette algorithme recherche l’erreur génétique : valeur de lotmanquante et positions des erreurs. Ensuite il regarde l’allure des parents pour réparer le chromosomefils.


& 64

Algorithme de réparation.

[] [ ]

( )

[]( )

ztfla gp lacep laceF a ire

C zz

t tp lace z

p lace zzfla g

zz zz

T a n t que z

P o u r i var

←←

←←←

←

= ⇒

← +←←=

← +

←

←←

←

←

= ⇒=

← −

←

00

11 02 0

11

20

1

;;

;;;

;

;

zz z + 1 ;F a ire

C z

z < l;z z + 1 ;

T a n t que z < l;fla g 2 1 ;

S i (fla g = 0 ) et (t = 1 ) a lors va le u r 0 ;ian t de 1 à l, fa ire

fla g 3 0 ; P o u r j v ar ian t de 0 à l - 1 faire

fla g 3 fla g 3 + 1 ;

S i C j ifla g 2 0 ;

fla g 3 f lag3 1fin p o u r

fin p o ur S i (fla g 3 = l) a lors va leur i;

[][] []

( ) ( ) [ ]( ) ( ) [ ]

[ ] { }

fin p o u rP o u r i varian t de 1 à l fa ire

A[ i] a lors va leur_ paren t_ A A i

S i B i a lors va leur_ paren t_ B B i

fin p o u r

v a leur_ p a r e n t_ A = valeur_ paren t_ Bv a leur_ p a r e n t_ A = valeur_ paren t_ B

v a leur_ p a r e n t_ A v a leur_ p a r e n t_ B

S i va leur

v a leur

S ie t va leur p a r e n t A C p lace v a leur

e t va leur p a r e n t A C p lace v a leurC p lace v a leur va leur

= ←= ←

> ⇒ ←< ⇒ ← −

≠ ⇒ ← −

_ __ _

0 20 2

2

2.3. Le crossover simple, bi et multi points.Les crossovers simple et bi-points correspondent à des cas particulier du crossover multi

points. Le principe de base consiste à prendre deux chromosomes sélectionnables à déterminer unensemble de points de coupures et à permuter les sous chromosomes pour obtenir de nouveaux en-fants.


& 65

Le principal problème avec ces méthodes est qu’elles ne donnent pas beaucoup d’enfants via-bles lors de chaque crossover. De plus, plus le nombre de points de croisement augmente, plus lenombre de chromosomes non viables augmente.

Algorithme du crossover multi-points.

{ ( ) }

( )

Soit 2 chr

Pour z var

z

Si p z et p z

omosomes A et B sélectionnables

point 0l2

iant de 0 à point fairerépéterflag = 0

p , l

point + 1l

point + 1<

lpoint + 1

alors flag = 1

jusqu' à flag = 1nb_ point[z] pfin pourSi point 2 = 0 alorsdébutz = 0répéterpour copie variant de nb_ point[z] à nb_ point[z + 1] faireA[copie] B[copie]fin pourz z + 2jusqu' à z < point - 1sinondébutz = 0répéterpour copie variant de nb_ point[z] à nb_ point[z + 1] faireA[copie] B[copie]fin pourz z + 2jusqu' à z <

∈ −

← +

≥ +

←

≡

←

←

←

←

1

0 1

1

*

* *

point - 2pour copie variant de nb_ point[copie - 1] à l + 1 faireA[copie] B[copie]fin pourfin si

←

Ne donnant pas de bons résultats et ne donnant pas souvent des individus viables, ces métho-des n’ont pas été retenues.

3. Choix de l’opérateur de croisement et des paramètres.Les algorithmes génétiques ont montré qu’ils étaient basés sur le processus d’évolution mais

plusieurs moteurs de crossover ont été mis au point. Donc comme dans le domaine naturel, certainsopérateurs sont plus approprié que d’autres pour obtenir un chromosome fils. Par conséquent, un en-semble de tests a été réalisé afin de déterminer le meilleur opérateur de crossover pour la recherched’optima de placements de lots. Afin de ne pas perturber les tests, ceux-ci ont furent réalisés en fixantl’ensemble des paramètres manipulés par les algorithmes génétiques.


& 66

Variation du retard en fonction des opérateurs de croisements avec les paramètres suivants:Ngen=5000, uPopSize=100, FlMRate=0,8, FlGap=1, FlXRate=0,98, FlDRate=0,66.

0

10

20

30

40

50

60

70

80

90

100

Simple Bi-points Permutation PMX CX OX Uniforme TG-Uniforme

Opérateurs de crossover

Ret

ard

Retard

Figure 14 : Variation du retard en fonction des opérateurs.

Donc nous pouvons conclure que les opérateurs classiques de croisements ne sont pas adaptésà l’ordonnancement d’ateliers car : ils donnent un nombre important de chromosomes non viables.Les opérateurs Permutation, PMX, CX et OX quant à eux, donnent un chromosome fils toujours via-bles du fait de leurs algorithmes (voir figure 15).

05

1015

20

25

30

35

40

45

50

Sim

ple

Mul

ti-po

ints

Per

mut

atio

n

PM

X CX OX

Uni

form

e

TG U

nifo

rme

0

100

200

300

400

500

600

Mau

vais

cro

ssov

er

Génération

Opérateur

Nombre de chromosomes non viables pour 100 crossovers par génération.

500-600400-500300-400200-300100-2000-100

Figure 15 : Nombre de chromosomes non valides en fonction des opérateurs et des générations.


& 67

Ces tests ont montré que l’ensemble des opérateurs de crossovers donnait de bon résultat deplacement de lot mais plus ou moins rapidement. Les opérateurs de croisements classiques donnent debons résultats mais au prix :

• d’un nombre important de générations, donc d’un temps de calcul très long,• d’un nombre important de chromosomes fils non valides.

Ainsi, il s’est avéré que les opérateurs issus du TSP (Problème du Voyageur de Commerce)donnaient de bons résultats et ceci plus rapidement.

De plus, parmi les opérateurs issus du TSP, c’est l’opérateur de croisement : le crossover CX(Cycle Crossover) qui donne les meilleurs résultats (Voir figure 16 et 17).

Donc, pour l’ensemble des tests suivants, nous utiliserons comme opérateur de croisement : lecrossover CX.

Evolution du retard en fonction des générations avec comme paramètres : uPopSize=10, nGen=5000, flXRate=0,98, flMRate=0,8, flDRate=0,66..

0

50

100

150

200

250

0 500 1000 1500 2000 2500 3000 3500 4000

Génération

Ret

ard

(Uni

té d

e te

mps

) SimpleBi-pointsPermutationPMXCXOXUniformeMoyenne

Figure 16 : Evolution du retard en fonction des générations.


& 68

Var ia t ion du temps e t du re ta rd en fonc t ion des opéra teurs pour l e f i ch ie r l 10o5m4. tx t avec comme paramèt res : uPopSize=10 , nGen=5000 , f lXRate=0 ,98 , f lMRate=0 ,98 , f lDRate=0 ,66

0:00

0:28

0:57

1:26

1:55

2:24

2:52

S i m p l e Bi -po in ts Permuta t ion P M X C X O X Uni fo rm e T G - U n i f o r m e

Opéra teurs de c rossover

Tem

ps (H

eure

)

0

1 0

2 0

3 0

4 0

5 0

6 0

7 0

8 0

9 0

100

Ret

ard

(Uni

té d

e te

mps

)

T e m p sRetard

Figure 17 : Evolution du retard et du temps en fonction des opérateurs.

La variation du temps pour réaliser 5000 générations montre que la progression est quasi li-néaire en fonction de la taille de la population (voir figure 18). De plus, à partir d’une certaine taillede la population, le résultat est identique donc il n’est pas nécessaire de rechercher un optimum pourun fichier donné avec une taille de population importante (voir figure 19). Il n’est pas nécessaired’avoir une taille importante de population pour avoir un bon résultat.

Pour les prochains essais, nous prendrons comme taille de population :

N=uPopSize=50.

Temps calcul en fonction de la taille de la population pour le fichier l10o5m4.txt avec comme paramètres : nGen=5000, flXRate=0,98, flMRate=0,8, flDRate=0,66, crossover=CX.

0:00

2:24

4:48

7:12

9:36

12:00

14:24

16:48

19:12

21:36

0 100 200 300 400 500 600 700 800 900 1000

Taille de la population

Tem

ps (h

eure

)

Temps

Figure 18 : Evolution du temps de calcul en fonction de la taille de la population.


& 69

Variation du retard en fonction de la taille de la population pour le fichier l10o5m4.txt avec comme paramètres : nGen=5000, flXRate=0,98, flMRate=0,8, flDRate=0,66, crossover=CX.

0

20

40

60

80

100

120

0 100 200 300 400 500 600 700 800 900 1000

Taille de la population

Ret

ard

Retard

Figure 19:Evolution du retard en fonction de la taille de la population.

0

10

20

30

40

50

60

70

80

90

100

0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

Probabilité de mutation

Ret

ard

(Uni

té d

e te

mps

)

RetardPolynomial (Retard)

Variation du retard en fonction de la probabilité de mutation pour le f ichier l10o5m4.txt avec comme paramètres : uPopSize=50, nGen=5000, f lXRate=0,98, f lDRate=0,66, crossover=CX.

Figure 20:Evolution du retard en fonction du taux de mutation.

Après avoir fixé la taille de la population à 50, il fallait tenter de trouver une valeur ou un in-tervalle pour le taux de mutation afin d’obtenir les meilleurs résultats. La théorie montre quel’opérateur de mutation joue un rôle secondaire dans le processus des algorithmes génétiques. Mais ilapparaît aussi que dans notre cas, la mutation joue un rôle non négligeable dans l’exploration del’espace des solutions pour la recherche d’optima. Donc nous prendrons comme taux de mutation(d’après la figure 20) la valeur :

p flMRatem = = 0 8. .La mutation joue un rôle peut-être secondaire mais elle doit toujours être présente afin :

• de respecter les principes de l’évolution,• d’introduire plus de variations de signes,• sortir des solutions sous-optimales.


& 70

Evolution du retard en fonction de la probabilité de crossover pour le fichier l10o5m4.txt avec comme paramètres : nGen=5000,uPopSize=50, flMRate=0,8, flDRate=0,66, crossover=CX.

0

10

20

30

40

50

60

70

80

90

100

0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

Probabilité de crossover

Ret

ard

(Uni

té d

e te

mps

)

RetardPolynomial (Retard)

Figure 21:Evolution du retard en fonction du taux de crossover.

Après avoir fixé le taux de mutation, il fallait enfin fixer le taux de crossover à employer pourobtenir des résultats corrects. Un ensemble de tests a été réalisé afin de montrer l’évolution possibledu retard en fonction d’une variation du taux de crossover. Ces tests ont montré qu’une variation dutaux de crossover avait une incidence directe sur le résultat donc sur la recherche d’un optimum dansl’espace des solutions. Ainsi, pratiquement, une probabilité de crossover faible engendre de mauvaisrésultats car peu de croisements vont être réalisés.

Donc, la probabilité de crossover, comme nous l’avions prévu dans la théorie, joue un rôleimportant dans le traitement de recherche d’optima par la méthode des algorithmes génétiques. Il avaitété montré empiriquement par GOLDBERG que le taux de crossover idéal était aux alentours de 0.8,pratiquement, nous pouvons voir que les meilleurs résultats sont obtenus avec un taux de crossovercompris entre 0.6 et 1.

{ }p flXRatec = ∈ 0 6 1. KFinalement, nous obtenons un fichier de confuguration pour la recherche d’un optimum par la

méthode des algorithmes génétiques de la forme :

Nombre de générations :5000Taille de la population :50Probabilité de crossover :0.98Probabilité de mutation :0.8Taux de déblocage :0.66Gain de génération :1

4. Les résultats.Pour réaliser les tests qui suivent, nous avons choisi le meilleur opérateur de croisement à

savoir le CX et les valeurs des paramètres trouvées précédemment.Tests de temps pour 10 000 placements :


l10o10m4.txt 584l20o3m4.txt 520


& 71

l20o5m4.txt 700l20o10m4.txt 2700l50o3m4.txt 960l50o5m4.txt 4340

l50o10m4.txt 7260

Tableau 9 : Temps d'exécution pour les algorithmes génétiques.

Ces temps ne sont pas meilleurs par rapport aux autres méthodes car les algorithmes généti-ques nécessitent plusieurs étapes avant de faire un placement toutefois les algorithmes génétiquesdonnent de meilleurs résultats en moyenne au niveau des retards pour les petits exemples.

Pour chaque fichier de la base d'exemples, nous avons aussi réalisé une série de cinq tests de20 000 placements chacun (1000 générations pour une population de 20 individus). Pour les résultats,nous mettrons là aussi la moyenne des meilleurs retards obtenus à chacun de ces tests et le meilleurvecteur (ordre des lots) obtenu.Nom du fichier Moyenne

desmeilleurs

retards

Meilleurretard


l10o3m4.txt 23 20 5 -3 2 4 6 -1 7 9 -10 -8l10o5m4.txt 86 70 -4 -10 5 1 -2 6 -9 7 -3 8

l10o10m4.txt 321 306 1 3 -5 4 2 7 9 6 8 10l20o3m4.txt 131 119 -6 -15 -7 -3 -18 -10 19 -17 -1 -11 8 20 2 14 -13 -3 12 4 -16 9l20o5m4.txt 458 420 16 -14 10 -9 -5 -2 -3 11 -6 17 -18 13 -8 -15 -4 -12 20 7 -19 1

l20o10m4.txt 1134 1013 4 -9 2 3 -10 5 6 7 -12 -1 -11 -13 20 8 18 15 -14 17 -16 19l50o3m4.txt 1001 842 49 48 -2 3 30 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

22 23 24 25 26 27 28 29 4 31 32 33 34 35 36 37 38 39 40 4142 43 44 45 46 47 1 50

l50o5m4.txt 2835 2287 -4 1 2 3 -15 5 6 7 8 9 10 11 12 50 13 14 15 16 17 -19 -18 2021 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 -48 49l50o10m4.txt 5110 5110 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 4344 45 46 47 48 49 50

Tableau 10 : Résultats de la simulation par la méthode des AG.

On peut comparer maintenant les résultats des AG avec les autres méthodes. Pour cela, voir les figu-res ci-dessous ( Figures 22 à 25).


& 72

Moyenne des retards pour chaque méthode.

0

100

200

300

400

500

600

l10o3m4.txt l10o5m4.txt l10o10m4.txt l20o3m4.txt l20o5m4.txt

Ret

ard.

Méthode Aléatoire Méthode GradientMéthode RecuitMéthode AG

Figure 22 : Moyenne du retard pour chaque méthode.

Moyenne du retard pour chaque méthode.

0

1000

2000

3000

4000

5000

6000

7000

l20o10m4.txt l50o3m4.txt l50o5m4.txt l50o10m4.txt

Ret

ard

Méthode Aléatoire Méthode GradientMéthode RecuitMéthode AG

Figure 23 : Moyenne du retard pour chaque méthode.

Meilleur retard pour chaque méthode.

0

50

100

150

200

250

300

350

400

450

500

l10o3m4.txt l10o5m4.txt l10o10m4.txt l20o3m4.txt l20o5m4.txt

Ret

ard

Méthode AléatoireMéthode GradientMéthode RecuitMéthode AG

Figure 24 : Meilleur retard pour chaque méthode.


& 73

Meilleur retard pour chaque méthode.

0

1000

2000

3000

4000

5000

6000

7000

l20o10m4.txt l50o3m4.txt l50o5m4.txt l50o10m4.txt

Ret

ard.

Méthode AléatoireMéthode GradientMéthode RecuitMéthode AG

Figure 25 : Meilleur retard pour chaque méthode.

Les algorithmes génétiques donnent de bons résultats surtout pour les petits exemples. Pourobtenir de meilleurs résultats sur les grands exemples, il aurait fallu prendre une taille de populationplus grande et réaliser plus de génération. Mais dans ce cas, cela aurait réclamé plus de 100 000 pla-cements ce qui aurait empêché de bonnes comparaisons avec les autres méthodes.

On peut cependant dire que pour 100 000 placements, les algorithmes génétiques donnent lesmeilleurs résultats parmi toutes les méthodes. En effet, les autres méthodes ont plus tendance à resterbloquées sur des solutions sous-optimales que les AG. Pour les deux premiers fichiers à 10 lots, onvoit clairement que les AG sont meilleurs puisqu’on trouve les deux valeurs optimales, ce qui n’étaitpas le cas avec les autres méthodes.

5. Conclusion.La technique de codage employée est un codage en décimal suivant la représentation chemin.

Ce codage diffère des codages classiques car chaque gène possède un signe caractérisant le sens deplacement du lot correspondant. L’opérateur de mutation est plus important ici que pour les AG tradi-tionnels car c’est à ce niveau que sont introduits les changements de signe et il permet de sortir desoptima locaux. Les meilleurs opérateurs de croisement sont ceux qui ont été définis à la représentationchemin car ils donnent des individus viables et permettent un meilleur brassage des gènes. Parmi cestrois opérateurs, le meilleur qui a été trouvé après plusieurs tests est le crossover CX. Ces tests ontaussi permis de déterminer les autres paramètres pour obtenir les résultats les plus intéressants.

Les algorithmes génétiques donnent de bons résultats pour les petits fichiers (10 lots) et attei-gnent l’optimum pour les exemples l10o3m4.txt et l10o5m4.txt contrairement aux autres méthodes.En moyenne, les résultats sont bons pour les petits fichiers mais afin d’effectuer une comparaisonavec les autres méthodes les tests ont été limités à 20000 placements. Avec une population et un nom-bre de générations plus important, les algorithmes génétiques donneraient les meilleurs résultats parmitoutes les méthodes.

Les algorithmes génétiques permettent donc d’explorer une }surface~ de l’espace des solu-tions (plusieurs individus par génération) alors que les autres méthodes n’explorent qu’un point à lafois (un individu par itération). Cela permet de déterminer ainsi la solution optimale plus rapidementet avec plus de sûreté que les autres méthodes


& 74

.

Modélisation agents en ordonnancement de production de typeJob-Shop

1. IntroductionA la différence de l'Intelligence Artificielle classique qui modélise le comportement intelli-

gent d'un seul agent, l'intelligence artificielle distribuée s'intéresse à des comportements intelligentsqui sont le produit de l'activité coopérative de plusieurs agents. Le passage du comportement indivi-duel aux comportements collectifs est considéré comme une extension et comme un enrichissement del'IA, d'où émergent de nouvelles propriétés et de nouveaux comportements.

2. L'intelligence artificielle distribuéeL'évolution des domaines d'applications de l'IA pour recouvrir des domaines complexes et

hétérogènes tels que l'aide à la décision, la reconnaissance, etc., a montré les limites de l'approcheclassique de l'IA qui s'appuie sur une centralisation de l'expertise au sein d'un système classique.L'Intelligence Artificielle Distribuée [13][12][4]a pour but de remédier aux insuffisances de l'appro-che classique de l'IA en proposant la distribution de l'expertise sur un groupe d'agents devant êtrecapables de travailler et d'agir dans un environnement commun et de résoudre les conflits éventuels.L'IAD peut alors être définie comme étant la branche de l'IA qui s'intéresse à la modélisation de com-portement intelligent par la coopération entre un ensemble d'agents[13].

3. De l'Intelligence Artificielle à l'Intelligence Artificielle Distribuée.Notre problème consiste à déterminer une bonne solution en un temps raisonnable à un pro-

blème d'ordonnancement de type Job-Shop. Pour ce faire, nous utilisons la technique des AlgorithmesGénétiques définis par J. Holland pour aboutir à une solution par dégradations, évolutions successi-ves. Cette méthode consiste à simuler le processus d'évolution des espèces défini par Darwin. Ainsi,étant donné la nature NP-Difficile du problème, nous ne sommes pas obligés de calculer l'ensembledes solutions pour obtenir la ou les solutions optimales. Cette méthode fait appel aux techniques del'intelligence artificielle. Toutefois, elle ne fait pas référence à la nature distribuée des problèmesd'ordonnancement.

3.1. Un premier niveau de représentation : le chromosome.Les Algorithmes Génétiques, par définition, simulent un processus Darwinien. Donc, ceux-ci fontréférence à une modélisation sous la forme de chromosome par analogie au chromosome humain re-présenté par une chaîne d'ADN. Donc comment un ordonnancement de n lots sur un ensemble de mmachines en utilisant la notion de chromosome peut-il être représenté ?

3.2. Placement contre simulation.Pour générer des solutions au problème d'ordonnancement, nous avons choisi une méthode de place-ment par lots et non de simulation. Le placement en général consiste à prendre les opérations une parune, regarder les machines sur lesquelles elles peuvent être réalisées, choisir celle donnant le meilleurrésultat en "plaçant" l'opération au mieux, c'est-à-dire à un endroit où la machine est libre et qui res-pecte les contraintes de précédence (la nième opération d'un lot ne peut commencer qu'après la fin de la(n-1)ième opération du même lot).Le placement par lots consiste à prendre chaque lot les uns après les autres et à placer toutes leursopérations d'un coup. Suivant l'ordre des lots que l'on choisit pour effectuer le placement, on obtientdes solutions totalement différentes (voir la Figure 27 ci-dessous qui compare la simulation avec le


& 75

placement : suivant que l'on commence par le lot1 ou le lot2, on obtient pas le même résultat). Ilexiste de plus deux types de placement :

ü en marche avant : on part de la date au plus tôt du lot et on prend les opérations dansl'ordre en partant de la première (op1 puis op2 puis op3 et op4 dans l'exemple 1 quisuit),

ü en marche arrière : on part de la date au plus tard du lot et on place les opérationsdans l'ordre inverse, c'est-à-dire en partant de la dernière (op4 puis op3 puis op2 etop1 dans la Figure 26 1 qui suit).

Lot : date au plus tôt = 0 date au plus tard = 140Opérations durée machine

op1 30 M2op2 20 M1op3 20 M2op4 40 M1

Placement en marche avant :M1

10 50 100 150M2

10 50 100 150Placement en marche arrière :M1

10 50 100 150M2

10 50 100 150


La simulation quant à elle, procède instant par instant en regardant les opérations qu'elle doit et peutplacer sur les machines. On avance ainsi progressivement dans le temps, mais le problème est qu'enplaçant une opération trop vite, on risque de bloquer un autre lot, entraînant ainsi de grands retards dufait de grands décalages. En effet, dans certains cas, il est préférable de retarder le lancement d'uneopération pour gagner du temps par la suite sur un autre lot. Pour bien comprendre ce phénomèneregardons l'exemple simple qui suit :Soient les deux lots suivants à placer sur deux machines M1 et M2 :


11 10 M112 10 M213 50 M1

op4op2

op3op1

op2 op4

op3op1


& 76


21 50 M222 50 M1

La simulation donnerait :

M1

10 50 100 150M2

10 50 100 150

Ce qui fait un retard de 80 pour le lot 1 et 0 pour le lot 2 ⇒ retard = 80 au total.Le placement donnerait en commençant par le lot1 :

M1

10 50 100 150M2

10 50 100 150


Ce qui fait un retard de 0 pour le lot 1 et 20 pour le lot 2 ⇒ retard = 20 au total.Le placement est donc meilleur dans ce cas. De plus, le placement en commençant par le lot 2 donne-rait le même résultat que la simulation. On a donc plus de possibilités en utilisant le placement que lasimulation et le placement est mieux adapté à notre étude (voir le chapitre sur les algorithmes généti-ques).

3.3. Choix du placement par lots.Nous avons choisi le placement par lots (c'est-à-dire prendre les lots un par un et placer toutes

leurs opérations) et non par opérations (à savoir placer toutes les opérations sans tenir compte du lotauquel elles appartiennent) pour des raisons de temps de calcul comme cela a déjà été dit précédem-ment. En effet, les algorithmes génétiques sont basés sur des vecteurs appelés chromosomes, et lataille de ces vecteurs détermine le nombre de possibilités et donc le temps de calcul.

La formule (c.f. Équation 1) indiquant le nombre de possibilités s'explique en considérant unvecteur de n lots : pour le choix du premier lot à placer, on dispose de n possibilités (parmi les n lots)et on peut le placer en marche avant ou en marche arrière. On a donc 2 n possibilités. De même pourle second lot, on a 2(n-1) possibilités (il reste n-1 lots à placer), et ainsi de suite. Au total, cela donne :

!21.22.2...)2(2)1(22 nnnn n ×=×××−×−×Équation 1 : Nombre d'ordonnancement possible en mode placement par lot.

132211

1221

221311

2112


& 77

Pour les opérations le principe est le même mais le vecteur a pour longueur le nombre d'opérations.

Remarque : le placement en marche avant est toujours possible alors que ce n'est pas le cas pour lamarche arrière car il se peut que l'on commence un lot avant sa date au plus tôt, ce qui est strictementinterdit. Dans un tel cas, on placera le lot obligatoirement en marche avant.

3.4. La représentation chromosomique.Une fois avoir choisi la méthode de placement par lots, il nous faut définir une représentation

commode à utiliser pour les algorithmes génétiques. D'après le principe du placement que nous avonsdécrit ci-dessus, nous avons une représentation vectorielle d'un ordonnancement (c.f Figure 28). C'estcette forme que nous avons utilisé pour obtenir une bonne solution après croisements, mutations etsélections par les Algorithmes Génétiques.

Figure 28 : Exemple de représentation chromosomique

Cette représentation est directement exploitable par les algorithmes génétiques. Elle correspond auplacement du lot 8 en marche avant, puis du lot 5 en marche arrière, puis du lot 2 en marche avant,etc. Ce type de chromosome fournit un ordonnancement par placement dont nous pouvons voir lareprésentation graphique sur la Figure 29.

Figure 29 : Interface graphique pour l'ordonnancement de lots.

4. Evolution vers les systèmes multi-agentsContrairement à l'approche centralisée de l'IA, l'intelligence artificielle distribuée vise la distributionde l'expertise sur un ensemble de composants qui communiquent pour atteindre un objectif global.

-5 2 -6 1 73 -9-4 -108


& 78

Cette approche nécessite la division du problème en sous-problèmes. Mais cette hypothèse n'est pastoujours réaliste car beaucoup de problèmes ne peuvent être partitionnés.Une extension des systèmes d'IAD est proposée : les composants doivent être capables de raisonnersur les connaissances et les capacités des autres dans le but d'une coopération effective. Pour ce faire,ils doivent être dotés de capacités de perception et d'action sur leur environnement et doivent posséderune certaine autonomie de comportement[9].Les systèmes multi-agents se caractérisent par l'autonomie et l'intelligence des composants impliqués.Toutefois, un agent ne dispose pas d'une vision globale de son environnement.

4.1. Concept d'agentUn agent peut être défini comme une entité (physique ou abstraite) capable d'agir sur elle-même et surson environnement, disposant d'une représentation partielle de cet environnement, pouvant communi-quer avec d'autres agents et dont le comportement est la conséquence de ses observations, de sa con-naissance et des interactions avec les autres agents[12].Les agents ont deux tendances :

F Une tendance sociale tournée vers la collectivité (les mécanismes et connaissances as-sociés concernant les activités du groupe) et

F Une tendance individuelle avec des mécanismes et des connaissances contenant lesrègles de fonctionnement interne de l'agent.

On peut caractériser un agent par : son rôle, sa spécificité, ses objectifs et des fonctionnalités,ses croyances, ses capacités décisionnelles, ses capacités de communication et éventuellement sescapacités d'apprentissage.

5. Modélisation agent d'un ordonnancement de type Job-ShopNous considérons une liste de jobs dont chacun comporte un certain nombre d'opérations en

moyenne. Les lots ont la possibilité d'être placé en marche avant ou en marche arrière, le tout en res-pectant les contraintes de précédences de ceux-ci. Ainsi, à partir de cette liste, nous obtenons un dia-gramme correspondant à l'ordonnancement de cette liste. C'est la méthode que nous avions utilisédans les algorithmes génétiques. Toutefois, pour les problèmes de grande dimension, les résultatsn'étaient pas toujours intéressant par rapport à d'autres méthodes comme le recuit-simulé, etc.

5.1. Modèle de systèmes d'IAD

5.1.1. Contract NetLe Contract Net [1] est un système de résolution de problème distribué, conçu par R. Davis et

R. Smith. L'objectif principal de ce système étant la distribution, il procède par allocation des tâches àun ensemble de résolveurs de problèmes et utilise le concept de négociation pour adjuger des contrats.L'architecture de base contient des nœ uds ayant des rôles de chef et d'exécutants.

5.1.2. Le système Contract NetLes systèmes Contract Net représentent un concept qui peut être utilisé pour établir des méca-

nismes de coordination efficace entre les agents d’un système multi-agent. Un contract net consiste enun nombre de nœ uds qui sont tissés par des agents individuels à l’intérieure d’un système multi-agent.Par analogie à une vente aux enchères, les sous-tâches en suspend sont ouvertement proposées auxenchères auxquelles chaque nœ uds peut répondre en fonction de l’intérêt qu’il porte envers cette sous-tâche. L’étape d’attribution des tâches représente un processus intéractif dans lequel tous les nœ uds(agents) sont associés. L’esprit est d’utiliser les ressources disponibles et la connaissance existantecourante des agents aussi efficacement que possible ; c’est-à-dire par assignation d’une sous-tâche àun agent qui est le plus apte à opérer à un moment donné.


& 79

Le protocole de Contract Net qui forme le squelette d’un système Contract Net, est défini par un lan-gage commun entre les nœ uds qui peut être compris par l’ensemble des agents. La communicationentre les agents est toujours pratiquer sur la notion d’un message d’acceptation. Cette spécificité défi-nie le rôle exact des agent associés. La base de données locale contient la connaissance de base desnœ uds associés et aussi les information sur l’état courant de cette négociation coopérative ainsi que leprocessus de résolution du problème. Le gestionnaire de communications a pour objectif d’établir lescommunications avec les autres nœ uds. C’est l’unique composant d’un nœ uds qui est en relation di-recte avec le réseau. En particulier, il assure la réception et l’envoie des messages.

Figure 30 : Structure d'un noeud du Contract Net

Le gestionnaire de contrats a pour tâche d’observer les tâches offertes aux enchères, le respect ducontrat et la finalisation de celui-ci. Globalement, le gestionnaire de contrats assure la coordinationentre tous les nœ uds. Le gestionnaire de tâches quant à lui est responsable de l’état d’avancementd’un processus et du résultat de l’assignation d’une tâche sur un nœ ud. Il reçoit les problèmes quidoivent être résolus du gestionnaire de contrat, utilise la base locale de données pour déterminer unesolution, et donne celle-ci au gestionnaire de contrat.

Gestionnaire detâches

Base de donnéeslocale

Gestionnaire decontrats

Gestionnaire decommunications Réseau


& 80

Figure 31 : Processus de négociation d'un contrat dans un système Contract Net

Le travail d’un système à base de Contract Net commence après une phase de division du problème, àsavoir après que le problème complet à résoudre eut été divisé en une série de sous-problèmes. Unnœ ud spécial, le “ manager ” entreprend d’assigner une tâche à un sous-problème. Le manager faitune offre public, appelé contrat, pour chaque sous-problème qui doit être résolu selon le schéma défi-ni par Albayrak et Bussmann.

En raison de la nature distribuée du problème, nous nous intéressons à une modélisation par agentd'une version simplifiée du programme FISIAS. Les éléments composant notre environnement (uni-vers) peuvent être les machines (et par extension les groupes de machines), les lots (et par extensionles groupes de lots), le diagramme de Gantt (attribut de l'univers) et enfin un agent distributeur de lot(ADL). Les machines peuvent être considérées comme des agents cognitifs dont le rôle est d'accom-plir les opérations d'un lot à un moment donné. Toutefois, les machines peuvent être vues comme desagents purement réactifs qui en fonction du lot qui arrivera répondront : "je peux le faire ou pas".

Ainsi, nous pouvons utiliser l'architecture de Contract Net définie par R. Smith dont le manager :l'ADL va proposer comme contrat le placement d'un lot sur une machine par l'intermédiaire d'un délé-gué à la négociation de ce lot (Agent Négociateur). En fonction des informations reçues par la ma-chine (ou le groupe de machines), l'AN va attribuer un contrat entre l'agent machine Mi et l'ADL. Maisl'ADL se réserve la possibilité de proposer un lot à plusieurs machines afin d'opérer une compétitionentre les agents machines mais l'ADL se réserve le droit de dénoncer ce contrat en cas de non respectpar l'agent machine. D'ou la première représentation correspondant à la Figure 32 .

Sous-Problème

Evaluation

Rien à faire

Sous solution

Evaluation

AnalyseDu

Contrat

Solution auSous-problème

Sous-solution

Proposition d’enchère

Résultat

Confirmation

Contrat

Application

Manager Noeuds


& 81

Figure 32 : Représentation de l'univers dans un paysage agent.

Dont voici une première représentation au niveau du Contract Net (cf. Figure 33). Une ma-chine peut accepter plusieurs contrat correspondant à un même lot mais négocié par plusieurs ANayant des stratégies différentes. Ainsi, la politique du contrat se résume à : "Que le plus fort gagne !"puisqu'un contrat à la possibilité d'être rompu de part et d'autre. Toutefois, comme agent, nous pou-vons proposer deux agents : un agent de placement en marche avant et un agent de placement en mar-che arrière. De plus, nous avons des spécificités au niveau de l'atelier puisque nous avons des machi-nes génériques, des groupes de machines et des machines spécifiques. Par conséquent, nous pouvonsconsidérer que nous avons des agents "groupe de machines" lesquels vont proposer le lot à traiter audifférentes machines de ce groupe. A ce niveau, nous pouvons opérer un calcul parallèle sur les ma-chines donc des plans de charge.

Figure 33 : Première représentation du Contract Net.

M1M4

M3M2

AgentDistributeur

de Lots Demande de contrat

Acceptation du contratou pas

DiagrammeDe

Gantt

Lots

ADL

ANiAN1 ANnAN2

M2M1

Création d'undélégué à lanégociationd'un lot

Propositionde contrat

Acceptationde contrat

Acceptationde la négo-ciation doncacceptationdu lot

Lots


& 82

Toutefois, pour le moment, nous considérons que l'ADL ne peut traiter qu'un lot à la fois. Or,un agent intermédiaire de choix du nombre de lot à traiter peut être proposé. D'où la nouvelle structurede Contract Net qu est présenté dans la Figure 34, où entre chaque agent, nous avons un système deContract Net.

Figure 34 : Structure de Contract Net entre les différents niveaux de représentation.

6. ConclusionLa vision distribuée d'un problème d'ordonnancement de type Job-Shop permet d'aboutir à une

vision plus réaliste puisque chaque agent dispose d'une vision de son environnement. C'est-à-dire queceux-ci son capable de réagir à un problème ponctuel tout comme un contremaître dans son atelier.Celui-ci va réagir immédiatement suite à la panne d'une machine. De même, il va prendre des déci-sions, comme les agents, qui vont avoir une répercussion sur l'environnement. Par conséquent, la mo-délisation par un système multi-agent utilisant un contract net est une vision proche de la réalité quipeut être facilement transcrite dans une organisation industrielle.

Liste deslots

Agentintermédiaire

Agent Négocia-teur du nombrede lots à traiter.

1, n lots pris

Agent AV Agent AR

Agent inter-médiaire de

classe demachine M

Agent inter-médiaire de

classe demachine M

M1 M2 M3 M1 M3

Plan de charge machineCalcul parallèle auniveau des machines

Possibilité depasser outre

l'agent négocia-teur du nombre

de lots

Limites del'univers


& 83

CONCLUSION

Après avoir présenté les différents problèmes d’ordonnancement dans la gestion de produc-tion et un certain nombre de méthodes de résolution, nous avons choisi d’appliquer les AlgorithmesGénétiques au problème du Job-Shop. La représentation de ce problème se fait à l’aide de fichierstextes décrivant la structure d’un atelier et celle des lots d’une façon proche de la réalité. Afin de pou-voir comparer les AG à d’autres méthodes plus ou moins aléatoires, nous avons créé une based’exemples à l’aide d’un générateur aléatoire et une interface graphique a été développée afin de per-mettre la visualisation de la répartition des opérations sur les machines de l’atelier après avoir réaliséun placement. Différentes méthodes de recherche d’optima ont été implémentées afin de pouvoircomparer et valider les résultats obtenus avec les AG. Parmi ces méthodes, celles du gradient et durecuit simulé donnent de meilleurs résultats que des méthodes totalement aléatoires ou heuristiques.

Basés sur un processus d’évolution naturelle, les Algorithmes Génétiques appartiennent auxtechniques d’optimisation se basant sur l’exploration aléatoire de l’espace des solutions et ils cher-chent l’optimum à partir d’une population de points et non à partir d’un seul point. L’algorithme debase des AG se décompose en 4 parties : la sélection, le croisement, la mutation et la reproduction.L’opérateur de crossover a une place importante et la mutation ne joue qu’un rôle secondaire par rap-port à ce dernier mais son influence sur l’exploration de l’espace des solutions n’est pas à négliger.

Parmi les représentations possibles du problème, nous avons choisi la représentation chemincar elle correspond à une représentation naturelle et les opérateurs qui y sont définis donnent lesmeilleurs résultats. De plus, le codage employé est en décimal et il diffère des codages classiques carchaque gène possède un signe caractérisant le sens de placement du lot correspondant. L’opérateur leplus performant qui a été trouvé après plusieurs tests est le crossover CX. Ces tests ont aussi permisde déterminer les autres paramètres pour obtenir des résultats intéressants. Finalement, nous avonsmontré que les algorithmes génétiques appliqués à l’ordonnancement sont efficaces car ils trouvent demeilleurs résultats et atteignent plus souvent l’optimum que les autres méthodes, même si les temps decalcul sont plus importants.

Les temps de calcul sur Origin2000 permettent un gain de temps important par rapport à unemachine même bi-processeurs. De ce fait, il est possible de générer un beaucoup plus grand nombresde tests afin de confirmer les premiers résultats déjà obtenus. Par rapport à une architecture standardde machine, il est possible de vérifier la validité des paramètres obtenus sur de "petits" exemples"pour les vérifier sur des exemples de taille importante. Par taille importante, nous entendons, pour lesproblèmes de placement, un ensemble de 200 à 500 lots avec 100 opérations en moyenne par lot àordonnancer sur un ensemble de 50 machines. Toutefois, en fonction de la taille des problèmes, ilnous faut adapter les différents paramètres pour les Algorithmes Génétiques.

La vision distribuée d'un problème d'ordonnancement de type Job-Shop permet d'aboutir à unevision plus réaliste puisque chaque agent dispose d'une vision de son environnement. C'est-à-dire queceux-ci son capable de réagir à un problème ponctuel tout comme un contremaître dans son atelier.Celui-ci va réagir immédiatement suite à la panne d'une machine. De même, il va prendre des déci-sions, comme les agents, qui vont avoir une répercussion sur l'environnement. Par conséquent, la mo-délisation par un système multi-agent utilisant un contract net est une vision proche de la réalité quipeut être facilement transcrite dans une organisation industrielle.


& 84

LEXIQUE

Allèle : Valeur prise par un gène dans un chromosome.

Atelier : Lieu de production dans une entreprise où sontsituées les machines. Un atelier se décompose en sec-tions, elles-mêmes décomposables en sous-sections.

Charge (d'un moyen de production) : Quantité d'unitésd'oeuvre correspondant à une demande, que l'on décidede réaliser sur un moyen de production déterminé(AFNOR).

Chromosome : chaîne de caractère composée de gènes.

Crossover : Opération consistant un prendre deux pa-rents et à les croiser entre eux autour de un ou plusieurspoint de coupures pour obtenir deux nouveaux chromo-somes.

Déblocage : Opération consistant à rendre sélectionnableun chromosome qui ne l’est pas.

Epistasie : Non linéarité en terme de position.

Fitness : Valeur moyenne du critère de sélection pour unchromosome.

Gamme : Une gamme représente l'énumération de lasuccession des opérations nécessaire à la réalisation d'unl'article. (AFNOR)

Gène : Constituant d’un chromosome, caractère compo-sant la chaîne.

Génotype : Ensemble du matériel génétique, c’est à direl’ensemble des chromosomes contenu dans une cellule ouune population.

Heuristique : Toute méthode permettant de guider lechoix d'une connaissance en se basant sur une évaluationdes résultats futurs de ce choix.

Job-shop : Type d'atelier dans lequel on doit fabriqueren même temps sur des machines différentes des produitsdifférents qui ont des gammes totalement définies etdifférentes selon les produits ou familles de produits. Lecheminement des produits dans l'atelier est spécifique à

chaque article et des produits différents en cours d'usi-nage devront vraisemblablement se croiser.

Locus : Position d’un gène sur un chromosome. La lec-ture du chromosome se fait de gauche à droite.

Lot : Pour un moyen de production ou un ensemble demoyens de production, c'est la quantité de pièces concer-nées par une même action ou un ensemble d'actions(opération ou transfert) entre deux événements interve-nant pour ce moyen de production (AFNOR). On parleaussi de job.

Moyen de production : Moyen élémentaire dont l'entre-prise dispose pour produire (AFNOR).

Mutation : Opération consistant à changer la valeur d’unbit dans un chromosome ou à changer le signe de lavaleur d’un lot dans un chromosome.

Opération : Action destinée à modifier les caractéristi-ques d'un article ou d'un en-cours, pour aboutir à unnouvel article ou un nouvel en-cours (AFNOR).

Ordonnancement : En production, ensemble des actionsqui permettent de répondre à la demande (spécifications,quantités, dates) exprimée en amont, en visant à utiliserau mieux les ressources dans le respect de la politiqueindustrielle définie (AFNOR). Il s'agit donc de répartir aumieux les lots (ou jobs) sur les machines de l'atelier.

Phénotype : L’interaction de l’ensemble du matérielgénétique avec son environnement.

Section : Division de base de l'atelier destinée à délimiterdes endroits où l'on fabrique un type ou une famille deproduits.

Sélection : Opération consistant à calculer le fitness dechaque chromosome afin de savoir son pouvoir à êtrecroiser et muter. En fonction de la valeur du fitness, lechromosome est sélectionnable ou non.

Sous-section : Séparation élémentaire de la section danslaquelle les machines peuvent réaliser le même typed'opérations.


& 85

Référence AG

[ADLER 19936] ADLER D. , Genetic Algorithms and Simulated Annealing: A MarriageProposal, IEEE International Conference on Neural Networks, March 28-April 1 1993,pp1104-1109.[AFNOR 1988] AFNOR, Concepts fondamentaux de la gestion de production, Agencefrançaise de normalisation, document X50-310, 1988.[BENSANA 1987] BENSANA E., Utilisation des techniques d’intelligence artificielle pourl’ordonnancement d’atelier, Thèse de l’ENSAE, Toulouse 1987.[BUXEY 1992] BUXEY G. , Production scheduling : Practice and theory, 1989[BOUKACHOUR 1992] BOUKACHOUR Jaouad , Ordonnancement d’atelier par simu-lation une approche orientée objet, Thèse Rouen, 13 Mai 1992.[CANALS 1986] CANALS D. ,Ordonnancement d’atelier par simulation : étude des règlesde priorité et aide au lancement, Thèse ENSAE, Toulouse 1986.[CARLIER et CHRETIENNE 1987] CARLIER et CHRETIENNE, Problèmesd’ordonnancement, Masson, 1987.[DAVIS 1985] L. DAVIS, Applying Adaptive Algorithms to Epistatic Domains, Proceedingof the International Joint Conference on Artificial Intelligence, pp. 162-164, 1985.[DEJONG] DEJONG K.A. , Using Genetic Algorithms to solve NP-Complete Problems,Spears, pp124-132.[DINCBAS 1988] DINCBAS M., The constarint logic programming language CHIPECRC, FGCS, ICOT, Tokyo.[FOX 1983] FOX M.S., Constraint directed search : a case study of job-shop scheduling,ISIS, Technical report Carnegie Mellon University, 1983.[FRANTZ 1972] D.R. FRANTZ, Non linearities in genetic adaptive search, Doctoral dis-sertation, University of Michigan, Dissertation Abstarcts International, No.73-11,116, 1972.[GALINHO 1994] GALINHO T. , Algorithme heuristique de placement pour l'ordonnan-cement, Université de Rouen, juillet 1994.[GOLBERG 1991] GOLBERG D.E. , Algorithmes génétiques, Addison-Wesley, 1991, pp1-24, p 189, p223.[GOLDBERG 1985] David E. GOLDBERG, Optimal initial population size for binary-coded genetic algorithms TCGA Report No. 85001, Tuscaloosa :University of Alabama TheClearinghouse for Genetic Algorithms, 1985.[GOLDBERG 1989] David E. GOLDBERG, Genetic Algorithms in Search, optimisationand machine learning, Addison-Wesley, 1989.[GOLDBERG 1994] David E. GOLDBERG, Algorithmes génétiques, Exploration, optimi-sation et apprentissage automatique, Addison-Wesley, 1994.[GOLDBERG & LINGLE 1985] David E. GOLDBERG & R. LINGLE, Alleles, Loci, andthe TSP, Proceedings of the Fist International Conference on Genetic Algorithms, Lawrenceerlbaum Associates, Hilsdale, NJ, pp 154-159, 1985.[HOFSTADTER 1979] D.R. HOPSTADTER, Godel, escher, Bach : An Eternal goldenbraid, New York Basic Books, 1979.[HOLLAND 1976] HOLLAND J.H. , Progress in Theoretical Biology, 1976, pp 263-293.[HOLLAND 1975] J.H. HOLLAND, Adaptation in natural and artifical systems, Univer-sity of Michigan Press, 1975.[HOLLAND 1981] HOLLAND J.H. , Genetic algorithms and adaptation (Technical Re-port N°34), University of Michigan, Departement of computer and communication sciences,1981


& 86

[HOLLAND 1973] HOLLAND J.H. , Genetic algorithms and the optimal allocations oftrials, SIAM Journal of computing, 1973, 2(2) pp 88-105.[KERR 1992] KERR R.M., Expert Systems in Production Scheduling : Lessons from aFailed Implementation, Journal of Systems and Software, 1992, Vol. 19, N° 2.[KOZA 1992] John R. KOZA, Genetic Programming, The MIT Press, pp. 28-29, 1992.[KUSIAK 1988] KUSIAK A. and CHEN M., Expert Systems for Planning and SchedulingManufacturing Systems, European Journal of Operational Research, 1988, Vol. 34, N° 2, pp.113-130.[LE PAPE 1985] LE PAPE C. and SAUVE B. , SOJA : Un Système d'Ordonnancementjournalier d'atelier, Cinquièmes Journées Internationales d'Avignon, 1985, pp. 849-867.[MENG 1993] MENG Q. , Application des Algorithmes Génétiques à la résolution de pro-blèmes et à la commande de systèmes, Thèse université Paris XII, 13 Octobre 1993, pp 5-17.[MICHALEWICZ 1994] MICHALEWICZ Z. , Genetic Algorithms + Data Structures =Evolution Programs, Springer-Verlag, 1994, pp 13-54, pp 211-237.[MUHLENBEIN] Heinz MUHLENBEIN, Evolutionary Algorithms : Theory and Applica-tions, GMD Schloss Birlinghoven.[OLIVER, SMITH, HOLLAND 1987] I.M. OLIVER, D.J. SMITH, J.H. HOLLAND , Astudy of Permutation Crossover Operators on the Traveling salesman Problem, Proceedingof the Second International Conference on Genetic Algorithms, Lawrence Erlbaum Asso-ciates, Hilsdale,pp.224-230.,1987.[PANWALKER 1977] PANWALKER S.S. and ISKANDER W. , A Survey of ScedulingRule, Operation Research, Vol. 25, N°1, January-February 1977.[ROY 1970] ROY B. , Algèbre moderne et théorie des graphes, Dunod, Tome 2 1970.[SUH et GUCHT 1987] SUH J-Y. et GUCHT Van D. , Incorporating Heuristic Informa-tion into Genetic Search, Proceeding of the Second International Conference on Genetic Al-gorithms, Lawrence Erlbaum Associates, Hilsdale,pp.100-107.,1987.[ZOONEKYND 1994] Vincent ZOONEKYND, Recuit simulé et autres méthodesd’optimisation, Ecole Nationale Supérieure de Cachan, 1994.


& 87

Référence SMA [1] H. S. Becker, "Notes of the Concept of Commitment", American Journal of Sociology 66, pages

32-40' July 1960.[2] H. Bond et L. Gasser, "An analysis of problems and Research in DAI", chapitre 1, Morgan

Kaufmann, California, 1988.[3] T. Bouron. "Structure de Communication et d'Organisation pour la Coopération dans un Uni-

vers Multi-agents: Une contribution à la définition d'un modèle de programmation agent basésur les concepts d'engagement et d'acte de langage". PhD thesis, Université Pierre et Marie Cu-rie (Paris VI), Novembre 1992.

[4] J. F. Allen. "Towards a General Theory of Action and Time", Artificial Intelligence 2S, pages123-154 1984.

[5] H. Bond et L. Gasser, "Readings in Distributed Artificial Intelligence", Morgan Kaufmann,California, 1988.

[6] T. Bouron, "Conception d'agents sociaux et évaluation de leurs performances". In Actes des3emes journces "Symbolique-numérique", mai 1992.

[7] S. Cammarata, D. McArthur, et R. Steeb, "Strategies of Cooperation in Distributed ProblemSolving". In Karlsruhe, editor, Proccedings of the 8th Internatinal Joint Conference on Artifi-cial Intelligence, volume 2, pages 767-770, Germany, August 1983.

[8] R. Davis et R. G. Smith. "Negotiation as a Metaphor for Distributod Problem Solving." Artifi-cial Intelligence, 20:63-109, 1983.

[9] E. H. Durfee, V. R. Gasser et D. D. Corkill, "Coherent cooperation among communicating pro-blem solvers", IEEE Transactions on computer C-36, pages 1275-1291, 1987.

[10] J. Erceau et J. Ferber. "L'intelligence artificielle distribuée". La Recherche, 22:750-758, juin1991.

[11] J. Ferber. "The Framework of Eco-Problem Solving". In Proccedings of the 2nd EuropeanWor1;shop MAAMAW'90, pages 103-114, Saint-Quentin en Yvelines-France, August 1990.

[12] J. Ferber et M. Ghallab, "Problèmatiques des univers multi-agents intelligents", Actes des jour-nées nationales PRC-GRECO Intelligence Artificielle, pages 295-320, Toulouse, Mars 1988.

[13] M. N. Huhns, "Distributed Artificial Intelligence", Pitman Publishing, Morgan Kaufmann,1987.

[14] W. Kornfeld et C. Hewitt, "The scientific community metaphor", IEEE Transactions on Sys-tems, Man and Cybernitics Conference, SMC-11(1), 1981.

[15] R. G. Smith, "The contract net protocol: high level communication and control in a distributedproblem solver", pages 357-366, Morgan Kaufmann, California, 1988.

[16] A. Vailly and M-A. Simon, "Des systèmes experts coopérants, pourquoi, comment?", In Coyni-tiva 87 AFCET, pages 183-188, Paris, 1987.


& 88

Annexe 1 : Interface graphique.


& 89

Annexe 2 : Liste des publications.

• VACHER Jean-Philippe, GALINHO Thierry, MAMMERI Zoubir, Une ap-plication des algorithmes génétiques à l’ordonnancement d’atelier, Procee-ding de la conférence MOSIM’97 à Mont-Saint-Aignan, 5-6 Juin 1997, Ed.Hermes.

• VACHER Jean-Philippe, CARDON Alain, GALINHO Thierry, Genetic Al-gorithms on Multi-Agents Systems, Proceeding de la conférence EURO-GEN’97, Trieste, Italie, 28-5 Décembre 1997.

• VACHER Jean-Philippe, CARDON Alain, GALINHO Thierry, HeuristicsGranularity in a Multi-Agents Systems (MAS) : Application to the Produc-tion Management, Article accepté à la conférence YOR10 à Guildford (UK),mars 1998.

• VACHER Jean-Philippe, CARDON Alain, LESAGE Franck, GALINHOThierry, Genetic Algorithms in a Multi-Agent System, IEEE InternationalJoint Symposium on Intelligence and Systems, Whashington, 21-23 Mai1998

• VACHER Jean-Philippe, CARDON Alain, GALINHO Thierry, InformationSystems for Management in Job-Shop Scheduling Problems using a Multi-Objective Genetic Algorithm, NIMES’98, Complex Systems, IntelligentSystems & Interfaces, 26-28 Mai 1998

• VACHER Jean-Philippe, CARDON Alain, GALINHO Thierry, InformationSystem for Management : Random generators for Job-Shop SchedulingProblems, The Seventh International Conference Information Systems De-velopment ISD’98, Bled, Slovenia, 21-23 September 1998.

• VACHER Jean-Philippe, CARDON Alain, GALINHO Thierry, AlgorithmesGénétiques Multi-Objectif en Ordonnancement de Production de type Job-Shop, FRANCORO II, Sousse, Tunisie, 6-8 Avril 1998

• VACHER Jean-Philippe, CARDON Alain, GALINHO Thierry, Genetic Al-gorithm using Multi-Objective in a Multi-Agent System, The 2nd Internatio-nal Symposium On Intelligent Manaufacturing Systems IMS’98, 6-7 August1998

• VACHER Jean-Philippe, CARDON Alain, GALINHO Thierry, Macropha-gic Agents in Multi-Agent Systems to Resolve Job-Shop Scheduling Pro-blem, The 32nd Hawaii International Conference on System Sciences HICSS-32, Maui, Hawaii, January 5-8, 1999. (accepté en première lecture)

Documents

Algorithmes Génétiques dans un Système Multi-Agents pour l