An infinite server system with general packing constraints: Asymptotic optimality of a greedy randomized algorithm

We consider a service system model primarily motivated by the problem of efficient assignment of virtual machines to physical host machines in a network cloud, so that the number of occupied hosts is minimized. There are multiple input flows of different type customers, with a customer mean service time depending on its type. There is infinite number of servers. Multiple customers can be placed for service into one server, subject to general ``packing'' constraints. Service times of different customers are independent, even if served simultaneously by the same server. Each new arriving customer is placed for service immediately, either into a server already serving other customers (as long as packing constraints are not violated) or into an idle server. After a service completion, each customer leaves its server and the system. We propose an exteremely simple and easily implementable customer placement algorithm, called Greedy-Random (GRAND). We prove that a special case of this algorithm, called GRAND(aZ), where a>0 is a parameter, is asymptotically optimal, as the input flow rates grow to infinity and a goes to 0, in the sense of minimizing the total number of occupied servers in steady-state.