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

Question

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

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

Проверки Sanity

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

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

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

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

Это доказано как NP-hard?

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

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

---

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

Answer 1

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

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

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

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

Answer 2

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

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

Answer 3

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

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

У населения есть две вещи:

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

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

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

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

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

Answer 4

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

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

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

Answer 5

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

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

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

Ссылка

---

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

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

Answer 6

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

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

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

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

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

Answer 7

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

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

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

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

Answer 8

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

Интернет-подход:
phpScheduleIt (не зависит от школы)

Answer 9

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

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

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

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

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

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

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

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

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

Answer 10

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