用于虚拟机安置问题的快速启发式算法

梁建斌

（广东工业大学，广州510006）

0 引言

云计算是分布式计算的一种特殊形式［1］，它可以按需访问可配置的计算资源共享池，如网络、服务器、存储和服务［2］。它通过最少的管理工作或者与最少的服务进行快速配置和发布［3］，是网格计算、并行计算和分布式计算的商业实现［4］。虚拟化技术提供云服务的技术支持，所有硬件资源经过虚拟化成为统一的资源［5］。虚拟机根据客户应用和所需硬件资源（如CPU、RAM和ROM等）创建，然后托管到服务器上运行［6］。

随着客户对计算能力的需求不断增长，促使云服务提供商部署越来越多的数据中心。用于服务器以及冷却服务器的设备能源成本显著增加，甚至已经超过硬件的购置成本［7］。云数据中心的能源相关成本达到运营总成本的一半［8］。因此，数据中心的生命周期成本通常由能耗决定［9］。目前，数据中心的资源使用与能源消耗比例并不高。即使服务器的CPU使用率只有10%，仍消耗服务器能耗峰值的50%以上的能源［10］。虚拟化技术允许一台服务器上同时让几个虚拟机分享硬件资源，与Xen、VMware和Hyper-V一样，允许将物理资源作为虚拟机进行共享与调配［11］，使得虚拟机整合变得可行。

虚拟机整合可以降低能源消耗，因此虚拟机安置问题（Virtual Machine Placement，VMP）被提出，一个寻求在服务器上获得虚拟机最佳部署的问题［12－13］。有效的分配有助于通过降低运行主机的操作成本来实现经济效益的最大化［14］。VMP是NP难问题［15］，计算难度大，且需要尽可能少的运算时间。过去的研究中，线性规划是VMP的最早解决方式［16－17］。线性规划简单，且确保获得最优解。但是随着问题规模增大，计算时间将不可接受。启发式算法被应用解决VMP［18］，然而启发式算法方法简单，计算时间短，但容易陷入局部最优。使用群体算法解决VMP，如蚁群系统、遗传算法（Genetic Algorithm，GA）［19］和 粒 子 群 优 化（Particle Swarm Optimization，PSO）［20］，不仅避免陷入局部最优，也能在可控时间内得到高质量解。然而，目前群体算法的运算时间明显过长。虽然启发式算法具有陷入局部最优的风险，如果克服了这个缺点，可以在更短的时间内获得可行解。本文提出一种避免局部最优解的启发式算法——强插算法。

本文的其余部分如下：第1部分回顾VMP的相关研究；第2部分概述VMP的模型和强插算法的算法原理；第3部分描述强插算法的具体步骤和流程；第4部分分别使用强插算法，RGGA（Reordering Grouping Genetic Algorithm）［19］和OMEACS（Order Exchange and Migration Ant Colony System）［21］在不同的环境下实验并对数据进行比较和分析；第5部分给出结论。

1 相关工作

线性规划是最早用于解决虚拟机整合问题的算法［22］。FFD（First-Fit Decreasing）是背包问题中简单且结果可靠的算法。BISON（Bin Packing Solution Procedure）算法［23］首先对所有背包采用FFD策略，然后执行分支与绑定的步骤。MBS（Minimal Bin Slack）［24］以背包为主，从物品中找到最适合当前背包的组合。Wu等人［25］提出了一种基于模拟退火的局部搜索算法。Murtazaev等人提出了结合First-Fit和Best Fit算法的SERCON方法，同时考虑最小化服务器和发生迁移的虚拟机数量［26］。Zhu等人［27］同时考虑CPU、内存和网络带宽因素，设计不同的算法，最大限度地降低能耗。Lago等人［28］同时考虑了服务器的硬件和带宽，提出一种在异构环境下调度虚拟机的启发式算法。

