Génération automatique de l'emploi du temps en utilisant des algorithmes génétiques

Abstract

L'élaboration d'un emploi du temps, une tâche 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. Le probléme de l'emploi du temps est classé sous catégorie des problèmes métaheuristiques qui sont généralement des algorithmes stochastiques itératifs visant à résoudre des problèmes d’optimisation difficiles, pour lesquels on ne connaît pas de méthode classique plus efficace. Les algorithmes génétiques appartiennent à la famille des algorithmes évolutionnistes. Leur but est d'obtenir une solution approchée à un problème d'optimisation, lorsqu'il n'existe pas de méthode exacte (ou que la solution est inconnue) pour le résoudre en un temps raisonnable.***

The development of a schedule, a habitual, complicated and cumbersome task in a company or in an establishment, is a NP-difficult problem; in this research, we propose an approach based on genetic algorithms to automate it. The tasks are methodically placed in a time grid. The time use problem is sub-categorized as metaheuristic problems which are generally iterative stochastic algorithms aimed at solving difficult optimization problems for which no more efficient classical method is known. Genetic algorithms belong to the family of evolutionary algorithms. Their goal is to obtain an approximate solution to an optimization problem, when there is no exact method (or the solution is unknown) to solve it in a reasonable time.