Analysis of The Relationship Between Characteristics and Hardness of Strip Packing Problem Instances
Keywords:Strip Packing, Characterization, Instance Analysis, Combinatorial problem
The Two-Dimensional Strip Packing Problem (SPP) is an NP-Hard problem where a list of rectangular objects must be accommodated in a container to minimize the objects' total height while avoiding overlapping. It is common to use meta-heuristic algorithms to solve this problem, which produces near-optimal solutions in a reasonable time. In this paper, we analyze several characteristics of SPP instances, looking for features that define their hardness. For further development of new algorithms that make use of this knowledge.