Arnaud Thiry Julien Mellano INSA de Rouen - GM4 Projet proposé par M. Youssef HARRATH

Arnaud ThiryArnaud Thiry

Julien MellanoJulien Mellano

INSA de Rouen - GM4INSA de Rouen - GM4

Projet proposé par M. Youssef HARRATH

SOMMAIRESOMMAIRE

Présentation généralePrésentation générale– Le problème d’ordonnancementLe problème d’ordonnancement– Le job shopLe job shop– Les algorithmes génétiquesLes algorithmes génétiques

Applications à des problèmes de taille 6*6Applications à des problèmes de taille 6*6– Description de l’algorithme programméDescription de l’algorithme programmé– Résultats obtenusRésultats obtenus– Interprétation des résultatsInterprétation des résultats

ConclusionConclusion

Présentation du problème Présentation du problème d’ordonnancementd’ordonnancement

Présentation généralePrésentation générale– Le problème Le problème

d’ordonnancementd’ordonnancement– Le job shopLe job shop– Les algorithmes Les algorithmes

génétiquesgénétiques Applications à des Applications à des

problèmes de taille 6*6problèmes de taille 6*6– Description de Description de

l’algorithme programmél’algorithme programmé– Résultats obtenusRésultats obtenus– Interprétation des Interprétation des

résultatsrésultats ConclusionConclusion

Un ordonnancement décrit Un ordonnancement décrit l’ordre d’exécution des tâches l’ordre d’exécution des tâches et l’allocation des ressources et l’allocation des ressources au cours du temps, afin de au cours du temps, afin de satisfaire un ou plusieurs satisfaire un ou plusieurs critères d’optimisationcritères d’optimisation..

Nos critères sont : Nos critères sont : – Le C_Max : date de Le C_Max : date de

l’achèvement de l’achèvement de l’ordonnancementl’ordonnancement

– Le flot total : somme des temps Le flot total : somme des temps passé sur les machines.passé sur les machines.

Présentation du job shopPrésentation du job shop Présentation généralePrésentation générale

– Le problème Le problème d’ordonnancementd’ordonnancement

– Le job shopLe job shop– Les algorithmes Les algorithmes





Le job shop est associé à des lignes Le job shop est associé à des lignes de production dédiées à la de production dédiées à la production de moyennes et de production de moyennes et de petites séries où les changements petites séries où les changements de produits sont fréquents de produits sont fréquents

Chaque tâche possède son propre Chaque tâche possède son propre mode de passage sur les machines.mode de passage sur les machines.

Présentation des algorithmes Présentation des algorithmes génétiquesgénétiques Basés sur le principe d’évolution d’une Basés sur le principe d’évolution d’une

population d’individus. population d’individus. Les plus forts survivent et engendrent des Les plus forts survivent et engendrent des

progénitures. progénitures. Sur ce schéma,Sur ce schéma,

– on crée une on crée une population de solutions population de solutions admissiblesadmissibles

– On élimine une partie des solutions les plus On élimine une partie des solutions les plus mauvaises puis on recombine les gènes afin mauvaises puis on recombine les gènes afin d’obtenir une nouvelle population de d’obtenir une nouvelle population de solutions.solutions.

– Chaque génération, on crée un nouvel Chaque génération, on crée un nouvel ensemble de solution à partir des meilleurs ensemble de solution à partir des meilleurs éléments des populations antérieures. éléments des populations antérieures.

Un intérêt supplémentaire des algorithmes Un intérêt supplémentaire des algorithmes génétiques est qu’ils permettent génétiques est qu’ils permettent l’optimisation multicritère.l’optimisation multicritère.



génétiques multicritèresgénétiques multicritères Applications à des Applications à des




Algorithme Génétique : principes Algorithme Génétique : principes de basede base

POPULATION(Chromosomes)

POPULATION(Chromosomes)

EVALUATION(fitness)

EVALUATION(fitness)

OPERATEURSGENETIQUES

OPERATEURSGENETIQUES

Manipulation

Nouvelle génération

SELECTION(groupement)

SELECTION(groupement)

Parents

Reproduction





l’algorithme programmél’algorithme programmé– Résultats obtenusRésultats obtenus– interprétation des interprétation des


Application à des problèmes de Application à des problèmes de tailles 6*6tailles 6*6







JobsJobs Opérations(Mi,Ti)Opérations(Mi,Ti)

11 3,13,1 1,31,3 2,62,6 4,74,7 6,36,3 5,65,6

22 2,82,8 3,53,5 5,105,10 6,106,10 1,101,10 4,44,4

33 3,53,5 4,44,4 6,86,8 1,91,9 2,12,1 5,75,7

44 2,52,5 1,51,5 3,53,5 4,34,3 5,85,8 6,96,9

