算法 - 根据两个标准平均填充不同大小的容器

Question

我正在努力思考一种算法。我以前从未编写过算法代码，也不确定如何解决这个问题。这是它的要点:

我可以有 n 个容器，每个容器有两组对我很重要的数字:内存量 (x) 和逻辑处理器数 (y) 每个容器可以有不同的值。

每个虚拟机都有一定数量的内存 (x) 和一定数量的逻辑处理器 (y)。我正在尝试创建一种算法，该算法将均衡地平衡集群中所有主机的内存负载 (x) 和多个逻辑处理器 (y)。它不会在所有主机之间真正相等，但所有主机都将在每个主机的 10% +/- 以内。

我将如何解决我在数学上假设的这个问题。

Answer 1

如果我对您的问题的理解正确，您希望将主机的相对负载降至最低，以便每个主机的负载与其他主机的偏差不超过 10%。所以我们想通过找到一个最小值来优化主机之间的“相对负载”。

为此，您可以使用某种 Combinatorial Optimization以达到可接受的或最佳的解决方案。经典的元启发式算法，如 Simulated Annealing或 Tabu Search会完成这项工作。

针对您的问题的示例通用步骤:

• 通过将每个 VM 随机分配给主机来定义初始状态
• 通过在主机之间反复交换 VM 来找到新状态，直到:
  • 找到了一些可接受的解决方案，或者
  • 迭代次数用完，或者
  • 满足其他一些条件(如模拟退火的“温度”)
• 开发一个比较函数来决定在每次迭代中何时切换状态(解决方案)
  • 在您的情况下，您应该测量所有主机之间的相对负载，并且仅当新状态的相对负载低于当前状态时才交换状态。

这当然假设您将使用某种形式的逻辑表示而不是实际的 VM 来执行此算法。找到模拟真实条件的解决方案后，您可以将它们实际应用到您的虚拟机/主机配置中。

希望这对您有所帮助!