Анализ технологий автоматического составления расписания в школе и их использования в школе

Одной из очень важных составляющих учебного процесса в образовательном учреждении среднего уровня (далее – ОУ) является расписание занятий, которое десятки лет составлялось вручную заместителями директоров ОУ, тративших на это дни и даже недели. И только в последние десятилетия можно увидеть в некоторых ОУ использование специализированных информационных систем для составления расписания. Но почему не во всех? Что мешает школам использовать такие программы?

• 1.    Разработка критериев для автоматического составления расписания

К составлению расписания предъявляется много требований, среди которых наиболее важными являются требования САНПИНа, а уже после этого идут требования, которые предъявляет само ОУ.

В 2010 году были утверждены новые санитарно-эпидемиологические требования к условиям и организации обучения в общеобразовательных учреждениях. В них САНПИН определяет:

• -    время проведения сложных по уровню трудности предметов для каждой параллели;

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

• -    максимальное время, которое ученики могут проводить за компьютерами на уроке (10-25 минут в зависимости от параллели) и т.д.

Для составления расписания используется указанная ранее нагрузка учащихся, измеряемая в баллах трудности по каждому предмету в отдельной параллели. Согласно САНПИНу, сумма баллов трудностей по предметам, поставленных в расписании на любой день, не должна превышать определенного значения [1].

Табл. 1. Шкала трудностей предметов в начальной школе

Общеобразовательные предметы	Количество баллов (ранг трудности)
Математика	8
Русский (национальный, иностранный язык)	7
Природоведение, информатика	6
Русская (национальная) литература	5
История (4 классов)	4
Рисование и музыка	3
Труд	2
Физическая культура	1

Табл. 2. Шкала трудностей предметов в 5-9 классах

Общеобразовательные предметы	Количество баллов (ранг трудности)
	5 классы	6 классы	7 классы	8 классы	9 классы
Химия	-	-	13	10	12
Геометрия	-	-	12	10	8
Физика	-	-	8	9	13
Алгебра	-	-	10	9	7
Экономика	-	-	-	-	11
Черчение	-	-	-	5	4
Мировая художественная культура (МХК)	-	-	8	5	5
Биология	10	8	7	7	7
Математика	10	13	-	-	-
Иностранный язык	9	11	10	8	9
Русский язык	8	12	11	7	6
Краеведение	7	9	5	5	-
Природоведение	7	8	-	-	-
География	-	7	6	6	5
Граждановедение	6	9	9	5	-

Общеобразовательные предметы	Количество баллов (ранг трудности)
	5 классы	6 классы	7 классы	8 классы	9 классы
История	5	8	6	8	10
Ритмика	4	4	-	-	-
Труд	4	3	2	1	4
Литература	4	6	4	4	7
ИЗО	3	3	1	3	-
Физическая культура	3	4	2	2	2
Экология	3	3	3	6	1
Музыка	2	1	1	1	-
Информатика	4	10	4	7	7
ОБЖ	1	2	3	3	3

Табл. 3. Шкала трудностей предметов в 10-11 классах

Общеобразовательные предметы	Количество баллов (ранг трудности)	Общеобразовательные предметы	Количество баллов (ранг трудности)
Физика	12	Информатика, Экономика	6
Геометрия, химия	11	История, Обществознание, МХК	5
Алгебра	10	Астрономия	4
Русский язык	9	География, Экология	3
Литература, иностранный язык	8	ОБЖ, Краеведение	2
Биология	7	Физическая культура	1

После сбора информации от администраций средних общеобразовательных школ, планирующих автоматизировать процесс составления расписания, были определены требования, которые необходимы в большинстве школ:

• 1)    выполнение требований САНПИНа;

• 2)    минимизация количества «окон» в расписании класса;

• 3)    возможность определения поурочная нагрузка преподавателя (согласно учебному плану на конкретный учебный год);

• 4)    возможность определения количества часов в неделю/год по каждому предмету;

