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

Question

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

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

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

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

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

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

Answer 1

С самого начала вы столкнулись с проблемой. Оптимизация планирования, такая как NP, завершена. Есть тонна статей о том, как бороться с такими проблемами, класс проблем известен как ограничение удовлетворения. Вы можете выполнить исчерпывающий поиск, который является самым простым, но также очень трудоемкий, если у вас более нескольких классов, это не сработает. Вы можете взглянуть на основание решателя, которое представляет собой набор инструментов для .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 является предпочтительным подходом, так как это то, что он предназначен. Большинство других подходов требуют от пользователя «принудительного» условия оптимальности для проблемы, когда она действительно не существует.