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

Question

Мне нужно реализовать алгоритм, который генерирует расписание для университета.Я искал и нашел много алгоритмов.Но здесь есть проблема.Мне нужен алгоритм, который генерирует расписание на весь семестр, а не на еженедельной основе.Следует также учитывать предопределенный порядок частей курса, например, упражнение 1 должно быть после лекции 2 и перед лекцией 3. У вас есть какие-либо предложения?

Спасибо.

ОБНОВЛЕНИЕ:
У меня есть следующие жесткие ограничения:
H1: Для каждой комнаты в любой промежуток времени назначена только одна часть курса.
H2: В комнате могут разместиться все учащиеся иудовлетворяет всем функциям, необходимым для мероприятия.
H3: Ни один студент не посещает режим, кроме одного курса одновременно (по крайней мере, обязательные курсы)
H4: Ни один учитель не преподает более одной части курса одновременно.

Мягкие ограничения:
S1: часть курса не должна выделяться для временного интервала, неудобного для лектора.
S2: должно быть минимальное количество промежутков между классами учителя.
S3: должно быть минимальное количество промежутков между классами для студента.
S4: классы должны удовлетворять предпочтениям лектора - дни и временные интервалы.
S5: Части курса должны быть запланированы в предопределенном порядке.

Пример:
Курс «Архитектура программного обеспечения»

Week No   Course    Room    Course Part   Day       Time
--------+---------+-------+--------------+----------+-----
Week 1:   SA        435     Lecture 1     Wednesday  8.15-11
Week 2:   SA        435     Lecture 2     Wednesday  8.15-11
Week 3:   SA        47      Lab 1         Monday     13-15
Week 3:   SA        436     Lecture 3     Wednesday  11-14
Week 4:   SA        243     Exercise 1    Monday     13-15
Week 5:   SA        436     Lecture 4     Wednesday  8.15-11

Answer 1

Возможно, вы захотите посмотреть планирование интервалов .Похоже, вам понадобится модифицированная версия, в которую добавлены некоторые ограничения, например, где разрешено размещать упражнения.Жадные алгоритмы обычно довольно легко модифицировать, и существует целая куча уже модифицированных версий базового алгоритма IS.

Answer 2

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

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

Answer 3

Я закончил с измененным алгоритмом предложенного здесь .Я использовал итеративный прямой алгоритм, а затем применил имитированный отжиг для мягких ограничений.Я изменил набор временных интервалов, чтобы он содержал весь набор временных интервалов на семестр без выходных и праздничных дней.Например, если в семестре 6 недель, а на каждую неделю у меня есть 40 часов, тогда мой набор временных интервалов будет содержать целые 240 временных интервалов.

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

Answer 4

IIRC такая проблема не совсем решаема алгоритмом.