2
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Is the number of jobs always the same as the number of workers with exactly one job for each worker? $\endgroup$
    – fontanf
    Jan 28 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
    Jan 28 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
    Jan 29 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
    Jan 29 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
    Jan 29 at 19:01
3
$\begingroup$
  • 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.

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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