Какой алгоритм использовать для генерации расписания для школ
Я работаю над простым приложением, которое генерирует расписание (ежедневник) для школ. Я считал основы алгоритмов, но перепутал как, туда, где запустить.
Проблема:
Выделите учителей классам, учитывающим много ограничений как:
1) Предмет
2) Экспертные знания учителя
3) Не больше чем 2 класса непрерывно.. и т.д.
Само собой разумеется, что не должно быть никакого наложения. В основном я должен присвоить учителям N классам M с постоянным числом рабочего времени каждый день (8).
Исходные данные:
1) Общее количество классов
2) Учителя наряду с их подчиненными экспертными знаниями
3) Предметы/Курсы для каждого класса
4) Количество лекций в классе в день
5) Другие гибкие ограничения как минимальное/максимальное рабочее время для учителя в день, общее рабочее время на учителя в неделю, и т.д.
Мои вопросы:
1) Действительно ли правильно посмотреть на него как на проблему присвоения с несколькими ограничениями?
2) Какой алгоритм я должен использовать? (Венгерский алгоритм?)
3) Я должен запустить путем получения полного набора ограничений в, каждый идет и затем генерирует таблицу, или это должно быть сделано на промежуточных шагах?
Я - новичок к изучению/реализации алгоритмов, таким образом, любая справка для указания на меня в правильном ценившем направлении!Спасибо.
2 ответа
Для начала вы выбрали несколько проблем. Такая оптимизация расписания завершена. Существует множество статей о том, как решать такие проблемы, как этот класс проблем, известный как ограничение удовлетворения. Вы можете выполнить исчерпывающий поиск, что проще всего, но отнимает много времени: если у вас больше нескольких классов, это не сработает. Вы можете взглянуть на 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 .
Этот вопрос появляется здесь по крайней мере раз в неделю, и ответы (включая мой) всегда одни и те же. Я думаю, нам следует создать специальный тег по алгоритмам планирования, если такового не существует.
Я повторю, что наиболее подходящие методы решения для задач планирования, подобных этой, находятся в области программирования с ограничениями. В то время как другие методы оптимизации хороши для небольших проблем, формулирование часто оказывается болезненным для некоторых ограничений. Подумайте обо всех целочисленных переменных, которые вам придется создать для некоторых простых ограничений. Поскольку проблема часто требует не оптимального решения, а набора выполнимых расписаний (или определения невыполнимости), CP является предпочтительным подходом, поскольку именно для этого он и предназначен. Большинство других подходов требуют от пользователя "навязать" условие оптимальности для проблемы, где его на самом деле не существует.