Подскажите алгоритм оптимизации расписания в ВУЗе

Здравствуйте, Аноним, Вы писали:

А>Подскажите алгоритм оптимизации расписания в ВУЗе

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

С практической или теоретической точки зрения?

Если с практической, то лучше оставить как было раньше . А вообще всегда
будут уважаемые преподаватели, которые хотят преподавать в четверг с 10 до
12 и вся оптимизация полетит к черту.

Если с теоретической то надо определить набор жестких условий (время
открытия здания, не больше одной лекции в одной аудитории в один момент
времени, одна группа студентов может быть только на одной паре в любой
момент времени и т.д. и т.п.). Ети условия должны жестко выполнятся -- иначе
расписание недопустимое. После етого надо определить набор мягких условий
(чтобы у студентов и преподавателей не было форточек, чтобы Николай Адамович
мог в четверг с 10 до 12 провести лекцию и т.п.). За нарушение мягких
условий надо накладывать штраф.

После етого можно адаптировать, например, генетический алгоритм (или вообще
любой алгоритм локального поиска "Local Search").

Плохо только, что полученное расписание будет отвратительным и все равно
придет ся все делать руками. Просто я знаю много попыток автоматизации
составления расписаний в унииверситетах, которые делались на
соответствуюсчих кафедрах отпимизации и НИ ОДНА разработка не применяется на
практике.

Здравствуйте, Cruelty! Спасибо за совет.


Подскажите ссылки на реализации подобных алгоритмов (желательно С/С++).
Не очень понятно как (по какому алгоритму) переставлять пары в уже готовом расписании с кучей штрафов.

А насчет пользы составления расписания хотел бы не согласится до конца. Так как одному человеку для прорисовки карандашем на бумаге недельного расписания факультета из 70 групп с боллее 200 преподавателями требуется неделя (сам пробовал). И программная генерация некоторого безошибочного варианта крайне необходима.

Здравствуйте, Аноним, Вы писали:

Есть такая книга: Теория расписаний. под рукой к сожалению нет. Точно есть в интернете в формате Doc.

В свое время долго бился над задачей (про книгу не знал, а жаль), однозначно пришел к тому, что нужно сначала разбивать нагрузку по дням, а уж потом внутри дня. Также в первую очередь следует расставлять лекции на самые "вакантные" места. Под вакантными в первую очередь понимается время, которое позволяет объединить максимальное кол-во групп в одной аудитории и т.д.
При решении задачи предполагалось, что аудиторий реально не хватает.
Результата добился (писал на 2 курсе), скорость считаю достаточной. Основная часть расстановки занимает 2 минуты при таком подходе. Потом я еще запускал оптимизирующий бесконечный цикл, занимающийся фактически перестановками до тех пор пока его не прервет пользователь. Объективно: результат этого цикла не намного улучшал результат.

Самая большая заморочка с всякими практиками типа полгруппы на английском пол на французском.

P.S. Многое может подстказать по теме Билл Гейтс, он такие штуки писал!