Research On The Steel Plates Combination Problem In Steel Enterprise

In iron and steel enterprises,the customer orders of heavy plates are characterized by small amount,multi-specification and single product-based delivery,which conflict with the production requirements of batch production and large dimension.This contradiction often results in the production of open-order steel plates.To improve resource utilization,reduce the costs of production and inventory,steel enterprises often assign open-order plates to matched customer orders,which is called steel plates combination.Taking the production and consumption of heavy plates in iron and steel enterprise as background,this thesis investigates steel plates combination problem.To describe the problem,a mixed integer programming model is formulated.A branch-and-price algorithm is developed to optimally solve the medium-scale instances of the problem.To solve large-scale instance in engineering application,an engineering optimization method is proposed to achieve near-optimal solution in a short time.Main contents of this thesis are as follows.1)For the steel plates combination problem,a mixed integer programming model is formulated.The goal of the steel plates combination problem is to assign steel plates to open orders of different dimension and performance requirements to meet the demand of customers and improve the utilization of steel plate.Different from the previous research,both of the two-dimensional cutting constraints and plate-order matching cost are considered in our problem.A mixed integer programming model is developed with consideration of the production requirements of dimension and steel grade.The objective is to minimize the mis-matching cost and the cut-loss cost of steel plates.Small-scale instances of the model are solved by standard optimization software CPLEX.The numerical result shows the proposed model is computationally efficient.2)A branch-and-price algorithm is designed to solve the problem.In the solution process,the column generation algorithm is embedded into the branch-and-bound framework to provide a lower bound for each node of the branch tree.Based on the structure of the problem,the mixed integer programming model is reformulated as a Set-Packing model.Distinguished from traditional decomposition methods,length limitation constraints of plates combination are added to sub-problems and the width limitation constraints of plates combination are added to master problems.Then the pricing sub-problem is a one-dimensional knapsack problem which can be easily solved.It significantly reduces the difficulty to solve pricing sub-problems.The computation results demonstrate that the proposed branch-and-price algorithm is effective for solving the steel plates combination problems.3)For the steel plates combination problem,an engineering optimization method is proposed to obtain the near-optimal solutions.On one hand,a width-based approximation strategy is proposed.By assuming that all steel plates have the same width,the knapsack capacity constraints can be approximate to the scenario selection constraints in the master problem of column generation.It can reduce the complexity of the master problem and speed up the convergence of the algorithm.On the other hand,a dynamic programming based heuristic is designed to select an appropriate combination of scenarios from the column pool in column generation process.It can quickly generate near-optimal solutions for large-scale instances of the steel plates combination problems.The computation results show that the proposed engineering optimization algorithm can effectively solve large-scale instances of the steel plates combination problems.