Algorithme d'allocation de blocs de temps, relation Professeur Privé-> Étudiant, maximiser le nombre de classes à donner

Question

La situation est la suivante. Je suis un enseignant privé avec des dizaines d'étudiants. J'ai quelques restrictions sur mon temps (par exemple je ne peux pas enseigner le vendredi après-midi) et les étudiants ont aussi beaucoup de restrictions sur leur temps. Sur cette base, j'essaie de créer mon agenda de manière à pouvoir faire autant de leçons privées que possible et optimiser mon temps en même temps. Idéalement, il faudrait même prendre en considération la distance entre moi et les étudiants (certains d'entre eux se trouvent dans une autre ville). Les classes ont également des durées variables. Idéalement, je veux pouvoir définir l'heure (chaque jour de la semaine) que je peux enseigner et régler l'heure (chaque jour de la semaine) où chaque élève peut avoir des leçons, pour combien de temps dure une leçon et la fréquence (soit 2x par semaine).

Je crois qu'il existe déjà un algorithme, mais je ne trouve pas le nom de ce problème. Je crois que ce n'est pas le cas du mariage stable et ce n'est pas le cas de celui-ci: Teacher time schedule algorithm

J'apprécierais beaucoup si quelqu'un pouvait me diriger vers un algorithme ou vers un matériau que je pourrais étudier afin d'essayer d'élaborer un si ça n'existe pas.

Merci beaucoup et passez une bonne journée!

Answer 1

Le problème semble être trop compliqué pour appliquer une bonne solution de temps polynomiale. Par exemple, vous pourriez le résoudre en utilisant un algorithme de débit maximum si vous ne vous souciez pas de la localisation des étudiants, si vous ne vous souciez pas de la fragmentation du temps, etc. Cependant, cela n'aboutira probablement pas à l'emploi du temps. Si vous voulez modéliser la situation du monde réel, en supposant que vous avez un petit nombre d'étudiants (par exemple < 10) et que vous êtes disponible petit nombre d'heures (par exemple < 40), vous devriez simplement faire backtracking, (c'est-à-dire force brute) afin d'essayer différentes missions et optimiser les contraintes que vous avez. Comme le temps d'exécution est exponentiel, vous devrez peut-être effectuer quelques optimisations. Quelle que soit votre approche, vous devrez simplifier ou préciser le problème de façon plus concrète. Par exemple, si vous décidez que les cours commencent toujours à 2, 4, 6 ou 8 heures, la résolution du problème sera beaucoup plus facile. Vous devrez également définir une formule qui donne la qualité de la solution (par exemple, temps total d'enseignement moins temps total de déplacement). Modéliser des problèmes comme celui-ci et écrire des solutions est généralement amusant, surtout si vous êtes un passionné de programmation ou d'algorithmes.