An exact approach for the constrained two-dimensional guillotine cutting problem with defects

Abstract

This paper studies the constrained two-dimensional guillotine cutting problem with defects, whose objective is to cut a subset of given items from a defective sheet such that the profit of selected items is maximised. The guillotine cut constraint, which requires each cut must go through one side of the sheet to the opposite side, is considered. We solve this problem via a recursive dynamic programming approach. A set of upper bounds is proposed to keep the promising nodes. The normal points and raster points are extended to reduce the number of vertical and horizontal cuts by considering the effect of the defect. The experiment results show that our approach can solve most of the instances in the literature and outperforms existing approaches.