Research On Plate Cutting Algorithm Based On Quasi Human-Dynamic Programming

In the process of plate cutting,an excellent cutting pattern can greatly improve the utilization rate of materials,thereby reducing the waste of materials,saving the cost of manufacturers,and bringing them greater profits.Therefore,how to improve the utilization rate of materials is one of the problems that industrialized manufacturers need to solve urgently.It is of great theoretical and practical value to develop a set of efficient plate cutting algorithms.The problem studied in this thesis is to cut a number of rectangular goods of a given size and direction in a two-dimensional rectangular plate with defects.The goods cannot contain defects.There is no limit to the number of each type of product,and each cut type is a guillotine,the goal of solving this problem is to maximize the sum of the value of the cut goods.To solve this problem,a combination of Quasi Human strategy and dynamic programming algorithm is used to design a Quasi HumanDynamic Programming Algorithm.From the research standard(without defects)twodimensional cutting problem,the length and width of the goods are used to construct the vertical and horizontal discrete sets and the sub-problem is divided,which can get a good solution.On this basis,it is generalized to the two-dimensional cutting problem with defects,and combines some ideas of engineering practice.In this paper,the algorithm for solving the two-dimensional cutting problem with defects is proposed in terms of recursive function design,discrete sets construction,and defect information processing.Specifically,first,notice the difference between the two-dimensional cutting problem with defects and the standard two-dimensional cutting problem during the research process.When constructing a discrete set,the right and upper boundaries of the cutting position are extended to the largest;Second,this article only performs normalized cutting on the non-defective sub-plate and de-normalized processing on the defective sub-plate.This is due to the complexity of the discrete set element distribution and the defect distribution;third,the defect Information processing takes into account the location of the defect.In order to prevent possible damage to the board during the cutting process,a personification strategy is designed.The method is to perform sub-problem decomposition at a unit away from the left and right boundaries of the defect and outside the upper and lower boundaries.In the first two points,this article designs the basic QHDP algorithm,and in the third point,this article proposes an extended version of the QHDP algorithm.In the solution process,if a recurring sub-problem occurs,a complete calculation is performed only when it first appears,and this result is saved for subsequent query.This is the characteristic of the dynamic programming algorithm.In order to test the performance of the algorithm in this paper,we have performed thousands of calculation experiments on typical instances.These instances are obtained based on the previous instance generator program that studied the problem.The calculation results show that in the case of moderate calculation time,the degree of solution optimization obtained in the experiment greatly exceeds the latest literature algorithms.The complexity and basic theorem of the algorithm have also been rigorously analyzed and proved,and the factors affecting the running time of the algorithm are also given.