Comment fonctionnent les moteurs de planification pédagogique ?

Une école doit programmer 400 séances sur un semestre avec plusieurs promotions, des dizaines d'intervenants et un nombre limité de salles. Comment proposer une organisation fiable sans tester manuellement toutes les combinaisons ? La recherche opérationnelle répond à cette question avec des modèles mathématiques, des algorithmes et des outils d'optimisation.

1. Pourquoi la planification est mathématiquement difficile

Prenons un exemple volontairement simplifié : dix séances et cinq créneaux possibles pour chacune. Avant toute contrainte, le nombre de combinaisons possibles est de 5 puissance 10, soit 9 765 625. Ajouter les salles, les intervenants et leurs disponibilités rend le problème plus complexe.

La planification universitaire est un problème d'optimisation combinatoire, souvent NP-difficile dans ses formulations générales. Cela ne signifie pas que chaque planning est impossible à calculer : cela signifie que les grandes instances peuvent être difficiles à résoudre de manière optimale.

Schéma 1 — Explosion combinatoire

2. Transformer une organisation pédagogique en règles calculables

Un moteur de planification commence par définir les séances, les ressources, les créneaux et les variables de décision. Pour chaque cours, il examine les possibilités d'affectation compatibles avec les données disponibles.

Les contraintes obligatoires excluent les conflits : un même intervenant ne peut pas travailler simultanément sur deux cours, une salle doit avoir une capacité suffisante. Les préférences permettent ensuite d'améliorer l'organisation. Si une règle importante n'est pas encodée, le logiciel ne peut pas en garantir le respect.

3. Qu'est-ce qu'un solveur ?

Un solveur est un outil informatique qui recherche des solutions respectant un ensemble de contraintes formalisées. Il peut trouver une première solution réalisable, améliorer son score, démontrer qu'aucune solution n'existe dans le modèle ou interrompre la recherche sans conclusion définitive.

Il faut distinguer ces résultats : ne pas avoir trouvé de planning dans le temps disponible n'est pas la preuve qu'aucun planning n'est possible. Les logiciels peuvent donc rendre visibles aussi bien les solutions que les limites de la recherche.

Schéma 2 — Le parcours d'un solveur

4. Quatre approches utilisées pour construire des plannings

La programmation par contraintes (CP) décrit les variables, les possibilités et les règles. Elle convient notamment aux problèmes de créneaux et d'affectations de ressources.

La programmation linéaire en nombres entiers (MILP) décrit des décisions et des limites sous forme mathématique. Les métaheuristiques, comme la recherche tabou, explorent de nombreuses configurations pour obtenir de bons compromis, sans garantir systématiquement un optimum.

Les approches hybrides combinent des méthodes selon la complexité du cas. Google OR-Tools avec CP-SAT, Timefold Solver et UniTime sont des exemples d'outils ou de projets dédiés à l'optimisation et aux emplois du temps. Leur mention ne signifie pas que Lecturer les utilise.

5. Un planning réalisable peut-il être mauvais ?

Oui. Une école peut obtenir trois calendriers sans chevauchement, mais qui imposent des journées à trous ou de nombreux déplacements. Supposons que le planning A crée huit heures d'attente et deux déplacements entre campus ; le B trois heures d'attente et six déplacements ; le C cinq heures d'attente et trois déplacements.

Une fonction objectif permet de privilégier certains critères. Les priorités d'un campus unique peuvent être différentes de celles d'un établissement réparti sur plusieurs sites. Le meilleur planning dépend des arbitrages retenus.

Schéma 3 — Contraintes fortes et souples

Schéma 4 — Trois plannings, trois compromis

6. Pourquoi un solveur ne remplace pas les responsables pédagogiques

Une directrice pédagogique peut vouloir conserver une progression particulière, ou éviter de bouleverser les séances déjà communiquées. Ces préférences peuvent être difficiles à exprimer complètement dans un modèle.

Les équipes doivent donc rester capables de comparer les scénarios, d'ajuster les priorités et de valider les décisions. Le moteur sert d'aide à la décision, pas de substitut universel au jugement pédagogique.

7. Replanifier sans tout reconstruire

Lorsqu'un cours est annulé, un moteur peut privilégier les modifications minimales : préserver les séances confirmées, limiter les déplacements et réduire le nombre de notifications. Cette recherche de stabilité compte autant que le calcul initial.

L'IA générative peut rendre cette démarche plus accessible : l'utilisateur formule son intention en langage naturel, le moteur vérifie les contraintes, puis les responsables examinent les propositions.

Le meilleur planning n'est pas simplement celui qui remplit toutes les cases. C'est celui qui respecte les règles et les priorités de l'établissement. Notre troisième article présente les applications possibles pour une coordinatrice pédagogique.

Glossaire

Recherche opérationnelle : discipline mathématique d'aide à la décision. Solveur : moteur recherchant des solutions. Programmation par contraintes : représentation de choix et de règles. MILP : programmation linéaire en nombres entiers mixtes. Métaheuristique : stratégie de recherche de bons compromis. Fonction objectif : mesure de qualité d'une solution. Replanification : modification contrôlée d'un planning.

Sources et références

Chen et al. (IEEE Access 2021) : https://doi.org/10.1109/ACCESS.2021.3100613

Google OR-Tools CP-SAT : https://developers.google.com/optimization/cp/cp_solver

Google OR-Tools Scheduling : https://github.com/google/or-tools/blob/stable/ortools/sat/docs/scheduling.md

Timefold Solver : https://docs.timefold.ai/timefold-solver/latest/

UniTime : https://www.unitime.org/