Algorithme pour la création d'un horaire scolaire

c'est le bordel. un embêtement royal. Pour ajouter aux réponses, déjà très complètes, je tiens à souligner mon expérience familiale. Ma mère était enseignante et participait au processus.

S'avère que d'avoir un ordinateur pour le faire est non seulement difficile à coder en soi, il est également difficile parce qu'il ya des conditions qui sont difficiles à spécifier à un programme d'ordinateur pré-cuit. Exemples:

• un professeur enseigne à la fois à votre l'école et à un autre institut. De toute évidence, s'il termine la leçon à 10h30, il ne peut pas commencer à 10h30 dans vos locaux, car il a besoin de 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 professeurs 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 pour éviter les deux enseignants à enseigner dans une classe spécifique de l'enfant.
• l'école est séparée des installations, 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, lorsque du personnel supplémentaire est nécessaire).
• certains enseignants ont des préférences pour le journée libre: certains préfèrent le lundi, certains sur vendredi, le mercredi. Certains préfèrent venir tôt le matin, certains préfèrent venir plus tard.
• vous ne devriez pas avoir des situations où vous avez une leçon de dire, histoire à la première heure, puis trois heures de mathématiques, puis une autre heure de l'histoire. Cela n'a pas de sens pour les élèves, ni pour l'enseignant.
• vous devez répartir les arguments uniformément. Il ne fait pas de sens d'avoir les premiers jours dans la semaine des mathématiques, et puis le reste de la semaine de 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, c'est NP-fou.

donc ce qu'ils font est qu'ils ont une grande table avec de petits inserts en plastique, et ils déplacent les inserts autour jusqu'à ce qu'un résultat satisfaisant est obtenu. Ils ne partent jamais de zéro: ils partent normalement du calendrier de l'année précédente et procéder à des ajustements.

le "International Timetrabling Competition 2007 avait une voie d'horaire de cours et une voie d'horaire d'examen. De nombreux chercheurs ont participé à ce concours. Beaucoup d'heuristiques et de métaheuristiques ont été essayées, mais en fin de compte, les métaheuristiques locales de recherche (telles que la recherche Tabu et le recuit simulé) clairement battre d'autres algorithmes (tels que les algorithmes génétiques).

jetez un coup d'oeil aux 2 cadres open source utilisé par certains des finalistes:

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

L'une de mes demi-affectations était une génération de tables d'école à Algorithme génétique.

table entière est un "organisme". Certains changements et mises en garde ont été apportés à 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 enseignant deux groupes en même temps, etc. Ces mutations ont été considérées comme mortelles immédiatement et un nouvel" organisme " a été lieu du" défunt " immédiatement. La première a été générée par une série d'essais aléatoires pour obtenir une légale (si insensée). La mutation létale n'a pas été prise en compte pour le compte des mutations dans l'itération.

• les mutations "D'échange" étaient beaucoup plus fréquentes que les mutations "modifiables". Les changements ne se sont produits qu'entre les parties du gène qui avaient du sens - aucun enseignant n'a été remplacé par une salle de classe.

• les petites primes étaient assigné pour grouper certains 2 heures ensemble, pour assigner la même salle de classe générique dans l'ordre pour le même groupe, pour maintenir les heures de travail de l'enseignant et la charge de la classe continue. Des primes modérées ont été attribuées pour donner des salles de classe correctes pour une matière donnée, en gardant les heures de classe à l'écart (matin ou après-midi), et ainsi de suite. Les primes élevées étaient destinées à l'attribution d'un nombre correct de matières données, d'une charge de travail donnée pour un enseignant, etc.

• les enseignants pourraient créer leur horaire de travail est le suivant:" je veux travailler alors"," j'accepte de travailler alors"," je n'aime pas travailler alors"," je ne peux pas travailler alors", avec les poids appropriés. 24 heures entières étaient des heures de travail légales, sauf que le temps de nuit était très indésirable.

• la fonction de poids... oh ouais. La fonction de poids était énorme, produit monstrueux (comme dans la multiplication) de poids attribués à des caractéristiques et des propriétés sélectionnées. Il était extrêmement raide, une propriété facilement capable de le changer par 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 organisme. Il en a résulté des nombres absolument énormes que les poids, et comme résultat direct, besoin d'utiliser une bibliothèque de bignum (gmp) pour effectuer les calculs. Pour un petit banc d'essai d'environ 10 groupes, 10 enseignants et 10 salles de classe, l'ensemble initial a commencé par une note de 10^-200something et s'est terminé par 10^+300something. Il était totalement inefficace quand il était plus plat. En outre, les valeurs ont augmenté une distance beaucoup plus large avec de plus grandes "écoles".

• 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 sur le même produit avec la même qualité.

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

• le problème est facilement paralysable en fournissant une facilité de réseau qui permettrait l'échange des meilleurs spécimens entre les ordinateurs exécutant le calcul.

