负载均衡算法 - 特例

Question

我们假设我有两座建筑,我可以在那里建造不同的单元.建筑物只能同时建造一个单元,但有一个最多5个单元的最后一个单元,它将按顺序构建.每个单元都有构建时间.我需要知道,考虑到已经在建筑物的构建队列中的单位,尽可能快地获得我的单位的最快解决方案.我认为像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) - 因此只需第一个元素查找。在这种情况下，您必须在操作单元（例如取消或添加）后重新使用列表。

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