Задача
В расписании вуза одновременно распределяются пять зависимых ресурсов: преподаватели, учебные группы, дисциплины, аудитории и время. Каждое назначение занимает сразу трёх участников, и любая перестановка тянет за собой цепочку конфликтов в других местах сетки.
К этому добавляются требования, которые нельзя выразить одним правилом. Есть жёсткие условия: никто не может находиться в двух местах одновременно, аудитория должна подходить по вместимости и типу занятия, все назначенные часы обязаны быть расставлены. Есть пожелания преподавателей: дни и часы, в которые им удобно работать. И есть норма нагрузки, превышение которой нужно замечать до утверждения расписания, а не в середине семестра. Если считать пожелания такими же обязательными, как физические ограничения, расписание перестаёт сходиться вообще.
Решение
Реестры и исходные данные. В системе велись аудитории, учебные группы, дисциплины и преподаватели. Для аудитории задавались вместимость, тип и оборудование, нужное для лекций или лабораторных работ. Для преподавателя — норма часов и объём занятий по видам нагрузки, включая количество назначенных студентов. В своём профиле преподаватель отмечал время, когда он точно не может работать, и отдельно — желательные дни и часы. Это разделение и стало основой алгоритма.
Генетический алгоритм. Один вариант расписания представлялся набором назначений «занятие — временной слот — аудитория», а качество варианта оценивалось суммой штрафов за нарушения:
- жёсткие ограничения — преподаватель, группа или аудитория заняты одновременно в двух местах; использовано запрещённое преподавателем время; аудитория не подходит по вместимости или типу занятия; часть назначенных часов не расставлена;
- мягкие ограничения — желательные дни и часы преподавателя, окна в сетке, равномерность нагрузки, удобство расписания для групп.
Конфликты ресурсов получали очень большой штраф, и такие варианты на практике отсеивались. Отклонения от пожеланий, окна и неравномерная нагрузка влияли на оценку мягче. Из лучших вариантов система собирала новые комбинации, меняла отдельные назначения и постепенно приходила к расписанию с минимальной суммой штрафов.
Ручная досборка. Последнее слово оставалось за диспетчером. Если приемлемого варианта не получалось, он расставлял занятия сам, а система сразу подсвечивала конфликты преподавателей, групп и помещений. Поэтому ручная правка не могла незаметно нарушить жёсткие ограничения.
Точечный пересчёт. При замене преподавателя или другом изменении система пересчитывала только затронутую часть расписания и уведомляла участников. Полностью пересобирать семестр из-за одной замены не требовалось.
Публикация. Итоговое расписание уходило в календари студентов и преподавателей, а у каждой аудитории был собственный календарь занятости. Отдельный модуль следил за нагрузкой ППС: превышение допустимого порога, дефицит часов и отклонения от нормы были видны до утверждения. Отчёты показывали нормативную и фактическую нагрузку, использование аудиторий и проблемные места.
Версии и история. Варианты расписания и журнал изменений хранились, поэтому можно было держать архив семестров, вернуться к предыдущей версии и разобрать историю замен: кто, когда и почему поменял занятие.
Реализация — PHP.
Результат
Учебная нагрузка, аудитории и время занятий, которые раньше вели в трёх параллельных процессах, свелись в одно расписание. Преподаватели получали занятия с учётом реальной доступности и по возможности своих предпочтений, студенты — актуальный календарь с аудиториями, диспетчер — автоматический расчёт и безопасную ручную корректировку с подсветкой конфликтов.
Главное изменение было в порядке обнаружения проблем: перегрузка преподавателя, недобор часов и конфликты ресурсов становились видны до окончательного утверждения, а изменения в течение семестра пересчитывались без полной ручной перестройки сетки. Пожелания преподавателей при этом не мешали сетке сойтись: система учитывала их ровно настолько, насколько позволяло остальное расписание.
