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