• 5)    возможность разделения класса на группы (на каждую группу одна строка в расписании);

• 6)    возможность разделения процесса автоматического составления расписания в школе (по приоритетам);

• 7)    возможность определения на каждый день максимальной нагрузки для каждого класса;

• 8)    возможность автоматического составления изменений в расписании;

• 9)    возможность определения некоторых данных вручную;

• 10)    наличие автоматического увеличения номера класса на единицу для 1-3 и 5-8 классов;

• 11)    возможность просмотра расписания с любого компьютера сразу после его составления (при дальнейшем развитии).

• 2.    Анализ существующих программ автоматического составления расписания

Таким образом, был составлен список желаемых требований, которые должны выполняться при составлении расписания информационной системой.

Для проведения анализа существующих систем составления расписания (точнее, для их выбора), был проведен опрос школ, в котором предлагалось ответить на следующие вопросы, объединенные в разделы:

• 1.    «Использует ли Ваша школа какую-нибудь компьютерную программу для составления расписания занятий?» (1 раздел).

• 2.    «Какую программу Вы используете (использовали) для составления расписания?» (2 раздел).

• 3.    «У какой компании была приобретена данная программа?» (2 раздел).

• 4.    «Какие плюсы и минусы у программы Вы можете выделить?» (2 раздел).

• 5.    «Данная программа используется сейчас Вашей школой или использовалась в прошлом?» (2 раздел).

• 6.    «По каким причинам Ваша школа не использует ни одну из существующих программ по составлению расписания?» (3 раздел).

• 7.    Полное наименование ОУ (4 раздел).

• 8.    Номер Вашего ответа на анкету (в случае ответа на анкету более одного раза) (4 раздел).

В ходе проведения опроса было выявлено:

• 1.    Только 23-24% ОУ используют программы автоматического составления расписания, примерно 15,5% использовали их в прошлом.

• 2.    ОУ, которые использовали или используют программы автоматического составления расписания, выделили такие программы, как «НИКА-ЛЮКС 6», «Ректор-школа», «Расписание-про», причем первая программа имеет противоположное мнение о себе у пользователей.

• 3.    Школы максимум пробуют одну программу автоматического составления расписания и, если не нравится результат (составленное расписание занятий), отказываются от его использования и закрывают глаза на этот вопрос, не просматривая другие программы.

• 4.    На вопрос «По каким причинам Ваша школа не использует ни одну из существующих программ по составлению расписания?» большинство ОУ отвечают, что «привычней старым способом, самостоятельно составлять расписание занятий».

• 3.    Алгоритм составления расписания

По результатам данного опроса были определены четыре самые популярные программы автоматического составления расписания: НИКА-ЛЮКС 6 (разработка компании НИКА-ЛЮКС), 1С: Автоматизированное составление расписания. Школа (разработка компании 1С), Расписание занятий – школа, Составитель расписания, которые необходимо проанализировать и сопоставить их возможности с разработанными требованиями образовательного учреждения, приведенными выше.

В таблице 4 приведено соответствие этих программ предъявленным требованиям.

Табл. 4. Соответствие требований программ к предложенным требованиям

Название программы	Номера требований по общему списку
	1	2	3	4	5	6	7	8	9	10	11
НИКА-ЛЮКС 6	+А	+	+	+	■	■	■	+	+А	■	■
1С:Автоматизирова нное составление расписания. Школа	+А	+	+	+	■	■	■	■	+А	■	■
Расписание занятий - школа	+А	+	+	+	■	■	■	■	■	■	■
Составитель расписания	+А	+	+	+	■	■	■	■	■	■	■

Согласно таблице №4 можно сделать вывод, что ни одна из рассмотренных программ не удовлетворяет одновременно всем требованиям, которые были перечислены выше. Именно поэтому требуется разработать проект программного обеспечения (системы) автоматического составления расписания, которое будет отвечать всем заявленным требованиям [4-7].

