Вот суть проблемы, которую я хочу решить. У нас есть работники, которые заботятся о детях в яслях в определенное время в выходные дни. Есть 16 различных слотов, которые нужно заполнить за один уик-энд. Итак, на 4-недельный месяц нужно заполнить 64 слота. У нас не более 30 работников яслей (хотя нам нужно гораздо больше. Кто-нибудь любит детей?).
РЕДАКТИРОВАТЬ: Каждый временной интервал дискретен - они не пересекаются.
В настоящее время есть человек, который придумывает яслях. расписание каждый месяц. Это' Сложная и трудоемкая задача - каждый месяц составлять этот график с учетом всех предпочтений. После рассмотрения проблемы я подумал «Должен быть способ получше!»
Я заметил, что проблема, по сути, двудольный граф . Проблема брака также является двудольным графом, который можно решить с помощью алгоритма сопоставления, такого как алгоритм сопоставления Эдмондса .
Но это предполагает, что каждый узел в одном наборе узлов соответствует только одному узлу в другом наборе узлов. В моем случае каждый работник питомника работал бы только в один временной интервал. Поскольку мы серьезно недоукомплектованы, это не сработает! Кучке людей придется работать дважды в месяц, чтобы заполнить все временные промежутки.
Это, кажется, означает, что это больше похоже на классику "