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 ?
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:
No worker exceeds their maximum time: for each i, the sum over all j of xij is less than or equal to mi
Each job is completed: for each j, the sum over all i of Rij*xij is greater than or equal to 1
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.