The constrained two-dimensional guillotine cutting problem with defects: an ILP formulation, a Benders decomposition and a CP-based algorithm

Abstract

This paper addresses a variant of two-dimensional cutting problems in which rectangular small pieces are obtained by cutting a rectangular object through guillotine cuts. The characteristics of this variant are (i) the object contains some defects, and the items cut must be defective-free; (ii) there is an upper bound on the number of times an item type may appear in the cutting pattern; (iii) the number of guillotine stages is not restricted. This problem commonly arises in industrial settings that deal with defective materials, e.g. either by intrinsic characteristics of the object as in the cutting of wooden boards with knotholes in the wood industry, or by the manufacturing process as in the production of flat glass in the glass industry. We propose a compact integer linear programming (ILP) model for this problem based on the discretisation of the defective object. As solution methods for the problem, we develop a Benders decomposition algorithm and a constraint-programming (CP) based algorithm. We evaluate these approaches through computational experiments, using benchmark instances from the literature. The results show that the methods are effective on different types of instances and can find optimal solutions even for instances with dimensions close to real-size.

Keywords:

• two-dimensional cutting
• defects
• guillotine cuts
• integer linear programming
• Benders decomposition
• constraint programming

Acknowledgments

We also would like to thank Professors Dr José Fernando Gonçalves and Dr Gerhard Wäscher for sharing the benchmark instances.

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

Mateus Martin  http://orcid.org/0000-0002-6722-7571

Pedro H.D.B. Hokama  http://orcid.org/0000-0002-3734-7679

Reinaldo Morabito  http://orcid.org/0000-0002-3948-305X

Pedro Munari  http://orcid.org/0000-0001-5929-593X

Additional information

Funding

The authors would like to thank the Sao Paulo Research Foundation Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) [grant numbers 16/08039-1, 16/11082-6, 16/01860-1, 13/07375-0]. This study was financed in part by Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) [grant number 435617/2018-4] and the 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 (grant 2013/07375-0).