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

摘要

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. (C) 2020 Elsevier B.V. All rights reserved.y