python - 匈牙利算法 : multiple jobs per worker

是否有匈牙利算法的扩展，可以满足为每个 worker 分配多个工作？在其最简单的形式中，该算法将单个工作分配给单个 worker 。

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

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

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

最佳答案

方法一

一个简单的方法是为每个 worker 制作 50 个克隆，然后正常解决问题。

要找到 worker 1 的工作，您可以收集分配给 worker 1 的克隆的所有工作。只有 50 个克隆，因此 worker 1 最多分配给 50 个工作。

这种分配问题可以表示为最小成本流问题，如果 worker 做某项工作，则存在从 worker 到工作的流动。

在这个公式中，每个 worker 都被提供了 1 个流量单位的容量。然后，您可以根据需要简单地增加容量来增加作业数量。

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

关于python - 匈牙利算法 : multiple jobs per worker，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48108496/