Modeling and solving university timetabling / Taha Arbaoui ; sous la direction de Jean-Paul Boufflet et de Aziz Moukrim

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : anglais / English

Emploi du temps (éducation) -- Modèles mathématiques

Résolution de problème -- Informatique

Planification -- Informatique

Heuristique

Programmation heuristique

Métaheuristiques

Programmation en nombres entiers

Programmation par contraintes

Boufflet, Jean-Paul (19..-....) (Directeur de thèse / thesis advisor)

Moukrim, Aziz (1964-....) (Directeur de thèse / thesis advisor)

Université de Technologie de Compiègne (1972-...) (Organisme de soutenance / degree-grantor)

École doctorale Sciences pour l'ingénieur (Compiègne) (Ecole doctorale associée à la thèse / doctoral school)

Résumé / Abstract : Cette thèse s’intéresse aux problèmes d’emploi du temps d’universités. Ces problèmes sont rencontrés chaque année par les utilisateurs. Nous proposons des bornes inférieures, des méthodes heuristiques et des modèles de programmation mixte en nombres entiers et de programmation par contraintes. Nous traitons le problème d’emploi du temps d’examens et celui d’affectation des étudiants. Nous proposons de nouvelles méthodes et formulations et les comparons aux approches existantes. Nous proposons, pour le problème d’emploi du temps d’examens, une amélioration d’un modèle mathématique en nombres entiers qui permettra d’obtenir des solutions optimales. Ensuite, des bornes inférieures, une formulation plus compacte des contraintes et un modèle de programmation par contraintes sont proposés. Pour le problème d’emploi du temps d’examens à l’Université de Technologie de Compiègne, nous proposons une approche mémétique. Enfin, nous présentons un modèle mathématique pour le problème d’affectation des étudiants et nous étudions sa performance sur un ensemble d’instances réelles.

Résumé / Abstract : This thesis investigates university timetabling problems. These problems occur across universities and are faced each year by the practitioners. We propose new lower bounds, heuristic approaches, mixed integer and constraint programming models to solve them. We address the exam timetabling and the student scheduling problem. We investigate new methods and formulations and compare them to the existing approaches. For exam timetabling, we propose an improvement to an existing mixed integer programming model that makes it possible to obtain optimal solutions. Next, lower bounds, a more compact reformulation for constraints and a constraint programming model are proposed. For the exam timetabling problem at Université de Technologie de Compiègne, we designed a memetic approach. Finally, we present a new formulation for the student scheduling problem and investigate its performance on a set of real-world instances.