论文标题
虚拟机组合并问题的内核搜索算法
A Kernel Search Algorithm for Virtual Machine Consolidation Problem
论文作者
论文摘要
虚拟机组合并描述了一组目标服务器上虚拟机（VM）的重新分配过程。它可以作为混合整数线性编程问题进行配合，这被证明是NP硬性问题。在本文中，我们提出了基于硬变量固定的内核搜索（KS）启发式算法，以快速获得大规模虚拟机组合并问题（VMCP）的高质量解决方案。由于现有KS工作中的可变修复策略可能使VMCP不可行，因此我们提出的KS算法采用更有效的策略来根据相应的降低成本选择一组固定变量。 VMCP实例上的数值结果表明，我们提出的KS算法在CPU时间方面显着胜过最先进的混合整数线性编程求解器，而我们提出的可变固定策略显着提高了KS算法的效率，可以降解解决方案的质量质量。
Virtual machine consolidation describes the process of reallocation of virtual machines (VMs) on a set of target servers. It can be formulated as a mixed integer linear programming problem which is proven to be an NP-hard problem. In this paper, we propose a kernel search (KS) heuristic algorithm based on hard variable fixing to quickly obtain a high-quality solution for large-scale virtual machine consolidation problems (VMCPs). Since variable fixing strategies in existing KS works may make VMCP infeasible, our proposed KS algorithm employs a more efficient strategy to choose a set of fixed variables according to the corresponding reduced cost. Numerical results on VMCP instances demonstrate that our proposed KS algorithm significantly outperforms the state-of-the-art mixed integer linear programming solver in terms of CPU time, and our proposed strategy of variable fixing significantly improves the efficiency of the KS algorithm as well as the degradation of solution quality can be negligible.
