Accueil > Documentations scientifiques > Revues récentes > Mada-ETI > Archives > Volume 2, 2019 > Application des algorithmes génétiques sur un planning sous contraintes

• 
  Application des algorithmes génétiques sur un planning sous contraintes
  Madaeti, 2019, vol 2, page 77-90

  Auteurs : Rakotomahefa A., Randimbindrainibe F., Robinson M.

  Mots clés : Sciences cognitives, Intelligence Artificielle, Planification, Algorithmes Génétiques.
  
  

  FR :
  L’élaboration d’un planning, une tache habituelle, compliquée et lourde, dans une entreprise ou dans un établissement, est un problème NP difficile ; dans cette recherche, nous proposons une approche basée sur les algorithmes génétiques pour l’automatiser. Les tâches sont placées méthodiquement dans une grille de temps ; tout en respectant les contraintes liées aux agents : leurs disponibilités aussi bien que leurs nombres d’heures de travail, et les contraintes liées aux temps : les jours ouvrables et le nombre d’heures de travail dans une journée. De générations en générations, les algorithmes génétiques approchent progressivement les solutions optimales. Nous avons pu montrer que ces solutions seront atteintes après quelques centaines de générations et que le temps d’exécution du modèle proposé est raisonnable car sa complexité algorithmique est polynomiale.

  EN :
  Scheduling, a habitual, complicated and heavy task for an organization and for a company is a NP-hard problem ; in this research, we propose an approach based on genetic algorithms to automate it. All tasks are methodically placed in a time grid, while respecting the constraints related to agents : their availability as well as their working hour’s number, and the time constraints : the working days, the number of working’s hours a day. From generation to generation, genetic algorithms approach gradually the optimal solutions. We have shown that these solutions will be reached after hundreds of generations, and the execution time of the proposed model is reasonable because its computational complexity is polynomial.

  Télécharger