le programme résultant n'a jamais vu la lumière du jour à l'extérieur m'obtenir une bonne note pour le semestre. Il a montré une certaine promesse, mais je n'ai jamais eu assez de motivation pour ajouter une interface graphique et le 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 regarder toutes les combinaisons possibles.

mais "regardez" ne vous dit pas grand chose sur ce que vous devez faire.

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

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

pour cela vous avez besoin de plus que juste "est-il une solution possible".

par exemple, le même enseignant travaille-t-il 5 jours par semaine pendant X semaines d'affilée? Même si c'est une solution de travail, il pourrait ne pas être une meilleure solution que alterner entre deux personnes pour que chaque professeur fasse une semaine chacun. Oh, vous n'avez pas pensé? Rappelez-vous qu'il s'agit de gens avec qui vous avez affaire, et pas seulement d'un problème d'affectation des 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ù vous essayez d'alterner entre les enseignants, et ce genre d'équilibre est très difficile à intégrer dans les logiciels.

pour résumer, produire une bonne solution à ce problème vaudra beaucoup, pour beaucoup de gens. Par conséquent, il n'est pas un problème facile à briser et à résoudre. Soyez prêt à fixer des objectifs qui ne sont pas à 100% et à les qualifier de "suffisamment bons".

mise à JOUR: à partir de commentaires ... il devrait y avoir des heuristiques aussi!

J'irais avec Prolog ... puis utilisez 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 (en tant que langage fonctionnel) rend vraiment la résolution de problèmes NP-Hard plus facile.

algorithmes génétiques sont souvent utilisés pour une telle planification.

Trouvé cet exemple (en Faisant d'Horaire des cours à l'Aide de l'Algorithme Génétique) , qui correspond à votre exigence assez bien.

voici quelques liens que j'ai trouvés:

horaire scolaire - liste des problèmes rencontrés

algorithme génétique hybride pour les horaires scolaires

planification des services publics et des outils

mon algorithme d'ordonnancement, mis en œuvre dans FET (logiciel D'ordonnancement libre, http://lalescu.ro/liviu/fet / , a successful application):

L'algorithme est heuristique. Je la nomme "récursive échange".

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 la simplicité). Algorithme doit mettre chaque activité à un créneau horaire, en respectant les contraintes. Chaque TA_i se situe entre 0 (T_1) et max_time_slots-1 (T_m).

Contraintes:

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

C2) beaucoup d'autres contraintes (exclues ici, pour des raisons de simplicité).

l'algorithme de programmation (qui I nommé "échange récursif"):

1. Classez les activités, les plus difficiles d'abord. Ne critique pas, mais accélère l'algorithme peut être 10 fois ou plus.

2. essayez de placer chaque activité (A_i) dans un créneau horaire autorisé, en suivant l'ordre ci-dessus, une à la fois. Recherchez un créneau disponible (T_j) pour A_i, dans lequel cette activité peut être placée en respectant les contraintes. Si plus de logements disponibles, choisir un au hasard. Si aucun n'est disponible, faites un échange récursif:

   un . Pour chaque fente 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 sont pas d'accord avec ce déplacement (par exemple, l'activité A_k est sur le même slot T_j et a le même enseignant ou les mêmes élèves que A_i). Gardez une liste d'activités conflictuelles pour chaque tranche horaire T_j.

   b . Choisissez une fente (T_j) avec le nombre le plus bas des activités conflictuelles. Supposons que la liste des activités dans cette fente contient 3 activités: A_p, A_q, A_r.

   c . Placez A_i à T_j et rendez A_p, A_q, A_r non attribué.

   d . Essayez de placer récursivement A_p, A_q, A_r (si le niveau de récursion n'est pas trop grand, disons 14, et si le nombre total d'appels récursifs comptés depuis l'étape 2) sur A_i began n'est pas trop grand, disons 2*n), comme à l'étape 2).

   e . Si vous avez réussi à placer A_p, A_q, A_r, revenez avec succès, sinon essayez d'autres créneaux horaires (passez à l'étape 2 b) et choisissez le meilleur créneau horaire suivant).

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

   g . Si nous sommes 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écursion. Nous avons maintenant 3 - 1 = 2 autres activités à mettre en place. Passez à l'étape 2) (certaines méthodes pour éviter le vélo sont utilisés ici).

j'ai conçu des algorithmes commerciaux pour les horaires de classe et 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 des slots swaps, très similaire au processus manuel original qui avait été développé. Pour que de telles solutions soient acceptées, il faut avant tout pouvoir représenter toutes les contraintes du monde réel et, pour les responsables de l'emploi du temps, ne pas être en mesure de trouver des moyens d'améliorer la situation. solution. En fin de compte, la partie algorithmique était assez simple et facile à mettre en œuvre par rapport à la préparation des bases de données, l'interface utilisateur, la capacité de rendre compte des statistiques comme l'utilisation de la salle, l'éducation des utilisateurs et ainsi de suite.

Ce document décrit le calendrier de l'école de problème et de leur approche de l'algorithme assez bien: " Le Développement de SYLLABUS Interactif, à Base de contraintes Planificateur pour les Écoles et les Collèges. "[PDF]

