首页 关于本刊 编 委 会 期刊动态 作者中心 审者中心 读者中心 下载中心 联系我们 English
 自动化学报  2017, Vol. 43 Issue (7): 1178-1189 PDF

1. 东北大学工业与系统工程研究所 沈阳 110819;
2. 东北大学数学系 沈阳 110819

Branch-and-price Algorithm for Rolling Batch Scheduling Problem in Continuous-casting and Rolling Processes with Hybrid Production Mode
WANG Gong-Shu1, LIU Jing-Yi2, TANG Li-Xin1
1. Institute of Industrial and Systems Engineering, Northeastern University, Shenyang 110819;
2. Department of Mathematics, Northeastern University, Shenyang 110819
Manuscript received : April 8, 2016, accepted: November 8, 2016.
Foundation Item: Supported by National Natural Science Foundation of China (71672032, 71621061, 71202151) and National Key Research and Development Program of China (2017YFB0304100)
Corresponding author. TANG Li-Xin Professor at the Institute of Industrial and Systems Engineering, Northeastern University. His research interest covers production scheduling, logistics and supply chain management, and combinational optimization. Corresponding author of this paper.E-mail:lixintang@mail.neu.edu.cn
Recommended by Associate Editor ZHAO Qian-Chuan
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.
Key words: Continuous-casting and rolling     hybrid production     column generation     branch-and-price     dynamic programming

1 问题描述及建模

 图 1 初轧生产工艺流程图 Figure 1 The production process of primary rolling

1) 模型参数

N:轧批集合;

T:时间槽集合;

$l_{t}$:时间槽t的长度;

$p_{i}$:轧批i的轧制时间;

$N_{t}$:允许分配到时间槽t的候选轧批子集;

$T_{i}$:轧批i可分配的候选时间槽子集;

$c_{it}$:轧批i分配到时间槽t的能损费用; 对温装钢坯和热钢锭$c_{it}＞0$, 对其他钢坯和钢锭$c_{it}=0$;

$\mu_{ij}$:轧批ij时由于坯型规格不同带来的机架切换时间;

w:轧制机组单位时间的产能损失费用.

2) 决策变量

$y_{it}$:轧批i分配到时间槽t时, 取1;否则, 取0;

$x_{ijt}$:轧批ij都安排在时间槽t内且轧批j紧接i之后轧制时, 取1;否则, 取0.

 $\min \alpha \sum\limits_{t \in T} {\sum\limits_{i \in {N_t}} {{c_{it}}{y_{it}}} } + (1 - \alpha )\sum\limits_{t \in T} {\sum\limits_{i \ne j \in {N_t}} {w{\mu _{ij}}{x_{ijt}}} }$ (1)
 ${\rm{s}}.{\rm{t}}.\;\;\sum\limits_{t \in {T_i}} {{y_{it}}} = 1,\;\forall i \in N$ (2)
 $\begin{array}{l} {y_{it}} = \sum\limits_{j \in {N_t} \cup \{ 0\} \backslash \{ i\} } {{x_{ijt}}} = \sum\limits_{j \in {N_t} \cup \{ 0\} \backslash \{ i\} } {{x_{jit}}} ,\\ \quad \quad \quad \quad \quad \quad \quad \quad \forall t \in T,\;i \in {N_t} \end{array}$ (3)
 $\sum\limits_{j \in {N_t}} {{x_{0jt}}} = \sum\limits_{j \in {N_t}} {{x_{j0t}}} \le 1,\;\forall t \in T$ (4)
 $\sum\limits_{i \in {N_t}} {{p_i}{y_{it}}} + \sum\limits_{i \ne j \in {N_t}} {{\mu _{ij}}{x_{ijt}}} \le {l_t},\;\forall t \in T$ (5)
 $\sum\limits_{i \ne j \in S} {x_{ijt}} \le |S| - 1,\forall t \in T,S \subseteq {N_t},|S| \ge 2$ (6)
 $\begin{array}{l} {y_{it}} \in \{ 0,1\} ,{x_{ijt}} \in \{ 0,1\} ,\\ \forall t \in T,i \ne j \in {N_t} \cup \{ 0\} \end{array}$ (7)

 $\min \left\{ {{c_\omega } - \sum\limits_{i \in {N_t}} {{a_{i\omega }}{\pi _i}} - {\sigma _t}|t \in T,\omega \in {\Omega _t}} \right\}$ (16)

SP可以按时间槽分解为$|T|$个子问题, 每个子问题记为SPt.

 $\min \left\{ {{c_\omega } - \sum\limits_{i \in {N_t}} {{a_{i\omega }}{\pi _i}} - {\sigma _t}|\omega \in {\Omega _t}} \right\}$ (17)

$c_\omega$表达式代入并整理得到：

 $\begin{array}{l} \min \left\{ {\sum\limits_{i \in {N_t}} {(\alpha {c_{it}} - {\pi _i}){a_{i\omega }}} + } \right.\\ \quad \quad \left. {(1 - \alpha )\sum\limits_{i \ne j \in {N_t}} {w{\mu _{ij}}\eta _{ijt}^\omega } - {\sigma _t}|\omega \in {\Omega _t}} \right\} \end{array}$ (18)

2.2 分支-定价算法

 图 2 分支-定价算法流程图 Figure 2 The flow chart of branch-and-price algorithm
