Solution And Application Of Plate Cutting Problem

In the process of manufacturer's production,an excellent cutting plan can greatly increase the utilization rate of raw materials,thereby reducing the waste of the plates and saving economic costs,thereby bringing greater economic effects to the manufacturers.Therefore,the research of an efficient plate cutting algorithm has important theoretical value and practical application value.The problem of plate cutting is NP hard in theory and also an important problem to be solved in industry.The problem of sheet metal cutting is a classic NP-hard problem,and it is constantly making trade-offs between time and goodness.The cutting problem studied in the paper is called the cutting optimization problem,which is the challenge of the ROADEF/EURO Challenge organized by the French Operation(OR)and the Decision Support Association(ROADEF)in 2018.The main content of the problem is to cut several pieces of raw material into the required target blocks in sequence.In this type of problem,the sheet will be cut in the form of a line cut and the sheet stock will have a defect.Due to the cutting machine and related hardware,many restrictions have been imposed on the cutting problem,which greatly increases the difficulty of designing the cutting scheme.In the paper,the combination of dynamic cutting and cluster search is used to solve the problem.The general idea is to split the problem from finding the overall approximate optimal cutting scheme into a local approximate optimal cutting scheme with the 1_cut cutting line as the dividing line.After the problem is broken into multiple problems for solving the local approximate optimal solution,the cluster search is used to find these local approximate optimal solutions.This splits an original huge search tree into numerous small search trees,making the search process more efficient and faster.When all the local approximate optimal solutions are found,they are combined as the approximate optimal solution of the population.In the method,the index named the margin is defined as the selection factor of the action in the local search.The first target block of each 1_cut area is used as a branch node,and the branch is cut according to the concept of layer-by-layer cutting,and the branch of the search tree is developed until the 1_cut area has no extra space to continue cutting the target block or all the target blocks.There are already cutting lines to cut them out as a partial termination pattern.The branch route with the highest utilization rate is selected from all the local termination patterns for cutting as a local approximate optimal solution.Repeat this operation for the subsequent 1_cut area until all 1_cut areas have been cut.In the process of cluster search,we also use the method of dynamic cutting to adjust the results of each local search.before each partial cutting plan is completed,all the cutting lines are dynamic,and the position of the cutting line in the 1_cut area will not be determined,but will be based on the action.Selecting the result of the selection of the strategy,the cutting line of the temporarily determined position is moved up or to the right to achieve higher local utilization efficiency.That is to say,the width of each 1_cut area is not determined by the placement of the first target square,but a pre-1_cut line appears as a reference line,and the subsequent targetblock will suppress the 1_cut line if it is determined to be placed.The pre-1_cut line will pan to the right,just before the excess.Similarly,the horizontal 2_cut cutting line will also be moved up and down as needed.Until the entire 1_cut area is divided by the cutting line,all the cutting line positions in this partial area will be determined and will not be changed.This innovation will provide some flexibility for the algorithm,so that the cutting line has a certain flexibility in the operation process,to avoid the fact that some target blocks are only a little worse,but the cutting line cannot be floated,and the result cannot be placed.The experiment verified the advantages and disadvantages of the original algorithm by calculating the Group A study provided by the official ROADEF/EURO Challenge in 2018.The experimental results are tested by the test code provided by the official competition to ensure the correctness of the results It is compared with the singleton optimal solution given by the government.The singleton optimal solution is the optimal solution of all the algorithms published by the government for each instance.Through the analysis and calculation results,it is concluded that the algorithm has a good cutting effect when the size difference between the target block and the sheet material is large.The utilization rate of the example sheet can be above80%.