M
M
MaksVal2014-10-14 08:44:35
Algorithms
MaksVal, 2014-10-14 08:44:35

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

3 answer(s)
S
SilentFl, 2014-10-14
@SilentFl

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.

M
MaksVal, 2014-10-15
@MaksVal

Yes thank you! I also think about grouping, but the idea does not mature. :)

M
Mercury13, 2015-03-10
@Mercury13

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 question

Ask a Question

731 491 924 answers to any question