Алгоритм создания школьного расписания

Мне было интересно, есть ли известные решения для алгоритма создания школьного расписания. По сути, речь идет об оптимизации «часового разброса» (как в случае учителей, так и в классе) для определенных ассоциаций класс-предмет-учитель. Мы можем предположить, что у нас есть наборы классов, предметов уроков и учителей, связанных друг с другом на входе, и что расписание должно подходить между 8:00 и 16:00.

Я предполагаю, что для этого, вероятно, нет точного алгоритма, но, возможно, кто-то знает хорошее приближение или подсказки для его разработки.

Эта проблема NP-Complete !
Короче говоря, нужно изучить все возможные комбинации, чтобы найти список приемлемых решений. Из-за различий в обстоятельствах, в которых возникает проблема в разных школах (например: Есть ли ограничения в отношении классов? Разделяются ли некоторые классы на подгруппы некоторое время? Это еженедельное расписание? и т. д.) не существует хорошо известного класса задач, который соответствовал бы всем задачам планирования. Возможно, проблема ранца во многом похожа на эти проблемы в целом.

Подтверждением того, что это одновременно сложная проблема и проблема, решение которой люди постоянно ищут, является проверка этого (длинного) списка (в основном коммерческих) инструментов планирования программного обеспечения.

Из-за большого количества задействованных переменных, самым большим источником которых, как правило, являются желания преподавателя; -) ..., обычно нецелесообразно рассматривать перечисление всех возможных комбинаций . Вместо этого нам нужно выбрать подход, который обращается к подмножеству областей проблемы / решения.
- Генетические алгоритмы , процитированные в другом ответе, (или, IMHO, кажется ) хорошо оснащены для выполнения такого рода полууправляемого поиска (проблема заключается в том, чтобы найти хорошую функцию оценки для кандидатов, которые будут сохранены для следующего поколения)
- График Подходы переписывания также используются с этим типом задач комбинаторной оптимизации.

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

• Определение и ранжирование всех известных ограничений
• Сокращение проблемного пространства за счет добавления набора дополнительных ограничений вручную .
  Это может показаться нелогичным, но, например, предоставляя начальное, частично заполненное расписание (скажем, примерно 30% временных интервалов) таким образом, чтобы полностью удовлетворить все ограничения, и, считая это частичное расписание неизменным, мы значительно сокращаем время / пространство, необходимое для выработки возможных решений.
  Другой способ помочь дополнительным ограничениям - это, например, «искусственное» добавление ограничения, которое не позволяет преподавать некоторые предметы в некоторые дни недели (если это недельный график ...); этот тип ограничений приводит к сокращению пространства проблем / решений, как правило, без исключения значительного числа хороших кандидатов.
