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

Question

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

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

Проверка на Вменяемость

• Учитель не может вести два урока одновременно
• Ученик не может посещать два урока одновременно
• У некоторых учителей должен быть хотя бы один выходной в течение недели
• Расписание должно охватывать все дни недели
• У субъекта X должно быть ровно столько-то часов в неделю
• ...

Предпочтения

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

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

Доказано ли, что это NP-сложно?

У кого-нибудь есть идея, как взломать эту штуку?

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

---

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

Answer 1

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

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

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

Текущая реализация планировщика написана на perl, но другими опциями, которые мы рассматривали ранее, были Prolog и CLIPS (экспертная система).

Answer 2

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

Разделите проблему:

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

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

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

Answer 3

В прошлом я сталкивался с подобными проблемами планирования, и метод искусственного интеллекта, который часто лучше всего подходит для решения задач этого класса, - это "Рассуждение, основанное на ограничениях".

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

Поиск в Google "Рассуждения, основанные на ограничениях" позволяет найти много ресурсов по этой методике и ее применению к задачам планирования.

Answer 4

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

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

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

Ссылка

---

Продолжение "Рассуждений, основанных на ограничениях", приведенных Строгим программным обеспечением в Википедии, привело меня к эти страницы в которых есть интересный абзац:

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

Answer 5

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

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

Должно ли население включать в себя две вещи:

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

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

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

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

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

Answer 6

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

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

Answer 7

Я думаю, что вам, возможно, не хватает некоторых ограничений.

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

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

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

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

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

Начните с небольшого набора ограничений и увеличивайте их по мере достижения успеха (если вы видите успех).

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

Я согласен.Это звучит как забавный вызов

Answer 8

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

Веб-подход:
phpScheduleIt ( РҺР - расписание ) (не зависит от конкретной школы)

Answer 9

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

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

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

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

Answer 10

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

---

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

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

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

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

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

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

Answer 11

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

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

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

Я думаю, что Билл Гейтс также работал над подобной системой в старших классах или колледже для своей средней школы.Хотя и не уверен.

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

Получайте от этого удовольствие

Answer 12

я вижу, что эта проблема может быть решена программой Prolog путем подключения ее к базе данных и программа может составить расписание с учетом набора ограничений прочитайте abt "Проблема удовлетворения ограничений prolog"