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

Question

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

Проблема:

Рассмотрим университет.У вас есть следующие предметы:

• Педагогический персонал.Каждый сотрудник преподает один или несколько документов.
• Студенты.Каждый студент берет одну или несколько работ.
• Комнаты.В комнатах обучается определенное количество студентов, и в них содержится оборудование определенного типа.
• Документы.Требуется определенный тип оборудования и определенное количество времени в неделю.

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

1. Персонал может учить только одной вещи за один раз.
2. Студенты могут посещать только одну работу за один раз.
3. В комнатах может находиться только определенное количество студентов.
4. Документы, требующие определенного типа оборудования, могут храниться только в комнате, в которой предоставляется оборудование такого типа.
5. Часыс понедельника по пятницу, 8-12 и 1-5.

Обсуждение:

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

Какой хороший подход для решения такого рода проблем, удовлетворяющих ограничениям??

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

Answer 1

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

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

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

Кодирование потребует некоторого понимания, но как только это будет сделано, оно должно быть простым, если, конечно, я что-то упустил:)

Answer 2

Очень ограниченная версия этой задачи - NP-Complete.

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

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

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

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

Надеюсь, это поможет.