Назначить сотрудников на даты
Это мое начальное состояние:
I have a set of employees E1, E2, E3, ...
I have a set of dates for an activity D1, D2, D3, ...
For every employee, I know on which dates he is available to perform the activity
Every employee should perform the activity only once
Мне нужно найти наилучшую конфигурацию, которая позволит каждому сотруднику выполнять действие, сводя к минимуму количество используемых дат и предоставляя максимальное количество сотрудников на дату. Так, например, если на определенную дату у меня может быть 20 сотрудников, мне нужно использовать только лучшие 10 из них, перенося остальные 10 в разные даты.
Я думаю, что решением может быть какой-то алгоритм, связанный с двудольными графами, но я не могу найти хороший подход для его решения.
Есть ли у вас какие-либо идеи о том, как решить эту проблему или проблема может вписаться в какой-то уже известный алгоритм?
Большое спасибо,
Marco
Решение
Эта проблема, кажется, известная проблема под названием планирование медсестры который, как известно, NP-трудной. В основном у ваших сотрудников и даты соответствуют медсестрам и сменам соответственно. Ваши жесткие ограничения — это дни доступности сотрудников, а мягкие ограничения — качество их работы, как вы упомянули при выборе 10 лучших в вашем примере.
К сожалению, я не думаю, что вы можете придумать оптимальное решение на макушке. В зависимости от размера набора сотрудников и дат, найти такое решение может быть довольно сложно, и я не думаю, что из-за вашего определения проблемы до сих пор было бы целесообразно сказать, какой метод можно использовать для Решите, что планирование медсестры может лучше всего соответствовать вашим требованиям.
Тем не менее, вот несколько статей, которые вы можете посмотреть и увидеть, насколько они соответствуют конкретным требованиям вашей проблемы.
Гибрид с рюкзаком для решения задачи медсестры
Двухфазный адаптивный подход с переменной окрестностью для составления списков медсестер
Косвенный генетический алгоритм для задачи планирования медсестры
Другие решения
Других решений пока нет …