• Langue : Anglais
• Discipline : Informatique et applications
• Identifiant : 2023ULILB040
• Type de thèse : Doctorat
• Date de soutenance : 12/12/2023

Résumé en langue originale

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é.

Résumé traduit

This thesis focuses on the Curriculum-Based Course Timetabling (CB-CTT) problem, a university timetabling problem belonging to the scheduling problems. The CB-CTT is therefore an Operational Research problem, and more specifically a combinatorial optimization problem. Metaheuristics are solving methods that offer good performance in a reasonable time. Metaheuristics are used for their genericity, which allows them to be adapted and applied to a large number of optimization problems. First, we analyze the fitness landscape of the CB-CTT to characterize the instances of the literature. Several indicators are then used to build a model for predicting the performance of solution algorithms such as metaheuristics. In addition, we propose a generalization of the state-of-the-art method called Iterated Sequential Local Search (ISLS) for solving CB-CTT, which allows the design of new versions of the original method and outperforms it. Performance prediction and automatic configuration require numerous training instances. We therefore also propose a statistical analysis of the instances and define an artificial intelligence model that selects the most suitable instances in terms of feasibility.