l'auteur m'informe que le logiciel SYLLABUS est encore utilisé / développé ici: http://www.scientia.com/uk/

je travaille sur un moteur de planification largement utilisé qui fait exactement cela. Oui, il est NP-complet; les meilleures approches cherchent à se rapprocher d'une solution optimale. Et, bien sûr, il ya beaucoup de façons différentes de dire laquelle est la "meilleure" solution - est-il plus important que vos professeurs sont heureux avec leurs annexes, ou que les élèves reçoivent dans toutes leurs classes, par exemple?

la question la plus importante que vous devez résoudre rapidement est qu'est-ce qui fait qu'une façon de programmer ce système est meilleure qu'une autre ? C'est-à-dire, si J'ai un horaire avec Mme Jones qui enseigne les maths à 8 ans et M. Smith qui enseigne les maths à 9 ans, est-ce mieux ou pire qu'un horaire où les deux enseignent les maths à 10 ans? Est-ce mieux ou pire qu'une avec Mme Jones qui enseigne à 8 ans et M. Jones qui enseigne à 2 ans? Pourquoi?

Le principal conseil que je donnerais ici est de diviser le problème autant que possible - peut-être, cours par cours, peut-être par l'enseignant professeur, peut - être pièce par pièce-et travailler à résoudre le sous-problème d'abord. Là, vous devriez vous retrouver avec plusieurs solutions à choisir, et besoin de choisir une comme la plus probable optimale. Ensuite, les sous-problèmes "antérieurs" tiennent compte des besoins des sous-problèmes ultérieurs dans la notation de leurs solutions potentielles. Ensuite, peut-être travailler sur la façon de vous sortir des situations peints-dans-le-coin (en supposant que vous ne pouvez pas anticiper ces situations dans les sous-problèmes plus tôt) quand vous arrivez à un "pas de solutions valables" de l'état.

un passe d'optimisation de recherche locale est souvent utilisé pour" polir " la réponse finale pour de meilleurs résultats.

notez qu'en général, nous avons affaire à des systèmes très limités en termes de ressources dans les horaires scolaires. Les écoles ne passent pas l'année avec beaucoup de chambres vides ou de professeurs 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 dans les horaires scolaires.

en général, la programmation contrainte est une bonne façon d'aborder ce type de problème d'horaire. Une recherche sur la " programmation de contraintes "et la programmation ou la" programmation basée sur les contraintes " à la fois dans stack overflow 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'aide des méthodes traditionnelles d'optimisation comme l'optimisation linéaire ou entière. Une sortie serait un calendrier existent qui satisfait à toutes les exigences? Que, en lui-même, est évidemment utile.

bonne chance !

vous pouvez le prendre avec des algorithmes génétiques, Oui. Mais vous ne devriez pas :). Il peut être trop lent et le réglage des paramètres peut prendre trop de temps, etc.

il existe d'autres approches réussies. Tous mis en œuvre dans des projets open source:

• approche fondée sur les contraintes
  • mis en place dans UniTime (pas vraiment pour les écoles)
  • vous pouvez également aller plus loin et utiliser Integer programmation. Fait avec succès à Université Udine et aussi à L'Université Bayreuth( j'y étais impliqué) en utilisant le logiciel commercial (ILOG CPLEX)
  • Règle approche fondée sur les heuristisc - Voir Bave planner
• Différentes heuristiques FET et mon

voir ici pour une liste de logiciels d'ordonnancement

je pense que vous devriez utiliser l'algorithme génétique parce que:

• il est le mieux adapté pour les grandes instances de problème.
• Il produit de la réduction du temps de la complexité sur le prix de la réponse inexacte(Pas l'ultime best)
• vous pouvez spécifier des contraintes et des préférences facilement en ajustant des punitions de fitness pour ceux qui ne sont pas rencontrés.
• vous pouvez spécifier le délai d'exécution du programme.

• la qualité de la solution dépend de combien de temps vous avez l'intention de passer à résoudre le programme..

  Algorithmes Génétiques Définition

  Algorithmes Génétiques Tutoriel

  Classe d'ordonnancement de projet avec GA

regardez aussi: une question similaire et un autre

je ne sais pas tout d'accord avec ce code mais j'ai développé ce code avec l'aide de mon propre algorithme et travaille pour moi en ruby.Espérons que cela aidera ceux qui le cherchent dans le code suivant le parodflag, le dayflag subjectflag et le teacherflag sont le hachage avec l'id correspondant et la valeur de drapeau qui est booléen. Toute question me contacter.......(- _- )

periodflag.chaque do / k2, v2 / 151920920"

            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
                                                @finaltt.timetable_struct_id=@subjectdetail.timetable_struct_id
                                                @finaltt.employee_id=@subjectdetail.employee_id
                                                @finaltt.section_id=section.id
                                                @finaltt.standard_id=standard.id
                                                @finaltt.division_id=division.id
                                                @finaltt.subject_id=@subjectdetail.subject_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