任务分配算法
Task assigning algorithm
我正在尝试找出将任务分配给人们的最有效方法。这是我正在努力解决的问题：
- 你有 X 个人都有资格工作
- 每个人一次可以完成 X 项任务
- 您有 X 个等待任务
- 每项任务需要不同的时间长度
挑战的目标是尽可能将任务平均分配给人们。一旦一个人完成了其中一项给定的任务，就会将 'queued' 项任务之一提供给他们。这是一个示例场景。
队列中有 500 个任务，有 50 个人可以 'take' 完成任务。每个人一次可以完成 2 个任务。一旦一个人完成了给定的任务，他们就会被另一个人喂饱。等待时间最长的任务获得最高优先级。
一种可行的方法是让 50 名有能力完成任务的人中的每一个根据他们上次给定的任务分配一个任务。例如：
- 任务 1 -> 人员 1
- 任务 2 -> 人员 2
- 任务 3 -> 人员 3
...
- 任务 4 -> 人员 1
- 任务 5 -> 人员 2
- 任务 6 -> 人员 3
根据最后分配给 X 人的任务，上次分配任务最早并且可以承担另一项任务的人会把任务交给他们。我不确定这是否是均匀任务分配的正确解决方案，很想听听建议！这种算法有名称吗？
另一种方法可能是根据当前服务最少任务的人分配任务。虽然如果多个人被绑定到最少数量的任务，任务将分配给可用时间最长的人（最后分配的任务）。
保留2个队列。一个用于任务，另一个用于等待任务的空闲人员。如果有任务要执行，队列中的第一个人将执行并离开。在此解决方案中，您不会考虑任务和人员的时间，因为它是公平的分配方式。如果您将来需要某种优先级排序，并且两个队列都几乎没有变化，您可能会考虑优先级队列。
作为zsiar，但使用两个优先级队列。假设他有能力，最高优先级队列中的最高任务将分配给最高工作人员。如果他不在，则任务无法完成，必须等待。
工作人员优先级队列中的工作人员按容量或空闲时间或任何看起来公平的方式排序。实际上这不是一个真正的优先级队列，因为当一个工作人员完成一个任务时，我们把他取出来，把他放回队列中，在更高的位置。
（如果工人可以同时完成两项任务，那么他们很可能是计算机而不是人，所以闲置时间不是一个有用的指标。只有人类工人才关心他们是否保持忙碌而其他人却在闲逛）。
请考虑从更高的层面来看待这个问题。
到目前为止的提议都是贪婪的。他们建立一个时间表并希望最好的。
您需要决定的第一件事是这是否是您想要的。贪心分配会为某些输入产生非常糟糕的答案，但如果输入是 "reasonable," 并且你想要的只是一个合理的答案，它可能没问题。
另一方面，找到 最优任务分配是 NP 难题。您需要输入大小的时间指数来确保您获得最佳答案。
有两种中间方法。
随机任务调度算法。这是一个很大的话题。 This paper 仍然是一个不错的起点，尽管它现在已经非常过时了。理查德卡普是惊人的。随机算法的好处在于它们可以提供非常有用的最优性保证。
启发式搜索。定义一个时间表的良好程度的单一数字指标。从一个合理的开始（贪婪决定或随机）。把它放在按度量 v 排序的搜索队列中，从队列中取出最好的度量，找到它的所有 "children"，即在所有可能的简单更改产生之前没有考虑过的调度，将它们添加到队列中，并重复。当你不能再等的时候就停下来。当前最好的就是你的答案。您还可以将其构造为遗传算法，这只是一种专门的启发式搜索。
我正在尝试找出将任务分配给人们的最有效方法。这是我正在努力解决的问题：
- 你有 X 个人都有资格工作
- 每个人一次可以完成 X 项任务
- 您有 X 个等待任务
- 每项任务需要不同的时间长度
挑战的目标是尽可能将任务平均分配给人们。一旦一个人完成了其中一项给定的任务，就会将 'queued' 项任务之一提供给他们。这是一个示例场景。
队列中有 500 个任务，有 50 个人可以 'take' 完成任务。每个人一次可以完成 2 个任务。一旦一个人完成了给定的任务，他们就会被另一个人喂饱。等待时间最长的任务获得最高优先级。
一种可行的方法是让 50 名有能力完成任务的人中的每一个根据他们上次给定的任务分配一个任务。例如：
- 任务 1 -> 人员 1
- 任务 2 -> 人员 2
- 任务 3 -> 人员 3
...
- 任务 4 -> 人员 1
- 任务 5 -> 人员 2
- 任务 6 -> 人员 3
根据最后分配给 X 人的任务，上次分配任务最早并且可以承担另一项任务的人会把任务交给他们。我不确定这是否是均匀任务分配的正确解决方案，很想听听建议！这种算法有名称吗？
另一种方法可能是根据当前服务最少任务的人分配任务。虽然如果多个人被绑定到最少数量的任务，任务将分配给可用时间最长的人（最后分配的任务）。
保留2个队列。一个用于任务，另一个用于等待任务的空闲人员。如果有任务要执行，队列中的第一个人将执行并离开。在此解决方案中，您不会考虑任务和人员的时间，因为它是公平的分配方式。如果您将来需要某种优先级排序，并且两个队列都几乎没有变化，您可能会考虑优先级队列。
作为zsiar，但使用两个优先级队列。假设他有能力，最高优先级队列中的最高任务将分配给最高工作人员。如果他不在，则任务无法完成，必须等待。
工作人员优先级队列中的工作人员按容量或空闲时间或任何看起来公平的方式排序。实际上这不是一个真正的优先级队列，因为当一个工作人员完成一个任务时，我们把他取出来，把他放回队列中，在更高的位置。
（如果工人可以同时完成两项任务，那么他们很可能是计算机而不是人，所以闲置时间不是一个有用的指标。只有人类工人才关心他们是否保持忙碌而其他人却在闲逛）。
请考虑从更高的层面来看待这个问题。
到目前为止的提议都是贪婪的。他们建立一个时间表并希望最好的。
您需要决定的第一件事是这是否是您想要的。贪心分配会为某些输入产生非常糟糕的答案，但如果输入是 "reasonable," 并且你想要的只是一个合理的答案，它可能没问题。
另一方面，找到 最优任务分配是 NP 难题。您需要输入大小的时间指数来确保您获得最佳答案。
有两种中间方法。
随机任务调度算法。这是一个很大的话题。 This paper 仍然是一个不错的起点，尽管它现在已经非常过时了。理查德卡普是惊人的。随机算法的好处在于它们可以提供非常有用的最优性保证。
启发式搜索。定义一个时间表的良好程度的单一数字指标。从一个合理的开始（贪婪决定或随机）。把它放在按度量 v 排序的搜索队列中，从队列中取出最好的度量，找到它的所有 "children"，即在所有可能的简单更改产生之前没有考虑过的调度，将它们添加到队列中，并重复。当你不能再等的时候就停下来。当前最好的就是你的答案。您还可以将其构造为遗传算法，这只是一种专门的启发式搜索。