Two-stage and one-group two-dimensional guillotine cutting problems with defects: a CP-based algorithm and ILP formulations

Abstract

We address two variants of the two-dimensional guillotine cutting problem that appear in different manufacturing settings that cut defective objects. Real-world applications include the production of flat glass in the glass industry and the cutting of wooden boards with knotholes in the furniture industry. These variants assume that there are several defects in the object, but the items cut should be defective-free; the cutting pattern is limited to two guillotine stages; and the maximum number of copies per item type in the pattern can be limited. The first variant deals with exact 2-stage patterns, while the second with exact 1-group patterns. To effectively solve these problems, we propose a Constraint Programming (CP) based algorithm as well as different Integer Linear Programming (ILP) formulations. The first presented formulations are extensions of the modelling approach of [Martin, M., E. G. Birgin, R. D. Lobato, R. Morabito, and P. Munari. 2020. “Models for the Two-Dimensional Rectangular Single Large Placement Problem with Guillotine Cuts and Constrained Pattern.” International Transactions in Operational Research 27: 767–793. doi:10.1111/itor.12703] for the case with defects, while the others are novel and more elaborate formulations based on the relative position of the items. We evaluate these three approaches with computational experiments using a set of benchmark instances from the literature. The results show that the approaches find optimal and near-optimal solutions in short processing times for several types of problem instances.

Keywords:

• Cutting and packing
• guillotine cuts
• defects
• 2-stage and 1-group patterns
• constraint programming
• iInteger linear programmingt

Acknowledgments

The authors are grateful to the four anonymous reviewers for their valuable comments and suggestions of revisions which improved the manuscript.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by National Council for Scientific and Technological Development (CNPq-Brazil) [grant number 304601/2017-9], [grant number 200745/2018-2] and the São Paulo Research Foundation (FAPESP-Brazil) [grant number 2020/00747-2], [grant number 2016/08039-1], [grant number 2016/01860-1]. This study was financed in part by Coordenação de Aperfeiçoamento de Pessoal de Nível Superior – Brasil (CAPES) – Finance Code 001. Research carried out using the computational resources of the Center for Mathematical Sciences Applied to Industry (CeMEAI) funded by FAPESP-Brazil [grant number 13/07375-0].

Notes on contributors

Mateus Martin

Mateus Martin is a postdoctoral researcher at the Federal University of São Paulo (UNIFESP), São José dos Campos, in Brazil. He received his doctoral degree in Industrial Engineering in 2019 from the Federal University of São Carlos. His main topics of interest are operations research, cutting and packing problems, and production systems.

Reinaldo Morabito

Reinaldo Morabito is a professor at the Production Engineering Department of the Federal University of São Carlos, in Brazil. He earned a B.S. in Civil Engineering from State University of Campinas, a M.Sc. in Computer Science and Computational Mathematics and a Ph.D. in Transportation Engineering, both from University of Sao Paulo, Brazil. He was a visiting scholar at the Sloan School of Management, M.I.T., Cambridge, MA. Prof. Morabito has coordinated many grants from funding agencies and has developed applied projects with several companies in Brazil, with a focus on Operations Research, Service and Operations Management, Production and Logistics Planning and Control. His research interests include cutting and packing problems, lot sizing and scheduling problems, queueing networks applied to manufacturing systems, probabilistic location problems, and logistics and transportation planning including vehicle routing problems. Additionally, he has worked on combinatorial optimisation, stochastic programming and robust optimisation.

Pedro Munari

Pedro Munari is a professor at the Production Engineering Department of the Federal University of São Carlos, in Brazil. He received his M.Sc. and Ph.D. in Computer Science and Computational Mathematics from the University of São Paulo. He was awarded the Doctoral Prize ‘Odelar Leite Linhares’ for the best PhD dissertation, by the Brazilian Society of Applied and Computational Mathematics. Prof. Munari has coordinated many grants from funding agencies and has developed applied projects with several companies in Brazil, with a focus on Operations Research and Logistics. His research interests include exact and heuristic methods, with focus on the column generation technique, the branch-price-and-cut method, and decomposition techniques for large-scale problems. Additionally, he has worked on new formulations and solution methods for challenging combinatorial optimisation problems, including the vehicle routing problem and the cutting/packing problems.