Cloud data centers consume an enormous amount of energy. Virtual Machine (VM) migration technology can be applied to reduce energy consumption by consolidating VMs onto the minimal number of servers and turn idle servers into power-saving modes. While most existing energy models consider mainly computing energy, an enhanced energy consumption model is formulated, which includes energy consumption for computation, for servers to switch from standby to active modes, and for communication during VM migrations. Next, two new dynamic VM migration algorithms are proposed. They apply a local regression method to predict potentially over-utilized servers, and the 0–1 knapsack dynamic programming to find the best-fit combination of VMs for migration. The time complexity of these algorithms is analyzed, which indicates that they are highly scalable. Performance is evaluated and compared with existing algorithms. The two new heuristics have significantly reduced the number of VM migration, the number of rebooted servers, and energy consumption. Furthermore, one of them has achieved the least overall SLA violations. We believe that the new energy formulation and the two new heuristics contribute significantly towards achieving green cloud computing.