Algorithme de création d'un horaire scolaire

Question

Je me demande s'il existe des solutions connues pour l'algorithme de création d'un emploi du temps scolaire. En gros, il s'agit d'optimiser la "dispersion des heures" (à la fois dans le cas des enseignants et des classes) pour des associations classe-matière-enseignant données. Nous pouvons supposer que nous avons des ensembles de classes, de sujets de cours et de professeurs associés les uns aux autres à l'entrée et que l'emploi du temps doit s'adapter entre 8h et 16h.

Je suppose qu'il n'existe probablement pas d'algorithme précis pour cela, mais peut-être que quelqu'un connaît une bonne approximation ou des conseils pour la développer.

Answer 1

Ce problème est NP-Complet !
En un mot, il faut explorer toutes les combinaisons possibles pour trouver la liste des solutions acceptables. En raison des variations des circonstances dans lesquelles le problème apparaît dans les différentes écoles (par exemple : Y a-t-il des contraintes en ce qui concerne les salles de classe, certaines classes sont-elles parfois divisées en sous-groupes, s'agit-il d'un horaire hebdomadaire, etc.), il n'existe pas de classe de problèmes bien connue qui corresponde à tous les problèmes d'horaire. Peut-être, le Problème de Knapsack présente de nombreux éléments de similitude avec ces problèmes au sens large.

Pour confirmer qu'il s'agit à la fois d'un problème difficile et d'un problème pour lequel les gens cherchent perpétuellement une solution, il suffit de vérifier ce (long) texte liste d'outils logiciels d'ordonnancement (principalement commerciaux)

