10

是否有匈牙利算法的扩展来满足每个工人分配多个工作的需求?在最简单的形式中,该算法将单个工作分配给单个工人。

我的应用程序是一个利润最大化问题,有 3 个工人和 180 个工作岗位。我还将添加约束(至少为每个工人分配 50 个工作)。

我已经设法使用 Python 中的 mungres 库实现了匈牙利算法,效果很好。我只是在努力寻找与每个工人的多项任务相关的文献。

https://pypi.python.org/pypi/munkres

https://en.wikipedia.org/wiki/Hungarian_algorithm

https://en.wikipedia.org/wiki/Generalized_assignment_problem

我已经尝试了评论中列出的标准 numpy 方法,但无法将其扩展到每个工作人员的多个任务。如果我的矩阵是矩形的(即 3 个工人和 4 个工作),则只有前 3 个工作分配给工人。我还尝试添加虚拟变量来创建方阵,但随后将工作分配给那些虚拟工人而不是实际工人

4

3 回答 3

10

方法一

一种简单的方法是,例如,为每个工人制作 50 个克隆,然后像往常一样解决问题。

要查找工人 1 的作业,您可以收集分配给工人 1 的克隆的所有作业。克隆只有 50 个,因此工人 1 最多将分配到 50 个作业。

方法二

这种分配问题可以表示为最小成本流问题,如果工人完成工作,就会有从工人到工作的流动。

在此公式中,为每个工人提供 1 个流量单位的容量。然后,您可以根据需要通过简单地增加容量来增加作业数量。

这种方法可能更有效(因为图更小),但需要修改底层算法,而方法 1 应该很容易实现。

于 2018-01-05T08:19:10.413 回答
1

这可以通过将其表述为具有 [50,inf) 范围的工人的运输问题来解决。如果我错了,请纠正我,彼得解决方案中的方法 1 适用于一个人最多可以做 50 次,而不是最低限度的情况。

于 2020-01-22T23:20:42.733 回答
-1

检查:https ://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linear_sum_assignment.html

线性和分配问题也称为二分图中的最小权重匹配。问题实例由矩阵 C 描述,其中每个 C[i,j] 是匹配第一个子集(“工人”)的顶点 i 和第二个子集(“工作”)的顶点 j 的成本。目标是找到一个完整的工人分配到最低成本的工作。

于 2018-01-05T06:57:35.287 回答