Формирование расписания / Алгоритм автоматического формирования

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

Как это работает

Когда вы запускаете формирование, Omniscol запускает отдельную параллельную вычислительную среду. Управлять очередью на стороне учебного заведения не нужно; подготовка часто занимает около десяти секунд, и только потом становятся видны первые вычисления. Итог зависит от качества введённых данных: площадок, кабинетов, преподавателей, групп, объёмов часов, доступности и несовместимостей. Чем больше ограничений или чем больше они противоречат друг другу, тем дольше может идти формирование или тем вероятнее частичный результат.

В основе лежит алгоритм оптимизации на основе ИИ — нейросимволическая метаэвристика Монте-Карло: она сочетает стохастический поиск, символические правила предметной области и оценку ограничений. Важно практическое следствие: алгоритм рассчитан на задачи с очень большим числом ограничений и сообщает о невыполнимых ситуациях, а не скрывает конфликты.

Строгие ограничения

Алгоритм строго соблюдает ограничения, нарушение которых сделало бы расписание недопустимым:

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

Ограничения оптимизации

Мягкие ограничения служат для оценки и улучшения найденных решений. Они не игнорируются: они становятся штрафами, которые алгоритм стремится уменьшить.

Частые примеры:

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

Поиск допустимого решения — первый этап. Оптимизация штрафов затем может стать самой долгой частью расчёта.

Поддержка режимов

• Недельные расписания — поддерживается.
• Циклические расписания — поддерживается.
• Календарные расписания — поддерживается при наличии занятий с датами и диапазона дат.

Что делать, если формирование не удалось

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

Частые причины:

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

См. Диагностика неудачного формирования расписания.

Принудительное размещение занятия

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