En raison du grand nombre de variables impliquées, dont la plus grande source est, typiquement, les désirs du membre de la faculté ;-)..., il est typiquement il n'est pas pratique d'envisager l'énumération de toutes les combinaisons possibles . Au lieu de cela, nous devons choisir une approche qui visite un sous-ensemble des espaces de problèmes/solutions.
- Algorithmes génétiques cité dans une autre réponse est (ou, IMHO, semble ) bien équipés pour effectuer ce type de recherche semi-guidée (Le problème étant de trouver une bonne fonction d'évaluation pour les candidats à conserver pour la prochaine génération).
- Réécriture de graphiques sont également utiles pour ce type de problèmes d'optimisation combinatoire.

Plutôt que de se concentrer sur des implémentations particulières d'un programme de générateur automatique de programmes, j'aimerais suggérer ce qui suit quelques stratégies qui peuvent être appliquées, au niveau de la définition du problème .
Le raisonnement général est le suivant : dans la plupart des problèmes d'ordonnancement du monde réel, certains compromis seront nécessaires, et toutes les contraintes, exprimées ou implicites, ne seront pas entièrement satisfaites. Par conséquent, nous nous aidons :

• Définir et classer toutes les contraintes connues
• Réduire l'espace du problème, en fournissant manuellement un ensemble de supplémentaire contraintes.
  Cela peut sembler contre-intuitif mais, par exemple, en fournissant un planning initial partiellement rempli (disons environ 30 % des créneaux horaires), de manière à satisfaire pleinement toutes les contraintes, et en considérant ce planning partiel comme immuable, nous réduisons considérablement le temps/espace nécessaire pour produire des solutions candidates.
  Une autre façon dont des contraintes supplémentaires peuvent aider est par exemple d'ajouter "artificiellement" une contrainte qui empêche d'enseigner certaines matières certains jours de la semaine (s'il s'agit d'un horaire hebdomadaire...) ; ce type de contraintes a pour résultat de réduire l'espace des problèmes/solutions, sans, typiquement, exclure un nombre significatif de bons candidats.
• S'assurer que certaines des contraintes du problème peuvent être calculées rapidement. Ceci est souvent associé au choix du modèle de données utilisé pour représenter le problème ; l'idée est de pouvoir rapidement opter pour (ou élaguer) certaines des options.
• Redéfinir le problème et permettre de briser certaines des contraintes, à quelques reprises (généralement vers les nœuds d'extrémité du graphe). L'idée ici est soit de supprimer un peu de de contraintes pour remplir les derniers créneaux de l'emploi du temps, ou pour que le programme de génération automatique de l'emploi du temps s'arrête avant de remplir l'ensemble de l'emploi du temps, nous fournissant plutôt une liste d'une douzaine de candidats plausibles. Un humain est souvent mieux placé pour compléter le puzzle, comme indiqué, en brisant éventuellement quelques-unes des contraintes, en utilisant des informations qui ne sont généralement pas partagées avec la logique automatisée (par exemple, la règle "Pas de mathématiques l'après-midi" peut être brisée à l'occasion pour la classe de "mathématiques et physique avancées" ; ou "Il vaut mieux briser l'une des exigences de M. Jones que celle de Mme Smith... ;-) )

En relisant cette réponse, je me rends compte qu'elle est loin de fournir une réponse définitive, mais elle n'en est pas moins pleine de suggestions pratiques. J'espère que cela vous aidera, pour ce qui est, après tout, un "problème difficile".

Answer 2

C'est un désordre. Un désordre royal. Pour compléter les réponses, déjà très complètes, je veux faire état de mon expérience familiale. Ma mère était enseignante et avait l'habitude de participer au processus.

Il s'avère qu'avoir un ordinateur pour le faire n'est pas seulement difficile à coder en soi, c'est aussi difficile parce qu'il y a des conditions qui sont difficiles à spécifier à un programme informatique pré-cuit. Exemples :

• un professeur enseigne à la fois dans votre école et dans un autre institut. Il est évident que s'il termine son cours là-bas à 10h30, il ne peut pas commencer dans vos locaux à 10h30, car il a besoin d'un certain temps pour faire la navette entre les instituts.
• deux professeurs sont mariés. En général, il est considéré comme une bonne pratique de ne pas avoir deux enseignants mariés dans la même classe. Ces deux enseignants doivent donc avoir deux classes différentes
• Deux enseignants sont mariés, et leur enfant fréquente la même école. Là encore, vous devez empêcher les deux enseignants d'enseigner dans la classe spécifique où se trouve leur enfant.
• l'école a des installations séparées, comme un jour la classe est dans un institut, et un autre jour la classe est dans un autre.
• l'école dispose de laboratoires partagés, mais ces laboratoires ne sont disponibles que certains jours de la semaine (pour des raisons de sécurité, par exemple, lorsqu'un personnel supplémentaire est nécessaire).
• certains enseignants ont des préférences pour la journée libre : certains préfèrent le lundi, d'autres le vendredi, d'autres encore le mercredi. Certains préfèrent venir tôt le matin, d'autres préfèrent venir plus tard.
• il ne faut pas que vous ayez des situations où vous avez une leçon d'histoire à la première heure, puis trois heures de mathématiques, puis une autre heure d'histoire. Cela n'a pas de sens pour les élèves, ni pour l'enseignant.
• vous devriez répartir les arguments de manière égale. Il n'est pas logique que les premiers jours de la semaine ne soient consacrés qu'aux mathématiques, puis le reste de la semaine qu'à la littérature.
• vous devriez donner à certains enseignants deux heures consécutives pour faire des tests d'évaluation.

Comme vous pouvez le voir, le problème n'est pas NP-complet, il est NP-insensé.

Ils disposent donc d'une grande table avec de petits inserts en plastique, qu'ils déplacent jusqu'à ce qu'ils obtiennent un résultat satisfaisant. Ils ne partent jamais de zéro : ils commencent normalement par l'horaire de l'année précédente et font des ajustements.

Answer 3

Le site Concours international de Timetabling 2007 avait une piste de planification des leçons et une piste de planification des examens. De nombreux chercheurs ont participé à cette compétition. De nombreuses heuristiques et métaheuristiques ont été testées, mais au final, les métaheuristiques de recherche locale (telles que la recherche Tabu et le recuit simulé) ont clairement battu d'autres algorithmes (tels que les algorithmes génétiques).

Jetez un coup d'œil aux 2 frameworks open source utilisés par certains des finalistes :

• JBoss OptaPlanner (Java, open source)
• Unitime (Java, open source) - plutôt pour les universités

Answer 4

L'un de mes travaux de mi-trimestre était la génération d'un tableau scolaire par algorithme génétique.

La table entière est un "organisme". Il y a eu quelques changements et mises en garde par rapport à l'approche générique des algorithmes génétiques :

• Des règles étaient établies pour les "tableaux illégaux" : deux classes dans la même salle, un professeur enseignant à deux groupes en même temps, etc. Ces mutations étaient jugées mortelles sur-le-champ et un nouvel "organisme" germait immédiatement à la place du "défunt". La mutation initiale était générée par une série d'essais aléatoires pour obtenir une mutation légale (bien qu'insensée). La mutation létale n'était pas comptabilisée dans le nombre de mutations de l'itération.

