algorithm - 将相同的队列项分配给多个工作人员

Question

我们有一个逻辑任务队列，其中每个任务都必须分配给多个工作人员。要分配的工人数量基于最小和最大工人的配置。工人不应该看到他们已经完成的相同任务。没有必要让所有工作人员都看到所有任务。

工人总数可以动态变化。每个工人都可以随时在线或离线。

每个工人都可以选择完成任务或让它过期。到期时，应将任务分配给尚未完成任务的任何工人。

有没有很好的算法来解决这种情况？

标签： algorithmqueuelanguage-agnosticcomputer-scienceworker

Answer 1

简单的解决方案：

贪婪分配任务：

• 对于每一个准备好的任务。
• 找到尚未看到任务的最小 <= N <= 最大工作人员并分配他们。
• 重复直到你用完工人或完成所有任务。
• 如果工作人员上线或完成任务，则重新检查所有任务。
• 如果有新任务出现，请重新检查可用的工人。

如果没有那么多任务，这个解决方案可能就足够了，因为它的计算量很大并且会重新计算所有内容。

可能的优化：

如果贪婪的解决方案失败（而且很可能会失败），有办法改进它。我将尝试列出我想到的那些，但它不会是一个详尽的列表。

首先，我个人最喜欢的：网络流。不幸的是，我没有看到解决最少工人要求的简单方法，但是它会很快，并且会导致在任何给定时刻分配尽可能多的工人。

• 创建网络 Source - Workers - Tasks - Sink。Edges 工作人员与任务将根据需要链接和取消链接：
• 当工人可用于任务时，创建权重为 1 的边，否则不创建边。
• 从源链接到每个在线工作者的权重为 1 的边缘。
• 从每个任务链接一条边，其权重等于其最大工人能力。

你甚至可以区分不同类型的工作者，网络流很棒。算法速度很快，这使得它们甚至适用于大图。此外，它们在许多库中都可用，因此您不必自己实现它们。不幸的是，没有简单的方法来执行最少工人规则。至少我现在没有看到，可能有某种方式。或者至少是启发式的

第二，贪婪时聪明：

• 为每个任务创建一个队列。
• 当工作人员可用时，将他可以执行的每项任务注册到其队列中。
• 当某个工作人员不可用时，将他从队列中移除。
• 当任务有足够的工人时，启动进度并禁用这些工人。

这仍然是蛮力方法，但是由于您保留队列，因此您将必要的计算量限制在合理的水平。潜在的缺点是大型任务（具有最少数量的工人）可能会被更容易开始的小任务所拖延 - 并且会吃掉工人。因此，可能需要进行一些进一步的检查/平衡和优先排序。

对于您手头的任务，肯定还有更多需要尝试和完成的工作，但是您提供的信息相当有限，所以这个建议并不那么具体。