Составление учебного расписания в образовательном учреждении – трудоемкий процесс, вызывающий многочисленные сложности перед каждым учебным периодом. В ВУЗе, например, существуют специальные штатные единицы при кафедрах, на факультетах, занятые только этой задачей. Зачастую, трудозатраты, связанные с составлением расписаний измеряются тысячами часов в год

 

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

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

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

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

Лаборатория 68 Института проблем управления РАН занимается созданием и внедрением наукоемких информационных систем. В 2012м году по заказу одного из федеральных университетов был создан и внедрен программный продукт на платформе 1С, автоматизирующий составление расписаний. 

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

Процесс  составления расписаний в системе делится на следующие этапы: 

•         ввод первичной информации: курсы, группы, дисциплины, преподаватели, помещения; 
•         ввод учебного плана на семестр, в котором указывается, кто, для кого, какое занятие и в каком объеме должен провести; 
•         ввод ограничений и предпочтений на преподавателей, студентов, помещения; 
•         составление учебного расписания. 

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

Таким образом, рассчитав шахматку автоматически, потом имеется возможность ее изменить вручную, или, наоборот, проставив что-то вручную, остаток можно рассчитать автоматически. 

Далее представлен список основных функциональных возможностей системы: 

•         составление расписаний в разрезе семестров/кафедр/сценариев («пессимистичный», оптимистичный). Можно составить несколько расписаний и выбрать из них лучшее; 
•         учет пожеланий и возможностей преподавателей (проф. Иванов И.И. не может во вторник и в четверг, а хочет в пятницу с 15 до 19), групп студентов (военная кафедра в четверг), помещений (в аудитории 105 собрание кафедры каждую пятницу с 16 до 18); 
•         сравнение на допустимость: тип помещения/тип занятия, вместимость помещения/занятия при составлении расписания в любом режиме; 
•         выбор произвольной периодичности занятий (неделя, две недели, сессия и т.д.); 
•         параллельные занятия, разбитие на группы и потоковые лекции; 
•         максимальное допустимое количество занятий в день; 
•         первая/вторая смена; 
•         оптимизация: минимизировать количество используемых помещений или минимизировать количество окон; 
•         многое другое.

Рис. 1. Ввод учебного плана

Рис. 2. Составление расписания

 

Рис. 3. Составление расписания. Шахматка

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

Разумеется, у каждого ВУЗа есть свои особенности, которые необходимо учитывать при доработке/внедрении/использовании подобного продукта.

Институт проблем управления РАН имеет богатый опыт в этой области и приглашает к сотрудничеству партнеров/потенциальных клиентов.

Контакт: 

Старший научный сотрудник к.ф.м.н. Гафаров Евгений.

Москва, Профсоюзная д.65, ИПУ РАН

+7 495 334 87 51

Этот адрес электронной почты защищен от спам-ботов. У вас должен быть включен JavaScript для просмотра.