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.