New lower bounds for the three-dimensional finite bin packing problem Original Research Article

The three-dimensional finite bin packing problem (3BP) consists of determining the minimum number of large identical three-dimensional rectangular boxes, bins, that are required for allocating without overlapping a given set of three-dimensional rectangular items. The items are allocated into a bin with their edges always parallel or orthogonal to the bin edges. The problem is strongly NP-hard and finds many practical applications. We propose new lower bounds for the problem where the items have a fixed orientation and then we extend these bounds to the more general problem where for each item the subset of rotations by 90° allowed is specified. The proposed lower bounds have been evaluated on different test problems derived from the literature. Computational results show the effectiveness of the new lower bounds.