# Optimize Multiple Agents Completing Multiple Tasks in Parallel

I have an optimization problem and I am wondering if there is a better way to solve it than using a naïve brute force method. I have a number of tasks T that must be completed, and a number of agents A to do work in parallel to one another. For this, T > A.

What I would like to do is write a program to figure out the optimal agent-to-task assignments such that all tasks have been completed and the least amount of time OVERALL has passed. In other words, because the agents work in parallel to one another, the agent that finishes their assigned tasks last is the limiting factor and determines the overall time needed. The amount of time a task takes is independent of which agent the task is assigned to. Each task can only be assigned to and worked on by one agent.

As a simple example:

Lets say we have 3 tasks, A, B and C, which take 30, 90, and 45 minutes respectively. Lets say we have 2 agents.

A bad assignment list would be:

Agent 1: Tasks A and B = 30 + 90 = 120 minutes

Agent 2: Task C = 45 minutes

overall time is 120 minutes

The optimal assignments would be:

Agent 1: Tasks A and C = 30 + 45 = 75 minutes

Agent 2: Task B = 90 minutes

overall time is 90 minutes.

The way I have solved this so far is with a simple brute force method like so:

1. Generate a new permutation of the task list
2. For each task in the list:
• Find the agent whose current task list requires the minimum time to complete
• Assign the task to this agent
3. Once all tasks have been assigned:
• Find the agent whose current task list requires the maximum time to complete
• Note this time as the result for this permutation of the task list
• Clear each agent's task list
4. Repeat steps 1 - 3 until all permutations have been generated
5. Once all permutations have been generated
• Find the permutation with the minimum result
• The agent-to-task assignments generated by this permutation is the optimal solution

The obvious problem with this is that when you get to more than 11 or 12 tasks the amount of permutations needed becomes unreasonable for a brute force solution.

Is there a more elegant solution to something like this? I'm not the most mathematically minded person, but the closest thing I could find when googling around was an unbalanced assignment problem, and as far as I could tell thats not quite the same thing.

PS: I'm not sure what tags to add to this question other than "optimization". I added "assignment-problem" as well but if there are more apt tags let me know and I will add them.

Thanks!

This problem is known as Makespan Scheduling and is $$\mathsf{NP}$$-complete. Hence, computing an optimal assignment cannot be done in polynomial time unless $$\mathsf{P} = \mathsf{NP}$$; i.e., under common complexity-theoretic assumptions, there is no algorithm which is guaranteed to find optimal assignments quickly.
However, steps (1) and (2) of your algorithm basically already yield a $$2$$-approximation (i.e. achieves an assignment whose makespan is at most twice the optimal makespan), and with some easy techniques, the approximation factor can be brought down to $$4/3$$. Indeed, the problem also admits a polynomial-time approximation scheme (PTAS) which achieves a $$(1 + \varepsilon)$$-approximation using time polynomial in the instance size and $$1 / \varepsilon$$. You can find a treatment of the problem in the great book Approximation Algorithms by Vazirani.