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

José Fernando Gonçalves and Gerhard Wäscher

European Journal of Operational Research, 2020, vol. 286, issue 3, 867-882

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.

Keywords: Cutting; Packing; Two-dimensional; Non-guillotine; defects; BRKGA; Biased random-key genetic algorithm (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720303623
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:286:y:2020:i:3:p:867-882

DOI: 10.1016/j.ejor.2020.04.028

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().