• Обеспечение быстрого вычисления некоторых ограничений проблемы. Это часто связано с выбором модели данных, используемой для представления проблемы; идея состоит в том, чтобы иметь возможность быстро выбрать (или исключить) некоторые из вариантов.
• Переопределение проблемы и разрешение несколько раз нарушить некоторые ограничения (обычно в направлении конечных узлов графа). Идея здесь состоит в том, чтобы либо удалить некоторые ограничения для заполнения последних нескольких слотов в расписании, либо заставить программу автоматического генератора расписания перестать стесняться завершения всего расписания, вместо этого предоставив нам список из дюжины или около того правдоподобных кандидаты. Человек часто находится в лучшем положении, чтобы решить головоломку, как указано, возможно, нарушив несколько ограничений, используя информацию, которая обычно не передается автоматизированной логике (например, правило «Никакой математики во второй половине дня» может быть нарушено в некоторых случаях для класса "продвинутая математика и физика" или "Лучше нарушить одно из требований мистера Джонса, чем одно из требований мисс Смит ... ;-))

Корректируя этот ответ, я понимаю, что он довольно стесняется дать определенный ответ, но, тем не менее, он полон практических предложений. Я надеюсь, что это поможет в том, что, в конце концов, является «сложной проблемой».

Это беспорядок. королевский беспорядок. В дополнение к уже очень полным ответам я хочу отметить свой семейный опыт. Моя мама была учителем и принимала участие в процессе.

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

• учитель преподает и в вашей школе, и в другом институте. Понятно, что если он заканчивает урок там в 10.30, он не может начать у вас в 10.30, потому что ему нужно время, чтобы добираться между институтами.
• два учителя женаты. В целом считается хорошей практикой не иметь двух женатых учителей в одном классе. Следовательно, эти два учителя должны иметь два разных класса.
• два учителя женаты, и их ребенок учится в одной школе. Опять же, вы должны запретить двум учителям преподавать в том классе, где находится их ребенок.
• в школе есть отдельные помещения, например, сегодня класс в одном институте, а в другой - в другом.
• в школе есть общие лаборатории, но эти лаборатории доступны только в определенные будние дни (например, из соображений безопасности, когда требуется дополнительный персонал).
• некоторые учителя предпочитают свободный день: кто-то предпочитает понедельник, кто-то пятницу, кто-то среду. Кто-то предпочитает приходить рано утром, кто-то - позже.
• у вас не должно быть ситуаций, когда у вас будет урок, скажем, истории в первый час, затем три часа математики, затем еще час истории. Это не имеет смысла ни для учеников, ни для учителя.
• аргументы следует распределить равномерно. Нет смысла проводить первые дни недели только по математике, а затем в остальные дни недели только по литературе.
• Вы должны дать некоторым учителям два часа подряд для проведения оценочных тестов.

Как видите, проблема не NP-полная, это NP-безумная.

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

На Международном соревновании по расписанию 2007 г. были предусмотрены дорожки для расписания уроков и экзаменов. В этом конкурсе участвовали многие исследователи. Было испробовано множество эвристик и метаэвристик, но в конце концов метаэвристики локального поиска (такие как Tabu Search и Simulated Annealing) явно превзошли другие алгоритмы (например, генетические алгоритмы).

Взгляните на 2 фреймворка с открытым исходным кодом, которые использовали некоторые из финалистов:

• JBoss OptaPlanner (Java, открытый исходный код)
• Unitime (Java, открытый код) - больше для университетов

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

Весь стол - это один «организм». Были внесены некоторые изменения и предостережения в подход к универсальным генетическим алгоритмам:

• Были установлены правила для «незаконных столов»: два класса в одном классе, один учитель обучает две группы одновременно и т. Д. Эти мутации сразу же считались смертельными, и на месте «умершего» немедленно появлялся новый «организм». Первоначальный был сгенерирован серией случайных попыток получить легальный (хотя и бессмысленный). Летальная мутация не учитывалась при подсчете мутаций в итерации.

• «Обменные» мутации были гораздо более распространены, чем «Модифицирующие». Изменения коснулись только тех частей гена, которые имели смысл - учителя нельзя было заменить классом.

• Небольшие бонусы были назначены за объединение определенных 2 часов вместе, за последовательное назначение одной и той же общей классной комнаты для одной и той же группы, за поддержание непрерывности рабочего времени учителя и нагрузки класса. Умеренные бонусы назначались за предоставление правильных классных комнат по данному предмету, за соблюдение ограничений на часы занятий (утром или днем) и тому подобное. Большие бонусы были за правильное присвоение номера предмета, заданной нагрузки учителя и т. Д.

• Учителя могут составлять свои графики нагрузки: «хочу работать тогда», «тогда можно работать», «тогда не любит работать», «тогда не могу работать», с правильными весами. Все 24 часа были законными рабочими часами, за исключением того, что ночное время было очень нежелательным.

• Функция веса ... о да. Весовая функция была огромным чудовищным произведением (как в умножении) весов, присвоенных выбранным функциям и свойствам. Он был чрезвычайно крутым, одно свойство легко могло изменить его на порядок в большую или меньшую сторону - а в одном организме были сотни или тысячи свойств. Это привело к абсолютно ОГРОМНЫМ числам в качестве весов и, как прямой результат, к необходимости использовать библиотеку bignum (gmp) для выполнения вычислений. Для небольшого теста, состоящего из 10 групп, 10 учителей и 10 классных комнат, начальный набор начинался с отметки 10 ^ -200something и завершался 10 ^ + 300something. Когда он был более плоским, это было совершенно неэффективно. Кроме того, ценности выросли намного дальше с большими «школами».

• По времени вычислений разница между небольшой популяцией (100) в течение длительного времени и большой популяцией (10k +) в течение меньшего количества поколений была небольшой. Вычисления за одно и то же время дали примерно такое же качество.

• Расчет (на некоторых процессорах с тактовой частотой 1 ГГц) потребует около 1 часа для стабилизации около 10 ^ + 300, генерируя графики, которые выглядели довольно хорошо для указанного тестового примера 10x10x10.

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

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

Эта проблема сложнее, чем кажется.

Как уже упоминали другие, это NP-полная проблема, но давайте проанализируем, что это значит.

По сути, это означает, что вам нужно рассматривать все возможные комбинации.

Но «посмотри на» мало что скажет о том, что вам нужно делать.

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

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

Для этого вам нужно больше, чем просто «возможно ли это решение».

Например, один и тот же учитель работает 5 дней в неделю в течение X недель подряд? Даже если это рабочее решение, оно может быть не лучшим решением, чем чередование двух человек, чтобы каждый учитель работал по одной неделе каждый. О, ты не думал об этом? Помните, вы имеете дело с людьми, а не только с проблемой распределения ресурсов.

Даже если бы один учитель мог работать полный рабочий день в течение 16 недель подряд, это могло бы быть неоптимальным решением по сравнению с решением, в котором вы пытаетесь чередовать учителей, а такую ​​балансировку очень сложно встроить в программное обеспечение.

Подводя итог, можно сказать, что хорошее решение этой проблемы будет дорого стоить многим людям. Следовательно, эту проблему нелегко сломать и решить. Будьте готовы выделить несколько целей, которые не являются стопроцентными, и назвать их «достаточно хорошими».

Мой алгоритм расписания, реализованный в FET (бесплатное программное обеспечение для расписания, http://lalescu.ro/liviu/fet/ , успешное приложение):

Алгоритм эвристический. Я назвал это «рекурсивным свопингом».

Вход: набор действий A_1 ... A_n и ограничения.

Выход: набор времен TA_1 ... TA_n (временной интервал каждого действия. Комнаты здесь исключены для простоты). Алгоритм должен помещать каждое действие в определенный временной интервал, соблюдая ограничения. Каждый TA_i находится в пределах от 0 (T_1) до max_time_slots-1 (T_m).

Ограничения:

C1) Базовый: список пар действий, которые не могут быть одновременными (например, A_1 и A_2, потому что у них один и тот же учитель или одни и те же ученики);

C2) Множество других ограничений (здесь исключены для простоты).

