algorithmoptimizationhungarian-algorithm

Hungarian algorithm with unequal number of workers and tasks


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 ?


Solution

  • There is a straightforward linear programming formulation.

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

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

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

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

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

    The wikipedia page provides pointers to various linear solver software.