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

Question

Я планирую разработать экспертную систему, которая автоматически соответствует рабочей нагрузке школьной преподавательской школы (время, учебная нагрузка и т. Д.), А также создавать секции классов, которые, по крайней мере, на 90% точны с тем, что хочет директор одного отдела назначить график для определенного семестра.

Какой алгоритм использовать? Эвристика? Оптимизация? Любые предложения или помощь высоко оценены!

Answer 1

Два моих друга сделали что-то подобное для проекта класса. Они использовали эвристику simulated annealing. Они пришли к выводу, что это не лучший инструмент для работы.

Эй, зная, что не делать может быть полезно, не так ли? :)

Answer 2

Здесь a paper о динамическом планировании с использованием генетических алгоритмов ... вы можете найти некоторые полезные здесь идеи ... даже если домен не является тем же, я думаю, что идея более общеприменима.

Answer 3

Вот некоторые общие замечания:

1) Руководство планирования редко пытались с нуля. Вместо этого кто-то начинает с графика за предыдущий год и изменяет его, чтобы учесть изменения в требованиях. Один из способов подделать это с помощью компьютера - использовать алгоритм альпинизма, который многократно пытается внести ряд небольших изменений, чтобы улучшить решение до сих пор. Затем его можно запустить в текущем расписании.

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

3) Любопытно, что система следующего поколения не использовала сложное планирование вообще. Оказалось, грубо говоря, что в то время, когда должны приниматься решения, не всегда можно было увидеть не все последствия сложных решений по планированию, и в конечном счете простой прогнозируемый график, который можно было бы поддерживать на неопределенный срок, был более продуктивным, чем постоянно перестраивая графики, чтобы получить небольшие мгновенные преимущества.

Answer 4

Взгляните на curriculum course lesson scheduling пример Drools Planner (с открытым кодом, я боюсь). Он использует метаэвристику, такую ​​как simulated annealing и tabu search.