Offre de thèse à l'UTC, laboratoire Heudiasyc

Titre : Conception d'emplois du temps

Sujet de thèse :

Par soucis d'efficacité, les formations et diplômes sont de plus en plus décloisonnés et le système d'enseignement doit offrir l'opportunité à un étudiant de s'inscrire et de suivre des modules d'autres spécialités. Force est de constater que les parcours de formation ne sont plus linéaires : le concept de promotion dans une spécialité, pour lequel tous les étudiants d'une promotion suivent exactement les mêmes cours, devient de plus en plus obsolète dans la majorité des universités. Cette évolution a tendance à s’accélérer étant donné le cadre budgétaire contraint.

De fait, les institutions de formation font face à des problèmes beaucoup plus complexes de planification. La conception des plannings devient un enjeu majeur. Il s'agit d'être en mesure de concevoir des emplois du temps d'examens et de cours, mais aussi d'assurer la répartition des étudiants dans les différentes activités d'enseignement, en étant en capacité de tenir compte des modules de formations choisis par les étudiants. Les problématiques et critères à optimiser varient d'un établissement à l'autre. Ce sont des problèmes de nature combinatoire qui sont généralement très difficiles à traiter de manière optimale dans des temps de calcul raisonnables. Les approches heuristiques permettent de construire rapidement des solutions et offrent l'opportunité au concepteur d’élaborer interactivement sa solution en agissant sur les contraintes à respecter et les critères d’évaluation.

L'objectif de cette thèse est de concevoir et mettre en œuvre des approches de résolution modulaires pour traiter de problèmes d'emploi du temps. Les approches développées devront offrir le plus de généricité possible afin de pouvoir être facilement adaptées et être en mesure de fournir des solutions de bonne qualité.

La série de conférences PATAT (Practice and Theory of Automated Timetabling) permet à la communauté des chercheurs du domaine de présenter leurs travaux et résultats sur des problèmes académiques et industriels. Comme il est difficile de comparer les approches et méthodes de résolution à cause de la forte variabilité des problèmes, des variantes couvrant des problèmes spécifiques sont proposées. Elles font l'objet de compétitions (ITC, International Timetabling Competition) avec des jeux tests standards permettant de comparer les approches et avancées théoriques.

Nos travaux ont abordé récemment les problèmes d'emplois du temps d'examens en considérant des variantes standards de la communauté (compétition ITC 2007) et le cas spécifique de l'UTC. Le système développé pour l'UTC a été élaboré en collaboration étroite avec la Direction à la Formation et à la Pédagogie (DFP) et la Direction des Systèmes d'Information (DSI). Ce système est basé sur nos travaux de recherche avec l’encadrement de plusieurs stages de Master et d’une thèse UTC. Ces travaux de recherche ont donné lieu à différentes innovations :

• élaboration d’un logiciel de planification des examens à l’UTC. Ce logiciel est utilisé depuis plusieurs semestres par la DFP ;
• élaboration d’un système de compatibilité de configurations d’UV de l’EDT général. Ce système est opérationnel (intégré dans le site d’inscription et dans l’interface de conception) ;
• élaboration d’un système d’affectation permettant de maximiser le nombre d’étudiants affectés aux cours/TD/TP d’un ensemble d’emplois du temps. Nous avons également étudié l’optimisation d’autres critères tels que l’équilibrage des groupes, la minimisation des déplacements des étudiants entre les différents sites et la prise en compte d’étudiants en situation de handicap.

Notre objectif dans ce sujet est d'aborder les problèmes de conception d'emplois du temps de cours d'université et de gestion d'horaires :

• conception de nouveaux prétraitements ;
• caractérisation d'ensembles de tâches difficiles à placer  (partitionnement/décomposition) ;
• hybridation de méthodes de résolution avec une conception générique en vue de traiter des problèmes académiques et industriels ;
• recherche et calcul de bornes inférieures.

Nous envisageons d’explorer des approches utilisant des hybridations de méthodes de résolution issues d’algorithmes de graphes, de la programmation linéaire et de la programmation par contraintes avec le recours à des approches développées en ordonnancement et bin packing. Il s’agit de développer des modèles linéaires et de procéder à la mise en place de schémas de résolution basés sur la génération de colonnes et/ou la génération de coupes. Un soin particulier devra être accordé pour établir des propriétés de dominance et des inégalités valides (symétrie, coupes de cliques, fonctions dual-réalisables, etc.). La validation s'appuiera sur les variantes ITC et sur le cas spécifique de l’UTC.

Profil recherché

Étudiant de niveau M2 en mathématiques appliquées ou informatique (recherche opérationnelle, C++).

Encadrement

Jean-Paul Boufflet, Aziz Moukrim
Sorbonne universités, Université de technologie de Compiègne, CNRS, Heudiasyc UMR 7253

Localisation, conditions et durée

Le doctorant travaillera au sein du laboratoire Heudiasyc, UMR CNRS 7253 :Heuristique et Diagnostic des Systèmes Complexes, https://www.hds.utc.fr/

Allocation de recherche du ministère de l'enseignement supérieur, durée 3 ans à partir du 1er septembre 2017.

Candidatures

CV, relevés de notes et lettre de motivation à envoyer par e-mail à Jean-Paul Boufflet et Aziz Moukrim (jean-paul.boufflet@hds.utc.fr, aziz.moukrim@hds.utc.fr)