基于列生成的钢铁供应链计划与调度研究

发布时间：2018-04-23 06:21

本文选题：钢铁生产 + 供应链计划　；参考：《东北大学》2015年博士论文

【摘要】：供应链计划与调度是供应链管理中优化资源配置、合理安排生产与物流等活动的过程,也是以供需匹配赢得竞争优势的途径。钢铁工业属于多阶段流程型制造业,不同阶段在生产工艺、制造模式、产品特征等方面具有较大的差异,从而导致不同阶段之间决策的冲突,为供应链计划与调度的理论、方法及技术的深入发展提供了研究背景。供应链计划与调度的优化已成为钢铁运营中急需解决的关键问题,这些优化问题通常可归结为难解的组合优化问题,因此探讨适合这些问题的有效算法已成为学术界关注的热点。本文针对从钢铁生产中提炼出的烧结-炼铁低碳供应链计划、炼钢-热轧生产与物流供应链计划、炼钢-连铸-热轧供应链调度问题,建立了相应的混合整数规划模型,分析问题结构和特征,分别设计了基于列生成的分支定价最优算法。主要内容概述如下：1)烧结-炼铁低碳供应链计划是在满足铁水需求的情况下,考虑碳排放总量控制与交易机制,根据烧结与炼铁两个阶段的生产配方要求,确定原燃料采购、生产配方的选择、原燃料与烧结矿的库存、碳交易的优化问题。以最小化采购、生产、库存和碳交易成本为目标,建立了混合整数规划模型。该模型的特点为把碳排放控制机制与组合优化相结合,在考虑多阶段经济性目标的同时,兼顾了碳减排的需要。2)烧结-炼铁低碳供应链计划问题的算法研究。针对常规算法对该问题在大规模下难以快速获得最优解,设计了基于列生成的分支定价最优算法。提出了两种改进策略,一是在分析炼铁生产中烧结矿消耗数量关系的基础上提出两类不影响子问题结构和算法的有效不等式以提升下界,二是基于子问题路径的检验数进行变量消除来降低搜索空间从而提高算法性能。实验结果显示所提出的算法性能优于商业求解软件CPLEX,验证了算法的有效性。3)炼钢-热轧生产与物供应链流计划研究。与常规单阶段不同,热轧需求的多样性与炼钢规模生产的冲突导致中间产品板坯和成品热轧卷的不合理库存以及需求的延期交货。在考虑炼钢和热轧受能力限制、两阶段之间三种连接方式的情况下,以最小化生产与物流成本及延期交货惩罚为目标,建立混合整数规划模型。设计了基于列生成的分支定价算法。从理论上分析了极点的性质,提出凸化和投影离散化的混合分解方法,实现整数变量和连续变量的分离,从而达到了对模型更为紧凑的等价变换和改进列生成收敛性的目的。实验结果表明了算法的有效性。4)炼钢-连铸-热轧供应链调度问题是在满足各阶段生产工艺约束的情况下,分析炉次、浇次和板坯之间的关系,确定它们在机器上的排序和调度时间的问题。以最小化炉次和板坯等待惩罚以及热轧生产切换成本为目标,建立混合整数规划模型。该模型不仅包含炉次和浇次对机器的选择和排序,还包板坯对轧制单元的选择和排序,以及热轧机上轧制单元的排序问题,具有复杂的耦合约束。5)炼钢-连铸-热轧供应链调度问题的算法研究。提出了基于机器和轧制单元的调度时间窗对原问题进行了更为紧凑的Dantzig-Wolfe分解策略,把炼钢和连铸阶段子问题归结为具有时间窗的最小化总加权完成时间的单机调度问题,提出了子问题的最优性并设计了双向动态规划算法求解。把热轧轧制单元子问题归结为具有资源约束和线性时间依赖成本的无环最短路问题,引入状态空间松弛技术设计了伪多项式时间算法求解。根据热轧生产的工艺要求,提出一类改进的能力有效不等式以提升基于列生成的分支定价算法的性能。实验结果验证了算法的有效性。
[Abstract]:Supply chain planning and scheduling are the process of optimizing resource allocation in supply chain management, arranging the activities of production and logistics, and also the way to win the competitive advantage by matching supply and demand. The iron and steel industry belongs to the multi stage process manufacturing industry, and the different stages have great differences in the production process, manufacturing mode and product characteristics, and thus lead to great differences. The conflict between different stages of decision making provides a research background for the theory, method and technology of supply chain planning and scheduling. The optimization of supply chain planning and scheduling has become the key problem to be solved urgently in iron and steel operation. These optimization problems can be summed up as difficult combinatorial optimization problems. Therefore, the discussion is suitable for these problems. The effective algorithm of the problem has become a hot topic in the academic field. In this paper, the sintering iron and iron low carbon supply chain plan, the steelmaking hot rolling production and logistics supply chain plan, the steelmaking continuous casting hot rolling supply chain scheduling problem, the corresponding mixed integer programming model are established, and the structure and characteristics of the problem are analyzed. The main content of the branch pricing optimal algorithm based on the column generation is summarized as follows: 1) the sintering and iron smelting low carbon supply chain plan is to consider the total carbon emission control and trading mechanism under the condition of meeting the demand of molten iron, and to determine the purchase of raw fuel, the selection of the production formula and the original combustion, according to the requirements of the two stages of sintering and ironmaking. In order to minimize the cost of purchasing, production, inventory and carbon trading, a mixed integer programming model is established to minimize the purchase, production, inventory and carbon trading costs. The model is characterized by combining carbon emission control mechanism with combined optimization, considering the multi-stage economic target and taking into account the need of carbon emission reduction.2) sintering and refining. Research on the algorithm of iron low carbon supply chain planning. Aiming at the problem that the conventional algorithm is difficult to obtain the optimal solution to this problem on a large scale, a branch pricing optimal algorithm based on column generation is designed. Two kinds of improvement strategies are proposed. One is to put forward two kinds of non influence sub problems on the basis of analyzing the quantity relation of sinter consumption in iron making production. The effective inequality of structure and algorithm is used to improve the lower bounds. Two is to reduce the search space based on the test number of the subproblem path to reduce the search space and improve the performance of the algorithm. The experimental results show that the performance of the proposed algorithm is better than the commercial solution software CPLEX, and validates the effectiveness of the algorithm.3) the steelmaking hot rolling production and supply chain flow plan. Different from the conventional single stage, the conflict between the variety of hot rolling demand and the scale production of steelmaking leads to the irrational inventory of slab and finished products of intermediate products and the delayed delivery of demand. In the case of three connections between the two stages, the cost and the delay of production and logistics are minimized considering the capacity limit of steelmaking and hot rolling. The goal of delivery penalty is to establish a mixed integer programming model. The branch pricing algorithm based on column generation is designed. The properties of the pole are analyzed in theory. The hybrid decomposition method of convexity and projection discretization is proposed to separate the integer variables and continuous variables, thus achieving a more compact equivalent transformation and an improved column for the model. The experimental results show the effectiveness of the algorithm. The results show the effectiveness of the algorithm.4) the scheduling problem of steelmaking continuous casting hot rolling supply chain is to analyze the relationship between the furnace times, the pouring time and the slab, and to determine the scheduling and scheduling time on the machine, in order to minimize the number of furnace and the slab. The mixed integer programming model is established for the penalty and the switching cost of hot rolling production. The model includes not only the selection and ordering of the furnace and the pouring time to the machine, but also the selection and ordering of the rolling unit for the slab, the ordering of the rolling units on the hot rolling mill, and the complex coupling constraint.5) for the steelmaking continuous casting hot rolling supply chain scheduling question. A more compact Dantzig-Wolfe decomposition strategy based on the scheduling time window based on machine and rolling unit is proposed. The problem of steelmaking and continuous casting order is reduced to a single machine scheduling problem with a time window to minimize the total weighted completion time. The optimality of the sub problem is proposed and the two-way motion is designed. The problem of the hot rolling rolling unit is reduced to the loop shortest path problem with resource constraints and linear time dependent costs, and the pseudo polynomial time algorithm is designed by the state space relaxation technique. According to the requirements of the hot rolling production, a class of effective inequalities for the ability to modify is proposed to improve the column generation based on the process requirements of hot rolling production. The performance of the branch pricing algorithm is proved. The experimental results verify the effectiveness of the algorithm.

【学位授予单位】：东北大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：F274;F426.31

【参考文献】