algorithm - 任务分配算法

Question

我正在尝试找出将任务分配给人们的最有效方式。这是我正在努力解决的问题:

• 你有 X 个人都有资格工作
• 每个人一次可以完成 X 项任务
• 你有X个等待任务
• 每项任务需要不同的时间长度

挑战的目标是尽可能将任务平均分配给人们。一旦一个人完成了一项给定的任务，其中一项“排队”的任务将被提供给他们。这是一个示例场景。

队列中有 500 个任务，50 个人可以“接手”这些任务。每个人一次可以完成 2 个任务。一旦一个人完成了给定的任务，他们就会被另一个人喂饱。等待时间最长的任务获得最高优先级。

一种可行的方法是让 50 名有能力完成任务的人中的每人根据他们上次给定的任务分配一个任务。例如:

• 任务 1 -> 人员 1
• 任务 2 -> 人 2
• 任务 3 -> 人员 3

...

• 任务 4 -> 人 1
• 任务 5 -> 人员 2
• 任务 6 -> 人员 3

根据最后分配给 X 人的任务，上次分配任务最早并且可以承担另一项任务的人会把任务交给他们。我不确定这是否是均匀任务分配的正确解决方案，很想听听建议!这种算法有名称吗？

另一种方法可能是根据当前服务最少任务的人分配任务。虽然如果多个人被绑定(bind)到最少数量的任务，任务将分配给可用时间最长的人(最后分配的任务)。

Answer 1

请考虑从更高的层面来看待这个问题。

到目前为止的提议都是贪婪的。他们建立一个时间表并希望最好的。

您需要决定的第一件事是这是否是您想要的。对于某些输入，贪心分配会产生非常糟糕的答案，但如果输入是“合理的”，并且您想要的只是一个合理的答案，那可能没问题。

另一方面，找到最佳任务分配是 NP 困难。您需要输入大小的时间指数来确保您获得最佳答案。

有两种中间方法。

• 随机任务调度算法。这是一个很大的话题。 This paper仍然是一个不错的起点，尽管它现在已经非常过时了。理查德卡普是惊人的。随机算法的好处在于它们可以提供非常有用的最优性保证。

• 启发式搜索。定义一个时间表的良好程度的单一数字指标。从一个合理的开始(贪婪决定或随机)。把它放在按度量 v 排序的搜索队列中，从队列中拉出最好的度量，找到它的所有“子项”，即之前没有考虑过的由于所有可能的简单更改而产生的调度，将它们添加到队列中，然后重复.当你不能再等的时候就停下来。当前最好的就是你的答案。您还可以将其构建为遗传算法，它只是一种专门的启发式搜索。