Задача оптимизации расписания

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

, (9.14)

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

Составление университетского расписания

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