Алгоритм вычисления расписания с учетом ограничений
Я рассматриваю гипотетическую проблему, и ищу руководство о том, как подойти к решению проблемы с алгоритмической точки зрения.
Проблема:
Рассмотрим университет. У вас есть следующие объекты:
- Преподавательский состав. Каждый сотрудник преподает одну или несколько работ.
- Студенты. Каждый студент сдает одну или несколько работ.
- Комнаты. Комнаты вмещают определенное количество студентов и содержат определенное оборудование.
- Документы. Требуется определенный тип оборудования и определенное количество времени каждую неделю.
Учитывая информацию о зачислении (т.е. сколько студентов зачислено на каждую работу, и какой персонал выделен для преподавания каждой работы), как я могу вычислить расписание, которое подчиняется следующим ограничениям:
- Персонал может обучать только одному предмету одновременно.
- Студенты могут посещать только одну работу одновременно.
- Комнаты могут вместить только определенное количество студентов.
- Документы, требующие определенного типа оборудования, могут храниться только в комнате, в которой имеется такое оборудование.
- Часы работы: с понедельника по пятницу с 8 до 12 и с 1 до 5.
Обсуждение:
На самом деле меня не слишком беспокоит описанная выше ситуация - это общий класс проблем, который меня интересует. На первый взгляд мне кажется, что это хорошо подходит для генетического алгоритма, но функция приспособленности для такого алгоритма будет невероятно сложной.
Какой хороший подход для попытки решить такого рода проблему с удовлетворением ограничений?
Я думаю, что, вероятно, нет никакого способа решить эту проблему идеально, поскольку студенты вполне могут взять комбинацию работ, которая приведет к невозможным ситуациям, особенно когда количество студентов и работ растет.