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:
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:
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:
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”):
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:
Voir ici pour une liste de logiciels de programmation
Je pense que vous devriez utiliser un algorithme génétique parce que:
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