| Cutting and packaging problems are widespread in manufacturing production processes,such as cutting glass,newspaper layout,and other fields.This issue has important practical significance in saving time,reducing costs,and maximizing the benefits of the cutting process.As a typical NP-hard problem,cutting problem is a kind of complex problem which combines combination and scheduling closely.The NP-hard problem has been developed for a long time,and it is of great significance both in the theoretical value of scientific research and in practical applications in practical production.The cutting problem studied in this thesis is the cutting problem of a two-dimensional rectangular guillotine with defects and constraints.Given the height and width of a large rectangular plate with defects and a certain number of small rectangular blocks,a number of small rectangular blocks,namely goods,are cut from the large rectangular plate on the premise of meeting the constraint conditions,and the goods obtained after cutting must not contain defect areas.The ultimate goal is to maximize the use rate of large rectangular blocks.The constraint condition that the cutting line cannot pass the defect is added to the cutting mode of the guillotine.At present,the research on this constraint condition is limited to the cutting mode of the non-guillotine.In this thesis,for the first time,linear programming and heuristic dynamic programming are combined to solve the plate cutting problem of the cutting mode of the guillotine with this constraint condition.In order to obtain more efficient cutting schemes,a large number of cutting-edge literature related to two-dimensional packing and cutting problems were consulted,and relevant algorithms for two-dimensional cutting problems were thoroughly studied.Based on linear programming and heuristic dynamic programming method,two algorithms with no defects are proposed: Benders decomposition algorithm without cutting defects(BDA＿WCD)and Benders decomposition algorithm for dividing discrete sets(BDA＿DDS).Algorithm BDA＿WCD is composed of BMP(Benders main problem)model and BSP(Benders sub problem)model,and the division of labor of these two models is different.BMP model is established by using linear programming to solve the model,and BSP model is established by using dynamic programming under the interaction of various constraints.The solution idea for algorithm BDA＿WCD is as follows: First,we can get a group of solutions by solving the BMP model.This group of solutions is the optimal solution for the original board to cut goods,but this solution may be guillotining mode or non-guillotine mode,and it is not sure whether the cutting line passes through the defect area;Then the BSP model needs to be used to analyze this group of solutions.Only when this group of solutions is in the guillotine mode and does not cut defects can it be accepted,otherwise the BMP model needs to be solved again.The algorithm BDA＿DDS is composed of the BMPD model and the BSPD model("D" is the abbreviation of "Discretization").The algorithm BDA＿DDS is obtained by dividing the discrete set of the algorithm BDA＿WCD,and the role of the two models in the algorithm BDA＿DDS is the same as that of the two models in the algorithm BDA＿WCD.After dividing the discrete set,the number of traversal points can be reduced,and the selection of cutting points is limited to the improved discrete set,which reduces the amount of calculation to a certain extent.This article evaluates algorithms BDA＿WCD and BDA＿DDS using three sets of instances,including and without constraints.The experimental results show that the computational efficiency of algorithm BDA＿DDS is much higher than that of algorithm BDA＿WCD,and both algorithms have obtained feasible solutions for all instances.Among them,algorithm BDA＿DDS saves a lot of time and verifies the efficiency of the algorithm. |
