Quel algorithme utiliser pour générer un tableau de temps pour les écoles?

Question

Je travaille sur une application simple qui va générer des horaires (planificateur journalier) pour les écoles. J'ai lu les bases des algorithmes, mais je ne sais pas par où commencer.

Le problème:
Allouer enseignants aux classes prenant en compte un grand nombre de contraintes comme:
1) Sujet
2) Expertise de l'enseignant
3) Pas plus de 2 classes en continu .. etc

Il va sans dire qu'il ne devrait pas y avoir de chevauchement. Fondamentalement, j'ai besoin d'affecter N enseignants à M classes avec un nombre fixe d'heures de travail tous les jours (8).

Les entrées:
1) Nombre total de classes
2) Les enseignants ainsi que leur sujet expertise
3) Sujets/Cours pour chaque classe
4) Nombre de cours par classe par jour
5) d'autres contraintes flexibles comme les heures de travail minimum/maximum pour un enseignant par jour, les heures de travail au total par enseignant par semaine, etc.

Mes questions: 1)
Est-il juste le considérer comme un problème d'affectation avec plusieurs contraintes?
2) Quel algorithme dois-je utiliser? (Algorithme hongrois?)
3) Dois-je commencer par obtenir l'ensemble des contraintes en une seule fois, puis générer la table, ou devrait-elle être faite dans les étapes intermédiaires? Je suis un débutant pour apprendre/implémenter des algorithmes, donc toute aide pour me diriger dans la bonne direction est appréciée! Merci.

Answer 1

Vous avez choisi un doozy d'un problème pour commencer. L'optimisation de planification comme ceci est NP complète. Il y a une tonne de documents sur la façon de traiter des problèmes comme celui-ci, la classe de problème est connue sous le nom de satisfaction des contraintes. Vous pouvez effectuer une recherche exhaustive qui est la plus simple mais qui prend également beaucoup de temps, si vous avez plus d'une poignée de classes cela ne fonctionnera pas. Vous pourriez jeter un oeil à la base de solveur qui est une suite d'outil pour .net pour résoudre ce genre de choses. Scott Hanselman a fait un podcast à ce sujet ici http://www.hanselminutes.com/default.aspx?showID=209 et vous pouvez trouver plus à ce sujet ici http://code.msdn.microsoft.com/solverfoundation. Si vous avez envie de le faire vous-même, essayez de regarder GSAT ou sinon certains de ces algorithmes évolutionnaires semblent intéressants http://www.springer.com/engineering/book/978-3-540-48582-7.

Answer 2

Cette question revient régulièrement au moins une fois par semaine ici et les réponses (y compris la mienne) sont toujours les mêmes. Je pense que nous devrions créer une balise spécifique sur les algorithmes de planification si elle n'existe pas. Je réitérerai que la technique de solution la plus appropriée pour planifier de tels problèmes est dans le domaine de la programmation par contraintes. Alors que d'autres techniques d'optimisation sont OK pour les petits problèmes, la formulation est souvent douloureuse pour certaines contraintes. Considérez toutes les variables entières que vous devez créer pour certaines contraintes simples. Parce que le problème nécessite souvent un tas de plannings réalisables (ou pour déterminer l'infaisabilité) plutôt qu'une solution optimale, le CP est l'approche préférée puisque c'est ce qu'il est conçu pour faire. La plupart des autres approches demandent à un utilisateur de "forcer" une condition d'optimalité sur le problème là où il n'y en a pas vraiment.