Algorithme de création d’un emploi du temps scolaire

Je me demandais s’il existe des solutions connues pour l’algorithme de création d’un calendrier scolaire. Fondamentalement, il s’agit d’optimiser la «dispersion des heures» (à la fois dans le cas des enseignants et des classes) pour des associations de cours-matières-enseignants données. Nous pouvons supposer que nous avons des ensembles de classes, des sujets de cours et des enseignants associés les uns aux autres à l’entrée et que cet emploi du temps doit se situer entre 8 heures et 16 heures.

Je suppose qu’il n’y a probablement pas d’algorithme précis pour cela, mais peut-être que quelqu’un connaît une bonne approximation ou des astuces pour le développer.

Ce problème est NP-Complete !
En bref, il faut explorer toutes les combinaisons possibles pour trouver la liste des solutions acceptables. En raison des variations dans les circonstances dans lesquelles le problème apparaît dans différentes écoles (par exemple: Y a-t-il des contraintes en ce qui concerne les salles de classe? Certaines classes sont-elles réparties en sous-groupes une partie du temps? etc.) il n’existe pas de classe de problèmes bien connue correspondant à tous les problèmes de planification. Peut-être que le problème de Knapsack comporte de nombreux éléments de similarité avec ces problèmes en général.

Une confirmation que ceci est à la fois un problème difficile et une solution permanente pour les personnes consiste à vérifier cette (longue) liste d’outils de programmation de logiciels (principalement commerciaux).

En raison du grand nombre de variables impliquées, dont la plus grande source est, généralement, les désirs des membres du corps professoral; -), il est généralement peu pratique d’envisager d’énumérer toutes les combinaisons possibles . Au lieu de cela, nous devons choisir une approche qui visite un sous-ensemble des espaces problèmes / solutions.
Les algorithmes génétiques , cités dans une autre réponse sont (ou, à mon humble avis, semblent ) 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)
– Les approches de réécriture de graphes sont également utiles avec ce type de problèmes d’optimisation combinatoire.

Plutôt que de mettre l’accent sur des implémentations particulières d’un programme de génération automatique de programmes, je voudrais suggérer quelques stratégies applicables au niveau de la définition du problème .
Le raisonnement général est que dans la plupart des problèmes d’ordonnancement du monde réel, certains compromis seront nécessaires, pas toutes les contraintes, explicites et implicites: seront pleinement satisfaits. Nous nous aidons donc par:

  • Définir et classer toutes les contraintes connues
  • Réduire l’espace des problèmes, en fournissant manuellement un ensemble de contraintes supplémentaires .
    Cela peut sembler contre-intuitif mais, par exemple, en fournissant un calendrier initial partiellement rempli (par exemple environ 30% des créneaux horaires), de manière à satisfaire pleinement toutes les contraintes, et en considérant ce calendrier partiel immuable, nous réduisons de manière significative temps / espace nécessaire pour produire des solutions candidates.
    Une autre façon d’aider les contraintes est par exemple «artificiellement» en ajoutant une contrainte qui empêche d’enseigner certains sujets certains jours de la semaine (s’il s’agit d’un programme hebdomadaire…); Ce type de contraintes se traduit par une réduction des espaces problèmes / solutions, sans exclure généralement un nombre important de bons candidats.
  • S’assurer que certaines des contraintes du problème peuvent être rapidement calculées. 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 choisir (ou éliminer) certaines des options.
  • Redéfinir le problème et permettre à certaines des contraintes d’être rompues, à quelques resockets (généralement vers les nœuds d’extrémité du graphique). L’idée ici est soit de supprimer certaines des contraintes liées au remplissage des derniers créneaux horaires, soit de laisser le programme automatique de génération d’horaires cesser de compléter tout le programme, en nous fournissant plutôt une liste d’une douzaine de plausibles. candidats. Un humain est souvent mieux placé pour compléter le casse-tête, comme indiqué, en cassant peut-être 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»). pour le cours “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’il est plutôt timide de fournir une réponse définitive, mais elle contient néanmoins des suggestions pratiques. J’espère que cette aide, avec ce qui est, après tout, un “problème difficile”.

C’est le bordel. un désordre royal. Pour compléter les réponses, déjà très complètes, je veux souligner mon expérience familiale. Ma mère était enseignante et participait au processus.

