Research On Two-Stage Cutting Stock Problem Of Steel Tube

The main task of the cutting stock problem of steel tubes is to determine how to cut raw steel tubes into several pieces of specified sizes to satisfy the dimension and quantity requirements of customer orders.In the practical production,the cutting of raw steel tubes should be done in a two-stage process.In the first stage,the raw tube is cut into several intermediate tubes with equal length.In the second stage,the intermediate tube is cut into final steel tubes with specific length required by customer orders.The cutting stock plan of each stage needs to be simultaneously determined in the two-stage cutting stock problem of steel tubes.Therefore,making cutting stock plan of steel tubes plays a necessary and important role in the manufacturing management process of steel tube production.And it is also of great significance to improve material utilization and enhance the profits of enterprises.Taking the practical production process of steel tubes as background,a two-stage cutting stock problem of steel tubes is studied.Different from the previous cutting stock problem of steel tubes,the customer orders include orders with the requirement of fixed-length and orders with unfixed-length.The length of final steel tubes for the orders with unfixed-length requirement is flexible,that is the length of each steel tube should fall in the given range.Considering the actual management requirements and production constraints,a mixed integer programming model is established for the problem.And a branch-and-price algorithm is designed to solve the problem.Finally,engineering optimization algorithm is proposed to solve the large-scale cutting stock problem of steel tubes.The main contents are shown as follows.1)Taking the practical production process of steel tubes as background,a two-stage cutting stock problem of steel tube with flexible length requirement is derived.The problem can be described as follows.Given a set of the customer orders with different length requirements,and a set of raw tubes with fixed length,the problem is to determine how to cut the raw tubes into intermediate tubes,and then how to cut the intermediate tubes into final steel tubes required by customer orders.Considering production process requirements,a mixed integer programming model is formulated with the objective by minimizing the number of used raw tubes and the total trim loss.A manual experience based heuristic is designed.The computational results show that the proposed model and heuristic are valid for solving the problem.2)For the two-stage cutting stock problem of steel tubes with flexible length requirement,a branch-and-price algorithm is designed.By introducing the new variable which indicates whether a cutting mode in each stage is selected or not,the original mixed integer programming model is reformulated into a set-covering model which is suitable for column generation.In the column generation algorithm,the proposed heuristic is adopted to obtain the initial columns.The pricing sub-problem can be seen as a knapsack problem,and then a dynamic programming algorithm is designed to solve it.Finally,the column generation algorithm is embedded into the branch-and-bound framework to obtain the optimal integer solution.The experimental results show that the designed branch-and-price algorithm is effective to solve the two-stage cutting stock problem of steel tubes.3)For the two-stage cutting stock problem of steel tubes with flexible length requirement,an integer programming based engineering optimization algorithm is proposed.Two approximate strategies are proposed.On the one hand,the final steel tubes,the sum of whose length is just equal to the length of an intermediate tube,are combined as one tube.That can reduce the number of variables in the model.On the other hand,taking the cutting scenarios generated by the column generation as the basic unit,a fast heuristic algorithm is proposed to obtain the feasible solution quickly,by selecting the reasonable cutting scenarios.The numerical experiments show that the proposed engineering optimization algorithm can solve the large-scale instances of the problem effectively.4)Embedding the proposed model and algorithms,a cutting plan decision support system for steel tubes is designed.The system contains data downloading module,cutting plan generated module,and result of the displaying module.It is a good foundation for improving the work efficiency of planners.