T. Buchwald and G. Scheithauer,
Improved Performance Bounds of the COMB-3D Heuristic
for the three-dimensional Strip Packing Problem
We present new performance results for the
FFDH-3D and the COMB-3D heuristic
for the three-dimensional strip packing problem (3dSPP)
which were proposed in a preceding paper.
There was shown that the absolute worst-case performance ratio
of the COMB-3D heuristic is at most 5.
In this paper, we prove that this bound is best possible.
For the $z$-oriented 3dSPP we propose an adapted version of the FFDH-3D heuristic whose application within the COMB-3D heuristic leads to an improved absolute worst-case performance ratio of at most $4.25$.
In the case of the $z$-oriented 3dSPP with quadratic container base area this absolute worst-case performance bound can further be improved to 4.
Based on the COMB-3D heuristic
we prove a new general upper bound
for the optimal height
which depends on the continuous
and the maximum height lower bound.
We show that the combination of both lower bounds has an absolute worst-case performance ratio less than $5$ for the standard 3dSPP, and of at most 4.25 for the $z$-oriented case.
This implies that the layer-relaxation of the 3dSPP has a worst-case performance ratio of at most 4.25 for the $z$-oriented 3dSPP, too.
(Preprint MATH-NM-01-2015, TU Dresden, January 2015)