Hungarian algorithm with unequal number of workers and tasks

Question

I have a problem bugging me for a while now.

We have "workers" w_0, w_1 ... w_n, and tasks t_0, t_1, ... t_m, and durations D_ij such that w_i can complete t_j in that number of hours. Each worker also has a maximum m_0,m_1... m_n number of hours that can be worked.

Multiple workers can work on the same task with pro-rated effort. For example if D_11 = 2 and D_21 = 4, then worker 1 is twice as efficient as worker 2 on task 1. So you could combine, e.g. 1 hour of 1's work and 2 of 2's to get the task done.

How can we determine the minimum amount of hours in which all tasks can be completed.

I have tried using the greedy technique to select the best worker for each task, but that doesn't work on each case. Say for example worker 1 can complete task 1 in 2 hours and task 3 in 4 hours. It is clear that worker 1 will be selected to work on task 1, even though, let's say that task 3 is very time consuming for other workers, and worker 1 would have been perfect for the job.

I've thought about reducing the problem to an assignment problem, but had no luck in finding a way.

How can this problem be solved ?

Answer 1

There is a straightforward linear programming formulation.

First, we convert the durations D_ij into rates R_ij by R_ij = 1/D_ij. Next, we define decision variables x_ij representing the amount of time that worker i works on task j.

The objective is simply the sum over all i and j of x_ij. The constraints are:

1. No worker exceeds their maximum time: for each i, the sum over all j of x_ij is less than or equal to m_i

2. Each job is completed: for each j, the sum over all i of R_ij*x_ij is greater than or equal to 1

3. No one can work negative hours: for all i and j, x_ij is greater than or equal to zero

The wikipedia page provides pointers to various linear solver software.