55 3,93,9 2,32,3 5,55,5 6,46,4 1,31,3 4,14,1

66 2,32,3 4,34,3 6,96,9 1,101,10 5,45,4 3,13,1

Contraintes et objectifsContraintes et objectifs

Les machines ne sont pas identiquesLes machines ne sont pas identiques Les opérations d’un même job s’exécutent Les opérations d’un même job s’exécutent

séparément sur les machines en respectant l’ordre séparément sur les machines en respectant l’ordre des séquencesdes séquences

Préemption non permisePréemption non permise Toutes les données du job shop sont connues Toutes les données du job shop sont connues

d’avanced’avance Disponibilité infinieDisponibilité infinie Problème de job shop classique dit « carré »Problème de job shop classique dit « carré »

Description de l’algorithme Description de l’algorithme programméprogrammé Le codage du chromosomeLe codage du chromosome

– A partir d’un problème donnéA partir d’un problème donné– Générer aléatoirementGénérer aléatoirement

La génération de la population initialeLa génération de la population initiale La mutationLa mutation Le croisementLe croisement L’évaluationL’évaluation La réparationLa réparation L’améliorationL’amélioration La sélectionLa sélection Le mode ParetoLe mode Pareto







On rentre une matrice job

Ou on génère la matrice

Mutation

Codage du premier chromosome

Génération de la première population

Croisement

Sélection (nouvelle population)

Affichage des chromosome dominant issue des itérations

Gantt & évaluation

Améliorer & réparer

Pareto

Le codage du chromosomeLe codage du chromosome

Le codage du Le codage du chromosomechromosome– A partir d’un problème A partir d’un problème

donnédonné– Générer aléatoirementGénérer aléatoirement

La génération de la La génération de la population initialepopulation initiale

La mutationLa mutation Le croisementLe croisement L’évaluationL’évaluation La réparationLa réparation L’améliorationL’amélioration La sélectionLa sélection Le mode ParetoLe mode Pareto

Choix du type de problème

•Problème proposé

•Problème aléatoire

Codage à partir d’un problème Codage à partir d’un problème donnédonné





Affichage des opérations :

•Le numéro de la machine

•Le temps de l’opération

Codage à partir d’un problème Codage à partir d’un problème générer aléatoirementgénérer aléatoirement





Génération de la population initialeGénération de la population initiale

Principe d’obtention des Principe d’obtention des 100 premiers 100 premiers chromosomes :chromosomes :– On prend le premier On prend le premier

chromosome appelé chromosome appelé «« chromosome père chromosome père »»

– On intervertit les On intervertit les colonnes = numéro colonnes = numéro de jobde job





La MutationLa Mutation





11 22 33 44 55 66

22 11 33 44 66 55

33 44 55 66 11 22

22 11 33 55 44 66

33 11 66 55 22 44

44 55 11 22 33 66

11 22 55 44 33 66

22 11 33 44 66 55

33 66 55 44 11 22

22 55 33 11 44 66

33 11 66 55 22 44

66 55 11 22 33 44

Pour chaque case i :Pour chaque case i :– Tirage d’un nombre aléatoire aTirage d’un nombre aléatoire a

Si a Si a ЄЄ [0;pourcentage mutation] [0;pourcentage mutation]– Tirage d’un deuxième nombre Tirage d’un deuxième nombre

aléatoire p aléatoire p ЄЄ [1;6] et échange [1;6] et échange des cellule i et p.des cellule i et p.

Le CroisementLe Croisement

Plusieurs croisements Plusieurs croisements possibles avec les possibles avec les algorithmes algorithmes génétiques.génétiques.

Le plus performant :Le plus performant :– Croisement d’ordre Croisement d’ordre

maximal (2 points de maximal (2 points de coupure)coupure)





Le CroisementLe Croisement

11 22 33 44 55 66

22 11 33 44 66 55

33 44 55 66 11 22

22 11 33 55 44 66

33 11 66 55 22 44

44 55 11 22 33 66

22 55 33 44 11 66

33 55 66 44 11 22

66 44 55 11 33 22

22 55 66 44 11 33

33 22 66 44 55 11

44 55 66 11 22 33

22 55 33 44 11 66

33 55 66 44 11 22

66 44 55 11 33 22

22 66 33 55 44 11

33 22 66 55 11 44

44 55 11 22 66 66

11 22 33 44 55 66

22 11 33 44 66 55

33 44 55 66 11 22

22 11 66 44 33 55

33 66 55 22 44 11

44 55 66 11 22 33

Chromosome Fils1

Chromosome Fils2

Chromosome Père Chromosome

Mère

Point de croisement 1




L’Evaluation (la méthode Gantt)L’Evaluation (la méthode Gantt)

Méthode principale du Méthode principale du programmeprogramme

