Combinatorial Benders' decomposition for the constrained two-dimensional non-guillotine cutting problem with defects

Abstract

This paper studies the constrained two-dimensional non-guillotine cutting problem with defects, in which a set of items of a specific size is cut from a large rectangular sheet with defective areas, with the number of each type of cut item cannot exceed a specified quantity. The objective is to maximise the total value of the cut items. We propose a decomposition approach to address the problem. The process involves decomposing the original problem into a master problem and a subproblem. The master problem is formulated as a one-dimensional contiguous bin packing problem, while the subproblem is an x-Check problem to identify a two-dimensional packing that does not lead to any overlap. The x-Check problem is effectively addressed by using an integer linear programming model. When the x-Check problem proves infeasible, cuts are added to the master problem, and the iteration is repeated until the x-Check finds a feasible solution. Furthermore, we introduce several novel techniques, including valid inequalities, preprocessing techniques, and lifting the cut methods to improve the performance of the algorithm. Extensive computational results show that our method can quickly find the optimal solution for the 5450 instances in the literature.

Keywords:

• Cutting
• packing
• defect
• decomposition algorithm
• integer linear programming

SUSTAINABLE DEVELOPMENT GOALS:

• SDG 9: Industry
• innovation andinfrastructure

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

All data created in this article is obtained via https://github.com/yao-shaowen/DataSets-of-two-dimensional-non-guillotine-cutting-problem-with-defects.git.

Additional information

Funding

This paper is supported by the Natural Science Foundation of China (Nos. 72271062, U20A6004, 52075107), the Science Fund for Distinguished Young Scholars of Guangdong Province (No. 2022B1515020076), the Province Natural Science Fund of Guangdong (No. 2021A1515012459, 2022A1515010991), and the Funding by Science and Technology Projects in Guangzhou (No. 2023A04J0407).

Notes on contributors

Shaowen Yao

Shaowen Yao received the B.S. degrees from Jinggangshan University, Ji'an, China, in 2020. He is currently pursuing the PhD degree at Guangdong University of Technology, Guangzhou, China. His current research interest includes intelligent manufacturing and optimisation algorithms.

Hao Zhang

Hao Zhang received the B.A. degree in mechanical engineering from Hunan Institute of Science and Technology, China, and the MS and PhD degree from the Guangdong University of Technology, China. His research interests include optimisation algorithms and digital twin and intelligent manufacturing.

Qiang Liu

Qiang Liu received the B.S. degree from Xi'an Ploytechnic University, Xi'an, China, the M.S. degree from the Guangdong University of Technology, Guangzhou, China, and the Ph.D. degree in mechatronics engineering from Sun Yat-sen University, Guangzhou, in 2009. He is currently a Professor at the Guangdong University of Technology. His current research interests include access control and intelligent manufacturing.

Jiewu Leng

Jiewu Leng received the Ph.D. degree in mechanical engineering from Xi'an Jiaotong University, Xi'an, China, in 2016. He is an Associate Professor with the State Key Laboratory of Precision Electronic Manufacturing Technology and Equipment, Guangdong University of Technology, Guangzhou, China. He has been a Visiting Fellow with the Department of Information Systems, City University of Hong Kong, Hong Kong, under the program of ‘Hong Kong Scholars’ since 2018. His current research interests include blockchain, digital twin, system security, and cyber-physical system.

Lijun Wei

Lijun Wei received the B.S. and M.S. degrees from Xiamen University, Xiamen, China, and the Ph.D. degree in management sciences from the City University of Hong Kong, Hong Kong, in 2013. He is currently a Professor at the Guangdong University of Technology, Guangzhou, China. His current research interests include intelligent algorithm, intelligent manufacturing, and intelligent transport system.