An Approximation Scheme for a One-Dimensional Bin Packing Problem with Shelf Divisions

Given bins of size B, non-negative values d and ∆, and a list L of items, each item e ∈ L with size se and class ce, we define a shelf as a subset of items packed inside a bin with total items size at most ∆ such that all items in this shelf have the same class. Two subsequent shelves must be separated by a shelf divisor of size d. The size of a shelf is the total size of its items plus the size of the shelf divisor. The Class Constrained Shelf Bin Packing Problem (CCSBP) consists to pack the items of L into the minimum number of bins, such that, the items are divided into shelves and the total size of the shelves in a bin is at most B. We present an asymptotic approximation scheme for the CCSBP problem where the number of different classes is bounded by a constant C. To our knowledge, this is the first approximation result where shelves of non-null size are used in packing problems