Compact integer linear programming formulations for the temporal bin packing problem with fire-ups

摘要

In this article we examine a specific version of the temporal bin packing problem (TBPP) that occurs in job-to-server scheduling. The TBPP represents a generalization of the well-known bin packing problem (BPP) with respect to an additional time dimension, and it requires to find the minimum number of bins (servers) to accommodate a given list of items (jobs) at any instant of time. In addition to this goal, recent publications suggest to also incorporate the number of fire-ups of the respective servers as an important factor in sustainable and energy-efficient overall operation. Addressing both these objectives by a weighted sum method typically increases the modeling complexity, thus leading to challenging ILP formulations, two of which have already been described in the literature. It has been shown that the parameter used to weight the two objectives strongly influences the applicability of heuristics and, therefore, the difficulty of the overall problem, so that only favorable choices can be handled so far. Even for these tailored scenarios, the current approaches already fail to compute an exact solution of many moderately-sized instances in reasonable times. For this reason, we propose various new preprocessing techniques to strengthen the LP bound and/or to reduce the numbers of variables or constraints appearing in the existing ILP formulations as well as one alternative modeling approach for the problem under consideration. Based on numerical tests with differently characterized sets of benchmark instances, the new and improved formulations are shown to lead (on average) to better performances (than compact state-of-the-art models) in terms of instances solved to optimality and computation times.