2.3 主问题的求解方法

 $\begin{array}{l} \min \sum\limits_{t \in T} {\sum\limits_{\omega \in {\Omega _t}} {\left( {{c_\omega } - \sum\limits_{i \in N} {{a_{i\omega }}{\eta _i}} } \right){\lambda _\omega }} } + \sum\limits_{i \in N} {{\eta _i}} \\ {\rm{s}}.{\rm{t}}.\;\;(14),(15) \end{array}$ (19)

LR问题可以分解为$|T|$个子问题, 每个对应一个时间槽t, 记为$LR_t$

 ${\delta _t}(\mathit{\boldsymbol{\eta }}) = \min \left\{ {{c_\omega } - \sum\limits_{i \in N} {{a_{i\omega }}{\eta _i}} |\omega \in {\Omega _t}} \right\}$ (20)

 $LB = \sum\limits_{t \in T} {\min ({\delta _t}(\mathit{\boldsymbol{\pi }}),0)} + \sum\limits_{i \in N} {{\pi _i}} \le opt({\rm{MP}})$ (21)

1) Initialization

2) ${\Lambda _0} \leftarrow \{ (0,0, \cdots ,0,0)\}$

3) For all $i\in N$ do

4) $\Lambda_i \leftarrow \varnothing$

5) End for

6) ${C^{{\rm{inc}}}} \leftarrow \infty ,P \leftarrow \left\{ 0 \right\}$

7) While $P\ne \varnothing$ do

8) $i=\arg \min\nolimits_{h\in P} \{\varsigma ^\omega \vert(R_h^\omega, C_h^\omega )\in \Lambda _h \}$

9) For all $j\vert (i, j)\in A$ do

10) For all $(R_i^\omega, C_i^\omega )\in\Lambda_i$ do

11)  If $y_j^\omega = 0$ and $\varsigma ^\omega +\tau_{ij} \le l_t$ then

12)  $(R_j^{\bar {\omega }}, C_j^{\bar {\omega }})\leftarrow (\varsigma ^\omega +\tau _{ij}, y_1^{\bar {\omega }}, \cdots, y_n^{\bar {\omega }}, C_h^{\bar {\omega }} ),$

其中, $y_j^{\bar {\omega }} =1$, $y_h^{\bar {\omega }}=y_h^\omega$, $\forall h\in N\backslash \{j\}$

13)  If LB$(R_j^{\bar {\omega }}, C_j^{\bar {\omega}} ) ＜ \min{\{}C^{\rm inc}, 0{\}}$ then

14)   If $(R_j^{\bar {\omega }}, C_j^{\bar{\omega }} )$不被$\Lambda _j$中的其他标号占优then

15)    $\Lambda_j \leftarrow \Lambda_j \cup\{(R_j^{\bar {\omega }}, C_j^{\bar {\omega }} )\}$

16)    删除$\Lambda_j$中被$(R_j^{\bar {\omega }}, C_j^{\bar {\omega }} )$占优的其他标号

17)    $C^{\rm inc} \leftarrow \min{\{}C_j^{\bar{\omega }}, C^{\rm inc}$

18)   End if

19)  End if

20)  End if

21) $\Lambda _i \leftarrow \Lambda _i \backslash(R_i^\omega, C_i^\omega )$

22) End for

23) If $\Lambda _j \ne \varnothing$ then

24)  $P\leftarrow P\cup \{j\}$

25) End if

26) End for

27) $P\leftarrow P\backslash \{i\}$

28) End while

2.5 分支策略

 ${\beta _{it}} = \sum\limits_{\omega \in {\Omega _t}} {{a_{i\omega }}{\lambda _\omega }} ,\;\;\forall i \in N,\;t \in T$ (22)

 $\begin{array}{l} {\beta _{it}} = \sum\limits_{\omega \in {\Omega _t}} {{a_{i\omega }}{\lambda _\omega }} \le \sum\limits_{t \in T} {\sum\limits_{\omega \in {\Omega _t}} {{a_{i\omega }}{\lambda _\omega }} } = 1,\\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \forall i \in N,\;t \in T \end{array}$ (23)

3 计算实验

3.1 实验数据

3.2 实验结果与分析

1) 所有测试实例的平均整数间隙不超过1.5 %, 最大整数间隙不超过4.0 %, 验证了Dantzig-Wolfe分解模型的线性松弛能为原问题提供紧的下界.

2) 分支-定价算法能够在合理计算时间内通过搜索有限节点来获得所测试实际规模问题的最优解, 说明分支-定价算法对求解这类问题的有效性, 且可以扩展到求解类似的组合优化问题.

3) 当轧批数固定时, 随着时间槽数增加, 计算时间减少.该现象可以解释为:对于固定的轧批, 时间槽数的增加意味着分配到每个时间槽的轧批平均数减少, 导致价格子问题更容易求解.

4) 随着问题规模的增大, 分枝节点增多, 计算时间也增多, 这是由于大规模算例的限制主问题和价格子问题的规模也变大, 因而更难求解.

4 结论

 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 Lv 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.( 吕志民, 徐金梧. 一种适用于热送热装生产计划优化的方法. 北京科技大学学报, 2002, 24(6): 675-678.) 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 Lv 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.( 吕志民, 牟文恒, 许剑桦, 唐荻, 徐金梧. 两流方式下薄板坯连铸连轧生产组织方法及仿真. 北京科技大学学报, 2005, 27(3): 356-359.) 10 Yu 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.( 于港, 田乃媛, 徐安军, 贺东风. 炼钢——热轧生产计划的优化与协调. 冶金能源, 2009, 28(4): 6-9.) 11 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.) 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