进化算法因为在VMP中的优异表现而得到了发展［29］。VMP可被视作背包问题［19］，David Wilcox等人将FFD应用到GGA（Grouping Genetic Algorithm）中，并提供了可靠的交叉算子，从而提出RGGA算法。Ibrahim等人［30］在考虑响应时间的前提下，提出了一种自适应遗传算法。Mi等人［31］使用GA同时优化资源使用率和减少能源消耗问题，多目标模型开始出现，一个改良的GA［32］使用了模糊多目标评价函数来优化VMP。Wang等人［33］提出了同时考虑最大化资源使用率，均衡多维资源的使用率和减少应用交流成本的优化模型，并使用GA进行解决。Raju等人［34］提出了EAMOCA（Energy-Aware Multi-Objective Chiropteran Algorithm）算法，其目的是在最大化资源利用率的同时最小化执行时间和能耗。Li等人［35］考虑了硬盘资源的上限和下限，将改进的PSO应用到VMP中，避免陷入局部最优。Wan等人［36］提出了一种同时考虑虚拟机热／冷启动和热／冷关闭的云计算资源分析模型，得到云平台的性能指标，并建立了一个多目标优化模型对云平台的性能和成本进行优化。

2 背景

2.1 VMP

VMP目的是使用尽可能少的服务器容纳所有的虚拟机。理想状态下大部分服务器满载。问题定义如下：

假设存在N个虚拟机（以下简称虚拟机）与M个服务器（以下简称服务器）。V＝｛v1，v2，...vi，...，vN｝代表虚拟机集合，vi＝｛vci，vri｝代表虚拟机vi需求的CPU与RAM资源。P＝｛p1，p2，...pi，...，pM｝代表服务器集合。pj＝｛pcj，prj｝代表服务器pj的CPU与RAM资源上限。B＝｛b1，b2，...，bi，...，bN｝代表安置方案，i∈［1，N］代表虚拟机编号，bi∈［1，N］表示将vi放入对应编号的服务器中。VMP问题如下描述：

式（2）中yj是服务器是否空闲的标志。如果yj＝0，代表该服务器空闲。式（3）与（4）分别统计每台服务器中虚拟机占用CPU和RAM的总和，并要求各项资源的使用不能超出该服务器对应资源的上限。

2.2 First-Fit算法

用于VMP的First-Fit算法最早由文献［5］提出。First-Fit算法难以得到VMP的最优解，但是时间复杂度低，且步骤简单，用作强插算法的评价函数。

2.3 强插算法

在虚拟机的安置过程中会出现一个趋势：各项资源需求小的虚拟机（以下简称小虚拟机）大量存在于高负载服务器中，各项资源需求量大的虚拟机（以下简称大虚拟机）大量存在于低负载服务器中。这个趋势导致安置方案过早收敛于局部最优解。本文提出的强插算法的设计思路是避免这种趋势的发生。也就是使用低负载服务器中的大虚拟机交换高负载服务器中若干个小虚拟机，从而打破安置方案的原有结构，而小虚拟机也尽可能不交换到低负载服务器中，进一步降低低负载服务器的负载。当存在若干个服务器负载足够低，可进行虚拟机再安置，减少服务器数量。

强插算法需要解决的问题是：已知大虚拟机和服务器集合，如何从服务器集合中找到含有最合适用作交换的小虚拟机集合的服务器？该问题可被拆分为两个子问题：

（1）交换后，服务器负载率的影响是否最低？

（2）交换的小虚拟机集合对其他服务器的提升效果是否最好？

强插算法的解决方案如下：

（1）从各个服务器中选出一批与大虚拟机需求比较接近的小虚拟机集合，并限制在对服务器负载率影响在不大的范围里。为此算法使用了强插算子确保选出的小虚拟机集合的需求总和与大虚拟机的需求尽可能接近。

（2）从选出的所有集合中选出一个提升其他服务器负载表现最好的集合。为此算法使用了再填充算子，让所有小虚拟机集合都尝试安置到其他高负载服务器上。

强插算法每次迭代都需要先对服务器筛选。因此强插算法分为三个部分：选举算子、变异算子和调整算子。

3 算法流程

3.1 初始化和参数设置

强插算法的参数会随着计算规模增大而增大，因此需要对问题先执行一次First-Fit算法，得到初始的安置方案B。B的服务器数量与最优安置方案所需要的服务器数量处于同一数量级，用于估计计算规模。根据Pub计算：

其中pNum和wNum分别是候选服务器集合规模和恶劣服务器集合的规模。

3.2 选举算子

选举算子分为三步：评价，选出恶劣服务器集合，和选出候选服务器集合。首先每台服务器统计各项资源使用情况，然后根据以下公式得到评价值：

