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

1С:Автоматизированное составление расписания. Школа

Программа «1С:Автоматизированное составление расписания. Школа» предназначена для составления расписания, индивидуальных  траекторий и дополнительной занятости учащихся с учетом основного расписания и аудиторного фонда в школах. Гибкие настройки программы позволяют успешно использовать ее в учреждениях со сложной структурой: образовательные комплексы, объединяющие детские сады, школы; центры творчества и дополнительного образования детей; частные школы или центры развития с индивидуальным графиком для каждого ребенка.

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

Реализованный в программе алгоритм автоматического расчета расписания представлен сотрудниками лаборатории №68 «Теории расписаний и дискретной оптимизации» Института Проблем Управления Российской академии наук (ИПУ РАН). Фактически это алгоритм решения популярной NP-трудной задачи комбинаторной оптимизации School timetabling.

Пользователями решения "1С:Автоматизированное составление расписания. Школа" являются завучи общеобразовательных организаций и ответственные за составление расписаний в учреждениях дополнительного образования детей.

Основные решаемые задачи

В системе "1С:Автоматизированное составление расписания. Школа" решается важная задача составления учебного расписания с учетом требований, предъявляемыми:

• 273-ФЗ "Об образовании в РФ";
• Федеральным базисным учебным планом и примерными учебными планами для образовательных учреждений РФ, реализующих программы общего и дополнительного образования;
• Федеральными государственными образовательными стандартами общего образования нового поколения, включающими:
  • построение индивидуальных траекторий обучения, дополнительная занятость ребенка (развитие индивидуальных творческих способностей),
  • создание информационно-образовательной среды образовательной организации;
• Действующими СанПиН "Гигиенические требования к условиям обучения в общеобразовательных учреждениях", в частности, ограничениями на:
  • нагрузку по предметам на год, неделю,
  • максимальная нагрузка и трудность предметов в баллах.

Ключевые задачи:

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

Функциональные возможности

В программе:

• учтены требования СанПиН, ФГОС к составляемым расписаниям (состав, порядок следования уроков, оптимальная нагрузка в течение дня, максимальная нагрузка и т.д.);
• встроены механизмы, позволяющие использовать "рекомендуемые" типовые расписания, копировать расписания прошлых периодов;

Программа позволяет:

• составлять расписание различной сложности в автоматическом, ручном и смешанном режимах;
• вести несколько сеток звонков;
• составлять расписание без привязки к сетке звонков, назначая для каждого занятия продолжительность и определяя произвольное время начала;
• выводить расписание на печать, по классам, преподавателям и помещениям, с возможностью быстрых настроек выводимой информации.
• копировать расписание прошлых периодов и корректировать его;
• учитывать требования СанПиН и ФГОС по последовательности проведения занятий, максимальной дневной нагрузке с учетом сложности занятий;
• учитывать время перемещения между зданиями;
• формировать отчеты по нагрузке и доступности объектов;
• создавать параллельные парные занятия;
• загружать данные из таблицы Excel и программы aSc;
• распределять нагрузку по учителям;
• вводить и учитывать сложность предметов/занятий/дисциплин в баллах;
• учитывать пожелания и возможностей учителей, классов учащихся, помещений;
• учитывать разбиение на подгруппы;
• составлять индивидуальные траектории для групп и отдельных учащихся;
• строить расписание для 1, 2-х и более смен;
• автоматически проверять расписание на ошибки, удобно их устранять;
• корректировать расписание с нужной периодичностью, сравнивать расписания;
• импортировать и экспортировать данные из «1С:Общеобразовательное учреждение»;
• формировать учебный план на основе готового шаблона базисного учебного плана, рекомендованного Министерством образования и науки РФ;
• составлять несколько расписаний и выбирать лучшее;
• подбирать и вести замены;
• вести учет аудиторного фонда образовательной организации;
• формировать отчеты об использовании помещений и проведенных занятиях.

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

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

В продукте реализована загрузка данных из «1С:Колледж» и «1С:Колледж ПРОФ» ред 2.1. Обмен выполнен с использованием типовой технологии обмена «Планы обмена». 

В «1С:Колледж» для плана обмена необходимо указать организацию и учебный год по которым будет происходить обмен данными.
На планируемую нагрузку преподавателей влияют следующие документы: 
 - формирование нагрузки МК;
 - передача нагрузки;
 - нагрузка (план) вручную;
 - снятие нагрузки преподавателя;
 - расписание курса.

Соответствие данных, подлежащих обмену, подробно описано в актуальном руководстве пользователя. 

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

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

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

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

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

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

Задачи назначения ограниченных ресурсов и на операции (работы) и составления расписания выполнения операций рассматриваются в рамках теории расписаний. Задачи, рассматриваемые в рамках данного проекта, принято называть «задачами составления временных таблиц (Time Tabling)». Обобщенная задача формулируется следующим образом. Даны множества ресурсов R1,R2,….Rk и множество операций J1,J2,….,Jn, которые нужно выполнить. Для каждой операции задан набор ресурсов, необходимых для ее  выполнения, причем ресурсы могут быть однозначно определены (фиксированные ресурсы), или может быть задано подмножество ресурсов, из которых нужно выбрать фиксированное их количество (свободные ресурсы). Каждый ресурс может быть назначен только на одну операцию в каждый момент времени.

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

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

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

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

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

