A Hierarchical Intelligent Search Algorithm For Multi-constraints Rectangle Cutting Problem With Defects

Cutting and packing problems belong to a class of classic NP hard problems in academia.They have many varieties,for example the knapsack problems in onedimensional,the rectangle cutting problems in two-dimensional,the bin packing problems in three-dimensional.We already have efficient and mature solutions for knapsack problems and some no-constraint rectangle cutting problems.These problems also been widely used in practical industrial production,such as glass,stone,cloth and paper cutting optimization.But the practical production had to consider constraints from process,customer demand and so on,which greatly increased the complexity and difficulty of optimization.This paper proposes a hierarchical intelligent search algorithm based on the limitations in actual glass cutting,such as defects,guillotine-cut,product sequence,cutting depth,multiple raw materials,etc.,for efficiently solving multi-constrained rectangular cutting problems with defects.First,for the guillotine-cut and cutting depth constraints,this paper proposes a new local solution representation method,which reduces the size of the local search space and greatly improves the search efficiency.Second,for the defects and product sequence constraints,this paper proposes a specific placement strategy for finished products,which greatly improves the quality of the solution.Third,to deal with multiple raw materials constraint and large-scale problems,this paper proposes a layered search framework and designs a specific search strategy for each layer,which not only improves the flexibility and accuracy of algorithm search,but also ensures optimization efficiency on large-scale problems.After testing 30 instances with 100-700 products,it is found that for 80% of the instances,the HISA-Beam algorithm proposed in this paper can give a solution with a usage rate of more than 93% in 3600 seconds.In addition,in the challenge ROADEF/EURO 2018,this algorithm achieved the fourth place in the final 64 teams.Therefore,in the actual cutting optimization of glass,stone,cloth and other raw materials,this algorithm can give a better cutting solution in a short time,which has great industrial application value.