algorithm - 负载均衡算法——特例

Question

假设我有两座建筑物，我可以在其中 build 不同的单元。一个建筑物只能同时 build 一个单元，但有一个最多 5 个单元的 fifo 队列，它们将按顺序 build 。每个单元都有构建时间。我需要知道，什么是最快的解决方案来尽可能快地获得我的单元，考虑到我建筑物的构建队列中已经存在的单元。我认为像 RoundRobin 这样的“著名”算法在这里不起作用。

有什么算法可以解决这个问题吗？

Answer 1

这让我想起了星际争霸:D

我只想在建筑物队列中添加一个整数，代表它忙碌的时间。当然，您必须每个时间单位更新一次此变量。 (这里的时间单位是“s”，代表秒)

假设我们有一栋建筑，我们要提交 3 个单元，每个单元需要 5 秒才能完成。总计 15 秒。我们在时间 = 0。然后我们有另一个建筑物，我们提交 2 个单元，每个单元需要 6 个时间单元来完成。

所以我们可以有一个这样的表:

Time 0 
Building 1, 3 units, 15s to complete.
Building 2, 2 units, 12s to complete.

Time 1
Building 1, 3 units, 14s to complete.
Building 2, 2 units, 12s to complete.

而我们想要添加另一个需要 2 秒的单元，我们可以简单地遍历选定的建筑物并选择完成时间最短的一个。在这种情况下，这将是建筑物 2。这将导致 Time2...

Time 2
Building 1, 3 units, 13s to complete
Building 2, 3 units, 11s+2s=13s to complete

...

Time 5
Building 1, 2 units, 10s to complete (5s are over, the first unit pops out)
Building 2, 3 units, 10s to complete

等等。

当然，您必须注意生产设施的上限。就像如果建筑物有 5 个元素，不要分配任何东西并选择下一个完成时间最短的建筑物。

我不知道您是否可以使用您的引擎轻松实现这一点，或者它是否支持某种时间单位。

这只会导致每个时间单位更新所有生产设施一次，O(n)，其中 n 是可以生产某种东西的建筑物的数量。如果您要提交一个单元，这将花费 O(1) 假设您将选定的建筑物按排序顺序排列，最低的在前 - 所以只是第一个元素查找。在这种情况下，您必须在操作单位(如取消或添加)后对列表进行求助。

否则阿米特的答案似乎也是可能的。