Алгоритмы: Задача о назначениях, как реализовать множественные назначения?
Привет!
Есть прекрасный "Венгерский алгоритм", который позволяет назначить работнику конкретную задачу.
Скажите, есть ли реализация или подобные алгоритмы для назначения одного задания нескольким работникам? Или сам венгерский алгоритм может быть модифицирован, для этих целей?
Так же, вероятно, вписывается задача о максимальном потоке, но с возможностью разделения потока...
Было бы здорово получить ссылки на литературу или просто советы. :)
Спасибо!
а какие криетрии? Не получится ли просто продублировать каждую "работу" несколько раз (создать для нее неколько вершин), или например, заранее сгруппировать работников?
самая первая мысль - можно "сгруппировать" работников, выдав их за одного. А для того, чтобы понять, каким образом правильнее их сгруппировать, просто обработать все перечисления таких групп.
Непонятно, как вы в такой ситуёвине считаете штраф. Ведь если штраф считается как раньше, а загрузка работника не ограничена, и задачи-то нет — каждую из работ можно дать тому работнику, который выполняет её лучше всех.
Если же загрузка работника ограничена m работами — тогда решите задачу о максимальном потоке.
Исток → работник: пропускная m
работник → работа: пропускная 1
работа → сток: пропускная 1
Средний