A Dynamic-Fit Heuristic Algorithm for the Rectangular Strip Packing Problem

Given a set of small rectangular pieces of different sizes and a rectangular container of fixed width and infinite length, the rectangular strip packing problem (RSPP) consists of orthogonally placing all the pieces within the container, without overlapping, such that the overall length of the packing is minimized. RSPP belongs to NP-hard problem in theory and has many industrial applications such as the composition of news, the cutting of clothing and the cutting of metal, etc. To solve the rectangular strip packing problem, a hybrid algorithm, which combines a novel heuristic algorithm—dynamic-fit heuristic algorithm (DFHA), with the genetic algorithm, is adopted. The DFHA algorithm can dynamically select the better-fit rectangle for packing, according to the width-fit first (WFF) rule, the height-fit first (HFF) rule, the placeable first (PF) rule, and the biggest-rectangle first (BRF) rule, and the evolutionary capability of genetic algorithm is used to optimize the height of the packing which is calculated by DFHA. The hybrid algorithm is tested on two sets of benchmark problems taken from the previous literature. The first set includes 21 instances and the other one includes 13 instances. The computational results show that the hybrid algorithm is more effective than the existing algorithms from the previous literature.