# How to determine least time required to complete all tasks?

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.

• Is the number of jobs always the same as the number of workers with exactly one job for each worker? Jan 28 at 20:21
• 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. Jan 28 at 22:02
• 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. Jan 29 at 0:33
• Number of jobs can be different than number of workers. Is there any working example like the example shown above? Jan 29 at 6:25
• @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 Jan 29 at 19:01

• 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.