Алгоритм расписания (который я назвал «рекурсивным переключением»):

1. Сортировка занятий, сначала самое сложное. Не критичный шаг, но ускоряет алгоритм может быть в 10 и более раз.

2. Постарайтесь разместить каждое действие (A_i) в разрешенном временном интервале, следуя приведенному выше порядку, по одному. Найдите доступный слот (T_j) для A_i, в котором можно разместить это действие с соблюдением ограничений. Если доступно больше слотов, выберите случайный. Если ничего не доступно, выполните рекурсивную замену:

   а . Для каждого временного интервала T_j подумайте, что произойдет, если вы поместите A_i в T_j. Будет список других действий, которые не согласуются с этим ходом (например, действие A_k находится в том же слоте T_j и имеет того же учителя или тех же учеников, что и A_i). Ведите список конфликтующих действий для каждого временного интервала T_j.

   б . Выберите слот (T_j) с наименьшим количеством конфликтующих действий. Скажем, список действий в этом слоте содержит 3 действия: A_p, A_q, A_r.

   c . Поместите A_i в T_j и сделайте A_p, A_q, A_r нераспределенными.

   d . Рекурсивно попробуйте разместить A_p, A_q, A_r (если уровень рекурсии не слишком велик, скажем 14, и если общее количество рекурсивных вызовов, подсчитанных с момента начала шага 2) на A_i началось, не слишком велико, скажем 2 * n), как на шаге 2).

   е . Если успешно размещены A_p, A_q, A_r, вернитесь с успехом, в противном случае попробуйте другие временные интервалы (перейдите к шагу 2 b) и выберите следующий лучший временной интервал).

   f . Если все (или разумное количество) временных интервалов были испробованы безуспешно, вернитесь безуспешно.

   г . Если мы находимся на уровне 0, и нам не удалось разместить A_i, поместите его, как в шагах 2 b) и 2 c), но без рекурсии. Теперь у нас есть еще 3 - 1 = 2 задания. Перейдите к шагу 2) (здесь используются некоторые способы избежать езды на велосипеде).

