2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wouldn't this question be better suited in the Computer Science Stack Exchange? $\endgroup$ – user635162 Jan 27 at 22:43
  • 1
    $\begingroup$ @palaeomathematician I've definitely done things like this in Decision Mathematics in school, which is why I posted it here. Perhaps doing so might be more useful though. $\endgroup$ – Oliver Wheat Jan 27 at 22:47
  • $\begingroup$ This question can belong on either site (especially if the algorithms tag is added), but you're likely to get differently-flavored answers depending on where you post it. $\endgroup$ – Misha Lavrov Jan 27 at 23:33
  • $\begingroup$ Please check Generalized assignment problem $\endgroup$ – W.R.P.S Jan 28 at 11:33
  • $\begingroup$ @W.R.P.S I've had a quick look at the Generalised assignment problem - I may have to look into it further but it appears to try and minimise the TOTAL cost, rather than the maximum cost of the individuals, as shown in the fourth bullet point - so I don't know if it is appropriate. $\endgroup$ – Oliver Wheat Jan 28 at 22:35
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.