1

问题场景：

  • 任务数（n）大于工人数（m）。

  • 我需要将多个任务分配给一个工人。

    这是成本矩阵

    • 我有 6 个任务和 3 个可用的工人。

    • C (i,j) = 1，对于指示的单元格，可以将工人分配给任务。

    • C (i,j) = 1000，对于表示不能将工人分配给任务的单元格。

成本矩阵

  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

这里，worker1可以做任务（TASK-1，TASK-4）worker2可以做任务（TASK-2，TASK-5）worker3可以做任务（TASK-6）

为了创建方阵，我添加了虚拟 WORKERS：DWORKER1、DWORKER2 和 DWORKER3)，如下所示，并为单元格值分配了非常大的值 (1000000)。

 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

我用了这个scipy包scipy.optimize.linear_sum_assignment。如下：

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)

col_ind 的输出是array([5, 3, 4, 0, 1, 2])

输出表明（如果我没记错的话）：

    - 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

我所期待的是，将 TASK（1、2 和 3）分配给真正的工人而不是假工人。通过这个实现有可能吗？或者我在这里遗漏了什么？

4

1 回答 1

1

匈牙利算法用于解决分配问题，其中每个工人都分配了一个任务。通过执行您提出的技巧，您确实会为每个虚拟工作者分配 1 个任务。

如果您只想将任务分配给真正的工人，并分配多个任务，那会容易得多：对于每个任务，选择成本最低的工人。在您的示例中，这意味着工人 1 将执行任务 1 和 4，工人 2 将执行任务 2 和 5，工人 3 将执行任务 6，任务 3 将由三个工人之一完成（取决于您如何处理平等情况）。

于 2017-09-12T09:57:21.343 回答