Concepts
Comment fonctionne réellement la génération automatique
Sans le discours commercial. Ce que fait le moteur, pourquoi le problème est difficile, et pourquoi la qualité de vos contraintes compte plus que l'ingéniosité de l'algorithme.
Le problème, énoncé simplement
Vous avez un ensemble de séances d'enseignement. Chacune a besoin d'un créneau, d'une salle et d'un enseignant. Certaines ressources sont partagées, certaines séances ne doivent pas se chevaucher, et une longue liste de règles limite les combinaisons admissibles. Trouvez une affectation qui n'enfreint aucune règle stricte et viole le moins de préférences possible.
C'est un problème de satisfaction de contraintes, et la planification d'emploi du temps universitaire en est un cas difficile bien étudié. Le nombre d'affectations possibles croît de manière explosive avec le nombre de séances : la recherche exhaustive n'est pas simplement lente, elle est astronomiquement irréalisable, même pour une faculté de taille modeste.
Aucun système pratique ne procède donc à une recherche exhaustive. Ils utilisent des heuristiques — des stratégies éclairées pour décider quoi placer ensuite et que faire en cas de blocage — afin de trouver rapidement une bonne solution plutôt qu'une solution prouvée optimale, un jour.
Ce que fait réellement le moteur
- Ordonnancement. Décider quelles séances placer en premier. Les séances très contraintes — une grande cohorte nécessitant un laboratoire précis avec un seul technicien qualifié — sont généralement placées tôt, car les placer en dernier oblige à défaire tout le reste.
- Placement. Affecter une séance à une combinaison admissible de créneau, de salle et d'enseignant qui n'enfreint aucune contrainte stricte.
- Retour arrière. Annuler des décisions antérieures lorsqu'une séance n'a plus aucun placement admissible. C'est là que passe l'essentiel du temps de calcul.
- Évaluation. Mesurer dans quelle mesure la solution partielle actuelle satisfait les préférences souples, afin que la recherche puisse privilégier les meilleures régions de l'espace.
- Amélioration. Une fois qu'une solution complète et admissible existe, effectuer des modifications locales qui améliorent le score sans rien casser.
Pourquoi vos contraintes comptent plus que l'algorithme
C'est la partie que les éditeurs sont le moins pressés d'avouer. Avec un ensemble de contraintes bien spécifié, la plupart des moteurs compétents donnent des résultats comparables. Avec un ensemble mal spécifié, aucun moteur ne produit rien d'utile.
L'échec le plus courant n'est pas algorithmique. C'est un ensemble de contraintes où des préférences ont été déclarées inviolables, de sorte qu'aucune solution admissible n'existe et que le moteur signale à juste titre un grand nombre de séances impossibles à placer. Le deuxième est celui de données d'entrée périmées ou erronées — des capacités de salles que personne n'a vérifiées depuis une rénovation, des disponibilités collectées il y a six semaines.
C'est pourquoi la question utile à poser à un éditeur n'est pas « quel algorithme utilisez-vous », mais « comment m'aidez-vous à bien définir les contraintes et les disponibilités ».
À quoi ressemble un bon système en pratique
Un système utilisable génère assez vite pour que la régénération soit une routine et non un traitement de nuit — Wise Timetable régénère même de grands emplois du temps en moins d'une minute, ce qui permet d'expérimenter plutôt que de s'en remettre à une seule exécution.
Il indique ce qu'il n'a pas pu placer, et pourquoi, au lieu d'enfreindre silencieusement une règle pour produire quelque chose qui semble terminé. Il respecte les séances que vous avez verrouillées, de sorte que le travail automatique et le travail manuel peuvent se combiner. Et il produit plusieurs variantes afin que vous puissiez comparer plutôt qu'accepter.
Envie de voir cela fonctionner ?
Réservez une présentation en ligne de 45 minutes et nous la déroulerons à partir du propre problème de planification de votre établissement.