Составить расписание всегда былом делом непростым. Доверить эту задачу компьютеру решались не все, потому что задача NP-полная и алгоритмического решения «в лоб» за обозримое время не имеет (объяснение).
Недавно ко мне в руки попал пакет математического решателя IBM CPLEX Solver и я попробовала сделать помощника для составления школьного расписания.
Модель решила сделать целочисленную, еще её называют MIP.
Исходные данные
Действующих лиц у нас четыре. Поэтому пусть будет четыре оси системы координат. Т.е. наше пространство будет четырехмерным. Зададим их в виде одномерных массивов данных:
Название оси |
Пример данных |
Пример в dat файле |
классы учеников |
5а или 9б |
classes = {"5a", "5b", "6a", "6b", "7a", "7b", "8a", "8b", "9a", "9b","10a", "10b", "11a", "11b"}; |
учителя |
Иванова Мария Ивановна, Петрова Татьяна Сергеевна и т.д. |
teachers = {"ivanova", "petrova_en", "sidorova_ge", "shumova", "trudovik_m", "trudovik_w", "stoprtteacher"}; |
кабинеты |
это про физические комнаты: 101 кабинет, спорт. зал, кабинет труда № 105, кабинет физики № 205 и т.д. |
rooms = {"18", "sport1", "trudy_m", "trudy_w" , "21","22","23","24", "25", "26", "27", "31","32","33","34"}; |
уроки |
это вакантные места в расписании. Выглядит это как 3х-значное число, в котором первая цифра – это номер дня от 1 до 6, если учатся по шестидневке и до 5, если по пятидневке вторя цифра – номер смены 1 или 2 третья цифра – номер урока в смене. Обычно от 1 до 6 или до 7 |
// day, shift, lesson number |
Между осями координат у нас получаются плоскости. И тут можно наложить ограничения на эти плоскости. Они представляют собой двумерные матрицы. В этих матрицах хранятся определенные целочисленные значения. Далее подробнее про каждое соотношение:
Название плоскости |
Пример |
Как выглядит в dat файле |
Отношения между кабинетами и учителями |
Хранится целое число >= 0. Если учитель НЕ может работать в этом кабинете – то 0. Например, нельзя проводить физкультуру в кабинете математики. Но можно провести математику в кабинете физики. Тут будем играть приоритетами. 1 – самый лучший кабинет для этого учителя. 2 – не такой хороший, 3 – приемлемый, но нежелательный. Далее мы еще используем это в целевой функции. |
roomTeachersRelation = [ |
Отношение между учителями и классами учеников |
Тут пишем сколько уроков в неделю должен провести конкретный учитель у конкретного класса. Например, Иванова М.И. должна провести 4 русских языка и 2 литературы в неделю у 6 Б класса. Значит в пересечении пишем цифру 4 + 2 = 6 |
teacherClassRelation = [ |
Отношение между классами учеников и уроками |
Значения этой матрицы 0 или 1. А точнее тут мы задаем в какой смене учится класс. Если 0 – то класс не может иметь уроки в это время. |
classLessonRelation = [ |
Отношение между учителями и номером урока |
Значение этой матрицы 0 или 1. Если стоит 0 – значит учитель не может вести уроки в это время. Это на тот случай, если какой-то учитель может работать только в определённые дни недели. Например, учителя с маленькими детьми не работают по субботам. |
teacherLessonRelation = [ |
Графически все вместе (4 оси координат и соотношения между ними) можно представить, как четырёхмерный куб. У нас есть 4 измерения и 4 заданные поверхности. Можно ограничить и больше поверхностей, например, соотношение классов и кабинетов, если каким-то классам нельзя ставить уроки в этих кабинетах. Или между номером урока и кабинетом, если какой-то кабинет недоступен, например, в среду. Но пока ограничимся малым.
Переменная для результата
В такой постановке задачи переменной для хранения результата являться 4х мерный массив, в котором каждое значение может быть 0 или 1.
1 - означает, что условия соотношений выполняется и урок может быть у данного класса, учителя в данном кабинете и в данное время.
0 - означает, что четыре условия не выполняются.
dvar int schedule [rooms][teachers][classes][lessons] in 0..1;Задание ограничений в модели
Имея все данные и переменные следует задать ограничения.
Самое строгое ограничение, что если в наших двумерных массивах встречается ноль, то и в результирующей переменной должен быть ноль
forall(
r in rooms,
t in teachers,
c in classes,
l in lessons
)
if(roomTeachersRelation[r][t] == 0 || teacherClassRelation[t][c] == 0 || classLessonRelation[c][l] == 0 || teacherLessonRelation[t][l] == 0)
{
schedule[r][t][c][l] == 0;
} Используем ограничение по поверхности между учителями и классами учеников
Мы знаем количество уроков в неделю, которое должен провести учитель у класса. Поэтому получаем такое ограничение: для каждого учителя и каждого класса сумма уроков в кабинетах должна быть равна цифре из нашего ограничения.
// teacher - class relations
forall( t in teachers, c in classes)
sum(r in rooms, l in lessons)
schedule[r][t][c][l] == teacherClassRelation[t][c]; Используем ограничение по поверхности между кабинетами и номерами уроков
В одном кабинете может проходить только один урок, что естественно
// room - lesson relations
forall(r in rooms, l in lessons)
sum(t in teachers, c in classes)
schedule[r][t][c][l] <= 1;Используем ограничение по поверхности между учителями и номерами уроков.
Потому что один учитель может присутствовать только на одном уроке
// teacher - lesson relations
forall( t in teachers, l in lessons)
sum(r in rooms, c in classes)
schedule[r][t][c][l] <= 1;И последнее ограничение по поверхности между классами учеников и номерами уроков. Это ограничение самое сложное, потому что для таких предметов как иностранный язык, физкультура, труды, информатика характерно разделение на подгруппы.
Подрассказ как решена проблема разделения на подгруппы
В реальной школе классы часто делятся на подгруппы: физкультура у юношей и девушек, труды у мальчиков и девочек, подгруппы по языку и информатике.
У этой проблемы тоже есть решение: введем набор данных для хранения подмножества «особенных» учителей. Например, учителя иностранного:
{string} foreignLangTeachers = ...;Тогда в ограничениях к модели напишем, что класс в одно и тоже время может быть у двух разных учителей и в разных кабинетах.
// class - lesson relations
forall( c in classes, l in lessons )
sum(r in rooms, t in teachers : t not in foreignLangTeachers)
schedule[r][t][c][l] <= 1;
forall( c in classes, l in lessons )
sum(r in rooms, t in teachers : t in foreignLangTeachers)
schedule[r][t][c][l] <= 2;
forall( c in classes, l in lessons )
sum(r in rooms, t in teachers : t not in trudyTeachers)
schedule[r][t][c][l] <= 1;
forall( c in classes, l in lessons )
sum(r in rooms, t in teachers : t in trudyTeachers)
schedule[r][t][c][l] <= 2;
forall( c in classes, l in lessons )
sum(r in rooms, t in teachers : t not in informaticsTeachers)
schedule[r][t][c][l] <= 1;
forall( c in classes, l in lessons )
sum(r in rooms, t in teachers : t in informaticsTeachers)
schedule[r][t][c][l] <= 2;
forall( c in classes, l in lessons )
sum(r in rooms, t in teachers : t not in sportTeachers)
schedule[r][t][c][l] <= 1;
forall( c in classes, l in lessons )
sum(r in rooms, t in teachers : t in sportTeachers)
schedule[r][t][c][l] <= 2;Целевая функция
При написании мат. модели требуется еще задать целевую функцию. Т.е. обозначить к чему мы стремимся. Тут нужно обратиться к пользователю и узнать, что для них важно. Первое, это чтобы уроки для учеников проводились как можно раньше в сутках. Т.е. желательно, чтобы все начинали учиться с первого урока своей смены. Второе требование, это чтобы учителя начинали работать пораньше. Третье условие, чтобы учителя вели уроки в приемлемых кабинетах. Но если это невозможно, то выбираем из того, что есть. Выглядит целевая функция следующим образом:
minimize
staticLex(
sum(c in classes, l in lessons) ( ClassLessonResult [c][l] * l )
,
sum(t in teachers, l in lessons) ( TeacherLessonResult [t][l] * l )
,
sum(r in rooms, t in teachers, c in classes, l in lessons) schedule[r][t][c][l] * roomTeachersRelation[r][t]
)
;Удобство считывания результата
Для удобства обработки результатов в более наглядном виде в OPL Studio я ввела дополнительные переменные
dvar int TeacherLessonResult[teachers][lessons] ;
dvar int ClassLessonResult[classes][lessons] ;
dvar int RoomLessonResult[rooms][lessons];
dvar int TeacherClassResult [teachers][classes];
dvar int RoomClassResult [rooms][classes];
dvar int RoomTeacherResult [rooms][teachers];Эти переменные копируют состояние соответствующих поверхностей в переменной schedule.
Поэтому можно видеть такие полезные наглядные результаты
Модель
Вот так выглядит полная модель
{string} rooms = ...;
{string} teachers = ...;
{string} foreignLangTeachers = ...;
{string} trudyTeachers = ...;
{string} informaticsTeachers = ...;
{string} sportTeachers = ...;
{string} classes = ...;
{int} lessons = ...;
int roomTeachersRelation [rooms][teachers]= ...;
int teacherClassRelation [teachers][classes] = ...;
int classLessonRelation [classes][lessons] = ...;
int teacherLessonRelation [teachers][lessons] = ...;
dvar int TeacherLessonResult[teachers][lessons] ;
dvar int ClassLessonResult[classes][lessons] ;
dvar int RoomLessonResult[rooms][lessons];
dvar int TeacherClassResult [teachers][classes];
dvar int RoomClassResult [rooms][classes];
dvar int RoomTeacherResult [rooms][teachers];
dvar int schedule [rooms][teachers][classes][lessons] in 0..1;
minimize
staticLex(
sum(c in classes, l in lessons) ( ClassLessonResult [c][l] * l )
,
sum(t in teachers, l in lessons) ( TeacherLessonResult [t][l] * l )
,
sum(r in rooms, t in teachers, c in classes, l in lessons) schedule[r][t][c][l] * roomTeachersRelation[r][t]
)
;
subject to
{
forall(
r in rooms,
t in teachers,
c in classes,
l in lessons
)
if(roomTeachersRelation[r][t] == 0 || teacherClassRelation[t][c] == 0 || classLessonRelation[c][l] == 0 || teacherLessonRelation[t][l] == 0)
{
schedule[r][t][c][l] == 0;
}
// teacher - class relations
forall( t in teachers, c in classes)
sum(r in rooms, l in lessons)
schedule[r][t][c][l] == teacherClassRelation[t][c];
forall( t in teachers, c in classes)
TeacherClassResult[t][c] == sum(r in rooms, l in lessons) schedule[r][t][c][l];
// room - lesson relations
forall(r in rooms, l in lessons)
sum(t in teachers, c in classes)
schedule[r][t][c][l] <= 1;
forall(r in rooms, l in lessons)
RoomLessonResult[r][l] == sum(t in teachers, c in classes) schedule[r][t][c][l] ;
// teacher - lesson relations
forall( t in teachers, l in lessons)
sum(r in rooms, c in classes)
schedule[r][t][c][l] <= 1;
forall( t in teachers, l in lessons)
TeacherLessonResult[t][l] == ( sum(r in rooms, c in classes) schedule[r][t][c][l] ) ;
// class - lesson relations
forall( c in classes, l in lessons )
sum(r in rooms, t in teachers : t not in foreignLangTeachers)
schedule[r][t][c][l] <= 1;
forall( c in classes, l in lessons )
sum(r in rooms, t in teachers : t in foreignLangTeachers)
schedule[r][t][c][l] <= 2;
forall( c in classes, l in lessons )
sum(r in rooms, t in teachers : t not in trudyTeachers)
schedule[r][t][c][l] <= 1;
forall( c in classes, l in lessons )
sum(r in rooms, t in teachers : t in trudyTeachers)
schedule[r][t][c][l] <= 2;
forall( c in classes, l in lessons )
sum(r in rooms, t in teachers : t not in informaticsTeachers)
schedule[r][t][c][l] <= 1;
forall( c in classes, l in lessons )
sum(r in rooms, t in teachers : t in informaticsTeachers)
schedule[r][t][c][l] <= 2;
forall( c in classes, l in lessons )
sum(r in rooms, t in teachers : t not in sportTeachers)
schedule[r][t][c][l] <= 1;
forall( c in classes, l in lessons )
sum(r in rooms, t in teachers : t in sportTeachers)
schedule[r][t][c][l] <= 2;
forall( c in classes, l in lessons )
{
ClassLessonResult [c][l] == ( sum(r in rooms, t in teachers) schedule[r][t][c][l] ) ;
}
//
forall( r in rooms, c in classes)
RoomClassResult[r][c] == ( sum(l in lessons, t in teachers) schedule[r][t][c][l] ) ;
//
forall( r in rooms, t in teachers)
RoomTeacherResult[r][t] == ( sum(l in lessons, c in classes) schedule[r][t][c][l] ) ;
}
Вот так выглядит файл с подготовленными данными
rooms = {"18", "sport1", "trudy_m", "trudy_w" , "21","22","23","24", "25", "26", "27", "31","32","33","34"};
teachers = {"ivanova", "petrova_en", "sidorova_ge", "shumova", "trudovik_m", "trudovik_w", "stoprtteacher"};
foreignLangTeachers = {"petrova_en", "sidorova_ge"};
trudyTeachers = {"trudovik_m", "trudovik_w"};
informaticsTeachers = {"trudovik_m", "trudovik_w"};
sportTeachers = {"trudovik_m", "trudovik_w"};
classes = {"5a", "5b", "6a", "6b", "7a", "7b", "8a", "8b", "9a", "9b","10a", "10b", "11a", "11b"};
// 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*/
};
roomTeachersRelation = [
[2,1,1,1,0,0,0],
[0,0,0,0,0,0,1],
[0,0,0,0,1,0,0],
[0,0,0,0,0,1,0],
[1,2,1,1,0,0,0],
[1,2,1,1,0,0,0],
[2,1,1,1,0,0,0],
[1,2,1,1,0,0,0],
[1,2,1,1,0,0,0],
[2,1,1,1,0,0,0],
[1,2,1,1,0,0,0],
[1,2,1,1,0,0,0],
[1,2,1,1,0,0,0],
[2,1,1,1,0,0,0],
[2,1,1,1,0,0,0]
];
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]
];
classLessonRelation = [
[0,0,0,0,0,0,0,1,1,1,1,1,1,1],
[0,0,0,0,0,0,0,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,0,0,0,0,0,0,0],
[1,1,1,1,1,1,1,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,1,1,1,1],
[0,0,0,0,0,0,0,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,0,0,0,0,0,0,0],
[1,1,1,1,1,1,1,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,1,1,1,1],
[0,0,0,0,0,0,0,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,0,0,0,0,0,0,0],
[1,1,1,1,1,1,1,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,1,1,1,1],
[0,0,0,0,0,0,0,1,1,1,1,1,1,1]
];
teacherLessonRelation = [
[1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1,1,0,0,0]
];
Это была тонировочная попытка автоматизировать составление школьного расписания. Следующим шагом должно быть написание программной «оболочки» для введение реальных данных.
Комментарии (4)
Yerin
04.02.2022 08:13Для подобного класса задач есть еще OR-tools от гугл. В бесплатной версии Cplex есть ограничение на количество данных и условий, поэтому в моем случае (планирование производства) выдавало ошибку.
MrsTroyan Автор
04.02.2022 08:54Согласна, OR-Tools тоже хороший инструмент, но у меня пока и датасет небольшой, поэтому Cplex работал.
JSmitty
как вы собираетесь санпин учитывать (например 5 математик во начальном звене в день нельзя)? и учительский критерий "поменьше окон"?
MrsTroyan Автор
Спасибо за Ваш комментарий.
Критерий "поменьше окон" стараемся удовлетворить в целевой функции, чтобы уроки были ближе к началу дня. Но даже в жизни это иногда почти невозможно, хотя и зависит от конкретной жизненной ситуации (т.е. от датасета).
А чтобы не более 5 математик в день, то нужно ограничение добавить, чтобы сумма по учителю и классу на уроках от 111 до 117, например, не была более 5.