Hungarian Algorithm not giving right result for multiple assignments

672 views Asked by At

The problem scenario :

  • The number of tasks(n) is greater than the number of workers(m).
  • I need to assign multiple tasks to a single worker.

    Here is the cost matrix

    • I have 6 tasks and 3 workers available.

    • C (i,j) = 1, for the cell which indicates, worker can be assigned to task.

    • C (i,j) = 1000, for the cell which indicates, worker can not be assigned to task.

The cost matrix

  TASK/WORKER        WORKER1   WORKER2  WORKER3

    TASK 1           1          1000     1000

    TASK 2           1000       1        1000

    TASK 3           1000       1000     1000

    TASK 4           1          1000     1000

    TASK 5           1000       1        1000

    TASK 6           1000       1000     1

Here , worker1 can do tasks ( TASK-1, TASK-4) worker2 can do tasks ( TASK-2, TASK-5) worker3 can do tasks ( TASK-6)

To create square matrix, I added dummy WORKERS : DWORKER1, DWORKER2 and DWORKER3) as follows and assigned very large value(1000000) to the cell value.

 TASK/WORKER        WORKER1   WORKER2  WORKER3  DWORKER1  DWORKER2 DWORKER3

    TASK 1           1          1000     1000   1000000   100000    1000000

    TASK 2           1000       1        1000   1000000   100000    1000000

    TASK 3           1000       1000     1000   1000000   100000    1000000

    TASK 4           1          1000     1000   1000000   100000    1000000

    TASK 5           1000       1        1000   1000000   100000    1000000

    TASK 6           1000       1000     1       1000000   100000    1000000

I used the scipy package scipy.optimize.linear_sum_assignment. As follows:

from scipy.optimize import linear_sum_assignment

cost = np.array([[1,1000,1000,1000000,100000,1000000],[1000,1,1000,1000000,1000000,1000000],[1000,1000,
1000,1000000,100000,1000000],[1,1000,1000,1000000,1000000,1000000],[1000,1,1000,1000000,100000,  1000000],[1000,1000,1,1000000,1000000,1000000]])

row_ind, col_ind = linear_sum_assignment(cost)

The output for col_ind is array([5, 3, 4, 0, 1, 2])

The output indicates (If I am not wrong):

    - Assign 6th task to worker 1
    - Assign 4th task to worker 2
    - Assign 5th task to worker 3
    - Assign 1st task to Dummy worker 1
    - Assign 2nd task to Dummy worker 2
    - Assign 3rd task to Dummy worker 3

What I am expecting is, assigning TASK ( 1, 2 and 3) to the real workers not the dummy workers. Is that possible through this implementation? Or I am missing anything here?

1

There are 1 answers

0
Damien Prot On

Hungarian algorithm is for solving the assignment problem, where there is exactly one task assigned to each worker. By doing the trick you propose, you will indeed have 1 task assign to each dummy worker also.

If you are interested in only assigning tasks to real workers, and assigning multiple tasks, that is much easier : for each task, select the worker with the smallest cost. In your example, it means that worker 1 will do tasks 1 and 4, worker 2 will do task 2 and 5, worker 3 will do task 6, and task 3 will be done by one of the three workers (depending on how you handle the equality case).