The Temporal Bin Packing Problem: An Application to Workload Management in Data Centres

摘要

This paper formalises a packing problem that emerges as a core sub-problem for managing workload consolidation in data centres. As a generalisation of the Bin Packing (BP) problem, it considers a set of tasks (items) to be assigned to a set of machines (bins) under capacity constraints (CPU usage) on each machine. Unlike classic BP settings, items have a lifespan. We define the cost of using a bin as the product of the bin's capacity and the time for which it is used. This problem will be referred to as the Temporal Bin Packing problem (TBP). We formalise the problem and present optimisation models using Mixed Integer Programming (MIP) and Constraint Programming (CP) for two contrasting but equivalent perspectives on the problem. The Packing model (PA) extends traditional BP models while the Temporal model (TP) explicitly models time with a sequence of packing problems. In addition, symmetry breaking techniques are developed. Finally, we introduce both a lower bound and an upper bound on the objective function. Our empirical results suggest that the TBP is a rather challenging problem for complete solvers to prove optimality. While breaking symmetry considerably reduces the computational effort for both PA and TP models, the Packing model using CP should be considered for larger instances.