ОБНОВЛЕНИЕ: из комментариев ... тоже должна быть эвристика!

Я бы пошел с Prolog ... затем использовал Ruby или Perl или что-то еще, чтобы очистить ваше решение до более красивой формы.

teaches(Jill,math).
teaches(Joe,history).

involves(MA101,math).
involves(SS104,history).

myHeuristic(D,A,B) :- [test_case]->D='<';D='>'.
createSchedule :- findall(Class,involves(Class,Subject),Classes),
                  predsort(myHeuristic,Classes,ClassesNew),
                  createSchedule(ClassesNew,[]).
createSchedule(Classes,Scheduled) :- [the actual recursive algorithm].

Я (все еще) пытаюсь сделать что-то похожее на эту проблему, но использую тот же путь, о котором я только что упомянул. Пролог (как функциональный язык) действительно упрощает решение NP-Hard задач.

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

Нашел этот пример (Составление расписания занятий с использованием генетического алгоритма), который очень хорошо соответствует вашим требованиям.

Вот несколько ссылок, которые я нашел:

Расписание занятий - список некоторых проблем

Гибридный генетический алгоритм для составления школьного расписания

Утилиты и инструменты для планирования

В этой статье довольно хорошо описывается школьное расписание и подход к алгоритму: « Разработка программы - интерактивного планировщика на основе ограничений для школ и колледжей». [PDF]

Автор сообщает мне, что программное обеспечение SYLLABUS все еще используется / разрабатывается здесь: http://www.scientia.com/uk/

Я работаю над широко используемым механизмом планирования, который делает именно это. Да, это NP-Complete; лучшие подходы стремятся приблизить оптимальное решение. И, конечно, есть много разных способов сказать, какое из них является «лучшим» - что важнее, чтобы учителя были довольны своим расписанием, или, например, чтобы ученики посещали все свои классы?

Абсолютно самый важный вопрос, который вам нужно решить на раннем этапе, - что делает один способ планирования этой системы лучше другого ? То есть, если у меня есть расписание, в котором миссис Джонс преподает математику в 8 лет, а мистер Смит преподает математику в 9, это лучше или хуже, чем в расписании, когда они оба преподают математику в 10? Это лучше или хуже, чем когда миссис Джонс преподает в 8 лет, а мистер Джонс преподает в 2 года? Зачем?

Главный совет, который я могу здесь дать, - разделить проблему как можно больше - может быть, курс на курс, может учитель на учителя, может быть, комната за комнатой - и сначала поработайте над решением подзадачи. Здесь у вас должно быть несколько решений на выбор, и нужно выбрать одно как наиболее вероятное оптимальное. Затем поработайте над тем, чтобы «более ранние» подзадачи учитывали потребности более поздних подзадач при оценке их потенциальных решений. Затем, возможно, поработайте над тем, как выйти из закрашенных в угол ситуаций (при условии, что вы не можете предвидеть эти ситуации в более ранних подзадачах), когда вы перейдете в состояние «нет правильных решений».

Этап оптимизации локального поиска часто используется для «полировки» конечного ответа и достижения лучших результатов.

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

Как правило, программирование с ограничениями является хорошим подходом к этому типу задач планирования. Поиск по «программированию с ограничениями» и планированию или «планированию на основе ограничений» как в пределах стека, так и в Google даст несколько хороших ссылок. Это не невозможно - просто об этом немного сложно подумать при использовании традиционных методов оптимизации, таких как линейная или целочисленная оптимизация. Один из выходов - существует ли расписание, удовлетворяющее всем требованиям? Это само по себе, очевидно, полезно.

Удачи !

Я разработал коммерческие алгоритмы как для расписания занятий, так и для расписания экзаменов. Сначала я использовал целочисленное программирование; для второго - эвристика, основанная на максимизации целевой функции путем выбора смены слотов, очень похожая на первоначальный ручной процесс, который был разработан. Главное в принятии таких решений - это способность представить все ограничения реального мира; и для людей, составляющих расписание, чтобы они не видели способов улучшить решение. В конце концов, алгоритмическая часть была довольно простой и простой в реализации по сравнению с подготовкой баз данных, пользовательским интерфейсом, возможностью составления отчетов по статистике, такой как использование комнаты, обучение пользователей и так далее.

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

Есть и другие удачные подходы. Все реализовано в open source проектах:

