Branch-and-price Algorithm for Rolling Batch Scheduling Problem in Continuous-casting and Rolling Processes with Hybrid Production Mode
-
摘要: 研究了连铸——轧制在热装、温装和冷装混流生产模式下的一类新型轧批调度问题.以最小化温装钢坯（热钢锭）缓冷（等待）导致的热能损失和连轧机架切换带来的产能损失为目标，建立了整数规划模型.由于商业优化软件难以在有限时间内直接求得模型的最优解甚至可行解，提出利用Dantzig-Wolfe分解技术将原模型分解为主问题和子问题，采用列生成算法对主问题和子问题进行迭代求解得到原问题的紧下界，最后以列生成算法作为定界机制嵌入分支——定界框架中形成分支——定价算法，执行分支搜索过程以获得整数最优解.本文还从影响分支——定价算法性能的要素出发提出改进策略.针对主问题，提出列生成和拉格朗日松弛混合求解策略来抑制单一列生成算法的尾效应.针对价格子问题，在动态规划算法中提出了基于占优规则和标号下界计算方法来及早消除无效状态空间，加速求解过程.以钢铁企业的实际生产数据和扩展的随机算例进行了数值实验，结果显示所提出改进策略能够突破求解能力的限制，使分支——定价算法在可接受计算时间内求得工业规模问题的最优解.Abstract: This paper studies a new type of rolling batch scheduling problem arising in continuous casting and rolling processes which are linked by the hybrid production mode of direct hot charge rolling (DHCR), hot charge rolling (HCR) and cold charge rolling (CCR). The problem is formulated as an integer programming model with the objective of minimizing heat energy loss due to cooling (Waiting) of HCR slabs (Hot ingots) and productivity loss caused by changeover of rolling shelves. Since the commercial optimization software is difficult to obtain an optimal solution or even a feasible solution of the model within a limited CPU time, the model is decomposed into a master problem and a set of subproblems using the Dantzig-Wolfe decomposition. The master problem and subproblems are iteratively solved through column generation algorithm to obtain a tighter lower bound of the original problem. Finally, the column generation algorithm acting as a bounding mechanism is embedded into the branch-and-bound framework to form a branch-and-price algorithm which performs the branch search process to obtain an integer optimal solution. Furthermore, key factors affecting the performance of the algorithm are analyzed and corresponding improvement strategies are proposed. For the master problem, a solution strategy of hybriding column generation and Lagrangian relaxation is proposed to restrain the tailing-off effect of column generation. For the pricing subproblem, a dominance rule and label lower bound calculation based method is proposed to eliminate non-promising state space early in the dynamic programming algorithm such that the solution procedure is speeded up. Numerical experiments are carried out on actual production data provided by a steel company and random instances extended from actual production data. The results show that the proposed improvement strategies can break through the limitation of the solving ability and enable the branch-and-price algorithm to solve industrial scale problem optimality within an acceptable CPU time.1) 本文责任编委 赵千川
-
表 1 分支-定价算法与CPLEX求解小规模算例的计算结果比较
Table 1 Comparison of computational results obtained by branch-and-price and CPLEX for small scale instances
问题规模 分支-定价 CPLEX 轧批数 时间槽数 LMP OPT GAP (%) CPU (s) LIP UB GAP (%) CPU (s) 20 5 2 479.77 2 483.8 0.16 0.11 2278.50 2 483.8 9.01 1.17 25 6 2 991.97 3 011.7 0.66 0.17 2782.05 3 011.7 8.25 2.76 30 7 3 693.91 3 726.4 0.88 0.43 3501.45 3 726.4 6.42 216.72 35 8 4 026.08 4 047.0 0.52 0.79 3842.80 4 047.0 5.31 501.53 40 10 4 622.63 4 634.8 0.26 1.18 4473.60 4 779.6 6.84 3 600.00 
下载: 导出CSV
表 2 分支-定价算法求解中规模算例的计算结果
Table 2 Computational results of branch-and-price for solving medium scale instances
问题规模 GAP (%) Nodes CPU (s) 轧批数 时间槽数 平均 最大 平均 最大 平均 最大 50 12 1.49 2.91 21 57 2.12 7.15 50 15 1.06 1.50 13 33 1.19 5.73 50 18 0.77 1.02 10 23 0.89 3.25 50 20 1.22 3.27 11 25 0.25 0.98 60 12 0.74 2.47 26 45 12.02 81.53 60 15 1.26 3.24 27 59 8.03 46.81 60 18 1.10 2.65 21 40 4.68 22.55 60 20 1.12 3.81 19 48 3.51 10.06 80 12 1.00 2.57 24 80 196.55 497.12 80 15 0.86 1.91 31 58 119.58 254.81 80 18 1.30 2.74 18 37 40.23 150.28 80 20 0.71 1.72 11 29 10.61 76.11 100 12 0.46 1.86 66 113 233.75 714.88 100 15 0.66 2.50 24 67 185.42 325.91 100 18 0.81 3.13 40 79 100.21 255.13 100 20 1.01 3.05 22 62 51.14 190.11
下载: 导出CSV
表 3 主问题和子问题改进策略的性能分析
Table 3 Performance analysis of improvement strategies for master problem and subproblem
问题规模 M1 (s) M2 (s) M3 (s) M4 (s) 轧批数 时间槽数 平均 最大 平均 最大 平均 最大 平均 最大 50 12 4.69 17.12 3.7 14.29 2.33 7.94 2.12 7.15 50 15 3.65 12.85 2.98 10.93 1.25 7.16 1.19 5.73 50 18 2.04 8.64 1.77 7.57 1.01 4.05 0.89 3.25 50 20 0.87 2.84 0.67 2.03 0.29 1.22 0.25 0.98 60 12 48.25 191.13 36.77 149.03 14.84 100.93 12.02 81.53 60 15 29.45 114.49 24.14 85.5 10.12 60.32 8.03 46.81 60 18 12.47 64.05 10.36 56.81 5.82 28.13 4.68 22.55 60 20 10.82 36.24 8.7 32.5 4.33 11.71 3.51 10.06 80 12 1 086.38 - 969.15 - 217.68 641.45 196.55 497.12 80 15 690 2 063.25 503.93 1 733.78 124.16 315.08 119.58 254.81 80 18 322.21 1 067.64 257.22 938.52 42.79 175.27 40.23 150.28 80 20 86.17 737.05 62.47 610.48 12.48 90.52 10.61 76.11 100 12 3 400.82 - 2 444.17 - 265.16 801.17 233.75 714.88 100 15 2 619.11 - 2 006.37 - 207.73 380.22 185.42 325.91 100 18 1 514.30 - 1 227.72 - 111.29 319.95 100.21 255.13 100 20 702.27 2 960.12 525.75 2 452.29 62.02 223.47 51.14 190.11 注:表中"-"表示算法在2小时内未完成分支搜索过程.
下载: 导出CSV
表 4 分支-定价算法与手工计划的结果比较
Table 4 Comparison results between branch-and-price and the manual planning method
问题规模 目标值 能耗费用 机架切换时间 轧批数 时间槽数 手工排产 分支-定价 手工排产 分支-定价 手工排产 分支-定价 51 12 1.0915 1.0000 1.0886 1.0000 1.3074 1.0000 56 12 1.0864 1.0000 1.0842 1.0000 1.2239 1.0000 55 13 1.0944 1.0000 1.0941 1.0000 1.1181 1.0000 56 13 1.0756 1.0000 1.0744 1.0000 1.1601 1.0000 58 14 1.0947 1.0000 1.0949 1.0000 1.0836 1.0000 平均 1.0885 1.0000 1.0872 1.0000 1.1786 1.0000
下载: 导出CSV
-
[1] Lopez L, Carter M W, Gendreau M. The hot strip mill production scheduling problem:a tabu search approach. European Journal of Operational Research, 1998, 106 (2-3):317-335 doi: 10.1016/S0377-2217(97)00277-4 [2] 吕志民, 徐金梧.一种适用于热送热装生产计划优化的方法.北京科技大学学报, 2002, 24 (6):675-678 http://www.cnki.com.cn/Article/CJFDTOTAL-BJKD200206023.htmLv Zhi-Min, Xu Jin-Wu. Optimization method for hot charge rolling manufacture plan. Journal of University of Science and Technology Beijing, 2002, 24 (6):675-678 http://www.cnki.com.cn/Article/CJFDTOTAL-BJKD200206023.htm [3] Cowling P. A flexible decision support system for steel hot rolling mill scheduling. Computers and Industrial Engineering, 2003, 45(2):307-321 doi: 10.1016/S0360-8352(03)00038-X [4] Zhao J, Wang W, Liu Q L, Wang Z G, Shi P. A two-stage scheduling method for hot rolling and its application. Control Engineering Practice, 2009, 17 (6):629-641 doi: 10.1016/j.conengprac.2008.10.014 [5] Pan C C, Yang G K. A method of solving a large-scale rolling batch scheduling problem in steel production using a variant of column generation. Computers and Industrial Engineering, 2009, 56 (1):165-178 doi: 10.1016/j.cie.2008.05.001 [6] Lee H S, Murthy S S, Haider S W, Morse D V. Primary production scheduling at steelmaking industries. IBM Journal of Research and Development, 1996, 40 (2):231-252 doi: 10.1147/rd.402.0231 [7] Cowling P, Rezi W. Integration of continuous caster and hot strip mill planning for steel production. Journal of Scheduling, 2000, 3 (4):185-208 doi: 10.1002/(ISSN)1099-1425 [8] Tang L X, Liu J Y, Rong A Y, Yang Z H. A review of planning and scheduling systems and methods for integrated steel production. European Journal of Operational Research, 2001, 133 (1):1-20 doi: 10.1016/S0377-2217(00)00240-X [9] 吕志民, 牟文恒, 许剑桦, 唐荻, 徐金梧.两流方式下薄板坯连铸连轧生产组织方法及仿真.北京科技大学学报, 2005, 27 (3):356-359 http://www.cnki.com.cn/Article/CJFDTOTAL-BJKD200503025.htmLv Zhi-Min, Mu Wen-Heng, Xu Jian-Hua, Tang Di, Xu Jin-Wu. Production organization method and simulation of dual-line thin slab continuous casting and hot rolling. Journal of University of Science and Technology Beijing, 2005, 27 (3):356-359 http://www.cnki.com.cn/Article/CJFDTOTAL-BJKD200503025.htm [10] 于港, 田乃媛, 徐安军, 贺东风.炼钢——热轧生产计划的优化与协调.冶金能源, 2009, 28 (4):6-9 http://www.cnki.com.cn/Article/CJFDTOTAL-YJLY200904003.htmYu Gang, Tian Nai-Yuan, Xu An-Jun, He Dong-Feng. Optimization and coordination of steelmaking-hot rolling production plan. Energy for Metallurgical Industry, 2009, 28 (4):6-9 http://www.cnki.com.cn/Article/CJFDTOTAL-YJLY200904003.htm [11] 汪恭书, 唐立新.连铸——轧制生产中带有批决策的排序问题的建模与优化方法.自动化学报, 2012, 38 (10):1713-1720 http://www.aas.net.cn/CN/abstract/abstract17727.shtmlWang 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 http://www.aas.net.cn/CN/abstract/abstract17727.shtml [12] Chen Z L, Powell W B. Exact algorithms for scheduling multiple families of jobs on parallel machines. Naval Research Logistics, 2003, 50 (7):823-840 doi: 10.1002/(ISSN)1520-6750 [13] Tang L X, Wang G S, Liu J Y. A branch-and-price algorithm to solve the molten iron allocation problem in iron and steel industry. Computers and Operations Research, 2007, 34 (10):3001-3015 doi: 10.1016/j.cor.2005.11.010 [14] Dantzig G B, Wolfe P. Decomposition principle for linear programs. Operations Research, 1960, 8 (1):101-111 doi: 10.1287/opre.8.1.101 [15] Gilmore P C, Gomory R E. A linear programming approach to the cutting stock problem. Operations Research, 1961, 9 (6):849-859 doi: 10.1287/opre.9.6.849 [16] Desrochers M, Desrosiers J, Solomon M. A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 1992, 40 (2):342-354 doi: 10.1287/opre.40.2.342 [17] Moukrim A, Quilliot A, Toussaint H. An effective branch-and-price algorithm for the preemptive resource constrained project scheduling problem based on minimal interval order enumeration. European Journal of Operational Research, 2015, 244 (2):360-368 doi: 10.1016/j.ejor.2014.12.037 [18] Restrepo M I, Gendron B, Rousseau L M. Branch-and-price for personalized multiactivity tour scheduling. INFORMS Journal on Computing, 2016, 28 (2):334-350 doi: 10.1287/ijoc.2015.0683 [19] Fragkos I, Degraeve Z, De Reyck B. A horizon decomposition approach for the capacitated lot-sizing problem with setup times. INFORMS Journal on Computing, 2016, 28 (3):465-482 doi: 10.1287/ijoc.2016.0691 [20] Tang L X, Wang G S, Chen Z L. Integrated charge batching and casting width selection at baosteel. Operations Research, 2014, 62 (4):772-787 doi: 10.1287/opre.2014.1278 [21] Battarra M, Erdoǧan G, Vigo D. Exact algorithms for the clustered vehicle routing problem. Operations Research, 2014, 62 (1):58-71 doi: 10.1287/opre.2013.1227 [22] Baldacci R, Mingozzi A, Roberti R, Wolfler Calvo R. An exact algorithm for the two-echelon capacitated vehicle routing problem. Operations Research, 2013, 61 (2):298-314 doi: 10.1287/opre.1120.1153 [23] Fleszar K. An exact algorithm for the two-dimensional stage-unrestricted guillotine cutting/packing decision problem. INFORMS Journal on Computing, 2016, 28 (4):703-720 doi: 10.1287/ijoc.2016.0708 [24] Gschwind T, Irnich S. Dual inequalities for stabilized column generation revisited. INFORMS Journal on Computing, 2016, 28 (1):175-194 doi: 10.1287/ijoc.2015.0670 [25] Vanderbeck F. On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Operations Research, 2000, 48 (1):111-128 doi: 10.1287/opre.48.1.111.12453 -
图(2) / 表(4)
计量
- 文章访问数: 2309
- HTML全文浏览量: 211
- PDF下载量: 994
- 被引次数: 0
