Beam search algorithm based on dynamic cutting

In this paper, a two-dimensional staged cutting problem is studied. It is required to cut a plurality of sheet materials containing defects into small rectangular blocks of a predetermined size in a guillotine method, and the finished product cannot contain defects. In order to solve the above problems, a beam search algorithm based on dynamic cutting is proposed. The algorithm splits the problem into multiple local rectangular cutting problems. The blanks are cut out in the first stage, and each area is solved by beam search. The action selection rules with the margins as indicators are defined and operated one by one. The current local area cannot cut any small rectangular block, and the strategy is made “flexible” by presetting the cutting line. Solving the local optimum and then achieving the global optimal goal. The experiment uses the official A group of examples to compare and analyze the current optimal solution of each study. When the algorithm deals with the large size difference between the small rectangular block and the sheet material, the utilization rate of the example plate can reach 80%.