A MIP model and a biased random-key genetic algorithm based approach for a two-dimensional cutting problem with defects

Keywords Cutting; Packing; Two-dimensional; Non-guillotine; defects; BRKGA; Biased random-key genetic algorithm Highlights * A novel MIP for the problem is developed. * A novel procedure to handle defects is proposed. * A novel placement procedure within a BRKGA is used to solve the non-guillotine version of the problem. * Computational tests on a set of 5414 instances validate the quality and the effectiveness of the proposed algorithm. Abstract This paper addresses a two-dimensional (2D) non-guillotine cutting problem, where a set of small rectangular items of given types has to be cut from a large rectangular stock plate having defective regions so as to maximize the total value of the rectangles cut. The number of small items of each item type which can be cut from the large object is unrestricted. A novel MIP model and a hybrid approach combining a novel placement procedure with a biased random-key genetic algorithm (BRKGA) are presented. The parameters used by the novel placement procedure for the development of a cutting plan are evolved by the BRKGA. The management of the free spaces and of the defects uses a maximal-space representation. The approach is evaluated and compared to other approaches by means of a series of detailed numerical experiments using 5414 benchmark instances taken from the literature. The experimental results validate the quality of the solutions and the effectiveness of the proposed algorithm. Author Affiliation: (a) LIAAD, INESC TEC, Faculdade de Economia, Universidade do Porto Rua Dr. Roberto Frias, s/n, 4200-464 Porto, Portugal (b) Faculty of Economics and Management, Otto-von-Guericke-Universitat Magdeburg, Germany (c) School of Mechanical, Electronic and Control Engineering, Beijing Jiaotong University, China * Corresponding author. Article History: Received 21 September 2018; Revised 29 January 2020; Accepted 11 April 2020 (footnote)[white star] This work has been supported by project NORTE-01-0145-FEDER-000020 financed by the North Portugal Regional Operational Programme (NORTE 2020), under the PORTUGAL 2020 Partnership Agreement, and through the European Regional Development Fund (ERDF). Byline: Jose Fernando Goncalves [jfgoncal@fep.up.pt] (*,a), Gerhard Wascher [gerhard.waescher@ovgu.de] (b,c)