I am trying to figure out how can I assign tasks to workers in a way that maximum time required to complete all tasks is minimum.

Suppose I have following matrix

|          | Job 1 | Job 2 | Job 3 |
| Worker 1 |     5 |     4 |     5 |
| Worker 2 |     3 |     2 |     5 |
| Worker 3 |     1 |     5 |     2 |

If I want to assign 1 task to each worker one way is to assign worker 1 Job 3 worker 2 Job 2 and Worker 3 Job 1. Using this approach we are minimizing overall cost for all workers. (i.e. 5 + 2 + 1 =8). What algorithm can be applied to get overall minimization using this approach?

Next approach is to find an assignment such that maximum time of assignment is minimized. Using this approach we assign worker 1 Job 2 worker 2 Job 1 and Worker 3 Job 3. (i.e. 4 + 3 + 2) Using this assignment approach maximum is 4 instead of 5. What algorithm can be used to make assignment in such manner?

Note: Each worker gets only 1 task.

  • $\begingroup$ Is the number of jobs always the same as the number of workers with exactly one job for each worker? $\endgroup$
    – fontanf
    Commented Jan 28, 2021 at 20:21
  • $\begingroup$ In the first case, you could try using the assignment problem and its famuse heuristic, hangarian method to reproduce your solution. In the second one, some parallel resource scheduling rules, might be useful to minimize the sum of the completion time. $\endgroup$
    – A.Omidi
    Commented Jan 28, 2021 at 22:02
  • $\begingroup$ As mentioned, minimizing the sum of the task times is an assignment problem. To minimize the maximum task time, you can use either an integer programming model or a constraint programming model. $\endgroup$
    – prubin
    Commented Jan 29, 2021 at 0:33
  • $\begingroup$ Number of jobs can be different than number of workers. Is there any working example like the example shown above? $\endgroup$
    – Lopez
    Commented Jan 29, 2021 at 6:25
  • 1
    $\begingroup$ @prubin if their is exactly 1 job per worker, I think the maximum can be solved in polynomial time by repeatedly finding a maximum matching and removing all edges with cost greater or equal than the maximum cost of the matching until the size of the maximum matching becomes strictly smaller than the number of workers. But maybe there is a more efficient algorithm $\endgroup$
    – fontanf
    Commented Jan 29, 2021 at 19:01

1 Answer 1

  • Minimizing the sum of all assignments: this is the classical version of the assignment problem. The Hungarian algorithm solves it in polynomial time.

  • Minimizing the maximum of all assignments: this one is known as the linear bottleneck assignment problem. The most obvious way to solve it is to solve a succession a decision problems: is it possible to find an assignment such that every worker is assigned exactly one job using only assignments with costs smaller than c? And to do a binary search on the value of c. This decision problem is a maximum cardinality matching problem in a bipartite graph which can be solved in polynomial time with Ford-Fulkerson algorithm or with Hopcroft–Karp algorithm. Additionally, a dual method and a dedicated augmenting path method can be found in the book "Assignment problems" (Burkard et al., 2009), section 6.2.

All these algorithms have a polynomial complexity. However, if you don't have them on hand, it might be faster to simply write an integer linear programming model or a constraint programming model and to solve it with a corresponding solver.

  • 1
    $\begingroup$ The minimax version is known as the linear bottleneck assignment problem. $\endgroup$
    – RobPratt
    Commented Jan 31, 2021 at 17:20
  • $\begingroup$ @RobPratt thanks, I've updated the answer $\endgroup$
    – fontanf
    Commented Jan 31, 2021 at 18:09

Your Answer

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

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