Hungarian algorithm: multiple jobs per worker

Question

Is there an extension of the Hungarian algorithm that caters for the assignment of multiple jobs per worker? In its simplest form, the algorithm assigns a single job to a single worker.

My application is a profit maximization problem, with 3 workers and 180 jobs. I'll add constraints as well (minimum of 50 jobs assigned to each worker).

I've managed to implement the Hungarian algorithm using the mungres library in Python, which works very well. I'm just struggling to find literature related to multiple assignments per worker.

https://pypi.python.org/pypi/munkres

https://en.wikipedia.org/wiki/Hungarian_algorithm

https://en.wikipedia.org/wiki/Generalized_assignment_problem

I've tried the standard numpy method listed in the comments, but was unable to extend it to multiple assignments per worker. If my matrix is rectangular (i.e. 3 workers and 4 jobs) only the first 3 jobs are assigned to the workers. I've also tried adding dummy variables to create a square matrix, but then jobs are assigned to those dummy workers rather than the actual workers

Answer 1

This can be solved by formulating it as a transportation problem with the workers having bounds of [50,inf). Correct me if I am wrong, approach 1 from peter's solution is for when a person can do a maximum of 50, not minimum.

Answer 2

Approach 1

One simple way of doing this is to make, for example, 50 clones of each worker and solve the problem as normal.

To find worker 1's jobs, you can then collect all the jobs assigned to the clones of worker 1. There are only 50 clones, so worker 1 will be assigned to at most 50 jobs.

Approach 2

This kind of assignment problem can be expressed as a min-cost flow problem where there is flow from a worker to a job if the worker does a job.

In this formulation, each worker is supplied with a capacity of 1 flow unit. You can then increase the number of jobs by simply increasing the capacity as required.

This approach is likely to be more efficient (as the graph is smaller) but requires modification of the underlying algorithm, whereas approach 1 should be trivial to implement.

Answer 3

Check: https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linear_sum_assignment.html

The linear sum assignment problem is also known as minimum weight matching in bipartite graphs. A problem instance is described by a matrix C, where each C[i,j] is the cost of matching vertex i of the first partite set (a “worker”) and vertex j of the second set (a “job”). The goal is to find a complete assignment of workers to jobs of minimal cost.