Answer the question
In order to leave comments, you need to log in
Algorithms: Assignment problem, how to implement multiple assignments?
Hey!
There is a wonderful "Hungarian algorithm" that allows you to assign a specific task to an employee.
Tell me, is there an implementation or similar algorithms for assigning one job to multiple workers? Or can the Hungarian algorithm itself be modified for these purposes?
Also, probably, the problem of the maximum flow fits in, but with the possibility of splitting the flow ...
It would be great to get links to the literature or just advice. :)
Thanks!
Answer the question
In order to leave comments, you need to log in
the very first thought - you can "group" workers, passing them off as one. And in order to understand how it is more correct to group them, simply process all the enumerations of such groups.
Yes thank you! I also think about grouping, but the idea does not mature. :)
It is not clear how you consider the penalty in such a situation. After all, if the fine is calculated as before, and the employee’s workload is not limited, and there is no task, then each of the jobs can be given to the employee who performs it best.
If the worker's workload is limited to m jobs, then solve the maximum flow problem.
Source → worker: throughput m
worker → work: throughput 1
work → sink: throughput 1
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question