为工人分配工作

Question

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

如果 N > M 那么是时候裁员了！ :)

职位属性：

每项工作都应在特定时间内执行 window，具体时间因工作而异。
每个职位的位置因职位而异。
有些工作需要特殊技能。完成工作所需的技能因工作而异
某些作业的优先级高于其他作业。某些职位的 "reward" 高于其他职位。

管道工的属性：

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

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

可能无法完成所有作业。例如，有一个水管工和两个工作，如果他们正在做工作 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。

似乎有点不同，但因为 space/time 皱纹：管道工可以做 A 或 B，但不能同时做，因为它们之间的距离（完成 A 后无法及时到达 B ).作业必须在一定时间内完成 windows.

此外，如果他们的时间太近（即使他们在 space 中很接近），水管工也可能无法兼任这两项工作。例如如果B必须在time_A_finished + time_to_travel_A_to_B之前开始，那么B不能在A之后完成。

感谢任何想法！任何有关该领域值得阅读的好东西的建议也很受欢迎。

Answer 1

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

我可以建议两种改进贪婪算法的通用方法。首先是本地搜索。得到一个贪心解后，看看assigning/reassigning/un-assigning几个作业有没有小改进。重复直到没有明显改善或 CPU 时间用完。

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

为工人分配工作

Assigning jobs to workers

algorithm

graph-algorithm