Virtual Machine (VM) migration is a critical technology for cloud management tasksKey use cases for VM migration are for server consolidation, server failure and load balancing. Many studies have now appeared on the design of VM migration algorithms, and most of them propose heuristics, advertising their real time scalability requirement. 

However, very few authors have investigated the quality of the solutions output by their heuristics, while it is not necessarily difficult to conceive tools in order to assess the effectiveness of a heuristic. We propose a new optimization model, which not only guarantees the finding of the VM migration with the smallest makespan (i.e., total duration of the migration), but also the migration of the largest possible number of VMs in the case of deadlocks. It allows the solution of fairly large data instances, and therefore can be used to assess the quality of heuristic solutions. 

Results show that our sequence-based model is very efficient, especially when no intermediate migrations are required, and can solve instances with up to 100 servers and 500 VMs (i.e., an average server load up to 60%) in less than a few seconds. For more difficult data instances, the newly proposed model can find in less than 30 minutes the exact solution for up to 500 servers initially loaded at 80% and for more than 2,000 VMs to migrate. Finally, we show that very few VM migration instances require the use of intermediate migrations in order to obtain a minimal makespan migration, even when servers are highly loaded.