Как составить школьное расписание с помощью IBM CPLEX Solver
Составить расписание всегда былом делом непростым. Доверить эту задачу компьютеру решались не все, потому что задача NP-полная и алгоритмического решения «в лоб» за обозримое время не имеет (объяснение).
Картинка про 4х мерный куб. Но как она связана с расписанием – внутри статьи
Недавно ко мне в руки попал пакет математического решателя IBM CPLEX Solver и я попробовала сделать помощника для составления школьного расписания.
Модель решила сделать целочисленную, еще её называют MIP.
Исходные данные
Действующих лиц у нас четыре. Поэтому пусть будет четыре оси системы координат. Т.е. наше пространство будет четырехмерным. Зададим их в виде одномерных массивов данных:
Название оси
Пример данных
Пример в dat файле
Иванова Мария Ивановна, Петрова Татьяна Сергеевна и т.д.
это про физические комнаты: 101 кабинет, спорт. зал, кабинет труда № 105, кабинет физики № 205 и т.д.
это вакантные места в расписании. Выглядит это как 3х-значное число, в котором
первая цифра – это номер дня от 1 до 6, если учатся по шестидневке и до 5, если по пятидневке
вторя цифра – номер смены 1 или 2
третья цифра – номер урока в смене. Обычно от 1 до 6 или до 7
// day, shift, lesson number
lessons = <
111, 112, 113, 114, 115, 116, 117, 121, 122, 123, 124, 125, 126, 127//,
211, 212, 213, 214, 215, 216, 217, 221, 222, 223, 224, 225, 226, 227,
311, 312, 313, 314, 315, 316, 317, 321, 322, 323, 324, 325, 326, 327,
411, 412, 413, 414, 415, 416, 417, 421, 422, 423, 424, 425, 426, 427,
511, 512, 513, 514, 515, 516, 517, 521, 522, 523, 524, 525, 526, 527,
611, 612, 613, 614, 615, 616, 617, 621, 622, 623, 624, 625, 626, 627
>;
Между осями координат у нас получаются плоскости. И тут можно наложить ограничения на эти плоскости. Они представляют собой двумерные матрицы. В этих матрицах хранятся определенные целочисленные значения. Далее подробнее про каждое соотношение:
Название плоскости
Пример
Как выглядит в dat файле
Отношения между кабинетами и учителями
Хранится целое число >= 0. Если учитель НЕ может работать в этом кабинете – то 0. Например, нельзя проводить физкультуру в кабинете математики. Но можно провести математику в кабинете физики. Тут будем играть приоритетами. 1 – самый лучший кабинет для этого учителя. 2 – не такой хороший, 3 – приемлемый, но нежелательный. Далее мы еще используем это в целевой функции.
Отношение между учителями и классами учеников
Тут пишем сколько уроков в неделю должен провести конкретный учитель у конкретного класса. Например, Иванова М.И. должна провести 4 русских языка и 2 литературы в неделю у 6 Б класса. Значит в пересечении пишем цифру 4 + 2 = 6
Отношение между классами учеников и уроками
Значения этой матрицы 0 или 1. А точнее тут мы задаем в какой смене учится класс. Если 0 – то класс не может иметь уроки в это время.
Отношение между учителями и номером урока
Значение этой матрицы 0 или 1. Если стоит 0 – значит учитель не может вести уроки в это время. Это на тот случай, если какой-то учитель может работать только в определённые дни недели. Например, учителя с маленькими детьми не работают по субботам.
Графически все вместе (4 оси координат и соотношения между ними) можно представить, как четырёхмерный куб. У нас есть 4 измерения и 4 заданные поверхности. Можно ограничить и больше поверхностей, например, соотношение классов и кабинетов, если каким-то классам нельзя ставить уроки в этих кабинетах. Или между номером урока и кабинетом, если какой-то кабинет недоступен, например, в среду. Но пока ограничимся малым.
Переменная для результата
В такой постановке задачи переменной для хранения результата являться 4х мерный массив, в котором каждое значение может быть 0 или 1.
1 — означает, что условия соотношений выполняется и урок может быть у данного класса, учителя в данном кабинете и в данное время.
0 — означает, что четыре условия не выполняются.
Задание ограничений в модели
Имея все данные и переменные следует задать ограничения.
Самое строгое ограничение, что если в наших двумерных массивах встречается ноль, то и в результирующей переменной должен быть ноль
Используем ограничение по поверхности между учителями и классами учеников
Мы знаем количество уроков в неделю, которое должен провести учитель у класса. Поэтому получаем такое ограничение: для каждого учителя и каждого класса сумма уроков в кабинетах должна быть равна цифре из нашего ограничения.
Используем ограничение по поверхности между кабинетами и номерами уроков
В одном кабинете может проходить только один урок, что естественно
Используем ограничение по поверхности между учителями и номерами уроков.
Потому что один учитель может присутствовать только на одном уроке
И последнее ограничение по поверхности между классами учеников и номерами уроков. Это ограничение самое сложное, потому что для таких предметов как иностранный язык, физкультура, труды, информатика характерно разделение на подгруппы.
В реальной школе классы часто делятся на подгруппы: физкультура у юношей и девушек, труды у мальчиков и девочек, подгруппы по языку и информатике.
У этой проблемы тоже есть решение: введем набор данных для хранения подмножества «особенных» учителей. Например, учителя иностранного:
Тогда в ограничениях к модели напишем, что класс в одно и тоже время может быть у двух разных учителей и в разных кабинетах.
Целевая функция
При написании мат. модели требуется еще задать целевую функцию. Т.е. обозначить к чему мы стремимся. Тут нужно обратиться к пользователю и узнать, что для них важно. Первое, это чтобы уроки для учеников проводились как можно раньше в сутках. Т.е. желательно, чтобы все начинали учиться с первого урока своей смены. Второе требование, это чтобы учителя начинали работать пораньше. Третье условие, чтобы учителя вели уроки в приемлемых кабинетах. Но если это невозможно, то выбираем из того, что есть. Выглядит целевая функция следующим образом:
Удобство считывания результата
Для удобства обработки результатов в более наглядном виде в OPL Studio я ввела дополнительные переменные
Эти переменные копируют состояние соответствующих поверхностей в переменной schedule.
Поэтому можно видеть такие полезные наглядные результаты
Модель
// day, shift, lesson number
lessons = <
111, 112, 113, 114, 115, 116, 117, 121, 122, 123, 124, 125, 126, 127//,
/* 211, 212, 213, 214, 215, 216, 217, 221, 222, 223, 224, 225, 226, 227,
311, 312, 313, 314, 315, 316, 317, 321, 322, 323, 324, 325, 326, 327,
411, 412, 413, 414, 415, 416, 417, 421, 422, 423, 424, 425, 426, 427,
511, 512, 513, 514, 515, 516, 517, 521, 522, 523, 524, 525, 526, 527,
611, 612, 613, 614, 615, 616, 617, 621, 622, 623, 624, 625, 626, 627*/
>;
teacherClassRelation = [
[2, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0],
[0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1],
[1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0]
];
Это была тонировочная попытка автоматизировать составление школьного расписания. Следующим шагом должно быть написание программной «оболочки» для введение реальных данных.
В среду в 3 классе 4 урока: математика (м), русский язык (р), чтение (ч) и физкультура (ф). Определи с помощью «дерева», сколько вариантов расписания
Как быстро выучить стихотворение наизусть? Запоминание стихов является стандартным заданием во многих школах.
Как научится читать по диагонали? Скорость чтения зависит от скорости восприятия каждого отдельного слова в тексте.
Как быстро и эффективно исправить почерк? Люди часто предполагают, что каллиграфия и почерк являются синонимами, но это не так.
Как научится говорить грамотно и правильно? Общение на хорошем, уверенном и естественном русском языке является достижимой целью.
Особенности составления расписания с помощью программы "Ректор"
Процесс составления расписания – очень трудоемкий и продолжительный по времени, который может продолжиться до одного месяца, даже с использованием специализированных программ. Программы облегчают и ускоряют процесс, но они не могут учесть всех человеческих условий, поэтому приходиться использовать комбинированный режим работы с программами.
При составлении расписании заместитель директора по УР сталкивается со следующими требованиями, которые хотя бы частично должны быть учтены (полный перечень требований изложен в Санитарно-эпидемиологических правилах и нормах СанПиН 2.4.2.1178-02 "Гигиенические требования к условиям обучения в общеобразовательных учреждениях", утвержденные в 2002 году, вводятся в действие с 1 сентября 2003 г. СанПиН содержит Приложение 6, в котором даны рекомендации по составлению расписания уроков в части распределения учебной нагрузки в течение дня и недели.) [1,2]
1. Методический день учителя.
Учителю на основании коллективного договора предоставляется методический день. Он устанавливается при условии объема учебной нагрузки, не нарушающей учебного режима, не создающей перегрузки учащихся. Методический день не является дополнительным выходным днем.
2. Окна в расписании учителя.
Никаких нормативов по количеству окон не существует. По нормативам, рабочее время работника может быть разделено на два периода. То есть, если у учителя в течение рабочего дня два окна – это незаконно, а если одно, но любой продолжительности, то законно. Специфика рабочего времени учителя (в том числе и окна) должна быть прописана в локальном нормативном акте школы: либо в правилах внутреннего трудового распорядка, либо в коллективном договоре [3]
3. Гигиенические требования – распределение учебной нагрузки по дням недели по баллам [4].
Научными исследованиями установлено, что оптимум умственной работоспособности у детей школьного возраста приходится на интервал 10-12 часов. Поэтому в расписании уроков для обучающихся I ступени основные предметы должны приходиться на 2–3 уроках, а для II и III ступеней – на 2, 3, 4 уроках.
Таблица 1. Наиболее благоприятные и неблагоприятные дни недели.
| Классы | Дни недели | |
| благоприятные | неблагоприятные | |
| 1–4 | Вторник, среда (небольшое снижение), четверг | Понедельник, пятница, суббота |
| 5 | Понедельник, вторник | Среда, четверг, пятница, суббота |
| 6 | Вторник, четверг, пятница (небольшое снижение), суббота | Понедельник, среда |
| 7–8 | Вторник (небольшое снижение), среда, четверг, суббота | Понедельник, пятница |
| 9–11 | Среда, четверг, пятница | Понедельник, вторник, суббота |
Таблица 2. Наиболее продуктивные и непродуктивные уроки.
| Классы | Уроки | |
| продуктивные | непродуктивные | |
| 1–2 | 1, 2, 4 | 3 |
| 3–5 | 1, 2, 3 | 4 |
| 6–7 | 1, 2, 3, 5 | 4,6 |
| 8 | 1, 2, 3, 5 | 4,6 |
| 9 | 1, 2, 3, 5 | 4,6 |
| 10 | 1, 2, 3, 5 6 | 4 |
| 11 | 1, 2, 3, 4, 5, 6 (при правильно выбранных методах и формах обучения) | – |
Неодинакова умственная работоспособность учащихся и в разные дни недели. Наибольшее количество баллов за день по сумме всех предметов приходится для 8–11-х классов – на вторник, среду и четверг; для 1–7-х классов – на вторник и четверг (среда – несколько облегченный день); суммарная нагрузка в начале и конце недели должна быть наименьшей (по ранговой шкале трудности). Изложение нового материала, контрольные работы следует проводить на 2–4 уроках в середине учебной недели.
Предметы, требующие больших затрат времени на домашнюю подготовку, не должны группироваться в один день.
Таблица 3. Шкала трудности учебных предметов для расписания начальной школы (по 11-балльной шкале И.Г. Сивкова).
| Предмет | Количество баллов | Предмет | Количество баллов |
| Математика | 11 | Физическая культура, ритмика | 5 |
| Иностранный язык | 10 | Художественный труд | 4 |
| История | 8 | Рисование | 2 |
| Русский язык, чтение | 7 | Пение, музыка | 1 |
| Природоведение, естествознание, окружающий мир | 6 |
Таблица 4. Шкала трудности учебных предметов для учеников 5-9-х классов (по 13-балльной шкале М.И. Степановой, И.Э. Александровой, А.С. Седовой).
| Школьные предметы* | Количество баллов (ранг трудности) | ||||
| 5-е классы | 6-е классы | 7-е классы | 8-е классы | 9-е классы | |
| Алгебра | 10 | 9 | 7 | ||
| Биология | 10 | 8 | 7 | 7 | 7 |
| География | |||||
| Геометрия | 12 | 10 | 8 | ||
| ИЗО | |||||
| Иностранный язык | 9 | 11 | 10 | 8 | 8 |
| Информатика | 2 | 10 | 4 | 7 | 7 |
| История, обществознание | 5 | 8 | 6 | 8 | 10 |
| Литература | 4 | 6 | 4 | 4 | 7 |
| Математика | 10 | 13 | |||
| Музыка | 2 | 1 | 1 | 1 | |
| МХК | 5 | 5 | |||
| ОБЖ | 1 | 2 | 3 | 3 | 3 |
| Природоведение | 7 | 8 | |||
| Ритмика | 4 | ||||
| Русский язык | 8 | 12 | 11 | 7 | 6 |
| Труд | 4 | 3 | 2 | 1 | 4 |
| Физика | 8 | 9 | 13 | ||
| Физическая культура | 3 | 4 | 2 | 2 | 2 |
| Химия | 13 | 10 | 12 | ||
| Черчение | 5 | 4 | |||
| Экология | 3 | 3 | 3 | 6 | 1 |
| Экономика | 11 | ||||
| Этикет | 7 | 5 | |||
* В перечень включены и факультативные курсы.
Таблица 5. Шкала трудности учебных предметов для учащихся 10-11-х классов (по 13-балльной шкале М.И. Степановой, И.Э. Александровой, А.С. Седовой).
| Предмет | Количество баллов | Предмет | Количество баллов |
| Физика | 12 | Информатика Экономика |
6 |
| Геометрия, химия | 11 | История Обществознание МХК |
5 |
| Алгебра | 10 | Астрономия | 4 |
| Русский язык | 9 | География Экология | 3 |
| Литература, иностранный язык | 8 | ОБЖ Москвоведение | 2 |
| Биология | 7 | Физическая культура | 1 |
Расписание составлено неправильно, когда наибольшее число баллов за день приходится на крайние дни недели или когда оно одинаково во все дни недели.
На практике из перечисленных выше требований полностью выполнить удается только первое, два других требования, как правило, учитываются только частично. Это может быть связано и с большим количеством классов, нехваткой учебных кабинетов, привлечение вузовских преподавателей и т.д.
Помимо требований со стороны законодательства выставляемых к составлению расписания, необходимо учитывать следующие моменты:
1. Пожелания учителей к составлению расписания.
У каждого учителя существуют личные причины работать в тот или иной день, время или в том или ином кабинете и т.д.
2. Загруженность классов с дополнительными услугами.
На практике встречаются “классы +” – это классы с дополнительными услугами, у них кроме основных учебных предметов ведутся занятия бальных танцев, бассейн, дополнительные занятия по математике, английскому языку и т.д.
3. Распределение учебных кабинетов.
Нехватка учебных классов из-за большого количества классов, проведение занятий в две смены. Так же здесь необходимо учитывать проведение дополнительных занятий для подготовки к олимпиадам, различным конференциям, консультаций по ЕГЭ, а так же индивидуальную работу учителя с учащимися.
С чего же начать составлять расписание начинающему:
А) Распределение учебной нагрузки между учителями. Особое внимание следует обратить на предметы, где занятия проходят при делении на подгруппы (например, английский язык, информатика и т.д.). Удобно, если пары учителя работают в одних и тех же классах.
Например: Английский язык
| Ф.И.О. | 2а | 2б | 2в | 3а | 3б | 3в | 4а | 4б | 4в | 5а | 5б | 5в | 11б |
| Валиева С.Т. | 2 | 2 | 2 | 2 | 2 | 2 | 3\3 | ||||||
| Ергулева Е.В. | 2 | 2 | 2 | 3 | 3 | ||||||||
| Ерзина Л.В. | 2 | 2 | 2 | 2 | 2 | ||||||||
| Шайдулина З.Р. | 2 | 2 | 2 | 3 | 3 | 3/3 |
Надо постараться, чтобы как можно меньше было ситуаций, когда один учитель ведет занятия в обоих подгруппах класса (из примера выше Шайдуллина З.Р. в 5в классе, Валиева С.Т. в 11 б классе)
Б) Распределение методических дней учителей: подсчитать общее количество баллов недельной нагрузки в каждом классе по учебному плану (можно использовать таблицы 3–5), с учетом факультативов. Распределите баллы на дни недели с учетом благоприятных и неблагоприятных дней (таблицы 1–2).
В) Ввод данных об учителе в программе Ректор:
- в разделе Списки – Свойства учителя чтобы указать методический день необходимо выделить выходным день недели и количество желаемых методических дней указать 0, чтобы программа сама не определила методдень на свое усмотрение. Из примера1 у учителя Басовой методический день – среда (см. Рисунок 1).
Рис. 1
- в разделе Нагрузка – Учителя желательно ввести кроме основных часов учителя, также указать все дополнительные часы. Это необходимо сделать, чтобы при составлении расписания зарезервировать день и час для данных занятий, например:7 уроками для проведения консультаций, чтобы было удобно учащимся. Можно попросить учителей, чтобы они обсудили это время заранее с учащимися.
- Если у учителя нет закрепленного за ним кабинета, то кабинет при вводе нагрузки указывать не надо. Распределение свободных кабинетов быстро производиться после составления расписания в разделе Расписание – Кабинеты.
- Ввод нагрузки, когда один учитель ведет урок в двух подгруппах, например: в 11б классе английский язык (3 часа) в двух подгруппах ведет Валиева С.Т.. Получается, что занятия английского языка в этом классе можно распределить в расписании только первыми или последними уроками в классе. Выход следующий: 1 час английского языка объединить в группу с информатикой (рисунок 2–3). Оставшиеся 2 часа английского вводим в один прием, с обязательным указанием, что группы одновременно не занимаются и уроки должны быть крайними (рисунок 4).
В аналогичных ситуациях необходимо искать предмет, с которым можно объединиться в пару. Обязательно нужно проконтролировать общую нагрузку учителя, с данном случае часто происходит потеря часов.
- Совместители: Учителя по совместительству работают по определенным дням, поэтому при вводе данных в разделе Списки – Свойства учителя необходимо сразу указать дни и время их работы.
Г) При составлении расписании удобно использовать таблицу 6.
В столбце Ф.И.О. вводиться список учителей по кафедрам, сначала учителя русского языка и литературы, математики и информатики, физики, биологи, химии, английского языка, татарского языка, технологии, музыки, ИЗО, физической культуры, ОБЖ. Данную таблицу можно получить и программе ректор в разделе Расписание – Учителя и запустить Мастер печати расписания учителя. Для удобства обработки и сортировки данных необходимо выбрать формат файла Excel. Конечно, таблица получается не на один лист, а на несколько, но зато по ней можно увидеть большое количество информации: распределение недельной нагрузки всех учителей, окна, методический день, во сколько заканчиваются уроки в классах по сменам, и многое другое. Данную таблицу хорошо научиться читать по вертикали, это позволяет при необходимости быстро находить замены учителей в классах. Совет: Чтобы быстро запомнить расписание учителей и легко в нем ориентироваться, то данную таблицу заполнить самому карандашом. И если затем будут производиться изменения в расписании, то и в данной таблице обязательно нужно вносить корректировки. Расписание в таком виде всегда должно находиться под рукой у замдиректора по УР.
Начинать составление расписания надо с учителей, которые ведут занятия в подгруппах, используя функцию поиска расписания. Еще раз следует отметить, что программа при составлении расписании для учителей в парах, может получить расписание одному учителю без окон, а другому учителю, стоящему с ним в паре, может оставить большое количество окон. Поэтому полученное расписание необходимо занести в таблицу 6 (или распечатать ее из программы только на данных учителей), проанализировать и исправить неточности в расписании.
Далее аналогичным способом обрабатываем расписание учителей, где уроки должны быть в парах. Затем обрабатываем учителей-совместителей, русского языка, математики, и т.д.