Comparative study between exact and metaheuristic approaches for virtual machine placement process as knapsack problem

In cloud computing, the virtual machine placement is a critical process which aims to identify the most appropriate physical machine to host the virtual machine. It has a significant impact on the performance, resource usage and energy consumption of the datacenters. In order to reduce the number of active physical machines in a datacenter, several virtual machine placement schemes have already been designed and proposed. This study investigates how do four different methods compare to each other in terms of accuracy and efficiency for solving the virtual machine placement as a knapsack problem. A new approach has been adopted which focuses on maximizing the use of a server's central processing unit resource considering a certain capacity threshold. The compared methods are classified; two belong to the category of the exact methods, i.e., branch and bound and dynamic programming, while the other two represent the approximate approach, i.e., genetic algorithm and ant colony optimization algorithm. Experimental results show that the metaheuristic ant colony optimization algorithm outperforms the other three algorithms in terms of efficiency.