Algorithme de l'horaire des enseignants

Question

C’est un problème qui me préoccupe depuis longtemps. En tant que fils d’enseignant et de programmeur, j’ai eu l’impression de l’avenir… mais je n’ai toujours pas trouvé de solution.

C'est donc le problème. Il faut créer un emploi du temps pour une école, en utilisant certaines contraintes. Ceux-ci sont généralement divisés en deux catégories:

Contrôles de santé mentale

• Un enseignant ne peut pas enseigner deux cours en même temps
• Un étudiant ne peut pas suivre deux leçons en même temps
• Certains enseignants doivent avoir au moins un jour de congé au cours de la semaine
• Tous les jours de la semaine doivent être couverts par l'horaire
• Le sujet X doit avoir exactement untel heures par semaine
• ...

Préférences

• L’horaire de chaque enseignant doit être le plus compact possible (l’enseignant doit travailler toute la journée de la journée, sans interruption si possible)
• Les enseignants qui ont des jours de congé doivent pouvoir exprimer leur préférence pour quel jour
• Les enseignants qui travaillent à temps partiel devraient pouvoir exprimer leur préférence de travailler au début ou à la fin de la journée d'école.
• ...

Maintenant, après quelques années passées à ne pas trouver de solution (et à apprendre une chose ou deux en attendant ...), je me suis rendu compte que cela sentait le problème du NP-difficile.

Est-il prouvé que NP-difficile?

Quelqu'un at-il une idée sur la façon de casser cette chose?

En regardant cette question a été posée Je pense à ce problème et à la question de savoir si des algorithmes génétiques seraient utilisables dans ce cas. Cependant, il serait assez difficile de muter les possibilités tout en maintenant les règles de vérification de la santé mentale. En outre, il m'est difficile de savoir comment distinguer les exigences incompatibles.

Un petit addenda pour mieux préciser le problème. Cela s'applique aux classes de style italien où tous les élèves sont associés dans différentes classes (par exemple: année 1, section A) et où les enseignants se déplacent d'une classe à l'autre. Tous les élèves de la même classe ont le même horaire et n'ont pas le choix quant aux leçons à suivre.

Answer 1

Je suis l'un des développeurs qui travaillent sur la partie programmateur d'un système d'information sur les étudiants. Lors de notre approche initiale du problème de planification, nous avions recherché des algorithmes génétiques pour résoudre les problèmes de satisfaction de contrainte, et même si nous avions réussi au départ, nous avons réalisé qu'il existait une solution moins compliquée au problème (après avoir assisté à un atelier de planification scolaire)

Notre implémentation actuelle fonctionne très bien et utilise la force brute avec des heuristiques intelligentes pour obtenir un planning valide dans un court laps de temps. L’horaire principal (affectation des classes aux enseignants) est d’abord construit en prenant en compte toutes les contraintes de chaque enseignant tout en minimisant les risques de conflits pour les étudiants (en fonction de leurs demandes de cours). Les étudiants sont ensuite programmés dans les classes selon la même méthode.

Cette opération vous permet de faire en sorte que la machine crée d'abord un calendrier principal, puis de la modifier manuellement si nécessaire.

L’implémentation actuelle du planificateur est écrite en perl, mais Prolog et CLIPS (système expert) ont également été visionnées précédemment

.

Answer 2

Ceci est un problème de mappage: vous devez définir chaque activité de la semaine et de chaque enseignant une activité (enseigner à une classe ou à une heure gratuite).

Divisez le problème:

1. Créez la liste des enseignants, des classes et des préférences, puis laissez l'utilisateur renseigner certaines des préférences sur une carte comme point de départ.
2. Prenez un élément de la liste au hasard et mettez-le à un emplacement libre au hasard sur la carte. s'il ne passe aucun contrôle de cohérence jusqu'à ce que la liste soit vide. Si, à une certaine itération, vous ne pouvez pas placer un élément sur la carte sans passer par un contrôle de cohérence, déplacez deux positions sur la carte et réessayez.
3. Lorsque la carte est remplie, essayez de déplacer les positions sur la carte pour optimiser le résultat.

Aux étapes 2 et 3, montrez chaque itération à l'utilisateur: les éléments restants dans la liste, les positions sur la carte et le prochain déplacement calculé, puis laissez l'utilisateur intervenir.

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

Answer 3

J'ai déjà abordé des problèmes de planification / planification similaires dans le passé et la technique d'IA qui convient le mieux à cette catégorie de problèmes est le "raisonnement par contrainte".

C’est fondamentalement une méthode de force brute, comme l’a suggéré Laurenty, mais cette approche implique l’application de contraintes dans un ordre efficace pour que les solutions irréalisables échouent rapidement - afin de minimiser le calcul requis.

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

Answer 4

Répondant à 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 à tour de rôle, en commençant par   les plus difficiles. Si ça ne peut pas   trouver une solution, il vous dirige vers le   activités impossibles potentielles, donc   vous pouvez corriger les erreurs. L'algorithme   échange d'activités récursivement si   est possible afin de faire de la place pour   une nouvelle activité ou, dans des cas extrêmes,   retour en arrière et commutateurs ordre de   évaluation. Le code important est en   src / engine / generate.cpp. S'il vous plaît envoyer un courriel   moi pour plus de détails ou rejoindre le mailing   liste. L'algorithme imite le   fonctionnement d'un horloge humaine, je   penser.

Lien

Suivi du "Raisonnement basé sur les contraintes" dirigé par Stringent Software sur Wikipedia me conduit à ces pages qui ont un paragraphe intéressant:

  