其中pcj和prj分别是服务器的CPU和RAM资源上限，pccj和pcrj分别是服务器当前CPU和RAM的使用情况，ac和ar是服务器CPU资源上限和RAM资源上限的比值。当服务器CPU资源上限是RAM资源上限两倍时，ac＝1，ar＝2。服务器的负载率越高，评价值越高。选取评价值最低的wNum台服务器构成恶劣服务器集合。

候选服务器集合则由两部分服务器构成：随机服务器集合和较差服务器集合。较差服务器集合是除了恶劣服务器集合以外，负载率最差的服务器集合。由于负载率较低，在再填充算子中可以被安置入更多小虚拟机。随机服务器集合是从未被选取的其他服务器中随机选取。其中，较差服务器集合规模worsePMsSize

和随机服务器集合规模randomPMsSize分别如下：

其中，ω是较差服务器占比。

3.3 变异算子

变异算子由强插算子和再填充算子组成。在一次变异中，需要依次选取恶劣服务器集合中的每一个大虚拟机执行强插算子，结果交由再填充算子进一步处理，决定最终的交换方案。

强插算子试图将恶劣服务器集合中的所有大虚拟机都交换到候选服务器集合中，对负载率影响尽可能小的情况下改变候选服务器中的虚拟机结构。

为了交换的大虚拟机和小虚拟机集合的需求尽可能接近，在强插算子中，选中的大虚拟机需要对所有候选服务器进行一次强插算子，得到若干个候选的小虚拟机集合。大虚拟机和所有小虚拟机集合将通过再填充算子进一步处理。强插算子分为4个步骤：排序、产生计算序列、评价和筛选。

排序是以大虚拟机为对照，将候选服务器中的虚拟机进行分类和排序。排序的顺序为：A类虚拟机、B类虚拟机、C类虚拟机和D类虚拟机。其中，A类虚拟机的各项资源需求都大于等于大虚拟机；B类虚拟机则具有一项资源需求大于大虚拟机，其余资源需求小于大虚拟机；C类虚拟机的资源需求都小于大虚拟机，但至少一项资源需求不低于大虚拟机该项资源需求的一半；D类虚拟机的资源需求都小于大虚拟机该项资源需求的一半。

产生计算序列将产生等同于B、C、D类虚拟机数量总和的计算序列。A类虚拟机不会产生计算序列，因为A类虚拟机各项资源需求都大于大虚拟机，如果发生交换，只让服务器的各项资源使用率下降，且难以再填充到其他服务器。每个计算序列都以P排序的结果副本为初始序列，选取B、C、D类虚拟机中的未被选取过的一个虚拟机，从原来的位置中取出并放到序列的末尾，最后将大虚拟机放到序列的首位。形成一条新的计算序列。

对每一条计算序列使用First-Fit算子进行计算并根据以下公式进行评价：

其中pccsj和pcrsj分别是大虚拟机交换到服务器后，服务器的CPU和RAM使用情况。适应度越少，说明交换方案在强插算子中越合理。如果交换后，服务器的各项资源使用情况都上升，说明本次交换可以单纯地提升服务器的负载率，因此适应度设置为0。否则使用服务器的资源空闲权重和作为评价值。

每条计算序列在经过First-Fit算子后，除了适应度外，还获得了在First-Fit算子中无法被安置入服务器的虚拟机，它们构成了小虚拟机集合。小虚拟机集合将在大虚拟机对所有候选服务器都进行强插算子后进行汇总，并将交给再填充算子进行进一步的处理。

变异算子的最后，最终交换方案中剩余的小虚拟机集合将被安置到恶劣服务器中。为了更进一步降低恶劣服务器集合的总负载，再填充算子将尽可能地将虚拟机保留在候选服务器集合中。为了找到保留效果最好的小虚拟机集合，需要对强插算子得到的所有小虚拟机集合都执行一次再填充算子。再填充算子具有两个步骤：排序和再填充与评价。

再填充算子通过提升候选服务器集合的总负载来降低恶劣服务器集合的总负载。一方面，资源需求量更大的虚拟机更难被安置入服务器。另一方面，将资源需求量大的虚拟机安置入候选服务器集合更符合再填充算子的目标。再填充算子需要先从资源需求量大的虚拟机开始执行，因此需要先对每个小虚拟机集合根据资源需求总量进行排序。资源需求总量的公式如下：

