Arnaud Thiry Julien Mellano

• Arnaud Thiry

• Julien Mellano

• INSA de Rouen - GM4

SOMMAIRE

• Présentation générale

• Le problème d’ordonnancement
• Le job shop
• Les algorithmes génétiques

• Applications à des problèmes de taille 6*6

• Description de l’algorithme programmé
• Résultats obtenus
• Interprétation des résultats

• Conclusion

Présentation du problème d’ordonnancement

• Présentation générale

• Le problème d’ordonnancement
• Le job shop
• Les algorithmes génétiques

• Applications à des problèmes de taille 6*6

• Description de l’algorithme programmé
• Résultats obtenus
• Interprétation des résultats

• Conclusion

Présentation du job shop

• Présentation générale

• Le problème d’ordonnancement
• Le job shop
• Les algorithmes génétiques

• Applications à des problèmes de taille 6*6

• Description de l’algorithme programmé
• Résultats obtenus
• Interprétation des résultats

• Conclusion

Présentation des algorithmes génétiques

• Basés sur le principe d’évolution d’une population d’individus.

• Les plus forts survivent et engendrent des progénitures.

• Sur ce schéma,

• on crée une population de solutions admissibles
• On élimine une partie des solutions les plus mauvaises puis on recombine les gènes afin d’obtenir une nouvelle population de solutions.
• Chaque génération, on crée un nouvel ensemble de solution à partir des meilleurs éléments des populations antérieures.

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

Algorithme Génétique : principes de base

Application à des problèmes de tailles 6*6

Contraintes et objectifs

• Les machines ne sont pas identiques

• Les opérations d’un même job s’exécutent séparément sur les machines en respectant l’ordre des séquences

• Préemption non permise

• Toutes les données du job shop sont connues d’avance

• Disponibilité infinie

• Problème de job shop classique dit « carré »

Description de l’algorithme programmé

• Le codage du chromosome

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

• La génération de la population initiale

• La mutation

• Le croisement

• L’évaluation

• La réparation

• L’amélioration

• La sélection

• Le mode Pareto

Le codage du chromosome

Codage à partir d’un problème donné

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

Génération de la population initiale

• Principe d’obtention des 100 premiers chromosomes :

• On prend le premier chromosome appelé « chromosome père »
• On intervertit les colonnes = numéro de job

La Mutation

• Pour chaque case i :

• Tirage d’un nombre aléatoire a
• Si a Є [0;pourcentage mutation]
• Tirage d’un deuxième nombre aléatoire p Є [1;6] et échange des cellule i et p.

Le Croisement

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

• Le plus performant :

• Croisement d’ordre maximal (2 points de coupure)

Le Croisement

L’Evaluation (la méthode Gantt)

• Méthode principale du programme

• Plusieurs utilités :

• définit si le chromosome est valide ou non
• Identifie les opérations bloquantes
• Identifie les périodes d’inactivités des machines
• Attribut au chromosome son C_max, son flot total et son flot moyen.

La Réparation

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

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

L’Amélioration

• But de la procédure :

• Améliorer le chromosome :
• ordonnancement semi-actif
• ordonnancement sans retard

La Sélection

• 2 modes de sélection possibles :

• Le mode « super héros » ou appelé sélection par classement
• Le mode de sélection par roulette

Le mode PARETO

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

• Chromosome dominant ssi :

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

Résultats obtenus

• En mode sélection par classement :

• Meilleurs chromosomes :
• C MAX = 55
• Flot total = 284
• Seul chromosome obtenu en PARETO.
• Obtenu avec 200 itérations en 15s

• En mode sélection par roulette

• Meilleurs chromosomes :
• C MAX = 58
• Flot total = 300
• Plus long
• Plus il y a d’itération, plus on diverge de la solution

Interprétation des résultats

• Sélection par roulette

• Résultats pas satisfaisants
• Poids mal affectés?

• Sélection par classement

• Résultat optimal obtenu
• 1 seul chromosome dominant
• C_max et Flot total très corrélés(?)
• Convergence prématurée(?)

Conclusion

• Projet très intéressant

• Découverte d’une nouvelle méthode d’optimisation par les algorithmes génétiques
• Sensibilisation au problème concret d’ordonnancement du job shop

• Un regret

• Manque de temps pour l’adapter l’algorithme à d’autres problèmes du même type