1
$\begingroup$

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!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

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.

I don't know about existing software tools, but I would be amazed to learn that none exist given the practical relevence of the problem.

Improve this answer
$\endgroup$
0
$\begingroup$

I believe your problem is equivalent to a bin packing problem. To determine whether there exists a schedule that finishes in M minutes, set the bin capacity to M. Each task is a item, whose size is equal to the time it takes to complete that that task, so we have T items. Then there exists a bin packing for these items into at most A bins, iff there is a schedule that finishes in at most M minutes. You can use any algorithm for bin packing to solve your scheduling problem, using binary search on M. Conversely, you can use any algorithm for your scheduling problem to solve bin packing, using binary search on A.

Consequently, assuming I didn't make any mistakes, your problem is about as hard or easy as bin packing is. Unfortunately, bin packing is NP-hard, so your problem is NP-hard, too. Fortunately, this does mean you can use any approximation algorithm or heuristic algorithm for bin packing to solve your scheduling problem.

A pragmatic approach for solving your problem (as for solving many real-world scheduling problems) is to formulate the problem as an instance of integer linear programming, then use an off-the-shelf ILP solver (e.g., Gurobi, CPLEX).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.