EUVIMEDEUVIMED entdecken
Crossref

A Skyline-Guided Bounded Tree Search Framework With Anticipative Pruning for the 2-D Strip Packing Problem With Rotations

Kun Li, Zhipeng Lü, Junwen Ding, Zhouxing Su, Qingyun Zhang

IEEE Transactions on Automation Science and Engineering · 2026 · 23 · 12174-12186

DOI: 10.1109/tase.2026.3708741 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Automation Science and Engineering, 2026. Verfasst von Kun Li und 4 weiteren Autor:innen. Die Arbeit nennt 36 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Interdisciplinary Research Program of Huazhong University of Science and Technology, Quantum Science and Technology-National Science and Technology Major Project.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The two-dimensional strip packing problem with rotations (2DSP-RF) is a fundamental NP-hard combinatorial optimization problem with wide applications in industrial production. This paper proposes a skyline-guided bounded tree search framework with anticipative pruning for efficiently solving the 2DSP-RF. First, the proposed framework tightly integrates the skyline-based layout representation with a limited-width tree search, where the skyline structure directly constrains the action space and guides the expansion of search nodes. Second, three complementary pruning mechanisms are designed to regulate the search process at different levels. Specifically, a local evaluation strategy filters low-potential placements based on skyline fitness, while two constructive pruning strategies employ greedy global and look-ahead evaluations to estimate the long-term packing potential of partial solutions. Third, a one-step forward-looking action selection strategy and an early-stopping mechanism are introduced to detect structurally inefficient expansions and terminate unproductive search branches in advance. Extensive experiments on 112 benchmark instances show that SGBTS achieves competitive or superior results compared with state-of-the-art algorithms and improves the best reported solutions for 21 instances. Ablation studies further verify the contributions of local evaluation, anticipative pruning, and adaptive search-width strategy. Note to Practitioners—This paper addresses the two-dimensional strip packing problem with rotations, which arises in practical cutting and layout tasks in industries such as metal, glass, wood, textile, and sheet-material manufacturing. In these applications, engineers need to arrange rectangular parts on a strip with fixed width while minimizing the used height or material waste. Existing constructive heuristics are usually fast but may make shortsighted placement decisions, whereas more extensive search methods can be computationally expensive for large instances. To improve this trade-off, this paper proposes a skyline-guided bounded tree search algorithm. The method uses the skyline to identify promising placement spaces, evaluates candidate rectangles with local and anticipative rules, and adaptively controls the search width under a given runtime limit. Computational results on standard benchmark instances show that the proposed method can obtain high-quality layouts within practical computation time. The algorithm is especially suitable for offline cutting-plan generation and production planning scenarios where improved material utilization is important. In real industrial deployment, additional constraints such as cutting order, machine limitations, defects, and setup costs can be incorporated as extensions of the current framework.

Förderung

  • National Natural Science Foundation of China
  • Interdisciplinary Research Program of Huazhong University of Science and Technology
  • Quantum Science and Technology-National Science and Technology Major Project

Zitieren

APA

Li, K., Lü, Z., Ding, J., Su, Z., & Zhang, Q. (2026). A Skyline-Guided Bounded Tree Search Framework With Anticipative Pruning for the 2-D Strip Packing Problem With Rotations. IEEE Transactions on Automation Science and Engineering, 23, 12174-12186. https://doi.org/10.1109/tase.2026.3708741

Vancouver

Li K, Lü Z, Ding J, Su Z, Zhang Q. A Skyline-Guided Bounded Tree Search Framework With Anticipative Pruning for the 2-D Strip Packing Problem With Rotations. IEEE Transactions on Automation Science and Engineering. 2026;23:12174-12186. doi:10.1109/tase.2026.3708741

BibTeX
@article{Li2026,
  author = {Li, Kun and Lü, Zhipeng and Ding, Junwen and Su, Zhouxing and Zhang, Qingyun},
  title = {A Skyline-Guided Bounded Tree Search Framework With Anticipative Pruning for the 2-D Strip Packing Problem With Rotations},
  journal = {IEEE Transactions on Automation Science and Engineering},
  year = {2026},
  volume = {23},
  pages = {12174--12186},
  doi = {10.1109/tase.2026.3708741}
}
Kostenlos starten →