Реализован следующий функционал:

• составление расписаний в режимах:
  • ручной,
  • автоматический,
  • смешанный,
  а также в режимах:
  • по помещениям,
  • по группам,
  • по преподавателям.
• встроенные средства интеграции с "1С:Университет", "1С:Университет ПРОФ";
• удобная форма "шахматка" для быстрой ручной модификации расписания перетаскиванием "drap&drop"
• составление нескольких расписаний и выбор лучшего;
• составление расписаний в разрезе:
  • семестров;
  • сценариев ("пессимистичный", оптимистичный).;
  • кафедр;
  • типа расписания;
  • периода, на который составлено расписание;
• учет пожеланий и возможностей преподавателей, групп студентов, помещений;
• консолидация расписаний. Например, расписания по кафедрам могут быть объединены в расписание по факультетам → институтам → университету. В консолидированном расписании:
  • устраняются временные коллизии, связанные с использованием общих ресурсов (помещений, преподавателей, групп студентов);
  • в общее расписание попадают "потоковые занятия", проводимые для групп разных кафедр;
  • в общее расписание попадают специализированные занятия в зарезервированные под факультет помещения (например, занятия физической культурой);
• оптимизация учебных расписаний по одному из критериев:
  • количество используемых помещений,
  • минимизировать количество окон и т.д.;
• сравнение на допустимость при составлении расписания в любом режиме:
  • тип помещения / тип занятия,
  • вместимость помещения / количество студентов в группе;
• выбор произвольной периодичности расписания (неделя, две недели, семестр, фиксированный период и т.д.);
• составление расписания сессии;
• учет параллельных занятий, разбиения на подгруппы и потоковых лекций при составлении расписания;
• учет максимального допустимого количества занятий в день для группы студентов или преподавателя при составлении расписания;
• построение расписания для 2-х и более смен;
• оперативное резервирование помещений (дополнительно можно указывать мероприятие и/или причину резервирования);
• просмотр расписаний и ввод предпочтений по web-интерфейсу;
• уведомление об изменении расписаний по e-mail для студентов и преподавателей (отсылаемый документ формируется автоматически в форме отчета "Печать расписания");
• быстрая форма замены занятий;
• учет графика учебно-производственного процесса;
• отчеты: "Проведенные занятия", "Использование помещений по периодам", "Нагрузка";
• загрузка справочников (в том числе списки преподавателей, дисциплин, групп) и учебных планов в форматах Excel и XML. Учебный план содержит сведения:
  • количество занятий за период планирования;
  • группа,
  • дисциплина,
  • краткое наименование дисциплины для вывода в расписании,
  • преподаватель,
  • количество академических часов,
  • количество занятий,
  • количество занятий за период планирования;
• оперативное изменение расписаний (путем перетаскивания). Перетаскивать можно:
  • занятие на пустую ячейку "шахматки",
  • занятие на заполненную ячейку, при этом занятие, стоявшее в ячейке, переместится в таблицу "Нераспределенные занятия";
  • занятие из одной ячейки "шахматки" в другую;
• разграничение доступа подокументно.

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

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

При вводе нового расписания заполняются реквизиты:

• семестр;
• сценарий («пессимистичный», оптимистичный).;
• кафедра, тип расписания;
• период, на который составлено расписание.

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

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

Цвета обозначают следующее:

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

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

Формулировка решаемой проблемы

Задачи назначения ограниченных ресурсов и на операции (работы) и составления расписания выполнения операций рассматриваются в рамках теории расписаний. Задачи, рассматриваемые в рамках данного проекта, принято называть "задачами составления временных таблиц (Time Tabling)". Обобщенная задача формулируется следующим образом. Даны множества ресурсов R1, R2,...Rk и множество операций J1, J2,... Jn, которые нужно выполнить. Для каждой операции задан набор ресурсов, необходимых для ее  выполнения, причем ресурсы могут быть однозначно определены (фиксированные ресурсы), или может быть задано подмножество ресурсов, из которых нужно выбрать фиксированное их количество (свободные ресурсы). Каждый ресурс может быть назначен только на одну операцию в каждый момент времени.

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

В качестве примера можно привести следующую задачу составления расписания занятий в ВУЗе, где R1 = группы студентов, R2 = преподаватели, R3 = помещения, операции = занятия. Ресурсы из R1 и R2 являются фиксированными, R3 - свободными. Имеются различные ограничения на время, когда каждый конкретный ресурс доступен (например, преподаватель Иванов И.И. может вести занятия только во Вт. и в Чт.). Требуется составить допустимое расписание учебных занятий, или оптимальное, при котором минимизируется, например, количество окон или количество используемых помещений.

Другим примером является задача составления графиков вахтования персонала на сырьевых предприятиях.

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

Сведения о рассматриваемой задаче и научная новизна

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

Рассматриваемая задача является NP-трудной в сильном смысле. В библиотеке ScienceDirect можно встретить более 1600 научных статей по данной тематике, что свидетельствует об ее актуальности.

Данная область теории расписаний активно развивается за рубежом. Например, в научной группе ASAP (Ноттингем, Великобритания). Многочисленные программные продукты для составления учебных расписаний или графиков работы персонала (в ресторанах, на транспорте) активно используются повсеместно.

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