5

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

我们有“工人” 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 本来是完美的工作。

我曾考虑将问题简化为分配问题，但没有找到方法。

如何解决这个问题？

4

1 回答 1

3

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

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

目标只是 x ij的所有 i 和 j 的总和。约束是：

  1. 没有工人超过他们的最大时间：对于每个 i，x ij的所有 j 的总和小于或等于 m i

  2. 每个作业完成：对于每个j，R ij *x ij的所有i之和大于等于1

  3. 没有人可以负工作时间：对于所有 i 和 j，x ij大于或等于零

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

于 2015-12-12T00:44:52.093 回答