Алгоритм планирования встреч
У меня есть следующая проблема для решения, возможно, вы могли бы дать мне несколько идей относительно подхода к решению проблемы:
Есть:
- 8 классных комнат
- 16 учителей
- 201 студент
- 149 родителей
- 241 посещение (большинству родителей необходимо посещать нескольких учителей, потому что у них более одного ребенка или потому, что два ребенка учат два или более учителя)
2 дня.
За каждый день:
- 7 классных комнат доступны по 20 часов в день.
- 1 класс доступен для 10 часов в день.
Каждый учитель занимает один класс
- Каждое посещение длится один час.
Дополнительные ограничения: - Для каждого родителя все встречи должны быть последовательными (с максимум 1 часом паузы) - Каждый родитель должен посещать школу только один день. - Для каждого учителя все встречи в течение дня должны быть последовательными (с перерывом не более 2 часов). - Из 16 учителей 3 могут присутствовать только один из двух дней.
Я пытаюсь найти подход для составления графика встреч, очевидно, не нужно рассчитывать все возможные варианты, пока все требования не будут выполнены. Есть идеи?
2 ответа
Вы должны определить свои ограничения немного больше; то есть, каковы отношения между учениками и учителями? Каковы отношения между учениками и родителями? Должны ли родители назначать индивидуальные встречи или родители одного учащегося могут встречаться с одним учителем вместе?
Я бы подошел к этому с начальным (в тестировании) наивным подходом; просто выберите ваш ресурс с наибольшим ограничением (похоже, учителя, которые могут присутствовать только в течение одного из двух дней), запланируйте тех, кто использует первые доступные ресурсы, а затем продолжите работу с набором ресурсов, планируя их с использованием первых доступных ресурсов, которые соответствуют их ограничения и посмотреть, если вы можете запланировать весь набор. Если нет, вам нужно найти свой ограничивающий ресурс (ы) и применить некоторые эвристики к вашему соответствию, чтобы найти наилучший способ оптимизации этих ограниченных ресурсов.
Это немного сложная проблема; повеселись!
Взгляните на курс учебной программы ITC2007 и его реализацию в Drools Planner или unitime. Оба они используют метаэвристику, такую как поиск по табу и имитационный отжиг.