Алгоритм распределения временных блоков, отношения между частным учителем и учеником, максимальное количество классов

Question

Ситуация следующая.

Я частный учитель с десятками учеников.У меня есть некоторые ограничения на мое время (например, я не могу преподавать во второй половине дня в пятницу), и у студентов также есть много ограничений на их время.Исходя из этого, я пытаюсь создать свою повестку дня таким образом, чтобы я мог сделать как можно больше индивидуальных уроков и оптимизировать свое время одновременно.В идеале это должно было бы принять во внимание расстояние от меня до студентов (некоторые из них находятся в другом городе).Классы также имеют переменную продолжительность.В идеале я хочу иметь возможность устанавливать время (каждый день недели), которое я могу преподавать, и устанавливать время (каждый день недели), на которое каждый ученик может иметь уроки, сколько времени он хочет, чтобы урок длился и как часто (т.е. 2 раза в неделю).

Я считаю, что алгоритм уже существует, но я не могу найти название этой проблемы.Я полагаю, что это не случай стабильного брака, и это также не тот случай: алгоритм расписания учителей

Я был бы очень признателен, если бы кто-то мог указать мне на алгоритм илик материалу, который я могу изучить, чтобы попытаться разработать один, если его не существует.

Большое спасибо и хорошего дня!

Answer 1

Проблема кажется слишком сложной, чтобы применить какое-то хорошее решение за полиномиальное время. Например, вы можете решить эту проблему с помощью некоторого алгоритма максимального потока, если вам не важно, где находятся учащиеся, не заботятся о фрагментации времени и т. Д. Однако это, вероятно, не приведет к тому, что график вас больше всего порадует. Если вы хотите смоделировать реальную ситуацию в мире, предполагая, что у вас небольшое количество студентов (например, <10) и у вас есть небольшое количество часов (например, <40), вам просто нужно сделать <a href="http://en.wikipedia.org/wiki/Backtracking" rel="nofollow noreferrer"> возврат , ( то есть, грубой силой), чтобы попробовать различные назначения и оптимизировать любые ограничения, которые у вас есть. Поскольку время выполнения является экспоненциальным, возможно, в конечном итоге вам придется выполнить некоторые ветвления и привязки оптимизаций.

Независимо от того, какой подход вы выберете, вам придется упростить или конкретизировать проблему более конкретно. Например, если вы решите, что занятия всегда начинаются в 2, 4, 6 или 8 часов, решение проблемы будет намного проще. Вам также необходимо определить формулу, которая дает качество решения (например, общее время обучения минус общее время в пути). Моделирование подобных проблем и написание решений обычно доставляет удовольствие, особенно если вы программист или энтузиаст алгоритмического процесса.