Infrastructure-as-a-Service (IaaS) cloud providers often combine different hardware components in an attempt to form a single infrastructure. This single infrastructure hides any underlying heterogeneity and complexity of the physical layer. Given a non-homogeneous hardware infrastructure, assigning VMs to physical machines (PMs) becomes a particularly challenging task. VM  placement decisions have to take into account the operational conditions of the cloud (e.g., current PM load) and load balancing prospects through VM migrations. In this work, we propose a service realizing a two-phase VM-to-PM  placement scheme. In the first phase, we identify a promising group of PMs, termed Cohort, among the many choices that might be available; such a Cohort hosts the virtual infrastructure of the user request. In the second phase, we determine the final VM-to-PM mapping considering all low-level constraints arising from the particular user requests and special characteristics of the selected Cohort. Our evaluation shows that in large non-homogeneous physical  infrastructures, we significantly reduce the VM placement plan production time and improve plan quality.