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

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

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

Проверка безопасности

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

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

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

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

Насколько он доказан как NP-жесткий?

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

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

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

Ответ 1

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

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

Это позволит вам сначала построить мастер-расписание, а затем при необходимости настроить его.

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

Ответ 2

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

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

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

Ссылка

Следуя "Основанию зависимости от ограничений", проводимому Stringent Software в Википедии, я приведу меня в эти страницы, которые имеют интересный абзац:

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

Ответ 3

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

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

Googling "Constraint Based Reasoning" приносит много ресурсов на эту технику и ее приложение для задач планирования.

Ответ 4

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

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

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

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

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

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

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

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

Ответ 5

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

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

Ответ 6

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

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

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

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

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

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

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

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

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

Ответ 7

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

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

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

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

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

Ответ 8

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

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

Ответ 9

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

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

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

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

Ответ 10

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

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

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

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

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

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

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

Ответ 11

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

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

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

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

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

Удачи с ним

Ответ 12

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