  Several cloud-based applications, such as cloud gaming, rent servers to
execute jobs which arrive in an online fashion. Each job has a resource demand
and must be dispatched to a cloud server which has enough resources to execute
the job, which departs after its completion. Under the `pay-as-you-go' billing
model, the server rental cost is proportional to the total time that servers
are actively running jobs. The problem of efficiently allocating a sequence of
online jobs to servers without exceeding the resource capacity of any server
while minimizing total server usage time can be modelled as a variant of the
dynamic bin packing problem (DBP), called MinUsageTime DBP.
  In this work, we initiate the study of the problem with multi-dimensional
resource demands (e.g. CPU/GPU usage, memory requirement, bandwidth usage,
etc.), called MinUsageTime Dynamic Vector Bin Packing (DVBP). We study the
competitive ratio (CR) of Any Fit packing algorithms for this problem. We show
almost-tight bounds on the CR of three specific Any Fit packing algorithms,
namely First Fit, Next Fit, and Move To Front. We prove that the CR of Move To
Front is at most $(2\mu+1)d +1$, where $\mu$ is the ratio of the max/min item
durations. For $d=1$, this significantly improves the previously known upper
bound of $6\mu+7$ (Kamali & Lopez-Ortiz, 2015). We then prove the CR of First
Fit and Next Fit are bounded by $(\mu+2)d+1$ and $2\mu d+1$, respectively.
Next, we prove a lower bound of $(\mu+1)d$ on the CR of any Any Fit packing
algorithm, an improved lower bound of $2\mu d$ for Next Fit, and a lower bound
of $2\mu$ for Move To Front in the 1-D case. All our bounds improve or match
the best-known bounds for the 1-D case. Finally, we experimentally study the
average-case performance of these algorithms on randomly generated synthetic
data, and observe that Move To Front outperforms other Any Fit packing
algorithms.
