Approche Métaheuristique Pour La Résolution Du problème D’emploi Du Temps

Abstract

Le projet de fin d'études qui nous a été proposé par l'école technique de Blida avait pour objectif de fournir un emploi du temps optimal respectant le maximum de contraintes définies par l'organisme d'accueil. Pour ce faire, une modélisation mathématique a été effectuée, ciblant une fonction objectif qui minimise les pénalités associées aux contraintes violées. Deux approches algorithmiques ont été élaborées : une méthode exacte (Branch and Bound) et une méthode métaheuristique basée sur l'optimisation par essaims particulaires (PSO).

Les programmes ont été implémentés en Python, offrant une flexibilité et une efficacité dans le développement et l'exécution des algorithmes. La méthode exacte a donné un résultat optimal en satisfaisant toutes les contraintes, mais uniquement pour des problèmes de petite taille en raison d'un temps d'exécution très long. En revanche, l'approche PSO a fourni des résultats très satisfaisants en prenant en compte un maximum de contraintes et dans des temps relativement courts pour des tailles de données importantes. Mots-Clés : Optimisation par essaims particulaires (PSO), Méthode exacte, Algorithme de Branch and Bound, La fonction de Pénalités, Modélisation mathématique, Python