资源需求总量越大的虚拟机在排序后的序列中的位置越靠前。然后，根据排序后的序列执行再填充。首先，获得除了该小虚拟机集合对应的服务器以外的所有候选服务器当前资源使用情况的副本。接着，从序列依次取出虚拟机，遍历副本中的每个服务器。如果虚拟机可以被安置到该服务器中，那么更新副本中该服务器的资源使用情况，并从序列中去除掉该虚拟机。最后，计算序列的适应度。序列中可能存在无法被安置的虚拟机，而序列的适应度即序列中剩余虚拟机的资源需求总量。剩余的虚拟机集合和适应度值是该小虚拟机集合在再填充算子中的结果。

选出适应度最低的小虚拟机集合，它以及所对应的服务器编号和大虚拟机就是大虚拟机最终的交换方案。剩余的虚拟机集合将被随机安置到恶劣服务器集合中的任意服务器中，且不会再参与变异算子。

3.4 调整算子

变异算子降低了恶劣服务器集合的总负载，但同时也带来了新的问题：

（1）降低了总负载，但是不能降低服务器数量。

（2）由于变异算子的最后，将虚拟机随机安置到恶劣服务器，可能会出现超载的情况。

问题1中，普遍的情况是存在若干低负载服务器，可通过重新安置其中的虚拟机来降低服务器的使用数量。问题2中，可以将重新安置超载服务器和低负载服务器中的虚拟机消除超载现象。因此，问题1和2可以合并为一个比VMP规模小的子问题。

子问题的复杂度低于VMP。由于出现问题的服务器都是恶劣服务器，经历了变异算子，恶劣服务器集合的总负载很有可能降低了。原有的恶劣服务器集合安置已经是合理的安置方案，再得到一个合理的安置方案并不困难。另外，变异算子已经占用了大量运算时间，算法需要采用时间更短的调整算子来调整恶劣服务器集合中的虚拟机。调整算子分为两个步骤：挑选服务器和remove算子。

首先，根据负载情况从所有服务器中选出符合以下条件的服务器：

其中，是负载系数。当一项资源使用率低于μ时，认为服务器的负载率过低。负载率过低的服务器和超载服务器将通过remove算子作进一步的处理。

在RGGA算法中，变异算子由swap算子，move算子和remove算子组成，swap算子和move算子提供的有效变异最多。但这两个算子只能作用于两个服务器之间，不适合多个服务器同时进行虚拟机整合。因此，强插算法采用remove算子作为调整算子。

为了提高remove算子的效率，调整算子将重复执行a次，选取服务器数量最少的安置方案作为调整算子的最终方案。

3.5 总流程

算法的总流程如图1所示，具体步骤如下。

图1 总体流程图

（1）使用First-Fit算法，获得初始安置方案B和Pub，根据Pub设置pNum和wNum。设置t＝0和Tmax。

（2）计算各个服务器的资源使用情况，并根据资源使用情况对所有服务器进行排序。

（3）使用选举算子分别选出候选服务器集合和恶劣服务器集合。

（4）逐一选取恶劣服务器集合中的所有虚拟机，使用强插算子获得该虚拟机对应的交换方案。并执行交换方案，更新候选服务器集合中的虚拟机构成。

（5）选出超载和低负载服务器，使用调整算子获得一个合理的再安置方案。

（6）如果t＝Tmax，算法结束。否则，设置t＝t＋1并跳到步骤（2）。

4 实验部分

实验部分将测试强插算法的性能。所有算法均使用Java实现，硬件环境CPU型号Intel Core i5－7550，8G内存。包含4种不同环境下的实验：TestA1和TestA2是同构服务器环境下不同虚拟机类型的两个测试，TestB和TestC分别在同构服务器与异构服务器的环境下瓶颈资源测试。强插算法的对比算法是使用遗传算法的RGGA和使用蚁群系统的OMEACS。强插算法的相关参数设置如下：ω＝0.4，μ＝0.99，a＝50。RGGA和OMEACS的参数值与原始论文中的一致。TestA1，TestA2和TestB中，最大迭代次数均为Tmax＝100，TestC由于异构环境更复杂，最大迭代次数均为Tmax＝1000。所有算法的最大迭代次数和FEs如表1所示。所有算法均每个实例中都独立重复执行100次，FEs和运算时间对应首次得到全局最优解所需要的FEs和运算时间。

表1 各个算法最大迭代次数和FEs

