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

Mateus Martin(mateus.pmartingmail.com)
Reinaldo Morabito(morabitoufscar.br)
Pedro Munari(munaridep.ufscar.br)

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 modeling approach of Martin et al. (2020a) 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 patterns, 1-group patterns, Constraint Programming, Integer Linear Programming

Category 1: Applications -- OR and Management Sciences

Citation:

Download: [PDF]

Entry Submitted: 01/16/2021
Entry Accepted: 01/16/2021
Entry Last Modified: 01/16/2021

Modify/Update this entry