Order And Static Stability Into The Strip Packing Problem

This paper investigates the two-dimensional strip packing problem considering the case in which items should be arranged to form a physically stable packing satisfying a predefined item unloading order from the top of the strip. The packing stability analysis is based on conditions for the static equilibrium of rigid bodies, differing from others strategies which are based on area and percentage of support. We consider an integer linear programming model for the strip packing problem with the order constraint, and a cutting plane algorithm to handle stability, leading to a branch-and-cut approach. We also present two heuristics: the first is based on a stack building algorithm; and, the last is a slight modification of the branch-and-cut approach. The computational experiments show that the branch-and-cut model can handle small and medium-sized instances, whereas the heuristics found almost optimal solutions quickly for several instances. With the combination of heuristics and the branch-and-cut algorithm, many instances are solved to near optimality in a few seconds. © 2014 Springer Science+Business Media New York