4.1 TestA大规模同构服务器测试

TestA1的实例生成方法提出于RGGA，与TestA2具有相同的特点：理想安置方案中，服务器的所有资源都被生成的虚拟机占满。TestA1具有9个实验用例。所有用例的服务器都具有500单位CPU和500单位RAM；每个虚拟机的CPU需求是位于［1，128］的随机整数，RAM需求是位于［0，100］的随机整数。TestA1的虚拟机生成方法以服务器为单位，不断生成虚拟机，直到存在虚拟机生成后，服务器某项资源不足以负载该虚拟机时，将该虚拟机的各项资源需求改为服务器剩余资源量，从而实现满载。除最后一个虚拟机外，其他虚拟机都是随机生成，因此各个虚拟机之间的资源需求差距很大。

续表

从表2看出，强插算法总能获得比其他算法更好的结果，体现了强插算法在TestA1中的稳定性。RGGA在实例A11和A15中获得与强插算法相同的最优解，但是平均值显示出结果并不稳定。OMEACS则难以获得与强插算法同等质量的解。此外，在所有实例中，强插算法首次获得最优全局最优解的时间和FEs都远低于RGGA和OMEACS。

表2 TestA1在不同虚拟机规模下的实验结果对比

TestA2的虚拟机生成方式与TestA1不同。首先确定服务器安置的虚拟机数量，按照均匀分布的方式生成虚拟机的各项资源需求。因此，TestA2的所有实例的理想安置方案中的每个服务器的托管虚拟机之间的资源需求差别不大。对比表2和表3，TestA2具有相同的服务器和更少的虚拟机，但所有算法都需要更多的运算时间和FEs，说明TestA2难度高于TestA1。从表3可见，强插算法稳定得到最高质量的安置方案。RGGA在TestA2的总体表现弱于TestA1，仅在实例TestA21获得与强插算法相同质量的安置方案，在其他实例则无法稳定。OMEACS无法获得与强插算法相同质量的安置方案，且在A21、A22、A27中过早收敛于局部最优解中。强插算法在时间复杂度上依然优秀。

表3 TestA2在不同虚拟机规模下的实验结果对比

从TestA可以看出，强插算法可以稳定得到接近于最优安置方案的方案，且首次获得最优全局最优解的时间也远低于其他算法，说明强插算法优化规则的合理性。

4.2 TestB大规模同构服务器测试

因为发展趋势，RAM的体量比CPU大，往往CPU密集型的任务导致瓶颈资源问题。TestB设置了9个不同规模的实例B1～B9测试三个算法在瓶颈资源环境下的性能。所有实例服务器均拥有16核CPU和32GB的RAM；虚拟机的CPU需求是［1，4］中的随机整数，RAM需求是［1，8］中的随机整数，所有随机整数服从均匀分布。每个虚拟机有25%几率需求4内核，同时有25%几率需求7GB或者8GB的RAM，因此CPU与RAM的使用率接近10∶9，CPU成为了瓶颈资源。TestB的虚拟机生成方法完全随机，不会提前设置需求的服务器数量，并在生成后使用以下公式对服务器数量进行估计：

其中，pci和pri分别是第i台服务器能提供的CPU和RAM资源上限，分别是该服务器上所有虚拟机需求的CPU和RAM总量。推算公式目的是以所有虚拟机需求总和的最大值来推算至少需要的服务器数量，在实际测试中，由于虚拟机需求的随机性和复杂性，需要的服务器数量可能大于这个值。

表4包含了三个算法在TestB的表现。RGGA仅在B1和B3中获得最优安置方案，OMEACS仅在B1和B2中获得最优安置方案，但是两个算法都不稳定。一方面，强插算法在所有的实例都能稳定地获得最优安置方案。另一方面，强插算法首次获得最优解所需要的运算时间和FEs远低于RGGA和OMEACS。

表4 TestB在不同虚拟机规模下的实验结果对比

4.3 TestC异构服务器环境下瓶颈资源问题

之前的测试，所有服务器都是同构服务器。TestC将在异构环境下进行测试。TestC根据目前两种主流服务器型号设置实验：s0（32核CPU和64GB的RAM）和s1（64核CPU和256GB内存）。TestC包含5个实例，s0和s1服务器的比例为1∶1。虚拟机的CPU资源需求是处于区间［1，8］的随机整数，RAM资源需求是处于［1，32］的随机整数。因此，TestC也是一个瓶颈资源场景。

