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

Question

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

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

Answer 1

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

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

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

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

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

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

Answer 2

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

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

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

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

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

Answer 3

Международный конкурс по расписанию 2007 имел расписание планирования урока и расписание экзамена. Многие исследователи участвовали в этом конкурсе. Много эвристики и метаэвристики были опробованы, но в итоге метаэвристика локального поиска (например, поиск по Табу и симуляция отжига) явно превосходит другие алгоритмы (например, генетические алгоритмы).

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

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

Answer 4

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

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

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

• Мутации "Exchange" встречались гораздо чаще, чем мутации "Modify". Изменения были только между частями гена, которые имели смысл - не заменяя учителя классной комнатой.

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

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

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

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

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

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

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

Answer 5

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

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

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

Но «взгляни» мало что говорит тебе о том, что тебе нужно делать.

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

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

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

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

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

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

Answer 6

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

Я бы пошел с Прологом ... затем использовал бы 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.

Answer 7

Мой алгоритм учета рабочего времени, реализованный в FET (Free Timetabling Software, 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) Basic: список пар действий, которые не могут быть одновременными (например, 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.

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

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

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

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

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

Answer 8

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

Расписание школы - Перечислите некоторые проблемы

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

Планирование утилит и инструментов

Answer 9

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

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

Answer 10

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

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

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

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

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