Integer linear programming formulations and heuristic solution approaches for busy time minimization in temporal bin packing

Abstract Given a set of jobs (or items), each of which is characterized by its resource demand and its lifespan, and a sufficiently large number of identical servers (or bins), the busy time minimization problem (BTMP) requires to find a feasible schedule (i.e., a jobs-to-servers assignment) having minimum overall power-on time. Although being linked to the field of temporal bin packing, BTMP represents an independent branch of research. Typically, such considerations (and generalizations of it) are very important in data center workload management to keep operational costs (e.g., caused by energy consumption) low. Hence, finding efficient and powerful solution techniques for BTMP is a relevant topic in cutting and packing, both from a theoretical and practical point of view. In this article, we give an overview of heuristic methods and integer linear programming (ILP) formulations for the problem under consideration and analyze their theoretical properties and computational behavior. At first, we study a best-cost heuristic showing convincing results in a wide variety of numerical tests, including real-world instances. In terms of ILP models, we propose some improvements for the approaches from the literature and establish a new combinatorial flow-based formulation. Based on extensive numerical tests with differently-characterized benchmark sets, the flow model is shown (i) to improve the state-of-the-art approach for general instances, and (ii) to be competitive with a matching formulation tailored for a special case.