表5包含了三种算法在TestC中的性能。平均值显示强插算法和RGGA的性能相近。RGGA获得所有实例中质量最好的安置方案，而强插算法在C2和C5中无法获得与RGGA相同质量的安置方案。OMEACS仅在C1中获得最优安置方案。这意味着在异构环境下，VMP问题变得更复杂，强插算法虽然表现不是最优秀，但首次获得最优全局最优解的时间和FEs仍远远低于RGGA。而RGGA虽然可以获得最优安置方案，但每次的运算结果并不稳定，导致运算时间不稳定。

表5 TestC在不同虚拟机规模下的实验结果对比

4.4 参数测试

强插算法包含三个参数：较差服务器占比系数ω，调整数量μ和校验系数a。为了研究这些参数对于安置方案质量的影响，使用TestA1对所有实例进行参数性能的评估。

首先测试较差服务器占比系数ω。在其余参数不变的情况下设置了从0.1－1.0的11个参数实验。图2在较差服务器占比系数在TestA的所有测试实例。随着ω的增加，FEs不断下降。但是运算时间经历了下降后上升，曲线大致呈现凹谷的形状。这说明当上升后，强插算子次数减少，强插算子运算时间上升，整体运算时间上升。当时ω＝0.4，运算时间达到最小值。所以，算法采用ω＝0.4。

图2 不同的较差服务器占比系数在TestA1各个实例的表现

图3是调整系数在TestA的所有测试实例。图3中，FEs大致上随着调整系数的增加而减少，运算时间大致上呈现凹谷形状。强插算法通过强插算子和调整算子优化结果，调整次数少，会使算法依赖强插算子优化结果，导致运算时间增长。调整次数多，会进无效的调整算子。因此，在a＝50时获得可接受的FEs和运算时间。

图3 不同的调整系数在TestA1各个实例的表现

图4是校验系数在TestA的所有测试实例。由于μ＝1无法获得最优安置方案，因此不予显示。大体上，Fes一致呈现下降的趋势。在TestA11-TestA14时，运算时间在μ＝0.98时获得最小值。而随着问题规模不断增加，μ＝0.99才能获得最小的运算时间。所以，强插算法采用μ＝0.99。

图4 不同的校验系数在TestA1各个实例的表现

4.5 收敛速度分析

本部分将评价强插算法的收敛性。使用TestA1为测试实例，使用强插算法，RGGA进行收敛性分析。每个算法具有100次迭代，独立重复运行100次。

图5是两个算法在TestA各个实例中的收敛曲线图。曲线中的每一个数值是算法100次运行的平均值。尽管RGGA一直在收敛，但是收敛速度过慢，甚至停留在局部最优解中，导致整体运算时间的增加。强插算法的初始化与RGGA类似，因此初始阶段与RGGA接近，但是收敛速度快于RGGA，因此最早获得质量最高的安置方案。

图5 强插算法和RGGA的收敛曲线对比

5 结语

能源消耗已经是数据中心的主要运营成本，已有的VMP算法可以获得高质量的安置方案，但是运算时间长。这促使我们提出基于启发式算法的强插算法，在更短运算时间获得合理的虚拟机安置方案，通过关闭空闲服务器最小化活动服务器数量。VMP问题是一个复杂的NP难问题，每个服务器中的虚拟机不仅作用于服务器的负载情况，更影响着其他服务器的虚拟机构成。当一个服务器中小虚拟机数量过多时，其他服务器由于缺少小虚拟机，空闲资源无法被利用，相互之间也难以进行虚拟机交换，因而负载率不高。为了解决这个现象，本文提出了强插算法。其中，强插算子将大虚拟机强行到服务器中，打乱服务器的虚拟机原有的虚拟机结构，释放其中的小虚拟机，提高其他服务器负载。由于强插算子的强随机性和明确的目的性，克服了启发式算法的早熟问题。调整算子则用于调整强插算子导致的安置方案不合理的问题。

强插算法被用于不同规模下的同构或异构服务器的测试中。结果表明强插算法在绝大部分测试用例中可以稳定获得最高质量的安置方案，且运算时间最短。即使不能获得最高质量的安置方案，结果依然相当接近。结论是，强插算法可以被视作一种高效且高速的VMP算法。