Recursive Algorithm With Pruning Strategy For A Class Of Rectangular Cutting Problems

Cutting and Packaging(C&P)is a fundamental research area in which two-dimensional layout optimization problems are a classical class of combinatorial optimization problems that are widely used in industrial manufacturing,logistics and transportation management,and ultralarge scale integrated circuits.With the development of economy and trade and the popularization of automation technology,the study of 2D layout optimization problems is crucial to enhance production revenue and promote academic research.This thesis studies the two-dimensional rectangular cutting problem with defects: a large rectangular plate with several defective regions is cut to obtain several smaller rectangular items with predefined dimensions and values,and each cut is required to satisfy the requirement of cutting vertically from one edge to the corresponding edge,and the resulting cut does not contain defects,with the aim of maximizing the sum of the values of all items.The problem is an NP-Hard problem whose input size depends on the size of the items and the original plate,and the computational effort grows exponentially as the input size increases.A good cutting solution can effectively reduce the waste of resources,lower the time cost,and enhance the economic efficiency of the company.In order to obtain a high quality cutting solution quickly,a large amount of literature in related fields has been reviewed and relevant algorithms in the field of cutting and packing have been studied in depth.Based on the idea of dynamic programming,an efficient recursive algorithm with pruning strategy(RAPS)is proposed in this thesis.Firstly,the width and height of the items are combined to construct a discrete set of cutting points starting from both the left(lower)boundary of the plate and the right(upper)boundary of the defects contained in the plate.This discrete set yields a normalized pattern for the subproblem without defects and the subproblem with defects,which generalizes the conclusion of theorem proposed by Herz,thus ensuring that the algorithm in this thesis obtains an optimal solution.Second,the lower bound of the clean plate is redefined,which is determined only by the proportional relationship between the clean plate and the dimensions of the items,when the clean plate can contain exactly one type of items,the lower bound of the clean plate is taken to be the area of the largest items it can contain,otherwise the lower bound is taken to be 0.The new lower bound can significantly reduce the computational volume of homogeneous cutting,thus significantly improving the efficiency of the algorithm.Then,a type of lower bound is defined for defective plates for the first time,and a pruning strategy is proposed in conjunction with the combinatorial nature of discrete sets: for the two subproblems generated by each cut,if the solution of one of them is 0,the other one is not computed.This strategy is applied to each level of subproblem decomposition,significantly reducing the size of the subproblem and without degrading the quality of the solution obtained by the algorithm.It is worth noting that this dynamic programming method with pruning strategy can be used to solve rectangular layout problems with different constraints and has a wide range of applications.RAPS was implemented using C++ coding and tested using 10814 classical instances.These instances are taken from random generators in the literature and the test results are compared with several current and up-to-date algorithms.The comparison results show that RAPS obtains the optimal solution for all instances and,moreover,is more than a hundred times more efficient than other algorithms in computing most of the instances.