Для автоматического составления расписания можно использовать следующие виды алгоритмов:

• -    алгоритм перебора,

• -    генетический алгоритм.

Алгоритм перебора хорошо подходит только при небольшом количестве данных по классам, учителям, кабинетам и предметам. То есть идеально подходит для начальных школ, в которых учеба проходит на 1-4 параллелях. Для составления расписания в средних образовательных учреждениях (учеба во всех параллелях с 1 по 11) данный алгоритм потребует в несколько раз больше времени из-за большего количества данных по учителям, аудиториям, классам и предметам. Даже при условии использования данных в виде объединенного кортежа, состоящего из атрибутов класс, предмет, учитель, базовая нагрузка, аудитория, количество уроков в неделю (фактического и планового) может быть уменьшено (в лучшем случае) примерно наполовину.

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

• 1)    создание новой популяции (создание несколько видов расписания случайным образом);

• 2)    размножение (при котором новая особь унаследует черты своего родителя, размножаются все особи);

• 3)    мутация (замена некоторых параметров как номер кабинета и последовательности уроков в конкретном учебном дне);

• 4)    отбор (выбор более подходящих вариантов расписания для дальнейшего использования генетического алгоритма).

• 4.               ----------

• Алгоритм перебора для составления расписания во второй группе

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

Алгоритм перебора для составления расписания в первой группе

Генетический алгоритм для дополнения информации в расписании и изменения последовательности уроков на день '                                     *                                    '

Алгоритм перебора для составления расписания в третьей группе

Генетический алгоритм для дополнения информации в расписании

Рис. 1. Работа предлагаемого алгоритма

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

• 1.    Определение текущего класса, а также дополнительного выходного дня (из БД).

• 2.    Вывод данных из основной таблицы по текущему классу.

• 3.    Пробег по таблице (6 раз - по количеству учебный дней в школе на неделе):

  • 3.1.    Если в выбранный день класс не должен учиться, то перейти к составлению расписания на следующий день.

  • 3.2.    Если выбранный день для класса выходной, и он последний рабочий день на неделе (по 6-ти дневке), то перейти к шагу 1.

  • 3.3.    Определение допустимой максимальной нагрузки для класса на текущий день.

  • 3.4.    Случайный выбор строки из основной таблицы.

  • 3.5.    Вставить данную строку в расписание определенное количество раз:

    • 3.5.1.    Если выбранный предмет – технология, а класс из 5, 6, 8 или 9 параллели, то сделать последовательное проведение уроков (два урока подряд). В средних общеобразовательных учреждениях принято ставить два урока технологии подряд для класса в один день.

    • 3.5.2.    Если количество занятий по плану больше количества учебных дней в классе, то разрешить сделать повторную вставку на какой-нибудь день.

    • 3.5.3.    При выборе предметов информатика или английский рассматривать только три разделения (инф./англ., англ./инф., англ./англ.).

  • 3.6.    Добавить в расписание не достающую информацию (номера кабинетов, кроме номеров кабинетов информатики и технологии, а также биологии и химии).

• 4.    Если не все классы пройдены, перейти к шагу 1.

• 5.    Дополнить расписание необходимой информацией (номера кабинетов, можно использовать все кабинеты).

• 4.    Проект разрабатываемого программного обеспечения

Как говорилось ранее, предлагаемый алгоритм будет использовать разделение классов на приоритеты. Самыми приоритетными будут научные (например, физико-математические) и спортивные классы. Вторая группа по приоритету будет включать 5-11 классы, не вошедшие в первую группу и последней. Последняя группа будет состоять из 1 -4 классов. Данное разделение классов на группы по приоритету можно обосновать тем, что в учебных заведениях преподаватели средних классов не всегда (местами редко) проводят уроки для учеников младших классов, а для проведения некоторых занятий в научных классах могут приглашаться преподаватели ВУЗов.

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

Поскольку предлагаемый алгоритм будет использовать систему приоритетов, то его сложность можно представить в следующем виде:

O ( Gr, K ( gr ), D ( k), Zn, Pr ( k), Prep (k, pr ), A( pr)), где Gr - количество групп приоритетов; K - количество классов в группе gr; D - количество учебных дней у класса k; Zn -количество уроков; Pr - количество учебных дисциплин, работающих в классе к; Prep - количество учителей, преподающих pr в к; A - количество аудиторий, подходящих для проведения занятий по предмету pr.

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

• -    администратор;

• -    секретарь;

• -    заместитель директора ОУ по УВР.

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

Рис. 2. Use-case диаграмма для учителя

Рис. 3. Use-case диаграмма для заместителя по УВР

Рис. 3. Пример работы пользователей с БД по составлению и просмотру расписания

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

Табл. 5. Структура предложенной БД

Таблицы	Атрибуты	Внешний ключ
Роль	ID_Rol
	Роль
	Описание
Пользователи	Login
	Password
	Name	Учителя (ФИО учителя)
	Rol	Роль ( ID_Rol )

Таблицы	Атрибуты	Внешний ключ
	Status
	Дата начала блокировки
	Дата окончания блокировки
Учителя	ФИО учителя
	{IJ} , I - день недели J - номер урока
	Ставка
	Кабинет
	Дата рождения
Отсутствующие преподаватели	Номер записи
	Дата
	Номер урока
	Преподаватель	Учителя (ФИО учителя)
Студенты	ID ученика
	ФИО
	Дата рождения
	Год прихода
	Год ухода
	Класс	Классы ( ID class )
	Серия диплома за 5-9 классы
	Номер диплома за 5-9 классы
	Серия диплома за 10-11 классы
	Номер диплома за 10-11 классы
	Телефон
	Email
	Адрес
	Пол
Предметы_САНПИН	Предмет
	{I} , I - от 1 до 11
Расписание	Номер записи
	День
	Номер урока
	Класс	Классы ( ID class )
	Предмет	Предметы САНПИН
	Преподаватель	Учителя (ФИО учителя)
	Кабинет	Кабинеты (кабинет)
Класс_предмет_преподаватель	ID_Zap
	Класс	Классы( ID class )
	Предмет	Предметы_САНПИН (Предмет)
	Преподаватель	Учителя (ФИО учителя)
	Кабинет	Кабинеты (Кабинет)
	Количество часов в неделю
	Количество часов в год

Таблицы	Атрибуты	Внешний ключ
Классы	ID_class
	Номер потока
	Буква класса
	Классный руководитель	Учителя (ФИО учителя)
	Максимальная нагрузка на I , I – {Пн., Вт., Ср., Чт., Пт., Суб.}
	{IJ} , I – день недели, J – номер урока
Кабинеты	Кабинет
	{IJ} , I – день недели J – номер урока
	Предмет	Предметы_САНПИН (Предмет)
Неактивные кабинеты	Номер записи
	Дата	График учебных дней (Дата)
	Номер урока
	Кабинет	Кабинеты (кабинет)
Параллели учителей	Номер записи
	Преподаватель	Учителя (ФИО преподавателя)
	Предмет	Предметы_САНПИН (Предмет)
	Параллель
Изменения в расписании	ID_Zap
	Дата	График учебных дней (Дата)
	Класс	Классы ( ID_class )
	Преподаватель	Учителя (ФИО учителя)
	Кабинет	Кабинеты (кабинет)
	Номер урока
	Предмет	Предметы_САНПИН (Предмет)
График учебных дней	Дата
	День недели (по которому работает школа)

При реализации данной структуры БД, в предлагаемом программном обеспечении, пользователь сможет:

• 1)    определять выходные дни для учителей и учеников среди недели;

• 2)    определять график работы ОУ во время учебного года;

• 3)    освобождать кабинеты для различных мероприятий и проверочных работ (например, пробные экзамены и всероссийские проверочные работы).

Заключение

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