• Les mutations "d'échange" étaient beaucoup plus courantes que les mutations "de modification". Les changements se faisaient uniquement entre les parties du gène qui avaient un sens - pas de substitution d'un professeur par une classe.

• De petites primes ont été attribuées pour le regroupement de certaines heures, pour l'affectation séquentielle de la même salle de classe générique pour le même groupe, pour le maintien des heures de travail de l'enseignant et de la charge de la classe. Des primes modérées ont été attribuées pour l'attribution de salles de classe correctes pour une matière donnée, pour le maintien des heures de cours dans les limites des obligations (matin ou après-midi), etc. Des primes importantes étaient attribuées pour l'attribution d'un nombre correct de matières, d'une charge de travail donnée pour un enseignant, etc.

• Les enseignants pouvaient créer leurs propres programmes de charge de travail : "veut travailler ensuite", "accepte de travailler ensuite", "n'aime pas travailler ensuite", "ne peut pas travailler ensuite", avec des pondérations appropriées. Les heures de travail légales étaient de 24 heures, sauf la nuit, qui était très indésirable.

• La fonction de poids... oh oui. La fonction de poids était un énorme, monstrueux produit (comme dans la multiplication) des poids attribués à des caractéristiques et propriétés sélectionnées. Elle était extrêmement raide, une seule propriété pouvant facilement la modifier d'un ordre de grandeur vers le haut ou vers le bas - et il y avait des centaines ou des milliers de propriétés dans un seul organisme. Il en résultait des nombres absolument ÉNORMES pour les pondérations et, en conséquence directe, la nécessité d'utiliser une bibliothèque bignum (gmp) pour effectuer les calculs. Pour un petit cas d'essai de quelque 10 groupes, 10 enseignants et 10 salles de classe, l'ensemble initial a commencé avec une note de 10^-200quelque chose et a fini avec 10^+300quelque chose. C'était totalement inefficace quand c'était plus plat. De plus, les valeurs s'éloignaient beaucoup plus avec des "écoles" plus grandes.

• En termes de temps de calcul, il y avait peu de différence entre une petite population (100) sur une longue période et une grande population (10 000+) sur moins de générations. Le calcul sur le même temps a produit à peu près la même qualité.

• Le calcul (sur un CPU de 1GHz) prendrait environ 1h pour se stabiliser près de 10^+300, générant des programmes qui semblaient très bien, pour le cas de test 10x10x10.

• Le problème peut facilement être paralysé en fournissant une installation de mise en réseau qui échangerait les meilleurs spécimens entre les ordinateurs exécutant le calcul.

Le programme qui en a résulté n'a jamais vu la lumière du jour, sauf pour me donner une bonne note pour le semestre. Il était prometteur mais je n'ai jamais été assez motivé pour ajouter une interface graphique et le rendre utilisable par le grand public.

Answer 5

Ce problème est plus difficile qu'il n'y paraît.

Comme d'autres l'ont fait remarquer, il s'agit d'un problème NP-complet, mais analysons ce que cela signifie.

En gros, cela signifie que vous devez examiner toutes les combinaisons possibles.

Mais "regarder" ne vous dit pas grand-chose sur ce que vous devez faire.

Il est facile de générer toutes les combinaisons possibles. Cela peut produire une énorme quantité de données, mais vous ne devriez pas avoir trop de problèmes pour comprendre les concepts de cette partie du problème.

Le deuxième problème est celui de juger si une combinaison possible donnée est bonne, mauvaise ou meilleure que la "bonne" solution précédente.

Pour cela, il faut plus qu'un simple "est-ce une solution possible".

Par exemple, le même enseignant travaille-t-il 5 jours par semaine pendant X semaines consécutives ? Même si cette solution fonctionne, elle n'est peut-être pas meilleure que l'alternance entre deux personnes, de sorte que chaque enseignant travaille une semaine chacune. Vous n'avez pas pensé à cela ? N'oubliez pas que vous avez affaire à des personnes, et pas seulement à un problème d'allocation de ressources.

Même si un enseignant pouvait travailler à temps plein pendant 16 semaines d'affilée, cela pourrait être une solution sous-optimale par rapport à une solution où l'on essaie d'alterner entre les enseignants, et ce type d'équilibre est très difficile à intégrer dans un logiciel.

En résumé, trouver une bonne solution à ce problème aura une grande valeur pour de nombreuses personnes. Il ne s'agit donc pas d'un problème facile à décomposer et à résoudre. Soyez prêt à fixer des objectifs qui ne sont pas à 100 % et à les qualifier de "suffisamment bons".