présentation de willow

Depuis les récents changements liés aux décisions de l'université, l'organisation et la consultation des edt à pns passent par ADE. Bien que ce logiciel assure la gestion globale des ressources, son utilisation quotidienne nous fait manquer la praticité de l'ancienne solution.

L'observation

Au delà des problèmes évidents d'interface, de performance et de stabilité de cette solution (et déjà brillamment traités par l'excellent Polytime Overflow), c'est l'agencement même des edt qui pose un problème bien plus important! Des étudiants ou enseignants, personne n'apprécie attendre 5 heures entre deux cours, se déplacer pour une seule heure de cours ou ne pas avoir assez de temps pour manger. On pense que l'emploi du temps universitaire est la véritable colonne vertébrale du quotidien étudiant, ainsi qu'un facteur déterminant et non négligeable de réussite académique. De là naît donc willow, un algorithme chargé de trouver le meilleur gain en un nombre de changements minimal:)

Plus tôt dans l'année les éblouissants yahya et andrii, ainsi que moi même avions donc cherché à trouver la source et quantifier les conséquences du système actuel, on peut consulter notre court rapport sur l'impact de l'emploi du temps sur la vie étudiante et l'empreinte carbone (pdf).

La réponse

Tout d'abord il a fallu déterminer si l'état proposé du planning était déjà le "meilleur".

Pour ça vient le premier brouillon de l'algorithme de scoring, dont le fonctionnement a été survolé dans le rapport. On attribue à chaque jour un budget de 100 points, que l'on vient baisser selon les pénalités qui s'y appliquent (heure de trou, fin tardive, temps pause dej...).
C'est une solution non exhaustive et subjective mais qui place les fondations pour commencer un premier solveur fonctionnel : willowengine.

Willowengine est un algorithme branch & bound (bnb) fait en C# qui a pour but de trouver le meilleur mouvement à jouer en un budget de déplacements très restreint. Son fonctionnement est maladroitement et non exhaustivement décrit dans la carte du moteur. Les premiers résultats ne laissent aucun doute: les plannings proposés sont très largement améliorables, mais ce ne sont que des premiers résultats. La principale limite étant que nous n'avons pas demandé les contraintes de chaque semaine à chaque enseignant, on considérait que les enseignants n'étaient disponibles uniquement les demies journées où ils donnaient déjà cours, ce qui était extrêmement restrictif. Le calcul a donc été relativement rapide (<50 mins pour 1 semaine), mais les résultats en ont été agressivement affectés (ce qui est encourageant pour la suite).

Les rendus du moteur étant difficiles à interpréter dans un terminal, j'ai recyclé un viewer d'ics (vanilla js) qui a fini par servir à afficher les cours des 9 groupes de peips et utilisé par des étudiants. J'ai donc passé quelques temps à le rendre plus confortable et réactif, et à ajouter ce qui n'était pas disponible dans les autres viewers, notamment:

• Lecture par groupe (et non par étudiant);
• Tous les groupes sont disponibles librement;
• Les plannings Unica des enseignants aussi;
• Les plannings des salles des lucioles / templiers;
• Les plannings restent entièrement disponibles quand ADE tombe;
• Des filtres sont disponibles pour les SHN (partagés pour tous, avec un score de popularité);
• Les enseignants peuvent facilement voir tous les cours d'une matière dans une semaine (utile lorsque des doctorants font cours);
• Recherche d'une salle libre, maintenant ou plus tard, dans tous les batiments;

On peut aussi consulter le calcul d'un score et la raison des pénalités appliquées. On voit sur l'image une courbe de visite cohérente (pics en début de semaine, creux le weekends et vacances). Pour que mon pauvre vps puisse rester debout et le site réactif, la page est mise en cache est n'est téléchargée à nouveau uniquement si l'edt a changé.

La suite

Je crois avoir tout dit des grandes lignes sur willow. Le projet semble donc se découper en deux parties distinctes : Willow EDT et Willow Optimiseur. En ce qui concerne le moteur, je suis en train de créer une baseline et un benchmark pour assurer mes tests de non régression, je pense maintenant implémenter une table de transposition (tt) pour éviter les calculs répétitifs. Je cherche aussi une solution aux contraintes manquantes des enseignants qui faussent encore les résultats.
C'est tout pour cette première update, merci de m'avoir lu:)

//pekmi