Research On Efficient Algorithm For Solving Two-Dimensional Rectangular Pieces Problem

With the rapid development of the economy and the continuous advancement of science and technology,it is very important to increase resource utilization and manufacturing efficiency.In the production process,an excellent layout scheme will greatly help the utilization of materials and cutting efficiency.Therefore,it is of important practical significance and theoretical value to study the layout problem of two-dimensional rectangular pieces.Two-dimensional rectangular patch layout problem is a classic NP difficulty problem.Inspired by the research results of previous generations,inspired by the habits of human daily life,it proposes the concept of the degree of regularity.This concept mainly integrates the corner area and the placement space.It is hope that the small rectangular blocks that have been placed and the flatness of the remaining space are as good as possible.The degree of regularity is not only considers the current state of placing the rectangular blocks,but also takes into account the state of the remaining space and prepares for the sustainable development of the rectangular blocks afterwards.In this thesis,a strategy of selecting action with the first rule is the degree of regularity,and the second rule is the degree of freedom.According to this strategy,the Basic algorithm is designed.The algorithm is based on the selection strategy,and chooses the best action for each step to place,until the final pattern.The algorithm can quickly get a solution.In order to broaden the search domain of the solution,in order to obtain a better solution,combined with the Basic algorithm and Beam Search strategy,a Enhanced algorithm is proposed.In the Enhanced algorithm,each step selects some corner-occupying actions according to the angle-occupied action selection strategy for trial placement,uses the Basic algorithm to reach the finalization,the final selection the action which has the maximum termination area utilization rate to become the actual action of this step.Perform this corner action and repeat the above process.Stop the process at some stage of the termination pattern,and then select the current optimal termination pattern to be the solution of the algorithm.In the process of picking out several angle-occupied actions and performing rehearsals,fixed the number of angle-occupied actions so as to increase the stability of the algorithm.In addition,the algorithm fixes the value of the number of steps,that is,only the trial placement of the angle-occupied action is performed in the range from the first step to the given step number.Compared to the basic algorithm,the search strategy has a wider range and is easier to obtain an optimal solution.Compared with the trial placement of the angle-occupied action at each step,this algorithm saves a certain amount of time.Because the degree of regularity depends on the number of corner regions and the number of placed spaces,the corner region and the placement space need to be updated when an angular position action occupied.Therefore,the update strategy of corner regions and placement spaces is an important part of the algorithm.By calculating the examples C21 and N13,the effectiveness of the algorithm was verified.This algorithm can be applied to the field of sheet cutting.