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?
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).