Алгоритм - Составление расписания экзаменов

У меня проблема с составлением расписания экзаменов, основанного на трех факторах: комнатах, курсах и днях. Есть заданное количество комнат r, курсов c и дней d, в которых каждый день имеет три слота.

Также есть набор студентов и отображение студентов на курсы, чтобы не было никаких конфликтов.

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

Спасибо


optimization flow algorithm constraint-programming
person John Smith    schedule 06.04.2013    source источник
comment
что ты уже испробовал? Есть подходы, отличные от предложенного вами. Например, генетический алгоритм (128.243.21.14/cs/pub/ cs / ttp / Papers / PDF / AISB95.pdf или codeproject.com/Articles/23111/) или удовлетворение ограничений (stackoverflow.com/questions/1597542/).   -  person Simon    schedule 07.04.2013
comment
Я создал общий сетевой потоковый граф, учитывая, что нет никаких ограничений (например, студенческие конфликты не имеют значения). Я просто в тупике по этому поводу. Я не уверен, как это сделать, чтобы при отображении, основанном на студентах, поток не мог проходить.   -  person John Smith    schedule 07.04.2013

Ответы (1)


arrow_upward
1
arrow_downward

Конкурс ITC2007 трек 1 экзамен определил очень хорошую, нетривиальную задачу планирования экзаменов с множеством реальных наборов данных. Поскольку проблема является NP-полной, человеку не известен полиномиальный алгоритм, который решал бы ее оптимальным образом.

Чтобы узнать, какие алгоритмы могут решить эту проблему, взгляните на эту java-реализацию с открытым исходным кодом этого конкурса с OptaPlanner:

person Geoffrey De Smet    schedule 07.04.2013