摘要

数据中心运营的主要挑战之一是在动态设置中以最佳方式将正在运行的进程重新分配给服务器，从而提高运营性能。2012年，谷歌与ROADEFEuro挑战赛合作提出了机器重新分配问题。这项工作的重点是解决这个问题的新方法。

特别的是，研究人员提出一种大型邻域搜索方法，该方法具有新颖的，特定于域的启发式邻域选择。这种启发式方法使用计算机上不平衡的资源使用情况来选择每次迭代中最有希望的进程。

此外，研究人员比较了两种搜索策略以优化子问题。第一个基于有限差异搜索的概念，尽管是针对大规模问题量身定制的；第二种方法涉及约束规划与随机重启策略的标准组合。

对ROADEF 2012中广泛研究的实例的实证评估证明了他们的方法对现有技术的有效性，并为三个实例找到了新的上限。

介绍

在过去的二十年中，数据中心显著增加，仅在美国就有近3000个，在爱尔兰有70多个。随着流媒体服务的增加，以及大多数网站的默认数据采集等。在研究界，许多研究自然而然地集中在减少数据中心对环境的影响上，而较少关注提高数据中心内的运营绩效。

2012年，谷歌通过2012年ROADEF/Euro挑战赛提出了一个挑战，以解决后一个运营绩效问题。总体目标是优化数据中心环境的虚拟化和服务配置。

他们提出了机器重新分配问题，该问题旨在将一组流程重新分配给一组机器，以最小化受许多约束的多目标功能。

在比赛期间，提出了一系列优化方法，Afsar等人总结了这些方法。正如Canales等人所讨论的那样，由于其复杂性和特异性，MRP一直是十年后文献中许多作品的焦点。

提出一个大型邻域搜索，其中包含一些特定的组件来解决MRP。这项工作的主要贡献是：一种新的领域特定邻域选择启发式、优化每个LNS子问题的新搜索策略。关于搜索策略，它依赖于一个已知问题，即启发式决策在搜索开始时更有可能出错，因为它的信息比搜索深度的信息少。

把这个问题带到MRP问题，当根据启发式将第一个进程分配给最好的机器时，因为其他进程还没有分配。而最后一个要分配的进程更有可能被正确分配，因为启发式具有已分配的所有进程的信息。

由于回溯算法使用深度优先搜索，因此它依赖于启发式算法做出的第一个决策，花费很长的搜索时间。为了克服这个问题，研究了两种搜索策略，它们不会花费大量时间调查更有可能正确的启发式决策的替代值。

机器重新分配问题

机器重新分配问题在文献中得到了相当大的关注，特别是谷歌在Roadef12中定义的问题。给定将流程分配给机器，问题涉及重新分配流程以最小化与重新分配的进程迁移相关的多目标成本函数。

虽然一些工作已经将该问题作为多目标优化问题来解决，但我们以Google定义的经典格式考虑该问题。在这里，使用成本加权总和将成本函数转换为单个目标函数。

成本与以下因素相关：机器上超过安全容量的资源负载，包括暂时性资源使用，其中进程同时使用原始机器及其重新分配的机器上的资源；机器上资源使用的平衡，以及与在计算机对之间迁移服务进程相关的成本。这个问题还受到诸如机器容量、过程子集和机器子集之间的关系等约束。

一项研究表明，大多数当前最先进的方法都应用了一些本地搜索技术的变化来解决MRP。他们还观察到使搜索策略适应每个实例特征的方法的优越性。

解决MRP最有效的本地搜索方法之一来自Gavranovic和Buljubasic，该技术的一个重要组成部分是帮助避免局部最优的噪声方法。当算法卡在局部最小值时，多目标成本函数中其中一个目标的权重发生了变化。

然后，搜索可以转义局部最优，因为它特定于前一个目标函数。当达到新的局部最优时，该方法返回到原始目标函数进行转义。这种方法是Roadef12的赢家。

已经为MRP提出了一些LNS方法，这些方法与这项工作特别相关。事实上，第二名的条目是基于CP的LNS。Mehta等人研究了基于CP的LNS和基于MIP的LNS的问题，发现基于CP的LNS方法明显更有效，特别是在大规模实例上。但是，此 LNS方法确实具有许多对问题实例特征高度敏感的参数。

在随后的工作中提出了一种改进的方法来解决参数敏感性问题，使用基于非模型的组合方法将LNS参数调整为类似实例的集群。

Brandt等人提出了另一种LNS方法，其中评估了四个特定于域的邻域选择启发式方法，并且只考虑了小的子问题（少于10个过程）。然而，这并没有达到与Mehta等人相同的性能水平，这是最先进的LNS方法。

就整体技术而言，Turky最近提出了两种双层超启发式方法，第一种涉及局部搜索，第二种涉及蚁群优化。展示的结果表明，该方法能够在Roadef12实例上优于大多数方法，实现了实例的许多新上限。

建议的算法

MRP 实施了大型邻域搜索，并比较了两种在 CP 求解器中优化子问题的方法。第一种方法是随机重启策略，其中根据失败阈值重新启动搜索。

通过在启发式的前 x 个选项中随机选择，在变量值排序启发式中添加了一个随机分量。因此，每次重新启动都可能会探索搜索空间的不同部分。此方法多次运行回溯搜索，在每次搜索中，失败阈值都会根据maxFail增加。终止标准是最大故障阈值。

