Analyse du paysage et reconfiguration d’algorithmes pour le problème CB-CTT d’emploi du temps universitaire

Abstract

Dans cette thèse, nous nous intéressons au problème du Curriculum-Based Course Timetabling (CB-CTT), un problème d'emploi du temps universitaire appartenant à la famille des problèmes d'ordonnancement. Le CB-CTT est donc un problème de recherche opérationnelle et plus précisément d'optimisation combinatoire. Les métaheuristiques sont des méthodes de résolution qui offrent de bonnes performances dans un délai raisonnable. Les métaheuristiques sont utilisées pour leur généricité qui leur permet de s'adapter et d'être appliquées sur un grand nombre de problèmes d'optimisation. Tout d'abord, nous analysons le paysage de recherche du CB-CTT pour caractériser les instances de la littérature. Différents indicateurs sont ensuite utilisés pour construire un modèle permettant de prédire la performance des algorithmes de résolution comme les métaheuristiques. De plus, nous proposons une généralisation de la méthode plébiscitée par la littérature pour résoudre le CB-CTT sous forme d'une recherche locale séquentielle itérée (ISLS : Iterated Sequential Local Search) qui permet la conception de nouvelles versions de la méthode originelle et qui surpasse ses performances. La prédiction de performance et la configuration automatique nécessitent de nombreuses instances d'entrainement. Ainsi, nous proposons également une analyse statistique des instances et définissons un modèle d'intelligence artificielle qui sélectionne les instances les plus adaptées en terme de faisabilité.