Arnaud Thiry Julien Mellano



Yüklə 445 b.
tarix26.07.2018
ölçüsü445 b.
#58618


  • 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

  • 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


Yüklə 445 b.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©muhaz.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin