Qu'est-ce qui rend la planification scolaire si difficile ? Petit tour d'horizon d'un problème délicat

L'emploi du temps scolaire appartient à une famille de problèmes que les informaticiens qualifient formellement de très difficiles. Voici pourquoi votre administrateur général mérite plus de sympathie, et voici comment les résolveurs modernes y parviennent de toute façon

Il y a un moment familier pour tous ceux qui ont déjà établi un emploi du temps scolaire à la main. Le réseau est plein à 90 %. Des semaines de travail sont au programme. Et les dernières leçons ne vous conviendront pas, non pas parce que vous vous êtes trompée, mais parce qu'un stage que vous avez effectué dans la première heure du premier jour, il y a des semaines, a discrètement rendu cette impasse inévitable.

Ce moment n'est pas un coup de malchance. C'est la nature mathématique du problème qui s'annonce.

Prenons un exemple délibérément minuscule : 10 professeurs, 8 groupes de classe, 30 leçons d'une heure par semaine par groupe, 25 créneaux d'enseignement par semaine.

Même dans cette école de jouets, les différentes manières d'organiser les leçons se comptent par dizaines de chiffres. Un véritable lycée — 50 professeurs, 25 groupes, des salles spécialisées, des contrats à temps partiel, des blocs d'options — dispose d'un espace de recherche qui dépasse largement le nombre d'atomes de l'univers observable

horaires appartient à la catégorie des problèmes pour lesquels il est facile de vérifier une solution (il est rapide de vérifier la présence de conflits sur une grille terminée), mais en trouver une peut coûter très cher, car la seule méthode garantie consiste, dans le pire des cas, à essayer un nombre impensable de combinaisons. C'est le territoire que les informaticiens appellent NP-Hard, et les horaires scolaires sont payants

Conséquence pratique : aucune expérience ne permet d'atteindre l'échelle de l'approche manuelle. L'expérience aide un planificateur humain à mieux éviter les pièges évidents, mais les pièges qui font mal ne sont jamais les plus évidents.

De nombreuses industries planifient les choses. Ce qui rend les écoles spéciales, c'est la densité de contraintes imbriquées

Tout est partagé. L'horaire des quarts de travail dans un hôpital limite principalement un type de ressource (le personnel). Un emploi du temps scolaire impose simultanément trois contraintes : les enseignants, les salles et les groupes d'élèves, et chaque leçon en consomme un. Le fait de placer une seule leçon supprime les options en trois dimensions à la fois.

Certaines règles sont physiques : un professeur ne peut pas être dans deux salles à la fois. D'autres sont des préférences : Mme Ortiz préfère enseigner le matin. Un bon emploi du temps doit satisfaire tous les objectifs du premier type et le plus grand nombre possible du second, et ces deux objectifs se disputent constamment.

La structure vit à l'intérieur de la structure. Les périodes doubles doivent occuper des créneaux consécutifs et ne doivent souvent pas chevaucher la pause déjeuner. Les blocs d'options nécessitent quatre leçons différentes, enseignées par quatre professeurs dans quatre salles, qui se déroulent simultanément afin que les étudiants puissent choisir différentes matières. Les séances de laboratoire nécessitent des salles spécifiques. Les réunions du personnel nécessitent que certains groupes de personnes puissent libérer à la même heure. Chacune de ces contraintes concerne des groupes de placements, ce qui est beaucoup plus difficile que les contraintes relatives à des stages individuels.

Les données sont humaines. Des contrats à temps partiel, des professeurs qui partagent leur semaine entre deux écoles, un entraîneur qui part tôt les jours de match. Les véritables écoles sont un ensemble d'exceptions, et un emploi du temps qui les ignore n'est pas un emploi du temps, c'est une suggestion

Les logiciels modernes de programmation n'utilisent pas de force brute l'univers des combinaisons et n'utilisent pas la magie. Il utilise une famille de techniques allant de la satisfaction des contraintes à l'optimisation combinatoire, qui sont vraiment magnifiques une fois que vous en voyez la forme

Propagation : laissez chaque stage vous apprendre quelque chose. Lorsque le solveur place une leçon, il en répercute immédiatement les conséquences : ce professeur est maintenant occupé le mardi, période 2, cette salle est occupée, ce groupe est occupé. Chaque option qui vient de devenir impossible est supprimée partout ailleurs. L'espace de recherche s'effondre de plusieurs ordres de grandeur à chaque étape de confiance

Échouez vite, revenez en arrière intelligemment. Au lieu de découvrir une impasse au bout de plusieurs semaines, comme le ferait un humain, un solveur détecte en quelques millisecondes qu'une branche de la recherche ne peut pas aboutir (une prochaine leçon ne comporte déjà aucun créneau légal) et l'abandonne instantanément. Il peut également identifier la décision antérieure à l'origine de l'impasse et revenir exactement à cette situation.

Heuristique : placez les choses les plus difficiles en premier. Les planificateurs humains expérimentés le font instinctivement (planifiez tôt les blocs d'options et les employés à temps partiel, remplissez les cases faciles en dernier). Les solveurs le font systématiquement, classant chaque leçon non placée en fonction de sa contrainte à chaque étape

Réparer et améliorer. Obtenir un emploi du temps réaliste ne représente que la moitié du travail. Les résolveurs l'améliorent ensuite en modifiant et en échangeant des chaînes de leçons pour réduire les écarts entre les enseignants, respecter davantage de préférences et équilibrer la charge de travail, sans jamais dépasser une contrainte stricte. C'est là que « valide » devient « bon ».

Le résultat, avec un outil comme Arignote Timetable, est qu'un emploi du temps complet et sans conflit pour une véritable école émerge en quelques minutes, chaque contrainte stricte étant vérifiée par machine et les contraintes souples optimisées bien au-delà du point où un humain, le quatorzième jour, aurait naturellement abandonné.

Voici ce qui surprend les gens : l'automatisation donne plus d'importance au rôle de l'homme, et non pas le moins.

La qualité du solveur dépend du modèle de l'école qui lui a été donnée. Décider que les doubles périodes ne devraient pas chevaucher le déjeuner, que le nouvel enseignant a besoin d'un premier trimestre doux, que le jeudi après-midi est consacré aux réunions du département — c'est la direction de l'école, encodé. Le travail du logiciel est de s'assurer qu'une fois que vous l'avez dit, c'est vrai partout, toujours, d'une manière qu'aucun humain ne peut garantir seul.

Et lorsque l'emploi du temps généré revient, vous le révisez comme un éditeur, pas comme un dactylographe : ajustez un emplacement ici, épinglez une leçon là-bas, chaque conflit d'édition étant vérifié en direct, et régénérez le reste en fonction de vos décisions.

semaines de travail mécanique deviennent des minutes de calcul auxquelles s'ajoutent des heures de jugement. Le jugement a toujours joué un rôle important.