Given a set of jobs (or items), each of which being 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 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 and exact approaches for the problem under consideration and analyze their theoretical properties and computational behavior. As a first main contribution, we suggest a new best-cost based heuristic showing convincing results in a wide variety of numerical test. In terms of exact approaches, we propose some improvements for the ILP models 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.
Citation
Preprint MATH-NM-01-2023, Technische Universität Dresden