Research On One-Dimensional Stitching Algorithm Based On Tabu Search Algorithm

In industrial production,it is often necessary to design a reasonable layout and cutting plan for the cutting of raw materials,cutting larger raw materials into order size according to the cutting plan.One-dimensional cutting problem,that is,the raw materials and items are only considered in length,is commonly seen in the section,bar,pipe and other materials cutting,so it is also called cutting stock problem.When the length of stock supply is the same,it is called single cutting stock problem.When the length of stock supply is different,it is called multistock cutting problem.With the introduction of computer-aided design,the research on improving the utilization ratio of materials is more and more.In this paper,the cutting stock problem of the steel length is less than the length of item and the steel is allowed to splice and the cutting stock problem of stock is more than the length of the item.The main research work includes the following aspects:(1)Aiming at the special cutting problem that the length of steel is less than the length of item and the steel is allowed to splice,different splicing methods are put forward,and the heuristic sequential value correction algorithm is adopted,the design conforms to the enterprise actual production may splice onedimensional cutting stock algorithm.First,the different splicing methods of two splicing and three splicing are proposed to splice steels,and then a mathematical programming model of the cutting problem is established according to the constraints of special cutting,and the cutting pattern is solved recursively by dynamic programming.Then,put forward the value correction formula under splicing mode,adjust the value of items,and design experiments to compare the two splicing mode.Experimental results show that three splicing can improve the utilization ratio of steels and increase the algorithm time in an acceptable range.(2)Aiming at the general one-dimensional cutting stock problem where the stock length is longer than the item length,an improved tabu search algorithm combining the heuristic sequential value correction algorithm and Tabu search algorithm is proposed,and a mutation operator is designed,it is used to improve the local search ability of the algorithm and generate a variety of layout schemes.The initial solution of the problem is generated by a heuristic sequential value correction algorithm with the tabu table length set according to the number of items,then the solution of the problem is optimized by using the neighborhood generation criterion of mutation operator.The experimental results show that the algorithm reduces the running time and improves the utilization ratio of stocks.(3)The two algorithms are realized by Java programming.Firstly,the feasibility of the algorithm is tested,and then the effectiveness of the algorithm is verified by random examples or by comparison with other literatures.The experimental results show that the proposed algorithm can effectively improve the material utilization ratio.To sum up,this study can not only enrich and improve the theoretical basis of one-dimensional cutting stock problem,but also provide guidance for the development of cutting stock optimization software and enterprise production.