Research On Two-Dimensional Irregular Guillotine Packing Problem

Two-dimensional one-cutter layout problem is that given several irregular shaped parts to be arranged and several rectangular rowable areas(two-dimensional boxes)with the same specifications,the parts to be arranged are placed in the rowable area without overlapping each other,and the one-cutter constraint is satisfied to minimize the number of boxes to be used.Two-dimensional cutting layout problem is mainly applied in irregular glass cutting industry in furniture industry.It is a typical combinatorial optimization problem and NP-complete problem.It has high computational complexity and has far-reaching theoretical research value and practical value.This paper presents a heuristic algorithm for two-dimensional irregular one-size-fits-all layout problem,which takes into account both the quality and speed of layout,and achieves good results.The main contents are as follows:(1)In order to overcome the shortcomings of high computational complexity,large computational complexity and large amount of pre-processing when using NFP for location,a new heuristic location algorithm,mobile packing algorithm,is proposed.(2)The concept of multi-fork cutting tree is proposed to reduce the computational complexity in order to avoid repetitive operations.A generalized two-dimensional maximum rectangle algorithm is proposed for the sequencing problem of arrangable parts.In the new algorithm,priority queue is used to process the arrangable region,and the heuristic rules of local optimal layout selection are given.By changing the cutting order,some regions are merged skillfully.(3)In view of the increase of the number of cutting edges and the time-consuming increase caused by the excessive number of cutting edges of irregular parts in practical application,we propose a parallel algorithm based on Golang's support for the coroutine under the condition that the different combinations of cutting orders in one-knife rule do not affect each other and the selection order of different arrangable regions does not affect each other.(4)Finally,a complete non-recursive heuristic layout algorithm is given.The numerical experiments and comparative analysis are carried out to verify the correctness and effectiveness of the proposed algorithm.The numerical results show that the proposed algorithm can greatly reduce the overall time consumption while guaranteeing the material utilization.