Examples provide two-tiered scheduling within a cluster. A coarse-grained analysis is performed on a candidate set of hosts to select a host for a virtual computing instance based on optimization of at least one resource. A host is selected based on the analysis results. The identified virtual computing instance is placed on the selected host. A fine-grained analysis is performed on a set of communication graphs for a plurality of virtual computing instances to generate a set of penalty scores. A set of communicating virtual computing instances are selected based on the set of penalty scores. A first virtual computing instance from a first host is relocated to a second host to minimize a distance between the first virtual computing instance and a second virtual computing instance. Relocating the first virtual computing instance reduces at least one penalty score for the set of communicating virtual computing instances.