第二种方法是有限差异搜索的变体，称之为受限域搜索。目标不是证明每个邻域的最优性，而是在较短的执行时间内为邻域找到最佳解决方案。因此，这种方法背后的想法是平等地研究子问题中的每个变量。

算法1描述了建议的 RDS 方法。它是一个递归函数，在每次调用中选择一个进程并调查要将所选进程分配到的D最佳计算机。分配所有进程后，它会检查当前解决方案是否优于迄今为止的最佳解决方案。

如果是这样，它将使用当前解决方案更新最佳解决方案。请注意，这是基于与LDS类似的逻辑，但不是在每次增加偏差时返回到搜索树的顶部，而是在深度搜索中首先执行其偏差。与LDS存在这种差异的原因是在搜索树顶部传播这种性质的问题的赋值的成本。

自适应邻域大小

大型邻域搜索的一个重要参数是每个邻域的大小，一个非常大的区域需要太多时间来优化，这导致对其他区域的调查不力。另一方面，太小的区域会导致陷入局部最小值。

邻里选择

为了定义在每次迭代中应放宽哪些变量，LNS方法侧重于每台机器中资源的不平衡使用。这个想法是，如果一台机器的使用不平衡，其中一个资源使用的容量比例与其他资源有很大不同，那么通过重新分配这台机器的进程，可能会实现更好的解决方案。

但是，这种启发式方法并未考虑多目标函数的所有组件。因此，交替使用基于最大机器成本的启发式方法。算法2和3显示了创建子问题的过程。

变量和值排序启发式

为了选择变量，使用众所周知的Fail First启发式方法，它只是根据最小化域大小对变量进行排序。这种启发式方法非常强大，广泛用于CP求解器。

此外，这种启发式方法还间接结合了Roadef12获胜者强调的“大流程优先”的知识，由于容量限制，较大的流程更难分配给机器，因此这些流程的可能机器领域更小。

对于值排序启发式方法，实现将流程分配给机器的最小成本的近似值。这种启发式方法在搜索树的底部具有很高的准确性，但当接近根时会失去准确性。为了从根本上缓解此问题，根据可以放置在计算机上的剩余未分配进程的数量断开了连接。

评估

实验在具有18个核心和04 GB的Ubuntu 3.4.15 LTS上运行。所有运行的运行时截止时间为每个实例5分钟。此外，由于所提出的方法具有随机分量，因此所呈现的结果是使用不同种子进行的5次运行的平均值。

实验使用了Roadef12中的三组实例，其中每组有10个实例。“A”实例集由较小的实例组成，最多有1000个进程和100台计算机。另外两组实例更复杂、更大，最多有50000个进程和5000台计算机。

结果

首先研究了邻域搜索方法，在30个实例中的一系列邻域上比较了受限域搜索（RDS）和随机重启搜索（RRS）。观察到，在总共271，219个社区中，其中一种方法设法找到了更好（和改进）的解决方案，RDS在54%的社区中找到了更好的解决方案，而RRS在46%的社区中找到了更好的解决方案。

这种行为可以通过以下事实来解释：每次在 RRS 中重新启动搜索时，算法都必须在搜索开始具有完整的解决方案或失败之前分配许多变量并传播约束，这与 RDS 相比大大增加了运行时间。科研人员最终独立测试了每种搜索方法，发现RRS 虽然性能相对较好，但与 RDS 相比，从未在实例上找到更好的解决方案。

对于CP-LNS方法，在与实验相同的机器上使用相同的实验设置运行他们的代码。其他两种方法的结果取自各自的参考文献。两者都使用了5分钟的运行截止时间，但NLS平均运行100次，而Ant-HH平均运行31次。

每个实例上每种方法的结果是根据运行的平均目标值以及与已知最佳解决方案的差距给出的。从差距来看，首先要注意的一点是，RDS-LNS 在 2/25 个实例上的平均性能与最知名解决方案的30%不到，而其中1个实例的平均性能不到17%。

结论

在本文中，提出一种新的针对机器重新分配问题的大邻域搜索方法，该方法具有新颖的域特定邻域算子，并针对子问题提出了新的搜索策略。实证评估证明了该方法在经过充分研究的问题集上的质量，从而改进了三十个实例中三个实例的最佳已知解决方案。

将结果与其他最先进的结果进行比较，证明了RDS-LNS的有效性。对子问题优化策略的进一步分析表明，与标准的随机重启策略相比，所提出的受限域搜索具有优越性。

●—<参考文献>—●

【1】Brandt，F.，Speck，J.，Völker，M.：基于约束的大型邻域搜索机器重新分配

【2】Canales，D.，Rojas-Morales，N.，Riff，M.C.：解决谷歌机器重新分配问题的最新方法的调查和分类

【3】Gavranović，H.，Buljubašić，M.：谷歌机器重新分配问题的高效本地搜索和噪声策略

【4】He， K.， Tole， K.， Ni， F.， Yuan， Y.， Liao， L.： 面向圆箱包装问题的自适应大邻域搜索

【5】Sellmann，M.，Tierney，K.：ISAC-实例特定的算法配置