Использование OptaPlanner для создания школьных расписаний с некоторыми хитрыми ограничениями

avatar
aioobe
8 августа 2021 в 20:44
100
1
0

Я собираюсь использовать OptaPlanner, чтобы составить расписание для школы.

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

Есть несколько сложных ограничений, которые необходимо учитывать:

1. Недельные расписания

  • Лекции по одному предмету должны быть равномерно распределены по семестру.
    • Мы не можем, например, провести 20 лекций по математике в первую неделю и "завершить" математику в этом семестре.
  • На самом деле неплохо иметь некоторую недельную предсказуемость
    • "У второго года обучения биология по вторникам"
    • Однако это ограничение не должно быть высечено в камне. Некоторые недели должны включать практические занятия, экскурсии по физкультуре и т. д., и в этом случае они должны отличаться от других недель.

Проблема

Если я создам ограничение, которое, скажем, дает -1soft для того, чтобы не запланировать тему на то же время, что и на предыдущей неделе, то OptaPlanner потратит много времени, прежде чем "случайно" найдет подходящее место для лекции, и даже если ему удастся сойтись так, чтобы каждый предмет планировался в одно и то же время каждую неделю, ему никогда не удастся перенести всю серию лекций, перемещая их одну за другой. (Этот локальный оптимум никогда не будет нарушен.)

2. Межгрупповые предметы

  • Существует большая корреляция между студенческими группами и курсами; Например, все учащиеся курса естественных наук 2 в основном читают одни и те же курсы: Chemistry for Science year 2, Biology for Science year 2<35<38658139,229275> >
  • За исключением языковых курсов.
  • Каждый учащийся может выбрать для изучения французский, немецкий или испанский. Таким образом, испанский язык для 2-го курса изучают в поперечном сечении учащиеся 2-го курса естественных наук и социальные науки 2-го года обучения2651>2651>338.
  • Исходя из предыдущего (ручного) планирования, оптимальным решением почти гарантировано является планирование всех языковых занятий в одни и те же временные интервалы. (Если французский запланирован на 9 часов по четвергам, то немецкий и испанский языки могут быть запланированы «бесплатно» на 9 часов по четвергам.)

Проблема

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

Кроме того, аналогично задаче 1: Если OptaPlanner удается запланировать одновременно французский, немецкий и испанский языки, эти "блоки" никогда не будут перемещены в другое место, поскольку они являются отдельными лекциями, а вероятность того, что все лекции "случайным образом" переместятся в один и тот же новый слот, ничтожно мала. Даже с большой длиной истории Табу и так далее.

Мои мысли на данный момент

Что касается проблемы 1 ("Еженедельная предсказуемость"), я думаю сделать следующее:

На этапе построения расписания на полный семестр я создаю сокращенную версию задачи, которая распределяет (сокращенный набор лекций) в единую "шаблонную неделю". Назовем это «предварительное планирование за одну неделю». Эта шаблонная неделя затем повторяется при построении исходного решения для всего семестра, которое является «настоящим» объектом планирования.

Этапы локального поиска будут сосредоточены только на добавлении экскурсий по физкультуре и т. д., а также на корректировке расписания для затронутых недель.

Что касается проблемы 2, я думаю, что решение проблемы 1 может решить эту проблему. Кажется разумным предположить, что при расписании на 1 неделю OptaPlaner поймет, что языковые занятия должны быть запланированы на одно и то же время.

Что касается локального оптимума, установленного предварительным расписанием за одну неделю («Биология запланирована на утро вторника»), я думаю, что мог бы создать пользовательскую операцию перемещения, которая «связывает» эти лекции в одно движение. Я понятия не имею, насколько это просто. Мне бы очень хотелось, чтобы код был максимально простым.

Вопросы

Разумны ли мои мысли? Есть ли более умный способ подойти к этим проблемам? Если мне все равно придется создавать пользовательские ходы, возможно, мне не нужно создавать неделю-шаблон?

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

Источник

Ответы (1)

avatar
Lukáš Petrovický
9 августа 2021 в 08:11
0

Отличный вопрос!

Что касается вашей первой проблемы, я предлагаю вам взглянуть на Список сотрудников OptaWeb и концепцию ротации. Ротация — это «как обычно обстоят дела», и тогда у планировщика есть свобода отклоняться от ротации в виде штрафа. Как только вы поймете концепцию ротации из пользовательского интерфейса, взгляните на элемент планирования Shift и на то, как ротация реализуется с использованием переменных employee и rotationEmployee. Обратите внимание, что только employee является фактическим @PlanningVariable, а rotationEmployee является фиксированным.

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

Что касается вашей второй проблемы, здесь тоже может помочь ротация. Но я думаю, может быть, какая-то фильтрация перемещений и пользовательские перемещения помогут OptaPlanner переместить либо все языковые классы, либо ни одного? Написание эффективных пользовательских ходов — непростая задача, а фильтрация биржевых ходов обременительна. Так что я бы сделал это только тогда, когда потенциал других вариантов исчерпан. Если вы в конечном итоге сделаете это, найдите MoveIteratorFactory.

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

aioobe
9 августа 2021 в 08:23
0

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

aioobe
9 августа 2021 в 11:12
0

Ничего себе, это большой проект, чтобы дать указатель. Есть ли у вас какие-либо подсказки, к каким классам присмотреться? На ум пришел еще один подход, возможно, слишком сложный, чтобы описывать его в комментарии, но я попробую. Что вы думаете о модели домена, в которой помимо Lecture есть LectureSeries? Lectures будут представлять "разовые" события в семестре, такие как экскурсии по физкультуре, а LectureSeries будут представлять набор повторяющихся лекций. Очевидно, более сложная модель, но на порядок меньше фактографических объектов, с которыми OptaPlanner может работать.

Lukáš Petrovický
9 августа 2021 в 11:35
0

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