Il s’avère que le fait d’avoir un ordinateur pour le faire est non seulement difficile à coder en soi, mais également parce qu’il existe des conditions difficiles à spécifier pour un programme informatique précuit. Exemples:

  • un enseignant enseigne à la fois dans votre école et dans un autre institut. Clairement, s’il termine la leçon à 10h30, il ne peut pas commencer dans vos locaux à 10h30, car il a besoin de temps pour faire la navette entre les instituts.
  • deux enseignants 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. Encore une fois, 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 où la classe est dans un institut, et un autre jour où 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, où du personnel supplémentaire est requirejs).
  • certains enseignants ont des préférences pour la journée libre: certains préfèrent lundi, d’autres vendredi, d’autres mercredi. Certains préfèrent venir tôt le matin, d’autres préfèrent venir plus tard.
  • Vous ne devriez pas avoir de situation où vous avez une leçon de lecture, une histoire à la première heure, puis trois heures de mathématiques, puis une autre heure d’histoire. Cela n’a aucun sens pour les étudiants, ni pour l’enseignant.
  • vous devez répartir les arguments de manière égale. Cela n’a pas de sens d’avoir les premiers jours de la semaine uniquement en mathématiques, puis le rest de la semaine uniquement de la littérature.
  • vous devez 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, c’est NP-insane.

Ainsi, ils ont une grande table avec de petits encarts en plastique et ils déplacent les encarts jusqu’à ce qu’un résultat satisfaisant soit obtenu. Ils ne partent jamais de zéro: ils commencent normalement à partir du calendrier de l’année précédente et font des ajustements.

L’ International Timetabling Competition 2007 comportait une piste de planification des cours et une piste de planification des examens. De nombreux chercheurs ont participé à cette compétition. Beaucoup d’heuristiques et de métaheuristiques ont été essayées, mais à la fin, les métaheuristiques de recherche locales (telles que la recherche Tabu et le recuit simulé) ont clairement surpassé 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) – plus pour les universités

Une de mes affectations à mi-parcours était une génération de table d’école d’algorithme génétique.

La table entière est un “organisme”. Il y a eu quelques changements et mises en garde concernant l’approche des algorithmes génétiques génériques:

  • Des règles ont été établies pour les «tables illégales»: deux classes dans la même classe, un enseignant enseignant deux groupes en même temps, etc. Ces mutations ont été jugées immédiatement mortelles et un nouveau «organisme» a été créé à la place du «défunt». Le premier a été généré par une série d’essais aléatoires pour obtenir un test légal (si insensé). La mutation létale ne comptait pas dans le décompte des mutations dans l’itération.

  • Les mutations “d’échange” étaient beaucoup plus courantes que les mutations “Modify”. Les changements ne concernaient que des parties du gène qui avaient du sens – ne pas remplacer un enseignant par une classe.

  • De petits bonus ont été atsortingbués pour grouper certaines 2 heures ensemble, pour affecter la même salle de classe générique dans l’ordre pour le même groupe, afin de maintenir les heures de travail et la charge de classe de l’enseignant. Des bonus modérés ont été atsortingbués pour donner des classes correctes à un sujet donné, en gardant les heures de cours dans les liens (le matin ou l’après-midi), etc. Les gros bonus consistaient à atsortingbuer un nombre correct de sujets donnés, à donner une charge de travail à un enseignant, etc.

  • Les enseignants peuvent créer leurs horaires de travail “vouloir travailler alors”, “travailler ensuite”, “n’aime pas travailler alors”, “ne peut pas travailler alors”, avec des poids appropriés. 24h entier étaient des heures de travail légales sauf la nuit était très indésirable.

  • La fonction de poids … oh oui. La fonction de pondération était un produit énorme et monstrueux (comme dans la multiplication) des poids atsortingbués aux caractéristiques et propriétés sélectionnées. C’était extrêmement raide, une propriété facilement capable de le changer d’un ordre de grandeur ou plus – et il y avait des centaines ou des milliers de propriétés dans un organisme. Cela a abouti à des nombres absolument ÉNORMES en tant que poids, et en conséquence directe, vous devez utiliser une bibliothèque bignum (gmp) pour effectuer les calculs. Pour un petit test d’environ 10 groupes, 10 enseignants et 10 salles de classe, l’ensemble initial commençait par une note de 10 ^ -200 et se terminait par quelque 10 ^ + 300. C’était totalement inefficace quand c’était plus plat. En outre, les valeurs ont augmenté beaucoup plus loin avec de plus grandes “écoles”.

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

  • Le calcul (sur certains processeurs à 1 GHz) prendrait environ 1 heure pour se stabiliser près de 10 ^ + 300, générant des calendriers qui semblaient bien, pour ce scénario de test 10x10x10.

  • Le problème est facilement paralellisable en fournissant une facilité de mise en réseau qui échangerait les meilleurs spécimens entre ordinateurs exécutant le calcul.

