Il existe un certain type d'après-midi que tout responsable d'emploi du temps connaît. Le générateur tourne depuis vingt minutes. Des cartes ne sont toujours pas placées. Vous avez essayé trois fois avec des réglages légèrement différents, et chaque exécution en laisse une poignée différente en rade. Quelque part dans les données se cache une raison, et vous allez la trouver à la main.
Avant de commencer à chercher, une chose mérite d'être sue : d'après notre expérience, la plupart de ces après-midi ne tiennent pas à un problème difficile. Ils tiennent à un problème impossible — des exigences qu'aucun agencement de cours ne pourrait jamais satisfaire, quelle que soit la durée de la recherche.
Difficile et impossible se ressemblent vus de l'extérieur
C'est là le piège. Un moteur heuristique réagit de la même façon dans les deux cas : il continue d'essayer, puis finit par s'arrêter en laissant des cours non placés. L'écran vous montre exactement la même chose, qu'il ait manqué au solveur une minute de plus ou un enseignant qui n'existe pas.
Alors le planificateur fait la seule chose qui lui reste — il relâche des contraintes. Supprimer une exigence de salle, assouplir la disponibilité d'un enseignant, autoriser un cours double là où vous vouliez des heures simples. Quelque chose finit par se placer, et l'emploi du temps part en production avec trois compromis que personne n'a décidés délibérément.
Les cinq façons dont un emploi du temps devient impossible
Presque toutes les infaisabilités authentiques que nous avons rencontrées relèvent de l'une de cinq familles. Toutes les cinq se détectent par un simple calcul, avant que la moindre recherche ne commence.
1. Pas assez de grille
Le cas le plus simple. Une classe a besoin de 34 heures par semaine ; la grille compte 5 jours × 6 heures = 30 créneaux. Aucun agencement n'entre, et aucune habileté de placement n'y changera rien. La même défaillance se présente sous une forme plus subtile lorsque les pauses méridiennes ou les après-midi bloqués réduisent la grille utilisable en deçà de ce qu'exigent les programmes.
2. Capacité des enseignants
Additionnez tout ce qu'un enseignant doit assurer. Comparez le total au nombre de créneaux où il est réellement disponible. Dès que le premier nombre dépasse le second, le plan est mort, quel que soit l'agencement. C'est extrêmement fréquent dans les établissements où un enseignant à temps partiel a repris « juste une classe de plus ».
3. Pénurie de salles spécialisées
Onze cours ont besoin d'un laboratoire de sciences. Il y a un laboratoire et 30 créneaux : jusqu'à 30 heures de laboratoire tiennent donc — sauf si huit de ces onze cours sont en outre contraints au mardi matin, où il n'y a que quatre créneaux. Les conflits de salles se manifestent rarement comme une pénurie globale ; ils se manifestent comme une pénurie à l'intérieur d'une fenêtre, et c'est pourquoi l'œil les repère si difficilement.
4. Des règles de répartition qui contredisent l'arithmétique
Une matière à 6 heures hebdomadaires dans une semaine de 5 jours, assortie d'une règle qui impose au plus une heure par jour, ne peut pas être placée. La règle et le volume horaire se contredisent. C'est, à lui seul, le constat que nous rencontrons le plus souvent, parce que les deux moitiés ont été configurées à des mois d'intervalle par des personnes qui, chacune, ont pris une décision raisonnable.
5. Des cours couplés sans créneau commun
Deux classes doivent avoir leur barrette d'options en même temps. La classe A est libre le lundi et le mercredi ; la classe B est libre le mardi et le jeudi. Il n'existe aucun créneau partagé. L'exigence est cohérente pour chaque classe prise séparément, et impossible pour le couple.
Ce que nous faisons pour y remédier
Bildena effectue ces vérifications avant le calcul, dans le Conseiller. Ce n'est pas une recherche — c'est de l'arithmétique sur vos données, et cela prend à peu près le temps de charger la page.
Le rapport distingue délibérément deux catégories :
- Critique. Ces constats rendent le problème prouvablement infaisable. La génération est bloquée, car lancer un calcul qui ne peut pas aboutir ne fait que vous coûter votre après-midi sans rien vous apprendre.
- Suggestions. Ces constats n'empêchent pas une solution, mais la rendent plus difficile ou moins bonne — un enseignant à 95 % de sa capacité, une matière dont la règle de répartition ne laisse qu'un seul schéma licite. Les calculs se lancent ; on vous indique simplement où se situe la tension.
Chaque constat nomme les objets concernés et renvoie directement à l'écran où vous le corrigeriez. « Les heures hebdomadaires dépassent la disponibilité de M. Lefèvre (28 attribuées, 24 disponibles) » est une phrase sur laquelle on peut agir en quatre-vingt-dix secondes. « Certaines cartes n'ont pas pu être placées », non.
Et quand c'est la recherche elle-même qui le prouve
L'arithmétique attrape les cinq familles ci-dessus, mais toute impossibilité n'est pas arithmétique. Certaines ne surgissent que du jeu simultané de nombreuses contraintes — le genre de chose qu'aucune vérification préalable ne peut voir, parce que la voir, c'est la recherche.
C'est ici qu'un solveur de contraintes se distingue d'une heuristique d'une manière qui compte en
pratique. Le solveur peut renvoyer INFEASIBLE — une preuve, pas un dépassement de délai. Cela
signifie : ces exigences ne peuvent pas être satisfaites toutes ensemble, et cette conclusion est
définitive. Aucun redémarrage, aucun réordonnancement, aucune attente ne produira d'emploi du temps, parce
qu'il n'en existe aucun.
Que faire d'une impossibilité
Un résultat infaisable n'est pas une défaite ; c'est une décision avancée dans le temps. Les options forment toujours le même petit ensemble, et vous pouvez désormais choisir en connaissance de cause :
- Ajouter de la capacité — un enseignant de plus, une salle de plus, une heure de plus dans la journée.
- Réduire la demande — moins d'heures pour une matière, une division de moins.
- Relâcher une règle dont vous savez maintenant qu'elle est la règle bloquante — et consigner que vous l'avez fait.
La troisième option est exactement le compromis qu'une heuristique vous aurait imposé en silence. La différence, c'est que vous le faites en mai, toutes vos options encore ouvertes, plutôt qu'à minuit au mois d'août — et que vous savez précisément ce qu'il a coûté.
Le Conseiller fonctionne dans tous les espaces de travail Bildena, essai gratuit compris. Importez vos données et regardez ce qu'il en dit avant de générer quoi que ce soit — la plupart des établissements y découvrent au moins un constat qu'ils ignoraient.