Алгоритм для создания школьного расписания
https://stackoverflow.com/questions/2177836
-
24-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Мне было интересно, есть ли известные решения для алгоритма создания школьного расписания. По сути, речь идет о оптимизации «часовой дисперсии» (как в преподавателях, так и в классах) для учебных ассоциаций учебных преподавателей класса. Мы можем предположить, что у нас есть наборы классов, предметов урока и преподаватели, связанные друг с другом на входе, и этот график должен соответствовать 8:00 до 4 вечера.
Я предполагаю, что для этого, вероятно, нет точного алгоритма, но, может быть, кто-то знает хорошее приближение или намеки на его развитие.
Решение
Эта проблема NP-Clace!
В двух словах нужно исследовать все возможные комбинации, чтобы найти список приемлемых решений. Из-за вариаций обстоятельств, в которых проблема появляется в различных школах (например: есть ли ограничения в отношении классных комнат?, Являются одними из классов разделения в подгруппах. и т. д.) Не существует известного класса проблем, что соответствует всем проблемам планирования. Может быть, то Задача Knaxackack Имеет много элементов сходства с этими проблемами в целом.
Подтверждение того, что это как сложная проблема, так и для того, для чего люди многолетнее ищут решение, это проверить это (длинный) Список (в основном коммерческих) инструментов планирования программного обеспечения
Из-за большого количества вовлеченных переменных крупнейший источник которого, как правило, желания факультета; -) ..., как правило, непрактично учитывать перечисление всех возможных комбинаций. Отказ Вместо этого нам нужно выбрать подход, который посещает подмножество пробелов проблем / решения.
- Генетические алгоритмы, цитируется в другом ответе (или, ИМХО, кажется) Хорошо оборудован для выполнения такого полупроизводительного поиска (проблема, чтобы найти хорошую функцию оценки для кандидатов для хранения следующего поколения)
- Перезапись графика Подходы также используются с этим типом комбинаторных задач оптимизации.
Вместо того, чтобы сосредоточиться на конкретных реализациях программы автоматического генератора графика, я хотел бы предложить Несколько стратегий, которые могут быть применены, На уровне определения проблемы.
Общие обоснование заключается в том, что в большинстве реальных проблем планирования мировых планировщиков некоторые компромиссы потребуются не все ограничения, выраженные и подразумеваемые: будут полностью удовлетворены. Поэтому мы помогаем себе:
- Определение и рейтинг всех известных ограничений
- Уменьшение проблемного пространства, вручную, обеспечивая набор дополнительный ограничения.
Это может показаться контр-интуитивно понятным, но, например, путем предоставления первоначального, частично заполненного графика (скажем, примерно 30% временных слотов), таким образом, что полностью удовлетворяет всеми ограничениям, и рассмотрев этот частичный график неизменно, мы существенно уменьшаем Время / пространство, необходимое для создания решений-кандидатов.
Другими способом дополнительные ограничения помогают, например «искусственно», добавляя ограничение, которое предотвращает преподавание некоторых субъектов в течение нескольких дней недели (если это еженедельное расписание ...); Этот тип ограничений приводит к снижению проблемных / решений, без, обычно, исключая значительное количество хороших кандидатов. - Обеспечение того, чтобы некоторые ограничения проблемы могут быть быстро вычислены. Это часто связано с выбором модели данных, используемой для представления проблемы; Идея состоит в том, чтобы быть в состоянии быстро выбрать (или обрезаться) некоторые варианты.
- Переопределение проблемы и позволяя некоторым ограничениям быть разбитым, несколько раз (обычно к конечным узлам графика). Идея здесь - либо удалить немного Ограничений для заполнения - в последние несколько слотов в расписании, или иметь программу автоматического генератора графика, остановит застенчивое завершение всего расписания, вместо этого предоставляя нам список дюжина или настолько правдоподобных кандидатов. Человек часто находится в лучшем положении для завершения головоломки, как указано, что, возможно, нарушая несколько разоблачков, используя информацию, которая обычно не передается с автоматической логикой (например, «без математики во второй половине дня», может быть нарушена по случаю Для класса «Усовершенствованная математика и физика»; или «лучше сломать один из требований мистера Джонса, чем один из MS Smith ... ;-))
В прочтении этого ответа я осознаю, что это довольно застенчиво предоставление определенного ответа, но оно не менее полное практических предложений. Я надеюсь, что эта помощь, с чем, в конце концов, «тяжелая проблема».
Другие советы
Это беспорядок. Королевский беспорядок. Чтобы добавить к ответам, уже очень завершено, я хочу указать на мой семейный опыт. Моя мама была учителем и использовалась участвовать в процессе.
Оказывается, что имея компьютер для этого, не только трудно кодировать Per-SE, он также сложно, потому что есть условия, которые трудно указать на предварительно запеченную компьютерную программу. Примеры:
- Учитель учит как в вашей школе, так и в другом институте. Очевидно, что если он заканчивает урок туда в 10.30, он не может начать в ваших помещениях в 10.30, потому что ему нужно немного времени для поездки между институтами.
- Два учителя женаты. В целом, это считается хорошей практикой, чтобы не иметь двух женатых учителей на одном классе. Поэтому эти два учителя должны иметь два разных класса
- Два учителя женаты, и их ребенок посещает ту же школу. Опять же, вы должны помешать двум учителям преподавать в конкретном классе, где их ребенок.
- Школа имеет отдельные объекты, как один день, класс в одном институте, а другой день класс в другом.
- Школа имеет общие лаборатории, но эти лаборатории доступны только на определенные будни (по соображениям безопасности, например, где требуется дополнительный персонал).
- Некоторые учителя имеют предпочтения на свободный день: некоторые предпочитают в понедельник, некоторые в пятницу, некоторые в среду. Некоторые предпочитают приходить рано утром, некоторые предпочитают приходить позже.
- У вас не должно быть ситуаций, когда у вас есть урок скажем, история в первый час, затем три часа математики, затем еще один час истории. Это не имеет смысла для студентов, ни для учителя.
- Вы должны раскладывать аргументы равномерно. Не имеет смысла иметь первые дни в неделю только математику, а затем остальная часть недели только литература.
- Вы должны дать некоторым учителям два часа подряд, чтобы выполнить оценочные тесты.
Как видите, проблема не является NP-завершением, это NP-безумно.
Итак, что они делают, это то, что у них большой стол с небольшими пластиковыми вставками, и они перемещают вставки, пока не получается удовлетворяющий результат. Они никогда не начинаются с нуля: они обычно начинаются с графика в предыдущем году и внесите коррективы.
То Международный соревнования по времени 2007 имел план планирования урока и планирования экзамена. Многие исследователи участвовали в этой конкуренции. Были опробованы множество эвристики и метаврейств, но в конце концов местные поисковые метеристы (такие как поисковый поиск и смоделированный отжиг) четко пробивают другие алгоритмы (такие как генетические алгоритмы).
Взгляните на 2 с открытым исходным средством, используемыми некоторыми из финалистов:
- Jboss optaplanner. (Java, открытый источник)
- Отделение (Java, открытый источник) - больше для университетов
Одним из моих полугодовых заданий было генетический алгоритм школьной школы поколения.
Целый стол - один «организм». Были некоторые изменения и предостережения на общие генетические алгоритмы подхода:
Правила были сделаны для «незаконных таблиц»: два класса в одном классе, один учитель, обучающий две группы одновременно и т. Д. Эти мутации сразу считались смертельными, а новый «организм» прорастал на месте «умершего» немедленно. Начальный был создан серией случайных попыток, чтобы получить правовую (если бессмысленно) один. Летальная мутация не учитывалась к подсчету мутаций в итерации.
Мутации «Exchange» были гораздо чаще, чем «модифицировать» мутации. Изменения были только между частями гена, имея смысл - не заменяют учителя в классе.
Небольшие бонусы были назначены для объединения определенных 2 часов вместе, для присвоения же универсального класса в последовательности для той же группы, для сохранения рабочих часов учителя и непрерывной нагрузки класса. Умеренные бонусы были назначены для предоставления правильных классных комнат для данного предмета, сохраняя часы класса в пределах облигаций (утром или днем), а также такие. Большие бонусы были для назначения правильного количества данной темы, задавая рабочую нагрузку для учителя и т. Д.
Учителя могут создать свои расписания рабочих нагрузок «Хотите работать тогда», «Хорошо, чтобы работать тогда», «не нравится работать», то «не может работать», а затем присваивается с надлежащими весами. Целые 24 часа были законные рабочие часы, кроме ночного времени, было очень нежелательно.
Весовая функция ... О да. Весовая функция была огромной, чудовищным продуктом (как в умножении) весов, присвоенных выбранным функциям и свойствам. Было чрезвычайно круче, одна недвижимость легко может изменить его на порядок вверх или вниз - и были сотни или тысячи свойств в одном организме. Это привело к абсолютно огромным количеством веса, и в качестве прямого результата необходимо использовать библиотеку Bignum (GMP) для выполнения расчетов. Для небольшого теста в 10 группах, 10 преподавателей и 10 классных комнат, начальный набор начался с примечания 10 ^ -200, и закончен и закончен с 10 ^ + 300Something. Это было совершенно неэффективно, когда это было более плоским. Кроме того, ценности выросли намного шире расстояния с большими «школами».
Время вычисления мудро, было мало различий между небольшой популяцией (100) в течение длительного времени и большим населением (10 к +) по поводу меньшего количества поколений. Вычисление в то же время производится примерно одинакового качества.
Расчет (на некотором 1 ГГц CPU) займет около 1 часа для стабилизации около 10 ^ + 300, генерирующих графиков, которые выглядели довольно приятно, для тех, кто выглядел тестируемым корпусом 10x10x10.
Проблема легко параллеллизуема, предоставив сетевое средство, которое обменивается лучшими образцами между компьютерами, выполняющими вычисление.
Полученная программа никогда не увидела дневной свет снаружи, получая мне хорошую оценку для семестра. Это показало некоторое обещание, но у меня никогда не получилось достаточно мотивации, чтобы добавить любой графический интерфейс и сделать его полезным для широкой публики.
Эта проблема более жесткая, чем кажется.
Поскольку другие намеревались, это проблема с НП, но давайте проанализируем то, что это значит.
По сути, это означает, что вы должны посмотреть на все возможные комбинации.
Но «посмотрите» не говорит вам много того, что вам нужно сделать.
Создание всех возможных комбинаций легко. Это может вызвать огромное количество данных, но у вас не должно быть много проблем, понимая понятия этой части проблемы.
Вторая проблема заключается в том, является ли данную возможную комбинацию хорошей, плохой или лучше, чем предыдущий «хороший» решение.
Для этого вам нужно больше, чем просто «это возможное решение».
Например, тот же учитель работает 5 дней в неделю за х недели прямо? Даже если это рабочее решение, это может быть не лучшее решение, чем чередование между двумя людьми, чтобы каждый учитель на одну неделю каждый. О, ты не думал об этом? Помните, что это люди, с которыми вы имеете дело, а не только проблема распределения ресурсов.
Даже если один учитель может работать на полную ставку в течение 16 недель прямо, это может быть подпунктивным решением по сравнению с решением, в котором вы пытаетесь чередовать преподавателей, и этот вид балансировки очень трудно встроить в программное обеспечение.
Подводя итог, производство хорошего решения этой проблемы будет стоить многих, для многих людей. Следовательно, это не легкая проблема разрушать и решать. Будьте готовы добиться за несколько целей, которые не на 100% и называют их «достаточно хорошими».
Обновление: от комментариев ... должен иметь эвристики тоже!
Я бы пошел с 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].
Я (все еще) в процессе выполнения чего-то похожего на эту проблему, но используя тот же путь, как я только что упомянул. Пролог (как функциональный язык) действительно облегчает решение проблем с НП.
Генетические алгоритмы часто используются для такого планирования.
Нашел Этот пример (создание расписания класса с использованием генетического алгоритма) который соответствует вашему требованию довольно хорошо.
Вот несколько ссылок, которые я нашел:
Школьное расписание - перечисляет некоторые проблемы с участием
Мой алгоритм сминания, реализованный в 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) Многие другие ограничения (исключаемые здесь, для простоты).
Алгоритм сминания (который я назвал «рекурсивным обмен»):
- Сортировать деятельность, самое сложное сначала. Не критический шаг, но ускоряет алгоритм, может быть, в 10 раз или больше.
Попробуйте разместить каждое действие (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 нераспределенный.
подразделение. Отказ Рекурсивно пытаются разместить 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 б) и 2 в), но без рекурсии. У нас сейчас 3 - 1 = 2 больше мероприятий на место. Перейти к шагу 2) (некоторые методы, чтобы избежать езды на велосипеде).
Я разработал коммерческие алгоритмы для обеих графических и экзаменационных графиков. Для первого я использовал целочисленное программирование; Для второго эвристика на основе максимизации объективной функции, выбирая слотные свопы, очень похоже на исходный ручной процесс, который был развит. Они главные вещи в получении таких решений, являются способностью представлять все реальные ограничения; И для человеческих расписаний не сможет увидеть способы улучшить решение. В конце концов, алгоритмическая часть была довольно простыми и простыми в реализации по сравнению с приготовлением баз данных, пользовательский интерфейс, возможность сообщить о статистике, такими как использование номеров, обучение пользователей и так далее.
Эта статья описывает проблему школьного расписания и их подход к алгоритму довольно хорошо: "Разработка учебных программ - интерактивной, планировщика на основе ограничений для школ и колледжей.[PDF
Автор сообщает мне, что программное обеспечение Syllabus все еще используется / разработан здесь: http://www.scientia.com/uk/
Я работаю над широко используемым механизмом планирования, который имеет именно это. Да, это NP-полное; Лучшие подходы стремятся приблизить оптимальное решение. И, конечно же, есть много разных способов сказать, какой из них является «лучшим» решением - это важно, чтобы ваши учителя были довольны своими расписаниями, или что студенты попадают в все свои занятия, например?
Абсолютный самый важный вопрос, который вы должны разрешить рано Что делает один из способов планирования этой системы лучше, чем другой? То есть, если у меня есть график с миссис Джонс, преподавая математику в 8 и мистер Смит, преподавая математику в 9, это лучше или хуже, чем у обоих из них обучение математике в 10? Это лучше или хуже, чем один с миссис Джонс, обучая в 8 и мистере Джонс, обучаю в 2? Почему?
Главный совет, который я дал здесь, состоит в том, чтобы разделить проблему как можно больше - возможно, конечно, конечно, может быть, учитель учитель, может быть, комната в комнате - и работать над решением подзагомости в первую очередь. Там вы должны в конечном итоге с несколькими решениями для выбора и необходимости выбрать один как наиболее вероятный оптимальный. Тогда работа по созданию «более ранних» подпространенных проблем учитывает потребности последующих подпротесов в забивших их потенциальных решений. Тогда, возможно, работать над тем, как выйти из окрашенных в углубимых ситуациях (предполагая, что вы не можете предвидеть те ситуации в более ранних проблемах), когда вы добираетесь до состояния «Нет действительных решений».
Пропуск по оптимизации локального поиска часто используется для «польского» конечного ответа для лучших результатов.
Обратите внимание, что обычно мы имеем дело с ограниченными ресурсами системами в школе планирования. Школы не проходят через год с большим количеством пустых комнат или учителей, сидящих в лаундже 75% дня. Подходы, которые лучше всего работают в богатых решениях, которые не обязательно применимы в планировании школы.
Как правило, программирование ограничений является хорошим подходом к этой проблеме планирования. Поиски на «программное обеспечение« ограничения »и планирование или« планирование на основе ограничений »как в пределах переполнения стека, так и в Google, создаст несколько хороших ссылок. Это не невозможно - это просто немного трудно подумать при использовании традиционных методов оптимизации, таких как линейная или целочисленная оптимизация. Один вывод будет - существует ли график, который удовлетворяет всем требованиям? Что, само по себе, очевидно полезно.
Удачи !
Вы можете вытащить его с генетическими алгоритмами, да. Но вы не должны :). Это может быть слишком медленным, а настройка параметров может быть слишком временем и т. Д.
Есть успешные другие подходы. Все реализованы в проектах с открытым исходным кодом:
- Подход на основе ограничений
- Реализован в Отделение (не на самом деле для школ)
- Вы также можете пойти дальше и использовать целочисленное программирование. Успешно сделан в Университет Удине а также в университете Байройт (я там вовлечен), используя коммерческое программное обеспечение (ILOG CPLEX)
- Подход на основе правил с Heuristisc - см. Планировщик слюни
- Разная эвристика - Добыча а также мой собственный
Смотрите здесь для Список программного обеспечения TimETable
Я думаю, что вы должны использовать генетический алгоритм, потому что:
- Лучше всего подходит для больших случаев проблем.
- Это дает снижение сложности времени по цене неточного ответа (не предельный лучший)
- Вы можете легко указать ограничения и настройки, регулируя фитнес наказания для не встречаемых.
- Вы можете указать ограничение по времени для выполнения программы.
Качество решения зависит от того, сколько времени вы намереваетесь тратить решение программы.
Определение генетических алгоритмов
Также посмотрите на:Подобный вопрос а также Еще один
Я не знаю, что кто-то согласится с этим кодом, но я разработал этот код с помощью своего собственного алгоритма и работает для меня в Ruby.hope. Это поможет им, кто ищет его в следующем коде. TUSSICFLAG и PESTUSTLAG - это хеш с соответствующим идентификатором и значением флага, которое логично. Любой вопрос связаться со мной ....... (-_-)
ProjectFlag.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
