Systems and methods for optimizing a virtual machine cluster. An example method may comprise receiving, by a processing device, an information characterizing a virtual machine cluster, the information comprising at least one of: values of one or more cluster configuration parameters, values of one or more cluster state parameters, or values of one or more user request parameters; and producing, in view of the received information, an ordered list of cluster configuration operations to be performed on virtual machines of the virtual machine cluster, the cluster configuration operations designed to yield a resulting configuration of the virtual machine cluster, wherein the resulting configuration is characterized by a quasi-optimal configuration score among configuration scores of two or more candidate configurations, the configuration score determined by applying one or more virtual machine scheduling policy rules to parameters of a candidate configuration.