Virtual Machine Placement with Disk Anti-colocation Constraints Using Variable Neighborhood Search Heuristic

In a cloud computing environment, virtual machine placement (VMP) represents an important challenge to select the most suitable set of physical machines (PMs) to host a set of virtual machines (VMs). The challenge is how to find optimal or near-optimal solution effectively and efficiently especially when VMP is considered as a NP-hard problem. However, the existing algorithms have focused mostly on compute resources when provisioning VMs and ignore storage resources. Therefore, they often generate non-optimal compute and storage resources for executing users applications. To address this problem, we outline more in details the binary linear programming (BLP) model previously proposed to solve the consolidated VMP with disk anti-colocation constraint (denoted VMcP-DAC) and we solve it using a heuristic algorithm. Our approach considers a special type of disk anti-colocation requirements to prevent Input/Output (IO) performance bottleneck. We implement a variable neighborhood search based optimization heuristic (denoted VNS-H) to solve the VMcP-DAC by minimizing both the resource wastage and the operational expenditure. To the best of our knowledge, only three studies in the literature that are devoted to VMcP-DAC problem. In two of these three works, authors proposed exact algorithms that are unable to solve large scale VMcP-DAC problem instances. For this reason, in a previous work, we proposed a decomposition based method to overcome the convergence issues for only large scale problems. In the present paper, our goal is to solve VMcP-DAC problem instances suitable for both regular and large data centers. We investigate the effectiveness of the proposed VNS-H, showing that it has a better convergence characteristics and it is more computationally efficient than compared methods from the literature.