Bin packing with thresholds: mathematical models and theoretical results

We present a new variant of one-dimensional bin packing, called the bin packing with thresholds problem. In this scenario, any item is equipped with a size and a threshold, and packing an item into a bin is possible if and only if the remaining capacity is larger than both these item-specific parameters. Thus, the feasibility of a subset of items typically depends on the packing order. This problem originates from a joint production/maintenance scheduling application in which processing jobs deteriorate the condition of the machine, meaning that the threshold constraint represents requirements on the machine’s condition to process a job. In this article, this novel variant of bin packing is investigated from a theoretical and numerical point of view. First, some important structural properties of an optimal solution are derived. Based on these observations, three integer linear programming (ILP) formulations are presented: a basic assignment model, an exponential-size pattern-based approach, and a pseudo-polynomial arcflow formulation. For these approaches, relations between the associated LP bounds are established mathematically. Finally, all three formulations are compared based on extensive numerical experiments involving differently characterized benchmark sets.