Составить расписание всегда былом делом непростым. Доверить эту задачу компьютеру решались не все, потому что задача 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]
];
Это была тонировочная попытка автоматизировать составление школьного расписания. Следующим шагом должно быть написание программной «оболочки» для введение реальных данных.
ссылка на оригинал статьи https://habr.com/ru/post/649445/
Добавить комментарий