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 '21 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 '21 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 '21 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 '21 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 '21 at 19:01