Résoudre une satisfaction de contrainte   problème sur un domaine fini est un   Problème NP-complet en général.   La recherche a montré un certain nombre de   sous-cas de temps polynomial, principalement   obtenu en limitant soit la   domaines autorisés ou contraintes ou la   les contraintes de manière peuvent être placés sur la   variables. La recherche a également   relation établie de la   problème de satisfaction de contrainte avec   problèmes dans d'autres domaines tels que fini   théorie des modèles et bases de données.

Answer 5

Cela me rappelle cette billet de blog sur la planification d'une conférence , avec un 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 une matière).
• Ce qu'une classe prend à 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 fonction fitness comprendrait:

• Combien de créneaux horaires donne chaque enseignant par semaine.
• Combien de créneaux horaires un enseignant a-t-il le même jour (ils ne peuvent pas passer toute une journée à enseigner, cela aussi doit être équilibré).
• Combien de créneaux horaires ont le même sujet dans une classe le même jour (ils ne peuvent pas avoir une journée complète de maths!).

Prenez peut-être l’écart type pour chacun d’entre eux car ils doivent être équilibrés.

Answer 6

Je ne sais pas si cela couvre le même motif que @Stringent Software répondre (car le nom est légèrement différent), mais j'ai quelques très bons amis qui étudient la zone Programmation par contraintes . La création d’horaires est une des applications de leurs recherches.

M. Chris Jefferson a créé un programme appelé Minion que vous pouvez télécharger depuis SourceForge, et qui est un solutionneur de problèmes de contrainte de force brute très rapide écrit en C ++

Answer 7

Je pense qu'il vous manque peut-être des contraintes.

On préférerait, dans la mesure du possible, que les enseignants soient affectés aux cours pour lesquels ils sont certifiés.

On pourrait penser que les classes demandées et l’effectif attendu dans chacune d’elles 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.

Créez ensuite une sorte de moteur qui construit une solution d’essai, puis évaluez son adéquation en fonction des contraintes.

Vous pouvez ensuite lancer la partie amusante des algorithmes génétiques et voir si vous pouvez avoir la capacité d'augmenter au fil du temps à mesure que les gènes se mélangent.

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

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

Je suis d'accord. Cela ressemble à un défi amusant

Answer 8

L’une des pires pages Web open source de tous les temps, mais le projet semble prometteur: http://www.lalescu.ro/liviu/fet/

Une approche Web:
phpScheduleIt (non spécifique à l'école)

Answer 9

  

En regardant cette question m'a fait réfléchir   à propos de ce problème, et si   des algorithmes génétiques seraient utilisables dans   ce cas. Cependant ce serait joli   difficile de muter les possibilités tout en   maintenir les règles de vérification de la santé mentale.   En outre, il m'est difficile de savoir comment   distinguer les exigences incompatibles.

Les algorithmes génétiques sont très bien adaptés à de tels problèmes. Une fois que vous obtenez une représentation décente du chromosome (dans ce cas, il s’agit probablement d’un vecteur représentant tous les emplacements de classe disponibles), vous y êtes pratiquement.

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

Les exigences incompatibles constituent un problème totalement différent. S'ils sont complètement incompatibles, vous obtiendrez une population qui ne convergera pas vers quelque chose d'utile.

Answer 10

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

Quand j'étais enfant, mon père avait prévu des officiels de match dans une ligue de sport locale. La liste de contraintes était également longue et j'ai essayé d'écrire quelque chose pour aider. Quand je suis arrivé à l'université, je l'ai même utilisé comme projet de dernière année et j'ai finalement opté pour une implémentation de Monte Carlo (utilisant un modèle de recuit simulé).

L’idée de base est que si ce n’est pas du NP, c’est assez proche, alors plutôt que de supposer qu’il existe 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é auraient des coûts énormes, les préférences auraient des coûts plus bas (mais augmenter pour plus de pauses, donc casser une fois serait moins de la moitié du coût de la casser deux fois).

L'idée de base est que j'ai commencé avec une solution "aléatoire" et que je l'ai chiffrée; a ensuite apporté des modifications en échangeant un petit nombre d’affectations, en la réévaluant, puis en acceptant ou en refusant la modification de manière probaliste.

Après des milliers d’itérations, vous vous approchez d’une solution acceptable.

Croyez-moi cependant, dans cette classe de problèmes, des groupes de recherche préparent des doctorants, vous êtes donc en très bonne compagnie.

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

Answer 11

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

J'ai travaillé sur un problème similaire à l'université 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 un programme adapté à celui-ci (c'était en 1990 ou à peu près). )

Je n'avais aucune idée de ce dans quoi je m'étais embarqué. Heureusement pour nous tout ce que j'avais à faire était de trouver une solution qui tienne compte des contraintes. Mais lors de mes tests, j'étais toujours inquiet de savoir s'il y avait une solution. Il n'a jamais eu trop de contraintes et le programme utilisait des méthodes heuristiques et de suivi différentes. C'était très drôle.

Je pense que Bill Gates a également travaillé sur un système comme celui-ci au lycée ou au collège pour son lycée. Pas sûr cependant.

Bonne chance. Toutes mes notes sont parties et je n'ai jamais réussi à mettre en œuvre une solution que je pourrais commercialiser. C’était un projet spécialisé que j’avais recodé à mesure que j’apprenais de nouveaux langages (Basic, Scheme, C, VB, C ++)

Amusez-vous avec elle

Answer 12

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 "Satisfaction de la contrainte Problème prologue"