Plusieurs utilités :Plusieurs utilités :– définit si le chromosome est définit si le chromosome est

valide ou nonvalide ou non– Identifie les opérations Identifie les opérations

bloquantesbloquantes– Identifie les périodes d’inactivités Identifie les périodes d’inactivités

des machinesdes machines– Attribut au chromosome son Attribut au chromosome son

C_max, son flot total et son flot C_max, son flot total et son flot moyen.moyen.





La RéparationLa Réparation

Procédure qui a pour but de Procédure qui a pour but de débloquer une tache.débloquer une tache.

Si deux taches sont bloquantes, Si deux taches sont bloquantes, on choisira celle avec le numéro on choisira celle avec le numéro de tache le plus faible.de tache le plus faible.





1,11,1 2,22,2 33 44 55 66

2,32,3 1,41,4 33 44 66 55

3,23,2 4,14,1 55 66 1,21,2 22

2,42,4 1,41,4 33 55 44 66

3,53,5 1,61,6 66 55 22 44

4,24,2 55 11 22 33 66

Cas où çà bloque

1,11,1 2,22,2 33 44 55 66

2,32,3 1,41,4 33 44 66 55

4,14,1 3,23,2 55 66 1,21,2 22

2,42,4 1,41,4 33 55 44 66

3,53,5 1,61,6 66 55 22 44

4,24,2 55 11 22 33 66

Une fois réparer

L’AméliorationL’Amélioration

But de la procédure :But de la procédure :– Améliorer le chromosome :Améliorer le chromosome :

ordonnancement semi-actifordonnancement semi-actif

ordonnancement sans retardordonnancement sans retard





Machines

Temps

1

2

4

3

5

6

1.1

1.3

6.1

2.4

2.3

3.1 5.2

2.1 1.2 6.6

2.2

5.1

3.2 4.1 2.66.2

6.3

6.4

6.5

1.4

1.5

1.6

2.5

3.3

3.4

3.5

3.6

4.2

4.3

4.4

4.5

4.6

5.3

5.4

5.5

5.6

L’AméliorationL’Amélioration

La SélectionLa Sélection 2 modes de sélection 2 modes de sélection

possibles :possibles :– Le mode Le mode « super héros » « super héros » ou ou

appelé sélection par classement appelé sélection par classement – Le mode de sélection par Le mode de sélection par

rouletteroulette





Le mode PARETOLe mode PARETO

Compare les chromosomes Compare les chromosomes obtenus après nos itérationsobtenus après nos itérations

Chromosome dominant ssi :Chromosome dominant ssi : C_Max 1 > C_Max 2C_Max 1 > C_Max 2 Flot total 1 Flot total 1 ≥ Flot total 2≥ Flot total 2

Ou si Ou si C_Max 1 C_Max 1 ≥≥ C_Max 2 C_Max 2 Flot total 1 > Flot total 1 > Flot total 2Flot total 2





Résultats obtenusRésultats obtenus En mode sélection par classement :En mode sélection par classement :

– Meilleurs chromosomes : Meilleurs chromosomes : C MAX = 55C MAX = 55 Flot total = 284Flot total = 284

– Seul chromosome obtenu en PARETO.Seul chromosome obtenu en PARETO.– Obtenu avec 200 itérations en 15sObtenu avec 200 itérations en 15s

En mode sélection par rouletteEn mode sélection par roulette– Meilleurs chromosomes : Meilleurs chromosomes :

C MAX = 58C MAX = 58 Flot total = 300Flot total = 300

– Plus longPlus long– Plus il y a d’itération, plus on diverge de la Plus il y a d’itération, plus on diverge de la

solutionsolution







Interprétation des résultatsInterprétation des résultats

Sélection par rouletteSélection par roulette– Résultats pas satisfaisantsRésultats pas satisfaisants– Poids mal affectés?Poids mal affectés?

Sélection par classementSélection par classement– Résultat optimal obtenuRésultat optimal obtenu– 1 seul chromosome dominant1 seul chromosome dominant

C_max et Flot total très corrélés(?)C_max et Flot total très corrélés(?) Convergence prématurée(?)Convergence prématurée(?)







ConclusionConclusion

Projet très intéressantProjet très intéressant– Découverte d’une nouvelle méthode Découverte d’une nouvelle méthode

d’optimisation par les algorithmes génétiquesd’optimisation par les algorithmes génétiques– Sensibilisation au problème concret Sensibilisation au problème concret

d’ordonnancement du job shopd’ordonnancement du job shop

Un regret Un regret – Manque de temps pour l’adapter l’algorithme à Manque de temps pour l’adapter l’algorithme à

d’autres problèmes du même typed’autres problèmes du même type

Documents

Arnaud Thiry Julien Mellano INSA de Rouen - GM4 Projet proposé par M. Youssef HARRATH