algorithm - 为 worker 分配工作

Question

有 N 个水管工，他们有 M 个工作要做，一般来说 M > N。

如果 N > M 那么裁员时间到了! :)

作业的属性:

1. 每项工作都应在特定时间范围内执行，具体时间因工作而异。
2. 每项工作的地点因工作而异。
3. 有些工作需要特殊技能。完成工作所需的技能因工作而异
4. 某些作业的优先级高于其他作业。某些工作的“返回”高于其他工作。

管道工的属性:

1. 水管工必须从一份工作开车到下一份工作，这需要时间。假设已知从每项工作到其他所有工作地点的行程时间是多少。
2. 有些水管工拥有其他人所没有的技能。

任务是找到管道工的最佳工作分配，以使奖励最大化。

有可能不是所有的工作都能完成。例如，有一个水管工和两个工作，如果他们正在做工作 A，他们可能无法做工作 B，因为一旦他们完成 A 而 B 应该开始，就没有足够的时间从 A 到 B .在这种情况下，最佳做法是让水管工完成工作并获得最大返回，然后我们就完成了。

我正在考虑一个像这样工作的贪心算法:

sort jobs by reward
while true:
  for each job:
    find plumbers that could potentially handle this job
      make a note of the association, used in next loop
    if each plumber is associated with a different job, break
  for each job that can be handled by a plumber:
    assign job to a plumber:
      if more than one plumber can handle this job, break tie somehow:
        for instance if plumber A can do jobs X,Y but 
        plumber B can only do X, then give X to B.
        else just pick a plumber to take it
    remove assigned job from further consideration
  if no jobs got assigned:
    break out of "while true" loop 

我的问题:有没有更好的方法？似乎是一个 NP-hard 问题，但我没有证据证明这一点。 :)

我猜它类似于 Assignment Problem .

虽然由于空间/时间的原因，它似乎有点不同:管道工可以做 A 或 B，但不能同时做，因为它们之间的距离(完成 A 后无法及时到达 B)。作业必须在特定时间窗口内完成。

另外，如果时间间隔太近(即使空间间隔很近)，水管工也可能无法同时兼顾这两个工作。例如，如果 B 必须在 time_A_finished + time_to_travel_A_to_B 之前开始，则 B 不能在 A 之后完成。

感谢您的任何想法!任何有关该领域值得阅读的好东西的建议也非常感谢。

Answer 1

即使在工作之间安排一名管道工也像 NP-hard 旅行推销员问题一样困难。

我可以建议两种改进贪心算法的通用方法。首先是本地搜索。获得贪心解后，通过分配/重新分配/取消分配一些作业，看看是否有任何小的改进。重复直到没有明显的改善或 CPU 时间耗尽。

另一种方法是使用列生成的线性规划。这更强大，但涉及更多。我们的想法是建立一个主程序，在该程序中，我们尝试通过选择使用或不使用每个可行的管道工时间表来获得尽可能多的奖励，但要遵守只做一次工作且不使用比实际更多的管道工技能的包装约束可用的。在解决主程序的每个阶段，工作和管道工对应的双重值(value)反射(reflect)了做特定工作/使用特定管道工的机会成本。子问题是弄清楚如何安排管道工的路线，以便获得比管道工“成本”更多的(调整后的)奖励。这个子问题是 NP-hard(根据上面的注释)，但它本身可能适用于动态规划或进一步的线性规划技术，具体取决于有多少工作。沿着这条路走，您很快就会触及学术运筹学的外部界限。