Enseignant horaire algorithme

C'est un problème de mappage: vous devez mapper à chaque heure dans une semaine et chaque enseignant une activité (enseigner à une certaine classe ou heure gratuite).

Diviser le problème:

1. créez la liste des enseignants, des classes et des préférences, puis laissez l'utilisateur remplir certaines des préférences sur une carte pour avoir comme point de départ.
2. prenez au hasard un élément de la liste et placez-le à une position libre aléatoire sur la carte si elle ne traverse aucune vérification de santé mentale jusqu'à ce que la liste soit vide. Si à une certaine itération, vous ne pouvez pas placer un élément sur la carte sans franchir un contrôle de santé mentale, décaler deux positions sur la carte et réessayer.
3. Lorsque la carte est remplie, essayez de déplacer les positions sur la carte pour optimiser le résultat.

Dans les étapes 2 et 3 montrent chaque itération à l'utilisateur: les éléments laissés dans la liste, les positions sur la carte et le prochain déplacement calculé et permettent à l'utilisateur d'intervenir.

Je n'ai pas essayé ceci, mais ce serait mon approche initiale.

J'ai abordé des problèmes de planification/planification similaires dans le passé et la technique D'IA qui est souvent la mieux adaptée à cette classe de problème est le "raisonnement basé sur les contraintes".

C'est essentiellement une méthode de force brute comme L'a suggéré Laurenty, mais l'approche consiste à appliquer des contraintes dans un ordre efficace pour provoquer l'échec rapide des solutions irréalisables - pour minimiser le calcul requis.

Googler "raisonnement basé sur les contraintes" apporte beaucoup de ressources sur le technique et son application aux problèmes de planification.

Répondre à ma propre question:

Le projet FET mentionné par gnud utilise cet algorithme:

Quelques mots sur l'algorithme: FET utilise un algorithme heuristique, plaçant les activités, en commençant par les moments les plus difficiles. Si elle ne peut pas trouver une solution à la activités impossibles potentielles, donc vous pouvez corriger les erreurs. Algorithme échange récursivement les activités si est possible pour faire de la place pour une nouvelle activité, ou, dans les cas extrêmes, backtracks et commutateurs ordre de évaluation. Le code est dans src / moteur / générer.rpc. S'il vous plaît e-mail moi pour plus de détails ou rejoindre le mailing liste. L'algorithme imite le fonctionnement d'un temporisateur humain, I penser.

Lien

Le suivi du "raisonnement basé sur la contrainte" mené par un logiciel rigoureux sur Wikipedia m'a conduit à ceux-ci pages {[10] } qui ont un paragraphe intéressant:

Résolution d'un contrainte satisfaction problème sur un domaine fini est un NP-problème complet en général. La recherche a montré un certain nombre de polynôme temps subcases, surtout obtenu en restreignant soit la domaines ou contraintes autorisés ou le façon dont les contraintes peuvent être placées sur le variable. La recherche a également relations établies de la contrainte satisfaction problème avec problèmes dans d'autres domaines tels que finis théorie des modèles et bases de données.

Cela me rappelle ce blog sur la planification d'une conférence , avec une explication vidéo ici .

Comment je le ferais:

Demandez à la population d'inclure deux choses:

• qui enseigne quelle classe (je m'attends à ce que les enseignants enseignent un sujet).
• Ce qu'une classe prend sur un créneau horaire spécifique.

De cette façon, nous ne pouvons pas avoir de conflits (un enseignant à 2 endroits, ou une classe ayant deux matières en même temps).

La forme physique la fonction inclurait:

• combien de créneaux horaires chaque enseignant donne par semaine.
• combien d'intervalles de temps un enseignant a le même jour (ils ne peuvent pas avoir une journée complète d'enseignement, cela aussi doit être équilibré).
• combien d'intervalles de temps du même sujet une classe A le même jour (ils ne peuvent pas avoir une journée complète de mathématiques!).

Peut-être prendre l'écart-type pour tous, car ils devraient être équilibrés.

Je ne suis pas sûr si cela couvre le même terrain que la réponse@Stringent Software (car le nom est légèrement différent), mais j'ai quelques très bons amis qui font des recherches sur le domaine de la programmation par contraintes . La création d'horaires est une application de leur recherche.

Dr Chris Jefferson a créé un programme appelé Minion que vous pouvez télécharger à partir de SourceForge, et est un résolveur de problème de contrainte de force brute très rapide écrit en C++

Je pense que vous pourriez manquer quelques contraintes.

On préférerait, dans la mesure du possible, que les enseignants soient programmés pour les classes pour lesquelles ils sont certifiés.

On soupçonnerait que les classes demandées et le nombre d'effectifs attendu dans chacune seraient significatifs.

Je pense que le point de départ serait de lister toutes vos contraintes, de trouver une structure de données pour les représenter.

Ensuite, créez une sorte de moteur pour construire une solution d'essai, puis évalue pour la forme physique en fonction des contraintes.

