Is there an algorithm to get a team of people to complete a certain number of tasks the fastest, where the time taken to complete a certain task is different for different people? Each task must be done fully by one person (eg can't have person A do the first half of task 1, then person B do the second half of task 1), and all members of the team should be working simultaneously and continuously.
To give an example, there are tasks 1-5 and people A-D.
- Person A takes a1 minutes to complete task 1, a2 for task 2 etc.
- Let tA be the total time person A spends working on tasks, ie if A is to complete tasks 3 and 4, tA = a3+a4.
- Each task must be completed by one person, no task requires any other tasks to be previously completed.
- All 4 people can work simultaneously to complete all the tasks, total time is given by T = max{tA,tB,tC,tD}, which we want to minimise.
Obviously the algorithm would ideally be generalisable to m tasks and n people.
Also if such an algorithm doesn't currently exist, how would you suggest going about constructing one? Currently I can only think of assigning the task relating to the biggest difference between the fastest and second fastest times to complete it, and I don't really know where to go from there.
I get the feeling like this is similar to some bin-packing algorithm, however each bit of 'rubbish' is differently sized depending on which bin it is put in. Also I think this is similar to what I found here Assignment problem with divisible tasks and hours, but here people can split tasks, and the question wasn't answered fully.
I hope I've clarified enough of the problem, can answer any questions if needed.
This problem is $NP$-complete, even in the case of two people and where both people take the same amount of time for each task (i.e.: $n = 2$ and $a_i = b_i$ for all $i=1,\ldots,m$) since this is essentially the PARTITION problem. As such, it is unlikely that you will find a polynomial-time algorithm that solves the problem exactly. However, it is possible that suitable approximations and/or super-polynomial-time solutions might exist for your purposes.