algorithm - 是否存在分配问题的算法，其中并非每个任务都可以由每个代理执行并且某些任务比其他任务更重要？

Question

我的问题与分配问题 ( http://en.wikipedia.org/wiki/Assignment_problem ) 非常相似，除了三个异常(exception):

1. 并非每个代理都可以执行所有任务。
2. 有些任务比其他任务更重要。
3. 绝对有可能不会完成所有任务。

这背后的真实世界故事是一个依靠志愿者运作的消防部门。一整天，志愿者都可以说他们有空或没有空，我们必须重新评估每项任务是否已完成。如果不是，则需要通知某人存在问题。如果我们只有最低金额，我们已经想通知。一般来说，一个小型消防队通常需要有一名领导、一名司机和 4 名随时待命的正规消防员。

将其转化为分配问题，我们说领导、司机、消防员是任务，每个消防员都是代理人。我们想要做的是找出是否存在问题(即我们没有 2 名可能的领导者、2 名可能的司机和 5 名普通消防员)，问题有多大(即我们有最小数量，或者我们是有麻烦)以及问题出在哪里(即我们需要另一名消防员或我们需要另一名领导，需要另一名领导比需要另一名消防员更重要)。

所以我们想要做的是给定一组任务和一组代理，每个代理都可以执行一组可变的任务，划分代理以便完成每个任务或完成最重要的任务。

我检查过的解决分配问题的算法最终出错的地方是你没有足够的人来完成所有任务。然后他们似乎被分配到优先级较低的任务，而让他们执行优先级较高的任务会“更好”。

这听起来很熟悉吗？在我看过的所有不同变体中，我是否都错过了这个问题的名称？或者有人可能对如何有效地解决这个问题有绝妙的想法？

Answer 1

您基本上可以使用首先安排最高优先级任务的贪心算法。我会做类似的事情:

• 接受最高优先级的任务
• 对于每个可以执行此任务的代理，确定他们可以执行哪些其他尚未分配的任务(“能力”)
• 如果代理没有其他能力，则将他们分配给此任务
• 否则[所有代理都有其他能力]计算有多少其他尚未安排的代理也具有这些其他能力
• 选择其他能力“重复”最多的资源
• 重复下一个最高优先级任务

那么举个具体的例子，假设你有5个agent如下:

A - leader, fireman
B - leader, driver
C - driver, fireman
D - fireman
E - fireman

你的最高优先级任务是领导者，所以选择代理人 A 和 B。A 也可以做“消防员”，由其他 3 人复制，B 也可以做“司机”，由另外 1 人复制。所以重复任务最多的代理是 A，A 被分配给领导者。

下一个最高任务是司机。 B 只能做“driver”，因为 leader 已经分配，​​所以 B 得到了 driver。

等等。

这有点蛮力，我敢肯定有些边缘情况它没有捕捉到，但至少这是一种可用的方法......