Upper Bounds for Heuristic Approaches to the Strip Packing Problem

We present an algorithm for the two-dimensional strip packing problem (SPP) that improves the packing of the FFDH heuristic, and we state theoretical results of this algorithm. We also present an implementation of the FFDH heuristic for the three-dimensional case which is used to construct the COMB-3D heuristic with absolute worst-case performance ratio of 5. We also show, that this heuristic has absolute worst-case performance ratio of at most 4.25 for the z-oriented three-dimensional SPP. Based on this heuristic, we derive a general upper bound for the optimal height which depends on the continuous and the maximum height lower bound. We prove that the combination of both lower bounds also has an absolute worst-case performance ratio of at most 5 for the standard three-dimensional SPP. We also show that the layer-relaxation has a worst-case performance ratio of at most 4.25 for the z-oriented three-dimensional SPP.