匈牙利算法具有不等数量的工人和任务

Question

我有一个问题困扰我一段时间了.

我们有"工人"w_0,w_1 ... w_n,以及任务t_0,t_1,... t_m和持续时间D_ij,使得w_i可以在该小时数内完成t_j.每个工作人员还可以使用最多m_0,m_1 ... m_n小时数.

多个工作人员可以通过按比例分配的工作来完成相同的任务.例如,如果D_11 = 2且D_21 = 4,则工作人员1在任务1上的效率是工人2的两倍.因此,您可以组合,例如1小时1的工作和2的2工作以完成任务.

我们如何确定完成所有任务的最短小时数.

我已经尝试使用贪婪技术为每个任务选择最佳工作者,但这并不适用于每个案例.例如,工人1可以在2小时内完成任务1,在4小时内完成任务3.很明显,工人1将被选中从事任务1工作,尽管如此,让我们说任务3对于其他工人来说非常耗时,而工人1对于工作来说是完美的.

我已经考虑过将问题减少到一个任务问题,但没有找到方法的运气.

怎样才能解决这个问题？

Answer 1

有一个简单的线性规划公式。

首先，我们通过 R _ij = 1/D _ij将持续时间 D _ij转换为速率 R _ij。接下来，我们定义代表工人 i 处理任务 j 的时间量的决策变量 x _{ij 。}

_{目标只是 x ij}的所有 i 和 j 的总和。限制条件是：

维基百科页面提供了各种线性求解器软件的链接。