Какой алгоритм использовать для создания расписания для школ

Question

Я работаю над простым приложением, которое будет генерировать расписание (ежедневник) для школ. Я прочитал основы алгоритмов, но не понял, с чего начать.

Проблема:
Назначайте учителей на занятия, принимая во внимание множество ограничений, таких как:
1) Тема
2) Экспертиза учителя
3) Не более 2 классов непрерывно .. и т. Д.

Само собой разумеется, что не должно быть перекрытия. В основном мне нужно назначить N учителей в M классах с фиксированным количеством рабочих часов каждый день (8).

Входы:
1) Общее количество классов
2) Учителя вместе с предметной экспертизой
3) Предметы / Курсы для каждого класса
4) Количество лекций в классе в день
5) Другие гибкие ограничения, такие как минимальное / максимальное рабочее время учителя в день, общее рабочее время учителя в неделю и т. Д.

Мои вопросы:
1) Правильно ли смотреть на это как на проблему назначения с несколькими ограничениями?
2) Какой алгоритм мне использовать? (Венгерский алгоритм?)
3) Должен ли я начать с получения всего набора ограничений за один раз, а затем сгенерировать таблицу, или это нужно сделать на промежуточных этапах?

Я новичок в изучении / реализации алгоритмов, поэтому любая помощь, чтобы указать мне правильное направление, приветствуется! Спасибо.

Answer 1

Вы выбрали несколько проблем для начала. Оптимизация планирования, подобная этой, завершена. Существует множество статей о том, как решать такие проблемы, как этот класс проблем, называемый ограниченным удовлетворением. Вы можете выполнить исчерпывающий поиск, который является самым простым, но также очень трудоемким, если у вас больше нескольких классов, он не будет работать. Вы можете взглянуть на Solver Foundation, который представляет собой набор инструментов для .net для решения подобных задач. Скотт Хансельман сделал об этом подкаст здесь http://www.hanselminutes.com/default.aspx?showID=209 и вы можете узнать больше об этом здесь http://code.msdn.microsoft.com/solverfoundation. Если вы хотите сделать это самостоятельно, попробуйте взглянуть на GSAT или иным образом некоторые из этих эволюционных алгоритмов выглядят интересно http://www.springer.com/engineering/book/978-3-540-48582-7.

Answer 2

Этот вопрос возникает здесь, по крайней мере, один раз в неделю, и ответы (включая мой) всегда одинаковы. Я думаю, что мы должны создать специальный тег для алгоритмов планирования, если он не существует.

Я еще раз повторю, что наиболее подходящая техника решения для планирования подобных задач находится в области программирования ограничений. В то время как другие методы оптимизации подходят для небольших задач, формулировка часто является болезненной для некоторых ограничений. Рассмотрите все целочисленные переменные, которые вы должны создать для некоторых простых ограничений. Поскольку для решения проблемы часто требуется множество выполнимых графиков (или для определения невозможности выполнения), а не оптимальное решение, CP является предпочтительным подходом, поскольку именно для этого он и предназначен. Большинство других подходов требуют, чтобы пользователь «навязал» условие оптимальности для проблемы, в которой он на самом деле не существует.