Vous pourriez alors lancer la partie amusante des algorithmes génétiques, et voir si vous pouvez obtenir la forme physique pour augmenter au fil du temps que les gènes se mélangent.

Commencez par un petit ensemble de contraintes, et augmentez-les à mesure que vous voyez le succès (si vous voyez le succès)

Il pourrait y avoir un moyen de prendre les contraintes et de les serrer avec quelque chose comme un algorithme de programmation linéaire.

Je suis d'accord. Il sonne comme un plaisir défi

L'une des pires pages web open source jamais, mais le projet semble prometteur: http://www.lalescu.ro/liviu/fet/

Un aproach basé sur le web:
phpScheduleIt (pas spécifique à l'école)

Regarder cette question m'a fait penser sur ce problème, et si les algorithmes génétiques seraient utilisables dans ce cas. Cependant ce serait joli dur à muter possibilités maintenir les règles de contrôle de santé mentale. En outre ce n'est pas clair pour moi comment distinguer les exigences incompatibles.

Algorithmes Génétiques sont très bien adaptés à des problèmes comme cela. Une fois que vous venez avec une représentation décente du chromosome (dans ce cas, probablement un vecteur représentant tous les emplacements de classe disponibles) vous êtes la plupart du temps là-bas.

Ne vous inquiétez pas de maintenir les contrôles de santé mentale pendant la phase de mutation. La Mutation est aléatoire. Les contrôles de santé mentale et de préférence appartiennent tous deux à la phase de sélection. Un échec du contrôle de santé mentale réduirait considérablement la condition physique d'un individu, tandis qu'une préférence ratée ne ferait que légèrement baisser la condition physique.

Les exigences incompatibles sont un problème complètement différent. Si elles sont complètement incompatibles, vous obtenez une population qui ne converge sur rien d'utile.

Bonne chance. Être le fils d'un père avec ce genre de problème est ce qui m'a amené au groupe de recherche dans lequel je me suis retrouvé ...

Quand j'étais enfant, mon père programmait des officiels de match dans une ligue sportive locale, cela avait une longue liste de contraintes et j'ai essayé d'écrire quelque chose pour aider. Quand je suis arrivé à L'Université, Je l'ai même utilisé comme mon projet de dernière année s'installant finalement sur une implémentation de Monte Carlo (en utilisant un modèle de recuit simulé).

L'idée de base est que si ce n'est pas NP, c'est assez proche, donc plutôt que de supposer qu'il y a une solution, je chercherais à trouver le meilleur dans un délai donné. Je pondérerais toutes les contraintes avec les coûts pour les casser: les contrôles de santé mentale auraient des coûts énormes, les préférences auraient des coûts plus bas (mais augmenter pour plus de pauses, donc le casser une fois serait moins de la moitié du coût de le casser deux fois).

L'idée de base est que j'ai commencé avec une solution 'aléatoire' et l'ai chiffrée; puis j'ai fait des changements en échangeant un petit nombre d'affectations, en le réévaluant, puis en acceptant ou en refusant le changement de façon probalistique.

Après des milliers d'itérations, vous vous rapprochez d'une solution acceptable.

Croyez-moi, cependant, que cette classe de problèmes a des groupes de recherche qui produisent des doctorats, donc vous êtes en très bonne compagnie.

Vous pourriez également trouver un certain intérêt dans le domaine de la programmation linéaire, par exemple simplex et ainsi de suite.

Oui, je pense que C'est NP complet - ou du moins pour trouver la solution optimale est NP complet.

J'ai travaillé sur un problème similaire au collège quand j'ai dit au Père d'un ami (qui était enseignant) que je pouvais résoudre ses problèmes d'horaire pour lui s'il ne trouvait pas de programme approprié (c'était en 1990)

Je n'avais aucune idée de ce dans quoi je me suis embarqué. Heureusement pour nous, tout ce que j'avais à faire était de trouver une solution qui correspondait aux contraintes. Mais dans mes tests j'étais toujours inquiet A propos de déterminer S'il y avait une solution du tout. Il n'a jamais eu trop de contraintes et le programme a utilisé différentes heuristiques et suivi arrière. Il a été beaucoup de plaisir.

Je pense que Bill Gates a aussi travaillé sur un système comme celui - ci au lycée ou à l'université pour son lycée. Ne sais pas si.

Bonne chance. Toutes mes notes ont disparu et je n'ai jamais eu le temps de mettre en œuvre une solution que je pourrais commercialiser. C'était un projet de spécialité que j'ai recodé au fur et à mesure que j'apprenais de nouvelles langues (de base, Régime, C, VB, C++)

Amusez-vous avec

Je vois que ce problème peut être résolu par le programme Prolog en le connectant à une base de données et le programme peut rendre le calendrier donné un ensemble de contraintes lire abt "prologue de problème de satisfaction de contrainte"