Research On Two-Dimensional Guillotine Bin Packing Problem

The two-dimensional guillotine bin packing problem refers to placing a number of rectangular pieces of different specifications on a given number of fixed-size two-dimensional plates(boxes),one by one,to ensure that they do not overlap each other.In the box,the number of occupied boxes is minimized,and the guillotine constraint is satisfied during cutting(here,the guillotine constraint refers to that the cutting line cannot be bent during cutting,and must be cut from one edge to the opposite edge through a straight line).The two-dimensional guillotine bin packing problem belongs to the two-dimensional layout problem in combination optimization problems.The most typical application is the layout optimization of glass cutting in the furniture production process.From the perspective of computational complexity theory,this problem belongs to the NP complete problem with the highest computational complexity and involves multidisciplinary knowledge such as computational geometry and operations research.It has high theoretical research and practical value.This paper has conducted in-depth research on the key issues in the two-dimensional guillotine bin packing problem.The main research work is described as follows:1.The concepts of G-region and GR-region are given to quantitatively describe the relevant conditions that need to be met in the process of layout for the first time.2.The definitions of clockwise cutting line group and counterclockwise cutting line group are proposed.Some supporting algorithms such as the G-region judgment algorithm,the G-region merge algorithm,and the full-region update algorithm are successively constructed on the basis of describing the layout structure using a triad tree.3.Based on the above work,a heuristic algorithm for two-dimensional guillotine bin packing problem is proposed,and numerical experiments andcomparative analysis are performed.4.Developed a packing software based on the proposed algorithm,and takes into account the relevant factors in the actual industrial production process such as the cutting line width and corner wear.The numerical experimental results show that,compared with the traditional two-dimensional guillotine bin packing algorithm,the concepts and related algorithms proposed in this paper can obtain the corresponding layout results more effectively and quickly.