N'importe quel logiciel d'emploi du temps finira par vous en produire un. La question que personne ne pose — et celle qui décide de la part de votre mois d'août que vous allez y laisser — est de savoir ce que le logiciel veut vraiment dire lorsqu'il annonce qu'il a terminé.
Il n'existe que deux réponses honnêtes. Soit le logiciel a cherché jusqu'à épuiser son temps, ses coups ou sa patience, et vous a remis le meilleur agencement qu'il ait croisé en chemin. Soit il a cherché jusqu'à pouvoir prouver qu'aucun agencement meilleur n'existe. Cela ressemble à deux variantes d'une même chose. Ce n'en est pas. Ce sont deux mathématiques différentes, et elles débouchent sur des semaines très différentes.
Le marché que propose l'heuristique
Les moteurs d'emploi du temps traditionnels sont heuristiques. Ils placent les cours selon des règles empiriques, détectent les conflits, reviennent en arrière, essaient un autre ordre, et recommencent. C'est délibérément une version mécanisée de ce que fait un planificateur humain avec des cartons sur une table — et les éditeurs le présentent ainsi. Le manuel d'aSc TimeTables indique que « le programme utilise des algorithmes dynamiques et heuristiques, qui lui permettent de suivre la même démarche qu'une personne ». Untis documente un processus en deux temps — une passe de placement initial suivie d'une passe d'optimisation par échanges — piloté par des curseurs de pondération que le planificateur règle lui-même.
Cette approche a une vraie qualité : elle est rapide, et pour un établissement dont les contraintes sont souples elle produit un plan tout à fait convenable. Des millions d'emplois du temps ont été construits ainsi.
Mais ce marché a une contrepartie, et cette contrepartie est rarement énoncée. Une heuristique ne peut pas vous dire où vous en êtes. Quand elle termine, elle sait une seule chose : qu'elle s'est arrêtée. Elle ignore si le plan qu'elle vous remet est excellent, médiocre, ou à deux échanges de quelque chose de bien meilleur. Il n'y a aucune mesure de la distance à l'idéal, parce qu'il n'y a aucune représentation de l'idéal.
La documentation est franche sur les conséquences. aSc prévient qu'en cas d'échec de la génération, « quelques cartons non placés subsisteront », et qu'il « ne vaut la peine de relancer que deux ou trois fois, après quoi il vaut mieux essayer de modifier les critères ». Ses paramètres de génération comprennent une option qui procède à un relâchement automatique des contraintes — le programme rompt discrètement des conditions que vous avez posées afin de caser les cartons restants. Untis réserve ses meilleurs résultats à l'Übernacht-Optimierung : laissez l'ordinateur tourner toute la nuit.
Ce que fait un solveur à la place
Bildena repose sur un solveur de contraintes que nous avons spécialisé de bout en bout pour une seule tâche : répartir les cours sur une semaine scolaire. Il ne simule pas une personne qui déplace des cartons. Il traduit votre établissement en un modèle mathématique — chaque cours une variable, chaque règle une contrainte — et explore ce modèle systématiquement.
L'essentiel n'est pas qu'il aille plus vite. C'est qu'il tient deux nombres à la fois : la meilleure solution trouvée jusqu'ici, et une borne sur la meilleure solution qui puisse exister. À mesure que la recherche avance, la solution s'améliore et la borne se resserre. Quand elles se rejoignent, la recherche est terminée — non parce que le temps est écoulé, mais parce qu'on peut prouver qu'il n'existe rien de mieux. Voilà ce qu'est l'optimalité : un énoncé mathématique, pas un argument commercial.
Trois choses que cela rend possibles
1. Un plan certifié, et non espéré. Quand Bildena annonce zéro conflit, cela ne signifie pas « aucun conflit n'a été remarqué ». Cela signifie : « aucun agencement de ces cours ne viole vos règles dures, et en voici un ». Les contraintes dures — un enseignant dans deux salles, une classe à deux endroits, une salle réservée deux fois — sont structurellement impossibles dans le modèle, plutôt que pénalisées après coup.
2. L'infaisabilité comme réponse, et non comme échec. Parfois, la réponse honnête est qu'aucun emploi du temps ne satisfait tout ce que vous avez demandé. Six heures de mathématiques dans une semaine de cinq jours avec un enseignant disponible trois jours, ce n'est pas un problème difficile : c'est un problème impossible. Une heuristique réagit à l'impossibilité exactement comme à la difficulté — elle continue d'essayer, puis laisse des cartons non placés. Un solveur, lui, peut prouver que les exigences se contredisent et le dire, avant le calcul plutôt qu'après. Le Conseiller de Bildena effectue ces vérifications en amont : capacité, disponibilité, types de salles, service des enseignants.
3. Un bouton d'arrêt qui a un sens. Comme il existe à tout instant une meilleure solution courante et un écart connu, vous pouvez interrompre à n'importe quel moment et conserver ce qui a été trouvé — assorti d'une indication honnête de la distance qui peut encore le séparer de l'optimum. « 98,4 sur 100, à moins de 1,8 % de la borne théorique » est une phrase qu'une heuristique ne peut pas produire.
Règles dures et préférences souples
Un emploi du temps scolaire n'est pas un problème mais deux, superposés. Certaines exigences sont absolues : un enseignant ne peut pas être dans deux salles à la fois, un cours de travaux pratiques exige un laboratoire. D'autres sont des préférences qui s'arbitrent les unes contre les autres — réduire les heures creuses, répartir les matières sur la semaine, équilibrer la charge quotidienne, éviter les heures isolées après le déjeuner. Chaque établissement les pondère différemment, et aucun logiciel ne peut décider de cette pondération à votre place.
La distinction compte parce que les deux appellent des traitements différents. Les exigences dures sont des contraintes : le solveur ne renverra jamais, en aucun cas, une solution qui en rompt une. Les préférences deviennent des termes d'une fonction objectif, avec des poids que vous maîtrisez. Le solveur fait alors ce qu'une personne ne parvient pas à faire de façon fiable à la main — il trouve l'agencement qui maximise le total pondéré sur l'ensemble des préférences simultanément, au lieu de régler une plainte à la fois et d'en créer deux nouvelles.
Pourquoi personne ne vous montre le calcul
Il y a une curieuse lacune sur ce marché. Chaque éditeur décrit la génération comme le cœur de son produit, et pas un seul ne la montre à l'œuvre. aSc met en avant un générateur qui évalue « plus de 5 000 000 de possibilités » mais n'affiche rien pendant qu'il le fait. Untis rapporte des pourcentages de qualité une fois le travail terminé. Les utilisateurs le réclament depuis des années ; l'absence de tout indicateur prédictif pendant la génération est une critique récurrente dans les avis.
Nous diffusons le calcul en direct. Pendant que Bildena travaille, vous voyez le nombre de conflits durs diminuer, le score de qualité monter, la phase passer de la recherche de faisabilité à l'optimisation, et l'écart à la borne théorique se réduire — un commentaire en continu sur une connexion ouverte, et non une barre de progression au pourcentage inventé.
C'est en partie de la transparence et en partie du diagnostic. Un calcul qui plafonne à 12 conflits restants sur le groupe des disponibilités enseignants vous dit quelque chose de précis sur vos données. Un sablier ne vous dit rien.
Ce que nous ne prétendons pas
L'optimalité prouvée est une propriété du modèle, pas une baguette magique, et il vaut la peine d'en énoncer précisément les limites.
- Optimal veut dire optimal au regard de l'objectif que vous avez défini. Si vous pondérez à zéro les heures creuses des enseignants, le solveur produira sans état d'âme un plan qui en regorge et en prouvera l'optimalité. Les mathématiques sont fidèles à vos priorités, y compris à vos erreurs.
- À données absurdes, absurdité prouvée. Un solveur ne peut pas inventer une salle que vous n'avez pas, ni une heure qui n'existe pas. Il peut seulement vous dire, précisément et tôt, que vous ne les avez pas.
- L'optimalité n'est pas toujours atteinte dans le temps que vous accordez. Pour des établissements très grands ou très contraints, le solveur peut atteindre sa limite de temps avec un petit écart résiduel. La différence, c'est qu'il vous annonce cet écart au lieu de présenter une recherche partielle comme une réponse achevée.
Ce que nous affirmons
À la fin du calcul, vous saurez lequel des trois cas s'est produit : cet emploi du temps est optimal ; cet emploi du temps est réalisable et se situe à une distance connue de l'optimum ; ou ces exigences ne peuvent pas être toutes satisfaites, et voici l'ensemble de celles qui se heurtent.
Vous n'aurez jamais « voici ce que j'ai réussi à faire ». C'est là toute la différence, et après trente ans de logiciels d'emploi du temps, il est étrange de pouvoir encore le dire.
Bildena Scheduler est un système d'emploi du temps scolaire en ligne, fondé sur un solveur de contraintes spécialisé pour la répartition des cours, développé et hébergé en Allemagne. Pendant l'essai gratuit, vous pouvez lancer une génération complète sur vos propres données — import depuis aSc TimeTables, Untis ou Excel — et comparer le résultat à votre plan actuel.