Алгоритм расписания учителя

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

Разделите задачу:

1. Создайте список учителей, классов и предпочтений, затем позвольте пользователю заполнить некоторые предпочтения на карте, чтобы иметь в качестве отправной точки.
2. Случайно возьмите один элемент из списка и поместите его в произвольно свободную позицию на карте, если он не пересекает никакие проверки здравомыслия, пока список не станет пустым. Если на какой-то определенной итерации вы не можете поместить элемент на карту, не пройдя проверку на разумность, сдвиньте две позиции на карте и попробуйте снова.
3. Когда карта заполнена, попробуйте смещать позиции на карте, чтобы оптимизировать результат.

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

Я не пробовал это, но это был бы мой первоначальный подход.

Я занялся подобными проблемами планирования/планирования в прошлом и методе AI, который часто подходит лучше всего для этого класса проблемы, "Обоснование На основе ограничений".

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

Гуглящее "Обоснование На основе ограничений" поднимает много ресурсов на технике и ее приложении к планированию проблем.

Отвечая на мой собственный вопрос:

Проект FET, упомянутый gnud, использует этот алгоритм:

Несколько слов об алгоритме: FET использует эвристический алгоритм, расставляя действия по очереди. начиная с самых сложных. Если он не может найти решение, он указывает на потенциально невозможные действия, поэтому вы можете исправить ошибки. Алгоритм рекурсивно меняет действия, если это возможно, чтобы освободить место для нового действия или, в крайних случаях, откатить назад и изменить порядок оценки. Важный код находится в src / engine / generate.cpp. Пожалуйста, напишите мне для деталей или присоединитесь к списку рассылки. Я думаю, что алгоритм имитирует работу человеческого таймера.

Ссылка

Вслед за «Рассуждением, основанным на ограничениях», проведенным Stringent Software в Википедии, я привел эти страницы с интересным абзацем:

Решение проблемы удовлетворения ограничений в конечной области является NP-полной задачей в целом. Исследования показали, что существует множество подслучей полиномиального времени, в основном получаемых путем ограничения либо разрешенных доменов, либо ограничений, либо способов размещения ограничений над переменными. Исследования также установили связь проблемы удовлетворения ограничений с проблемами в других областях, таких как теория конечных моделей и базы данных.

Это напоминает мне об этом сообщение в блоге о планировании конференции , с видео объяснение здесь .

, Как я сделал бы это:

Сделали, чтобы население включало две вещи:

• , Кто преподает, какой класс (я ожидаю, что учителя будут преподавать один предмет).
• , Что класс берет на определенном временном интервале.

Этот путь у нас не может быть конфликтов (учитель в 2 местах или класс, имеющий два предмета одновременно).

функция фитнеса включала бы:

• , Сколько временные интервалы каждый учитель дают в неделю.
• , Сколько временные интервалы учитель имеют в тот же день (У них не может быть целого дня обучения, это также должно быть сбалансировано).
• , Сколько временные интервалы того же предмета класс имеют в тот же день (У них не может быть целого дня математики!).

, Возможно, берут стандартное отклонение для всех них, так как они должны быть сбалансированы.

Я не уверен, охватывает ли это то же основание, что и ответ @Stringent Software (поскольку название немного отличается), но у меня есть пара очень хороших друзей, которые исследуют область Ограничительное программирование . Создание расписаний является одним из приложений их исследований.

Доктор Крис Джефферсон создал программу под названием Minion , которую вы можете скачать с SourceForge, и является очень быстрым решателем проблем с грубой силой, написанным на C ++

Я думаю, что Вы могли бы пропускать некоторые ограничения.

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

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

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

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

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

Запускаются с маленького набора ограничений и увеличивают их, поскольку Вы видите успех (если Вы видите успех)

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

я соглашаюсь. Это походит на забавную проблему

Одна из худших когда-либо открытых веб-страниц, но проект выглядит многообещающе: http://www.lalescu.ro/liviu/fet/

Сетевой подход:
phpScheduleIt (не для школы)

Рассмотрение этого вопроса заставило меня думать об этой проблеме, и были ли генетические алгоритмы применимы в этом случае. Однако было бы довольно трудно видоизменить возможности при поддержании правил проверки работоспособности. Также мне не ясно, как отличить несовместимые требования.

Генетические алгоритмы очень хорошо подходят для проблем, таких как это. Как только Вы придумываете достойное представление хромосомы (в этом случае, вероятно, вектор, представляющий все доступные слоты класса), Вы - большая часть пути там.

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

Несовместимые требования являются различной проблемой в целом. Если они будут абсолютно несовместимыми, Вы получите население, которое не сходится ни на чем полезном.

Удачи. Сын отца с такой проблемой - вот что привело меня в исследовательскую группу, в которую я попал ...

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

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

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

После тысяч итераций вы приближаетесь к приемлемому решению.

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

Вы также можете найти некоторый интерес в области линейного программирования, например, симплекс и так далее.

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

Да, я думаю, что это - завершенный NP - или по крайней мере найти, что оптимальным решением является завершенный NP.

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

, я понятия не имел, во что я вовлек себя. К счастью для нас всех я должен был сделать, была находка одно решение, которые соответствуют ограничениям. Но в моем тестировании я всегда волновался по поводу определения, ЕСЛИ было решение вообще. У него никогда не было слишком многих ограничений, и программа использовала различную эвристику и заднее отслеживание. Это была большая забава.

я думаю, что Bill Gates также работал над системой как это в средней школе или колледже для его средней школы. Не уверенный все же.

Удача. Всех моих примечаний не стало, и я никогда не находил время для реализации решения, которое я мог продать. Это был специализированный проект, который я повторно кодировал, поскольку я узнал, что новые языки (Основной, Схема, C, VB, C++)

Весело проводят время с ним