Research On Thick Plate Matching Problem Of Steel Enterprise Based On Branch-and-Price Algorithm

In order to improve the utilization rate of thick plates,steel companies usually cut the thick plates in two directions,width direction and length direction,and assign them to contracts with the same property requirements such as steel grade and specifications,so as to avoid repeated steelmaking and lower the stock of surplus board.In the matching process of the thick plates,it is necessary to consider the matching of the steel plate attributes of the thick plate and the contract,and also consider the two-dimensional cutting of the thick plate,which can be reduced to a two-dimensional cutting problem with complex matching constraints,which is typically NP-hard.Previous studies have focused on matching problems with one-dimensional cutting mode,while matching problems with two-dimensional cutting mode are usually solved by artificial heuristics.It is difficult to ensure global optimization of matching schemes,resulting in waste of material resources.Therefore,studying the thick plate matching problem with two-dimensional cutting mode is of great significance to improve the refined production level and reduce the production cost of steel enterprises.In this thesis,for the thick plate matching problem with two-dimensional cutting mode,the mixed integer programming model is established with the goal of minimizing the amount of cutting remain and minimizing the matching penalty.The branch and price algorithm based on column generation is designed to solve the problem optimally.At the same time,the data analysis method is used to approximate the strong branching process,which effectively reduces the solution time of the algorithm.Finally,combined with the field research,the thick plate optimization matching system was designed and developed to reduce the cost of steel enterprises and improve the efficiency of staff operation.The specific work is as follows:(1)For the thick plate matching problem,a mixed integer programming model is established.The task of the matching problem of steel enterprises is to cut and distribute the remaining materials of the thick plates in the width and length directions under the premise of satisfying the matching requirements of the thick plates and the contract,and the two-dimensional cutting requirements of the thick plates.Aiming at this problem,with the goal of maximizing the matching of wide and thick plates,minimizing the matching penalty and the thickness of the thick and thick plates,a mixed integer programming model is established.The row pattern matching relationship and the column pattern matching relationship are used as the decision variables in this model,in order to match requirements for different cutting modes in production.The model is solved by the standard optimization solver software,which verifies the correctness of the model.(2)For the small-scale thick plate matching problem,the branch and price algorithm is designed to obtain the optimal solution.The mixed integer programming model is equivalently transformed into a set-packing model,and the lower bound of the problem is obtained by the column generation algorithm.An effective dynamic programming algorithm is designed for the price sub-problem of the column generation algorithm.The column generation algorithm is embedded into the branch and bound framework,and the optimal solution of the thick plate matching problem is obtained.The effectiveness of the algorithm is verified by numerical experiments.(3)Aiming at the problem of thick plate matching,combining data analysis with precise algorithm,a branch price algorithm based on data analysis is proposed.The scoring mechanism of branch variables is designed.The support vector machine regression method(SVR)is used to fit the branch variables and their corresponding scores in the historical branch data.The SVR function predicts branch variable's score by some features,and the variable with the highest score is selected for branching.This strategy effectively reduces the size of the branch tree and shortens the solution time of the branch price algorithm.The numerical experiment is used to verify the superiority of the hybrid algorithm with data parsing.(4)The thick plate matching system is designed and developed with the above model and algorithm embedded,which can effectively calculate the optimal matching scheme,meet the needs of the actual production process and the operating habits of the staff,and automatically realize the matching of thick plates and contracts in steel enterprise.