Le programme qui en a résulté n’a jamais vu la lumière du jour me procurer une bonne note pour le semestre. Cela était prometteur mais je n’ai jamais eu assez de motivation pour append une interface graphique et la rendre utilisable par le grand public.

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

Comme d’autres l’ont mentionné, il s’agit d’un problème NP-complet, mais analysons ce que cela signifie.

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

Mais “regarder” ne vous dit pas grand-chose ce que vous devez faire.

Générer toutes les combinaisons possibles est facile. Cela peut produire une énorme quantité de données, mais vous ne devriez pas avoir beaucoup de mal à comprendre les concepts de cette partie du problème.

Le second 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, vous avez besoin de plus que “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 s’il s’agit d’une solution de travail, ce n’est peut-être pas une meilleure solution que l’alternance entre deux personnes pour que chaque enseignant fasse une semaine chacune. Oh, tu n’y as pas pensé? Rappelez-vous que ce sont des personnes avec lesquelles vous traitez, pas seulement un problème d’allocation de ressources.

Même si un enseignant pouvait travailler à plein temps pendant 16 semaines, cela pourrait être une solution sous-optimale par rapport à une solution où vous essayez d’alterner entre les enseignants, et ce type d’équilibrage est très difficile à intégrer au logiciel.

En résumé, produire une bonne solution à ce problème vaudra beaucoup pour beaucoup de gens. Par conséquent, ce n’est pas un problème facile à résoudre et à résoudre. Soyez prêt à définir des objectives qui ne sont pas 100% et à les qualifier de «suffisamment bons».

MISE À JOUR: à partir des commentaires … devrait avoir des heuristiques aussi!

J’irais avec Prolog … puis utiliser Ruby ou Perl ou quelque chose pour nettoyer votre solution dans une forme plus jolie.

teaches(Jill,math). teaches(Joe,history). involves(MA101,math). involves(SS104,history). myHeuristic(D,A,B) :- [test_case]->D='<';D='>'. createSchedule :- findall(Class,involves(Class,Subject),Classes), predsort(myHeuristic,Classes,ClassesNew), createSchedule(ClassesNew,[]). createSchedule(Classes,Scheduled) :- [the actual recursive algorithm]. 

Je suis (encore) en train de faire quelque chose de similaire à ce problème mais en utilisant le même chemin que je viens de mentionner. Prolog (comme langage fonctionnel) facilite la résolution des problèmes NP-Hard.

Les algorithmes génétiques sont souvent utilisés pour cette planification.

Nous avons trouvé cet exemple (Making Class Schedule en utilisant l’algorithme génétique) qui correspond assez bien à vos besoins.

Voici quelques liens trouvés:

Calendrier scolaire – Répertorie certains problèmes

Un algorithme génétique hybride pour les horaires scolaires

Utilitaires de planification et outils

Mon algorithme de mise en œuvre, implémenté dans FET (logiciel de programmation gratuit, http://lalescu.ro/liviu/fet/ , une application réussie):

L’algorithme est heuristique. Je l’ai appelé “échange récursif”.

Entrée: un ensemble d’activités A_1 … A_n et les contraintes.

Sortie: un ensemble de temps TA_1 … TA_n (le créneau horaire de chaque activité. Les chambres sont exclues ici pour des raisons de simplicité). L’algorithme doit mettre chaque activité à un intervalle de temps, en respectant les contraintes. Chaque TA_i est compris entre 0 (T_1) et max_time_slots-1 (T_m).

Contraintes:

C1) Basique: liste de paires d’activités qui ne peuvent être simultanées (par exemple, A_1 et A_2, car elles ont le même enseignant ou les mêmes élèves);

C2) Beaucoup d’autres contraintes (exclues ici pour simplifier).

