  Motivated by current trends in cloud computing, we study a version of the
generalized assignment problem where a set of virtual processors has to be
implemented by a set of identical processors. For literature consistency, we
say that a set of virtual machines (VMs) is assigned to a set of physical
machines (PMs). The optimization criteria is to minimize the power consumed by
all the PMs. We term the problem Virtual Machine Assignment (VMA). Crucial
differences with previous work include a variable number of PMs, that each VM
must be assigned to exactly one PM (i.e., VMs cannot be implemented
fractionally), and a minimum power consumption for each active PM. Such
infrastructure may be strictly constrained in the number of PMs or in the PMs'
capacity, depending on how costly (in terms of power consumption) is to add a
new PM to the system or to heavily load some of the existing PMs. Low usage or
ample budget yields models where PM capacity and/or the number of PMs may be
assumed unbounded for all practical purposes. We study 4 VMA problems depending
on whether the capacity or the number of PMs is bounded or not. Specifically,
we study hardness and online competitiveness for a variety of cases. To the
best of our knowledge, this is the first comprehensive study of the VMA problem
for this cost function.
