Введение

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

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

1.Постановка задачи

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

2. Требования к расписанию в школе

Как уже было сказано, требования, предъявляемые к школьному расписанию строже, чем требования к расписанию для ВУЗов.

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

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

Таблица 1. Желаемое место предметов в расписании, согласно нормам СанПин

В таблице 2 приведена шкала трудности учебных предметов для учеников среднего звена по 13-балльной шкале М.И. Степановой, И.Э. Александровой, А.С. Седовой.

Таблица 2. Шкала трудности учебных предметов для среднего звена

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

Таблица 3. Предметные области и учебные предметы, которые в них входят

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

Таблица 4. Пожелания учителей

3. Графы в задаче составления расписания

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

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

Таблица 4. Предметы, которые должны быть проведены у каждого класса.

Основываясь на данной таблице, построим графы для каждого дня недели, вершинами которых будут являться названия дисциплин (для более удобного представления в таблице указан порядковый номер дисциплины, если предмет должен проводиться дважды, то к номеру предмета добавляется «д»). Ребра будут соединять дисциплины, которые нельзя проводить одновременно. В одно время не могут проводиться занятия по предметам, которые ведет один и тот же учитель, а также остальные дисциплины, которые должны быть проведены в этот день у данного класса. На рисунках 1, 2, 3, 4 и 5 в приложении представлены графы для каждого дня недели. На них наглядно отображено, какие предметы не могут проводиться в одно время, а какие можно проводить одновременно.

Для определения номера урока в расписании необходимо раскрасить граф. Основываясь на таблице 1 и таблице 3, для каждого дня недели составим в таблицу, в которой будет указано, каким по счету уроком должен проводиться этот предмет и на каких уроках учитель может провести его. Каждому уроку был присвоен свой цвет: 1-ый урок – красный; 2-ой урок – оранжевый; 3-ий урок – желтый; 4-ый урок – синий; 5-ый урок – фиолетовый; 6-ой урок – зеленый; 7-ой урок – серый. Любая раскраска, удовлетворяющая составленной таблице, будет давать подходящий вариант расписания. Тем самым посмотрев на граф, можно сразу сказать каким по счету уроком какой предмет и у какого класса проводиться.

3.1 Понедельник

Таблица 5. Входные данные для построения графа

Опираясь на информацию, приведенную в таблице 5, раскрасим граф. На рисунке 6 в приложении представлена одна из возможных раскрасок графа.

3.2 Вторник

Таблица 6. Входные данные для построения графа

Опираясь на информацию, приведенную в таблице 6, раскрасим граф. На рисунке 7 в приложении представлена одна из возможных раскрасок графа.

3.3 Среда

Таблица 7. Входные данные для построения графа

Опираясь на информацию, приведенную в таблице 7, раскрасим граф. На рисунке 8 в приложении представлена одна из возможных раскрасок графа.

3.4 Четверг

Таблица 8. Входные данные для построения графа

Опираясь на информацию, приведенную в таблице 8, раскрасим граф. На рисунке 9 в приложении представлена одна из возможных раскрасок графа.

3.5 Пятница

Таблица 9. Входные данные для построения графа

Опираясь на информацию, приведенную в таблице 9, раскрасим граф. На рисунке 10 в приложении представлена одна из возможных раскрасок графа.

В таблице 10 приведен готовый вариант расписания для 9А класса, который был составлен, опираясь на графы, приведенные в приложении .

Таблица 10. Расписания для 9А класса

В таблице 11 приведен готовый вариант расписания для 9Б класса, который был составлен, опираясь на графы, приведенные в приложении .

Таблица 11. Расписания для 9Б класса

В таблице 12 приведен готовый вариант расписания для 9В класса, который был составлен, опираясь на графы, приведенные в приложении .

Таблица 12. Расписания для 9В класса

Заключение

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

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

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

ПРИЛОЖЕНИЕ

Рисунок 1. Рисунок 2.

Граф, соответствующий Граф, соответствующий понедельнику. вторнику.

Рисунок 3. Рисунок 4.

Граф, соответствующий Граф соответствующий среде. четвергу.

Рисунок 5. Граф, соответствующий пятнице.

Рисунок 6.

Рисунок 7.

Граф, иллюстрирующий Граф, иллюстрирующий вариант расписания на понедельник. вариант расписания на вторник.

Рисунок 8.

Рисунок 9.

Граф, иллюстрирующий Граф, иллюстрирующий вариант расписания на среду. вариант расписания на четверг.

Рисунок 10. Граф, иллюстрирующий вариант расписания на пятницу.