L’algorithme de programmation (nommé “échange récursif”):

  1. Trier les activités, les plus difficiles en premier. Pas une étape critique, mais accélère l’algorithme peut-être 10 fois ou plus.
  2. Essayez de placer chaque activité (A_i) dans un intervalle de temps autorisé, en suivant l’ordre ci-dessus, un à la fois. Recherchez un emplacement disponible (T_j) pour A_i, dans lequel cette activité peut être placée en respectant les contraintes. Si plusieurs emplacements sont disponibles, choisissez-en un au hasard. Si aucun n’est disponible, effectuez un échange récursif:

    a . Pour chaque intervalle de temps T_j, considérez ce qui se passe si vous mettez A_i dans T_j. Il y aura une liste d’autres activités qui ne correspondent pas à ce mouvement (par exemple, l’activité A_k se trouve sur le même emplacement T_j et a le même enseignant ou les mêmes élèves que A_i). Conservez une liste des activités en conflit pour chaque intervalle de temps T_j.

    b . Choisissez un emplacement (T_j) avec le plus petit nombre d’activités en conflit. Disons que la liste des activités dans cet emplacement contient 3 activités: A_p, A_q, A_r.

    c . Placez A_i à T_j et faites A_p, A_q, A_r non alloué.

    d . Essayez de placer récursivement A_p, A_q, A_r (si le niveau de récursivité n’est pas trop élevé, disons 14, et si le nombre total d’appels récursifs comptés depuis l’étape 2) sur A_i a commencé, par exemple 2 * n), comme à l’étape 2).

    e . Si placé avec succès A_p, A_q, A_r, retournez avec succès, sinon essayez d’autres plages horaires (passez à l’étape 2 b) et choisissez le prochain meilleur intervalle de temps).

    f . Si tous les créneaux horaires (ou un nombre raisonnable) ont été essayés sans succès, revenez sans succès.

    g . Si nous sums au niveau 0, et que nous n’avons pas réussi à placer A_i, placez-le comme aux étapes 2 b) et 2 c), mais sans récursivité. Nous avons maintenant 3 – 1 = 2 autres activités à placer. Passez à l’étape 2) (certaines méthodes pour éviter le cyclisme sont utilisées ici).

J’ai conçu des algorithmes commerciaux pour les horaires de cours et les horaires d’examen. Pour le premier, j’ai utilisé la programmation entière; pour le second, une heuristique basée sur la maximisation d’une fonction objective en choisissant les swaps de machines à sous, très similaires au processus manuel original qui avait été développé. Les principales raisons pour lesquelles ces solutions sont acceptées sont la capacité à représenter toutes les contraintes du monde réel; et que les horodateurs humains ne soient pas en mesure de voir comment améliorer la solution. Au final, la partie algorithmique était assez simple et facile à mettre en œuvre par rapport à la préparation des bases de données, de l’interface utilisateur, de la capacité à générer des rapports statistiques sur l’utilisation des salles, l’éducation des utilisateurs, etc.

Cet article décrit assez bien le problème des horaires scolaires et leur approche de l’algorithme: ” Le développement de SYLLABUS – un planificateur interactif basé sur les contraintes pour les écoles et les collèges ” [PDF]

L’auteur m’informe que le logiciel SYLLABUS est toujours utilisé / développé ici: http://www.scientia.com/uk/

Je travaille sur un moteur de planification largement utilisé qui fait exactement cela. Oui, c’est NP-Complete; les meilleures approches cherchent à approcher une solution optimale. Et, bien sûr, il y a beaucoup de manières différentes de dire laquelle est la “meilleure” solution – est-il plus important que vos enseignants soient satisfaits de leurs horaires ou que les élèves entrent dans toutes leurs classes, par exemple?

La question la plus importante que vous devez résoudre dès le début est ce qui rend une manière de planifier ce système mieux qu’un autre . En d’autres termes, si j’ai un programme avec Mme Jones qui enseigne les mathématiques à 8 ans et M. Smith qui enseigne les mathématiques à 9 ans, est-ce mieux ou pire que d’en enseigner les deux à 10 ans? Est-ce meilleur ou pire que l’un avec Mme Jones à 8 ans et M. Jones à 2 ans? Pourquoi?

Le principal conseil que je donnerais ici est de diviser le problème autant que possible – peut-être cours après cours, peut-être enseignant par enseignant, peut-être pièce par pièce – et de travailler d’abord sur la résolution du sous-problème. Là, vous devez choisir parmi plusieurs solutions et en choisir une qui soit la plus optimale. Ensuite, le travail sur les sous-problèmes “antérieurs” prend en compte les besoins des sous-problèmes ultérieurs pour évaluer leurs solutions potentielles. Ensuite, peut-être travaillerez-vous sur la manière de vous sortir des situations peintes dans les coins (en supposant que vous ne pouvez pas anticiper ces situations dans les sous-problèmes précédents) lorsque vous arrivez à un état “sans solution valable”.

Un passage d’optimisation de la recherche locale est souvent utilisé pour “améliorer” la réponse finale afin d’obtenir de meilleurs résultats.

Notez que nous avons généralement affaire à des systèmes fortement limités en ressources dans la planification scolaire. Les écoles ne passent pas l’année avec beaucoup de salles vides ou d’enseignants assis dans le salon 75% de la journée. Les approches qui fonctionnent le mieux dans des environnements riches en solutions ne sont pas nécessairement applicables à la planification scolaire.

