Modeling and Branch-and-price Algorithm for Logistics Optimization Problem of Plant-wide Production Processes in Steel Industry
-
摘要: 研究了钢铁企业的全流程物流优化问题, 该问题在确保全流程各个工序机组产能和库存能力限制以及满足客户需求的前提下, 决策炼钢、连铸、热轧及冷轧工序间的物料流向和流量, 最小化物流成本、产能损失及库存费用. 为该问题建立了混合整数规划(Mixed integer programming, MIP)模型. 在问题求解中, 首先对MIP模型进行了Dantzig-Wolfe分解, 得到一个结构相对简单但列变量数目非常多的主问题和四个描述列向量空间的子问题. 然后, 从一个包含部分列变量的限制主问题出发, 通过子问题和主问题之间的迭代来获取主问题线性松弛的最优解. 最后, 将列生成同分支—定界相结合, 即分支—定价算法, 以获取原问题的整数最优解. 对某钢铁企业的实际生产数据扩展的随机算例进行仿真实验, 结果显示所提出的算法能够在合理计算时间内获得最优解或次优解.
-
关键词:
- 钢铁全流程 /
- 物料流 /
- Dantzig-Wolfe分解 /
- 列生成 /
- 分支—定价
Abstract: In this paper, we investigate the logistics optimization problem of plant-wide production processes in steel industry, which is to decide the amount of material flow between steelmaking, continuous-casting, hot rolling and cold rolling processes such that the constraints on unit's capacity, the storage capacity and the customer's demands are satisfied and the logistics cost, penalty of production capacity loss and stock cost are minimized. A mixed integer programming (MIP) model is formulated, then a column generation based optimization solution method is developed according to the model's characters. In the solution method, we first use the Dantzig-Wolfe decomposition method to split the MIP model into a master problem which has a simple structure but contains numerous columns and 4 types of subproblems which describe the vector space of the columns. Then, the column generation algorithm starts from a restricted version of master problem which contains only a subset of columns, and executes iterative operations between the restricted master problem and subproblems to obtain the optimal solution of the linear relaxation of the master problem. Finally, a branch-and-price algorithm, which is a branch and bound framework by embodying column generation as a bounding estimation mechanism, is designed to obtain the integral optimal solution for the original problem. Computational experiments are carried on a set of instances which are randomly generated based on the practical production data collected from a large steel company in China. The results demonstrate that the proposed algorithm can obtain the optimal or sub-optimal solution within a reasonable CPU time. -
[1] Shapiro J F. Modeling the Supply Chain. Duxbury: Thomson Learning, 2001 [2] Drexl A, Kimms A. Lot sizing and scheduling-survey and extensions. European Journal of Operational Research, 1997, 99(2): 221-235 [3] van Hoesel S, Romeijn H E, Morales D R, Wagelmans A P M. Integrated lot sizing in serial supply chains with production capacities. Management Science, 2005, 51(11): 1706-1719 [4] Bredstróm D, Lundgren J T, Rónnqvist M, Carlsson D, Mason A. Supply chain optimization in the pulp mill industry-IP models, column generation and novel constraint branches. European Journal of Operational Research, 2004, 156(1): 2-22 [5] Carlsson D, Rónnqvist M. Supply chain management in forestry-case studies at Sódra Cell AB. European Journal of Operational Research, 2005, 163(3): 589-616 [6] Lidestam H, Rónnqvist M. Use of Lagrangian decomposition in supply chain planning. Mathematical and Computer Modelling, 2011, 54(9-10): 2428-2442 [7] Gunnarsson H, Rónnqvist M. Solving a multi-period supply chain problem for a pulp company using heuristics——an application to Sódra Cell AB. International Journal of Production Economics, 2008, 116(1): 75-94 [8] Tang Li-Xin, Zhao Ren. A new enhanced-dynasearch & TS for the pickling-rolling scheduling problem. Acta Automatica Sinica, 2010, 36(2): 304-313 (唐立新, 赵任. 强化Dynasearch & TS 算法求解酸轧生产调度问题. 自动化学报, 2010, 36(2): 304-313) [9] Zhao Yu-Fang, Tang Li-Xin. Scheduling with agreeable release times and due dates on a single continuous batch processing machine. Acta Automatica Sinica, 2008, 34(8): 957-963 (赵玉芳, 唐立新. 释放时间和工期同序的单机连续型批调度问题. 自动化学报, 2008, 34(8): 957-963) [10] Wang Gong-Shu, Tang Li-Xin. Modelling and optimization methods for the sequencing problem with batching decision in the continuous-casting and rolling production. Acta Automatica Sinica, 2012, 38(10): 1713-1720 (汪恭书, 唐立新. 连铸—轧制生产中带有批决策的排序问题的建模与优化方法. 自动化学报, 2012, 38(10): 1713-1720) [11] Tang L X, Liu J Y, Rong A Y, Yang Z H. A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex. European Journal of Operational Research, 2000, 124(2): 267-282 [12] Chai Tian-You. Challenges of optimal control for plant-wide production processes in terms of control and optimization theories. Acta Automatica Sinica, 2009, 35(6): 641-649 (柴天佑. 生产制造全流程优化控制对控制与优化理论方法的挑战. 自动化学报, 2009, 35(6): 641-649) [13] Luo Zhi-Hong, Tang Li-Xin. Modeling and solution to integrated production and logistics planning of steel making and hot rolling. Journal of Management Sciences in China, 2011, 14(6): 16-23 (罗治洪, 唐立新. 炼钢热轧一体化生产与物流计划模型及求解. 管理科学学报, 2011, 14(6): 16-23) [14] Dantzig G B, Wolfe P. Decomposition principle for linear programs. Operations Research, 1960, 8(1): 101-111 [15] Lübbecke M E, Desrosiers J. Selected topics in column generation. Operations Research, 2005, 53(6): 1007-1023 [16] Desaulniers G, Desrosiers J, Solomon M M. Column Generation. Berlin: Springer-Verlag, 2005 [17] Desrosiers J, Soumis F, Desrochers M. Routing with time windows by column generation. Networks, 1984, 14(4): 545-565 [18] Restrepo M I, Lozano L, Medaglia A L. Constrained network-based column generation for the multi-activity shift scheduling problem. International Journal of Production Economics, 2012, 140(1): 466-472 [19] de Queiroz T A, Miyazawa F K, Wakabayashi Y, Xavier E C. Algorithms for 3D guillotine cutting problems: unbounded knapsack, cutting stock and strip packing. Computers and Operations Research, 2012, 39(2): 200-212 [20] Baldacci R, Mingozzi A, Roberti R. New route relaxation and pricing strategies for the vehicle routing problem. Operations Research, 2011, 59(5): 1269-1283 [21] Baldacci R, Mingozzi A, Wolfler Calvo R. An exact method for the capacitated location-routing problem. Operations Research, 2011, 59(5): 1284-1296 [22] Staalhane M, Andersson H, Christiansen M, Cordeau J F, Desaulniers G. A branch-price-and-cut method for a ship routing and scheduling problem with split loads. Computers and Operations Research, 2012, 39(12): 3361-3375 [23] Muter Ī, Birbil S Ī, Bülbül K, Sahin G, Yenigün H, Tas D, Tüzün D. Solving a robust airline crew pairing problem with column generation. Computers and Operations Research, 2013, 40(3): 815-830
点击查看大图
计量
- 文章访问数: 1916
- HTML全文浏览量: 109
- PDF下载量: 1805
- 被引次数: 0