With the advent of the Software-as-a-Service (SaaS) deployment model, managing operational costs becomes more and more important for providers of hosted software. The cost for hosting and providing a service is directly proportional to the operational margin that can be achieved when running a SaaS business. Possible avenues for reducing operational costs are consolidation (i.e. co-locating multiple customers onto the same server) and automation of cluster management (i.e. migration of customers between servers, automatic replication for performance or high availability). In this paper, the authors propose the formalization for the problem of assigning \"Tenants\" (i.e. the customers) to servers of an on-demand database cluster.