  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 types of arriving customers, where a customer's mean
service time depends on its type. There is an 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 extremely simple and easily implementable customer placement
algorithm, called Greedy-Random (GRAND). It places each arriving customer
uniformly at random into either one of the already occupied servers (subject to
packing constraints) or one of the so-called zero-servers, which are empty
servers designated to be available to new arrivals. One instance of GRAND,
called GRAND($aZ$), where $a\ge 0$ is a parameter, is such that the number of
zero-servers at any given time $t$ is $aZ(t)$, where $Z(t)$ is the current
total number of customers in the system. We prove that GRAND($aZ$) with $a>0$
is asymptotically optimal, as the customer arrival rates grow to infinity and
$a\to 0$, in the sense of minimizing the total number of occupied servers in
steady state. In addition, we study by simulations various versions of GRAND
and observe the dependence of convergence speed and steady-state performance on
the number of zero-servers.
