Abstract:
For the two-dimensional rectangular strip packing problem, the objective is to minimize the emission height of the fixed-width strip, thereby enhancing the space utilization and loading efficiency in manufacturing and logistics processes. A hyper-heuristic algorithm integrating the best-fit skyline method with adaptive multi-operators is proposed. First, multiple sorting strategies combined with the best-fit skyline heuristic are employed to rapidly generate high-quality initial solutions. Subsequently, an acceptance criterion based on the Metropolis principle is introduced, and eleven global and local perturbation operators are designed. These operators are dynamically scheduled via adaptive weights to achieve a balance between global exploration and local exploitation. The results indicate that in the Hopper C-class benchmark instances, the proposed algorithm achieves superior packing height in seven instances, reducing the packing height of instance C5P3 from 96 to 91 compared to the benchmark algorithms. On the real-world industrial dataset, the packing height is reduced from 9,567 mm to 9,445 mm, with a total decrease of 122 mm. In another dataset of rectangular items, the algorithm achieves an average packing height of 2,666 mm, which is 58 mm lower than the 2,724 mm achieved by the comparison algorithm. The finding suggest that the proposed method significantly improves the solving accuracy and robustness of 2D strip packing with a hyper-heuristic algorithm framework and an efficient operator scheduling mechanism, and provides a practical technical route and theoretical support for efficient and compact loading in complex production environments.