On-demand service activation and deactivation has made private cloud a platform of choice for enterprises. Private clouds allow end users to request virtual machines along with a lease period, during which the virtual machine will be utilized. Automatic deactivation of virtual machines due to the expiry of the lease leads to fragmentation of the cloud; a large number of physical servers become operational with low utilization as virtual machines have been deactivated. To optimize the use of resources, clouds would need to periodically 'de-fragment' the cloud, leading to performance implications. In this work, we propose a service deactivation aware placement methodology, SDAP, which places virtual machines in a way that minimizes the cost of de-fragmentation in the cloud. Coupled with SDAP, we also propose a low cost de-fragmentation methodology, Defrag, to periodically consolidate the cloud. Using request traces from a live production cloud, we show that SDAP and Defrag can ensure high utilization in the cloud without expensive de-fragmentation costs. © 2011 IFIP.