An effective shaking procedure for 2D and 3D strip packing problems

Strip packing intends to minimise the height required for placing a set of rectangular items into a strip with infinite height. The present paper introduces a fast, yet effective shaking algorithm for the two- and three-dimensional strip packing problems, which are both NP-hard. The proposed heuristic procedure starts from an ordered item list, from which it alternates between forward and backward construction phases. The algorithm builds upon the common (deepest) bottom-left-fill algorithm, but shows significantly better results. Improvements on the solution quality of more than 9% can be observed. Moreover, applying the shaking procedure as a post processing algorithm to existing high performance heuristics also leads to improvements.