Methods, apparatus, and computer readable media with executable instructions stored thereon for virtual machine placement are provided. A user's demands on execution of a number of tasks, each task including a demand trace, can be defined as Service Level Agreement (SLA) information, including one or more Class of Service (CoS) levels defined by a Base Resource Entitlement (BRE) criteria and a Reserved Resource Entitlement (RRE) criteria (222). A highest CoS level of the one or more CoS levels can be selected (224) and the tasks within the Cos level can be load-balanced across a pool of servers (226). At least a portion of the RRE criteria can be removed from the demand trace of the selected CoS level (228). The selecting, load-balancing, and removing steps can be repeated until there are no more CoS levels (230).