• Подход на основе ограничений
  • Реализовано в UniTime (не совсем для школ)
  • Вы также можете пойти дальше и использовать целочисленное программирование. Успешно выполнено в университете Удине, а также в университете Байройта (я был там задействован) с использованием коммерческого программного обеспечения (ILOG CPLEX)
  • Подход на основе правил с эвристикой - см. Планировщик Drools
• Различная эвристика - FET и моя собственная

См. Здесь список программного обеспечения для расписания

Я думаю, вам следует использовать генетический алгоритм, потому что:

• Он лучше всего подходит для крупных проблемных ситуаций.
• Это снижает временную сложность за счет неточного ответа (не самое лучшее)
• Вы можете легко указать ограничения и предпочтения, изменив фитнес-наказания за невыполненные.
• Вы можете указать срок выполнения программы.

• Качество решения зависит от того, сколько времени вы собираетесь потратить на решение программы.

  Определение генетических алгоритмов

  Учебник по генетическим алгоритмам

  Проект планирования занятий с GA

Также посмотрите: аналогичный вопрос и еще один

Я не знаю, что кто-то согласится с этим кодом, но я разработал этот код с помощью своего собственного алгоритма и работает для меня в ruby. Надеюсь, это поможет им, кто ищет его в следующем коде: periodflag, dayflag subjectflag и teacherflag - это хэш с соответствующим идентификатором и значением флага, которое является логическим. По любым вопросам, свяжитесь со мной ....... (-_-)

periodflag.each do | k2, v2 |

            if(TimetableDefinition.find(k2).period.to_i != 0)
                subjectflag.each do |k3,v3|
                    if (v3 == 0)
                        if(getflag_period(periodflag,k2))
                            @teachers=EmployeesSubject.where(subject_name: @subjects.find(k3).name, division_id: division.id).pluck(:employee_id)
                            @teacherlists=Employee.find(@teachers)
                            teacherflag=Hash[teacher_flag(@teacherlists,teacherflag,flag).to_a.shuffle] 
                            teacherflag.each do |k4,v4|
                                if(v4 == 0)
                                    if(getflag_subject(subjectflag,k3))
                                        subjectperiod=TimetableAssign.where("timetable_definition_id = ? AND subject_id = ?",k2,k3)
                                        if subjectperiod.blank?
                                            issubjectpresent=TimetableAssign.where("section_id = ? AND subject_id = ?",section.id,k3)
                                            if issubjectpresent.blank?
                                                isteacherpresent=TimetableAssign.where("section_id = ? AND employee_id = ?",section.id,k4)
                                                if isteacherpresent.blank?
                                                    @finaltt=TimetableAssign.new
                                                    @finaltt.timetable_struct_id=@timetable_struct.id
                                                    @finaltt.employee_id=k4
                                                    @finaltt.section_id=section.id
                                                    @finaltt.standard_id=standard.id
                                                    @finaltt.division_id=division.id
                                                    @finaltt.subject_id=k3
                                                    @finaltt.timetable_definition_id=k2
                                                    @finaltt.timetable_day_id=k1
                                                    set_school_id(@finaltt,current_user)
                                                    if(@finaltt.save)

                                                        setflag_sub(subjectflag,k3,1)
                                                        setflag_period(periodflag,k2,1)
                                                        setflag_teacher(teacherflag,k4,1)
                                                    end
                                                end
                                            else
                                                @subjectdetail=TimetableAssign.find_by_section_id_and_subject_id(@section.id,k3)
                                                @finaltt=TimetableAssign.new
                                                @finaltt.timetable_struct_id=@subjectdetail.timetable_struct_id
                                                @finaltt.employee_id=@subjectdetail.employee_id
                                                @finaltt.section_id=section.id
                                                @finaltt.standard_id=standard.id
                                                @finaltt.division_id=division.id
                                                @finaltt.subject_id=@subjectdetail.subject_id
                                                @finaltt.timetable_definition_id=k2
                                                @finaltt.timetable_day_id=k1
                                                set_school_id(@finaltt,current_user)
                                                if(@finaltt.save)

                                                    setflag_sub(subjectflag,k3,1)
                                                    setflag_period(periodflag,k2,1)
                                                    setflag_teacher(teacherflag,k4,1)
                                                end
                                            end
                                        end
                                    end
                                end
                            end
                        end
                    end
                end
            end
        end