En général, la programmation par contraintes est une bonne approche pour ce type de problème d’ordonnancement. Une recherche sur la «programmation par contraintes» et la planification ou la «planification basée sur des contraintes» à la fois dans le débordement de stack et sur Google générera de bonnes références. Ce n’est pas impossible – il est juste un peu difficile de penser à l’utilisation des méthodes d’optimisation traditionnelles telles que l’optimisation linéaire ou entière. Un résultat serait – existe-t-il un calendrier qui répond à toutes les exigences? Cela en soi est évidemment utile.

Bonne chance !

Vous pouvez le prendre avec des algorithmes génétiques, oui. Mais tu ne devrais pas :). Il peut être trop lent et le réglage des parameters peut être trop long, etc.

Il y a d’autres approches réussies. Tous mis en œuvre dans des projets open source:

  • Approche basée sur les contraintes
    • Implémenté dans UniTime (pas vraiment pour les écoles)
    • Vous pouvez également aller plus loin et utiliser la programmation Integer. Fait avec succès à l’ université d’Udine et à l’université Bayreuth (j’y étais impliqué) en utilisant le logiciel commercial (ILOG CPLEX)
    • Approche basée sur des règles avec heuristisc – Voir planificateur Drools
  • Différentes heuristiques – FET et le mien

Voir ici pour une liste de logiciels de programmation

Je pense que vous devriez utiliser un algorithme génétique parce que:

  • Il convient mieux aux grandes instances de problèmes.
  • Cela réduit la complexité du temps pour le prix de la réponse inexacte (pas le meilleur)
  • Vous pouvez spécifier des contraintes et des préférences facilement en ajustant les punitions de remise en forme pour les non rencontrées.
  • Vous pouvez spécifier une limite de temps pour l’exécution du programme.
  • La qualité de la solution dépend du temps que vous comptez consacrer à la résolution du programme.

    Définition d’algorithmes génétiques

    Tutoriel sur les algorithmes génétiques

    Projet de planification de classe avec GA

Jetez également un oeil à: une question similaire et une autre

Je ne sais pas si quelqu’un acceptera ce code, mais j’ai développé ce code à l’aide de mon propre algorithme et travaille pour moi dans ruby. J’espère que cela les aidera à le rechercher dans le code suivant: periodflag, dayflag subjectflag et le teacherflag sont le hash avec l’identifiant correspondant et la valeur du flag qui est booléenne. Tout problème contactez moi ……. (-_-)

periodflag.each do | k2, v2 |

  if(TimetableDefinition.find(k2).period.to_i != 0) subjectflag.each do |k3,v3| if (v3 == 0) if(getflag_period(periodflag,k2)) @teachers=EmployeesSubject.where(subject_name: @subjects.find(k3).name, division_id: division.id).pluck(:employee_id) @teacherlists=Employee.find(@teachers) teacherflag=Hash[teacher_flag(@teacherlists,teacherflag,flag).to_a.shuffle] teacherflag.each do |k4,v4| if(v4 == 0) if(getflag_subject(subjectflag,k3)) subjectperiod=TimetableAssign.where("timetable_definition_id = ? AND subject_id = ?",k2,k3) if subjectperiod.blank? issubjectpresent=TimetableAssign.where("section_id = ? AND subject_id = ?",section.id,k3) if issubjectpresent.blank? isteacherpresent=TimetableAssign.where("section_id = ? AND employee_id = ?",section.id,k4) if isteacherpresent.blank? @finaltt=TimetableAssign.new @finaltt.timetable_struct_id=@timetable_struct.id @finaltt.employee_id=k4 @finaltt.section_id=section.id @finaltt.standard_id=standard.id @finaltt.division_id=division.id @finaltt.subject_id=k3 @finaltt.timetable_definition_id=k2 @finaltt.timetable_day_id=k1 set_school_id(@finaltt,current_user) if(@finaltt.save) setflag_sub(subjectflag,k3,1) setflag_period(periodflag,k2,1) setflag_teacher(teacherflag,k4,1) end end else @subjectdetail=TimetableAssign.find_by_section_id_and_subject_id(@section.id,k3) @finaltt=TimetableAssign.new @[email protected]_struct_id @[email protected]_id @finaltt.section_id=section.id @finaltt.standard_id=standard.id @finaltt.division_id=division.id @[email protected]_id @finaltt.timetable_definition_id=k2 @finaltt.timetable_day_id=k1 set_school_id(@finaltt,current_user) if(@finaltt.save) setflag_sub(subjectflag,k3,1) setflag_period(periodflag,k2,1) setflag_teacher(teacherflag,k4,1) end end end end end end end end end end end