Как написать программу для составления расписания

Содержание

Есть задача — на основе данных о преподах, группах, предметах, количестве часов в неделю для каждого предмета расставить корректное расписание занятий, желательно, оптимальное (без окон у групп и преподов, желательно без перепадов времени (сегодня первая смена, завтра вторая), по возможности, чтобы не было такого, что у препода всего 1 пара в день). В какую сторону копать? Какие есть алгоритмы?

Отслеживать
задан 30 мая 2020 в 10:07
Дима Диман Дима Диман
322 3 3 серебряных знака 15 15 бронзовых знаков

Нифига у вас алгоритмы. Самый простой способ – это брать готовое распсание, а потом свапать уроки. Например, в среду 1 урок свапаем с 4-м, зн. и у 1-го, и у 2-го, и у 3-го, и у <вставьте число сюда>-го классов нужно поменять 1-й и 4-й уроки. Так вы избежите коллизий. Ну а как расставить уроки в вашем случае я пока не знаю, если разберусь, напишу.

30 мая 2020 в 10:28

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

Программа полностью автоматического составления школьного расписания

1 июн 2020 в 10:17
А какова целевая функция, как оценивать оптимальность решения?
7 июн 2020 в 6:54

4 ответа 4

Сортировка: Сброс на вариант по умолчанию

Успешность человеческих начинаний, как правило, обратно пропорциональна предсказуемости их результата. (с) Насим Талеб

Я довольно долго занимался составлением расписания в университете и мне есть что сказать на эту тему.

Первое, к сожалению, программы, которая составляет расписание в полностью автоматическом режим нет. С этим нужно просто смириться. Её нет не потому что это супер-мега сложная задача, а потому что это как раз рутина, которой никому не интересно заниматься, поскольку она не несёт больших экономических выгод. Тех, кого пугает перебор 51! вариантов (1.5511e+66) могут попробовать запустить такой цикл. У меня на (Xeon e5 2678 v3 + GTX 2060) весь процесс занимает 30 минут, поэтому говорить о вычислительной сложности, сейчас, при всём уважении, это просто смешно.

Второе, если Вам необходимо реальное расписание, а не решение теоретической задачи, то нужно иметь ввиду следующее — математически идеальное расписание на практике НЕ будет идеальным. Несколько раз на протяжении 7 лет мне удавалось составить идеальное расписание (в математическом смысле), но ни разу оно не оказалось практически идеальным. Объясню почему, преподавателю внезапно нужно отвести дочку на секцию не в 9 утра, а в 17:00 после школы, вот так изменились обстоятельства, другой сорвал спину на даче, теперь он ходит на процедуры и надо изменить время, третьему перестало быть удобно это время просто потому что. Кроме того, часто бывает такое, что нескольким людям удобно одно и тоже время, а это коллизия, которую можно разрешить только вручную.

Третье, Вы знаете, как преподаватель скажу, провести 3 пары + 2 пары с одним окном, это не тоже самое, что провести 5 пар подряд. То есть, конечно, я не за всех говорю, может кому-то и легче, но наличие окон иногда очень упрощает жизнь и снижает общую нагрузку.

Программа для автоматического составление расписания (ЭлМектеп)

чтобы не было такого, что у препода всего 1 пара в день

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

Идеального варианта не выйдет, но 10к — всяко больше чем сможет самый крутой завуч

Самый крутой завуч (в ВУЗе обычно эту тему курирует зам. декана) сделает любой алгоритм в лёгкую. Люди, которые занимаются составлением расписаний по 15-20 лет делают за пару дней расписание, которое всех устраивает с минимальным числом правок, а из 10к вариантов он сразу видит какие есть смысл рассматривать, а какие нет, потом за пару правок всё становится на свои места.

Как составить школьное расписание с помощью IBM CPLEX Solver

Составить расписание всегда былом делом непростым. Доверить эту задачу компьютеру решались не все, потому что задача NP-полная и алгоритмического решения «в лоб» за обозримое время не имеет (объяснение).

Картинка про 4х мерный куб. Но как она связана с расписанием – внутри статьи

Недавно ко мне в руки попал пакет математического решателя IBM CPLEX Solver и я попробовала сделать помощника для составления школьного расписания.

Исходные данные

Действующих лиц у нас четыре. Поэтому пусть будет четыре оси системы координат. Т.е. наше пространство будет четырехмерным. Зададим их в виде одномерных массивов данных:

Название оси

Пример данных

Пример в 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.

Задание ограничений в модели

Имея все данные и переменные следует задать ограничения.

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

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)

Используем ограничение по поверхности между учителями и классами учеников

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

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

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

Пример. Пусть имеется три процессора и шесть заданий , время выполнения каждого из которых равно:

Рассмотрим расписание В начальный момент времениT=0, процессорначинает обработку задания, процессор— задания, а процессор— задания. Процессорзаканчивает выполнение заданияв момент времении начинает обрабатывать задание, пока процессорыивсе еще работают над своими первоначальными заданиями.

ПриT=3процессоропять заканчивает заданиеи начинает обрабатывать задание, которое завершается в моментT=4. Тогда он начинает выполнять последнее задание.

Процессорыизаканчивают задания приT=5, но, так как списокLпуст, они останавливаются. Процессорзавершает выполнение заданияприT=12. Рассмотренное расписание проиллюстрировано на рис.1. временной диаграммой, известной каксхема Ганта. Очевидно, что расписание не оптимально. Можно «подобрать», например, расписание

, которое позволяет завершить все задания заT* = 8 единиц времени (рис.2.).

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

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