1С:Автоматизированное составление расписания. Колледж

Программа для составления расписания «1С:Автоматизированное составление расписания. Колледж», «1С:Автоматизированное составление расписания. Колледж. (USB)» , является специальной версией конфигурации «1С:Автоматизированное составление расписания», предназначенная для использования в образовательных организациях СПО.

В продукте реализована загрузка данных из «1С:Колледж», «1С:Колледж ПРОФ», внутренний алгоритм автоматического расчета расписания реализован на внутреннем языке «1С:Предприятие 8». В этом алгоритме расчета по составлению расписания не учитываются переходы между зданиями.

В конфигурации реализованы следующие функции:

• удобная форма «шахматка» для быстрой ручной модификации расписания перетаскиванием;
• составление расписаний в разрезе:
  • семестров;
  • отделений;
  • сценариев («пессимистичный», оптимистичный);
  • составление нескольких расписаний и выбор лучшего.
• учет пожеланий и возможностей преподавателей, групп студентов, помещений;
• сравнение на допустимость при составлении расписания в любом режиме:
  • тип помещения;
  • тип занятия;
  • вместимость помещения;
  • количество студентов в группе.
• выбор произвольной периодичности расписания (неделя, две недели, фиксированный период и т.д.);
• составление расписания сессии;
• учет параллельных занятий, разбиения на подгруппы и потоковых лекций при составлении расписания;
• учет максимального допустимого количества занятий в день для группы студентов или преподавателя при составлении расписания;
• учет смены, в которую занимается группа студентов, при составлении расписаний;
• оптимизация учебных расписаний по одному из критериев:
  • минимизировать количество используемых помещений;
  • минимизировать количество окон и т.д.
• оперативное резервирование помещений;
• просмотр расписаний и ввод предпочтений по web-интерфейсу;
• уведомление об изменении расписаний по e-mail для студентов и преподавателей;
• обмен данными с тиражными продуктами «1С:Колледж», «1С:Колледж ПРОФ»;
• загрузка справочников и учебных планов из Excel;
• оперативное изменение расписаний и составление «текущих» расписаний;
• компоновка расписаний по отделениям в расписания по колледжу;
• разграничение доступа подокументно.

На следующем рисунке представлена основная форма для составления расписания («шахматка», строки – дни недели, пары, колонки — помещения).

На шахматке отображаются уже поставленные в расписание занятия, а специальным цветом подсвечиваются ячейки, куда может/не может быть установлено занятие из нижнего списка «неупорядоченных» занятий. Оператор может вручную перетаскивать занятия из нижнего списка в шахматку или двигать занятия по шахматке.  Таким образом, рассчитав шахматку автоматически, потом имеется возможность ее изменить вручную, или, наоборот, проставив что-то вручную, остаток можно рассчитать автоматически. Система автоматически показывает все коллизии и несоблюдения условий и позволяет их быстро отрабатывать (см. рисунок ниже).

Задача составления учебного расписания является  хорошо известной задачей комбинаторной оптимизации «Составление временных таблиц» (timetabling). Даже нахождение допустимого расписания является NP-трудной в сильном смысле проблемой.  Поэтому при ее решении необходимо использовать математические методы решения задач комбинаторной оптимизации. Их использование позволяет сократить трудоемкость вычислений, ускорить поиск допустимого или оптимального расписания.

Задачи назначения ограниченных ресурсов и на операции (работы) и составления расписания выполнения операций рассматриваются в рамках теории расписаний. Задачи, рассматриваемые в рамках данного проекта, принято называть «задачами составления временных таблиц (Time Tabling)». Обобщенная задача формулируется следующим образом. Даны множества ресурсов R₁,R₂,….R_k и множество операций J₁,J₂,….,J_n, которые нужно выполнить. Для каждой операции задан набор ресурсов, необходимых для ее  выполнения, причем ресурсы могут быть однозначно определены (фиксированные ресурсы), или может быть задано подмножество ресурсов, из которых нужно выбрать фиксированное их количество (свободные ресурсы). Каждый ресурс может быть назначен только на одну операцию в каждый момент времени.

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

В качестве примера можно привести следующую задачу составления расписания занятий в колледже, где R₁ = группы студентов, R₂  = преподаватели, R₃ = помещения, операции = занятия. Ресурсы из R₁ и R₂ являются фиксированными, R₃ – свободными. Имеются различные ограничения на время, когда каждый конкретный ресурс доступен (например, преподаватель Иванов И.И. может вести занятия только во Вт. и в Чт.). Требуется составить допустимое расписание учебных занятий, или оптимальное, при котором минимизируется, например, количество окон или количество используемых помещений.

Данная конфигурация разработана в сотрудничестве с лабораторией №68 «Теории расписаний и дискретной оптимизации» Института проблем управления им. В.А. Трапезникова РАН. В конфигурации реализован алгоритм решения задачи, предложенный сотрудниками лаборатории.