Мобильная версия

Математические методы оптимизации при составлении учебного расписания

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

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

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

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

Компания "Дусофт" сотрудничает с лабораторией 68 Института проблем управления РАН, которая занимается созданием и внедрением наукоемких информационных систем. 

В 2012м году по заказу одного из федеральных университетов был создан и внедрен программный продукт на платформе 1С, автоматизирующий составление расписаний.

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

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

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

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

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

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

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

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

 

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

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

 

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

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

 

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

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

Компания «Дусофт» сотрудничает с институтом проблем управления РАН, который имеет богатый опыт в этой области и готова реализовать схожие задачи для своих клиентов.

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


Все решения

Лучшая компания занимается автоматизацией управления и учета на базе программных продуктов «1С»
Наша компания также занимается разработкой собственных программных продуктов на платформе «1С:Предприятие 8».
В нашей компании работают сертифицированные фирмой «1С» специалисты, которые постоянно совершенствуют свои знания и навыки. Они помогут качественно и оперативно решить задачи по автоматизации управления и учета на вашем предприятии.
Наша компания опирается в своей работе на знание и повседневное применение стандартов качества, проектных методов в управлении, процессного подхода в организации нашей деятельности.
Наша компания успешно прошла сертификационный аудит на соответствие системы менеджмента качества международному стандарту ISO 9001. Наличие сертификата свидетельствует, что компания хорошо организована, в ней четко распределены обязанности, процедуры, соблюдается технология работы, имеются оперативные инструкции, документированные и известные всему персоналу, существуют отработанные процедуры контроля выполняемых работ и, конечно, профессиональный и хорошо обученный персонал, способный качественно выполнять свою работу.