Research On Efficient Algorithm For Rectangular Cutting Problem With Defects

With the rapid development of science and technology,computers have been integrated into various fields of national production,and software products are gradually becoming an indispensable auxiliary tool in social production.Layout problem widely exists in industrial manufacturing,transportation,daily life management and other important fields.The work of this paper is to promote and improve the optimization method in the plate cutting problem.Layout problems are common in industrial production,such as glass cutting,steel cutting,product packaging,container loading,carriage loading,tray assembly,as well as text typesetting,cloth cutting and article placement.In order to reduce cost consumption,improve production efficiency and save social production resources,a good layout plan will bring huge social production benefits and improve the quality of life and production.Cutting optimization is a specific form of layout problem.Given a two-dimensional plate and a certain number of items to be laid out,the items to be laid out are placed in the space reasonably on the premise of meeting certain constraints,so that the space utilization efficiency can reach some optimal goal.The quality of layout will directly or indirectly affect the production,transmission and sales of related industries,and then affect their economic benefits.Cutting problem is also a combinatorial optimization problem.Its biggest challenge is combinatorial explosion,especially when the computing scale increases,its combinatorial scale will show exponential growth.Experts and scholars at home and abroad have made a lot of explorations in this area and put forward many algorithms.Based on these algorithms,this paper designs a anthropomorphic algorithm for cutting problem through analysis and comparison.In this paper,several kinds of small rectangular blocks with certain size and direction are cut on the two-dimensional rectangular plate with defects.The number of each kind of rectangular block is unlimited.The requirement is that guillotine type must be met in the cutting process,and the cut rectangular block cannot contain the defective area.The purpose is to maximize the area of the small rectangular block.This problem is equivalent to covering the initial plate with rectangular blocks,and A Quasi-Human Recursive Algorithm based on dynamic programming is designed.Different strategies are used to decompose the sub problems of two kinds of plates with and without defects.First of all,using the knapsack model,the discretization sets of horizontal and vertical dimensions are constructed from the width and height of small rectangular blocks.For the plates with defects,the location information of defects is added to the discretization sets to increase more feasible solutions.Then,each element of the sets is traversed on the current subproblem and the subproblem is decomposed until the recursive boundary is triggered.The maximum value of multiple results is compared and the largest one is recorded as the solution of the current subproblem.Finally,we use different heuristic strategies for the two kinds of plates,the normalization strategy for the plates without defects,the selective normalization strategy for the plates with defects,and the extended strategy for the discrete set evolution to obtain an Enhanced Quasi-Human Recursive Algorithm.In order to test the performance of the algorithm in this paper,C + + language is used to complete the experiment.According to the generator provided by the reference,more than 9000 experimental samples are generated.Compared with several existing algorithms,the results show that the algorithm in this paper almost reaches the optimal value.In addition,the complexity of the algorithm is analyzed and proved.