Two-stage Optimal Modeling and Algorithm of Production Scheduling for Steelmaking and Continuous Casting
-
摘要: 以某钢厂多台转炉及多台精炼炉对多台连铸机的复杂生产线为研究对象，针对其调度过程涉及多设备、多目标、多约束等调度要素，且离散和连续变量混杂，采用常规建模方法难以满足现场对调度的精度及排产速度的需求问题，提出一种新型的两阶段优化建模方法.首先，证明了炉次从炼钢到连铸总等待时间最小的调度目标与该炉次在转炉开始作业时间最大是等价的事实，并以离散型的设备变量为决策变量，以转炉开始作业时间最大为动态规划最优指标，建立设备指派多阶段动态规划基本方程和设备指派优化模型；然后，以炉次在设备开始作业时间的连续型变量为决策变量，并将准时开浇的非线性调度指标转化成与之等价的线性优化目标，以在同一台连铸机上浇铸的炉次之间断浇的时间间隔最小、钢包在设备之间的冗余等待时间最小、提前与滞后理想开浇时间的时间间隔最小为目标，建立线性规划冲突解消模型.工业实验表明所提出两阶段优化建模方法在求解速度与求解精度均满足现场要求.Abstract: Steelmaking and continuous casting production scheduling is a multi-equipment assignment, multi-objective, multi-constraint, discrete and continuous variables hybrid optimization problem. Traditional modeling and solving methods are usually adopted to solve it, but they cannot meet the requirement in terms of high scheduling accuracy and fast problem solving speed. A new two-stage optimal modeling algorithm is proposed in this paper. In stage one, we show that minimizing the waiting time from steelmaking to continuous casting is equivalent to maximizing the converter operating time at first. Then we built a multiple-stage dynamic programming equation and optimization model using discrete variables, with the goal of maximizing the converter operating time. In stage two, we establish a linear programming conflict elimination model using continuous variables by converting a non-linear performance index into two equavalent linear optimization indexes including lead time, lag time between pratical casting and planned casting, and combining the other two indexes including time gap between furnaces on same caster and waiting duration for steel ladle among converters, refining furnaces and casters. On-site industry application validates that the proposed method can solve the scheduling problem with high speed and accuracy.
-
图 2 基于动态规划10个炉次的粗调度甘特图
Fig. 2 Gantt chart of ten charges rough scheduling based on dynamic programming
图 3 10个炉次冲突解消后的调度甘特图
Fig. 3 Scheduling Gantt chart after ten charges machine conflicts eliminated
i 浇次序号,i = 1,2,3, $\cdots,N$ ; Ni 第i个浇次中的炉次数; j 炉次序号,j = 1,2,...,Ni; Lij 第i个浇次的第j个炉次; $\vartheta_{ij}$ 炉次Lij从转炉到连铸工序的加工设 备总数; 浇次计划中的精炼方式确定后, $\vartheta_{ij}$ 的取值就确定了; θ 炉次Lij从转炉到连铸加工的顺序号, θ = 1,2,..., $\vartheta_{ij}$ ; g 表示设备类,g = 1,2,3,...,G,如g = 1表示转炉设备; $g = 2$ 表示第一类 精炼设备类, $g = G$ 表示连铸设备类; Ti 浇次i的理想开浇时间,由现场给定; Mg 表示第g类设备中含有的并行机数; kg 设备变量,表示g类设备的第k个设 备序号; kg = 1,2,3 $,\cdots$ ,Mg; Tij( $k_{g(\theta)})$ 炉次Lij的第θ个操作在第g类设备的 第 $k_{g(\theta)}$ 个设备上的加工时间;当θ不 同时,炉次Lij的操作设备类型g也不 同,所以,g是θ的函数,即g = $g(\theta)$ , kg = $k_{g(\theta)}$ ;对于连铸设备,不同炉次在 连铸机的处理时间是不尽相同的.所以, 处理时间Tij( $k_{g(\theta)}$ )是设备变量 $k_{g(\theta)}$ 的函数; Tij( $k_{g(\theta)}$ , $k_{g(\theta+1) }$ ) 炉次Lij从第θ个操作设备 $k_{g(\theta)}$ 到第 $\theta+1$ 个操作设备 $k_{g(\theta+1) }$ 之间的运输时 间.由于炉次Lij的第θ和 $\theta+1$ 个操 作设备不同,其运输时间也不尽相同,所 以运输时间Tij( $k_{g(\theta)}$ , $k_{g(\theta+1) }$ )是炉次上 下操作设备的函数; yij( $k_{g(\theta)}$ ) 设备变量 $k_{g(\theta)}$ 的函数,当yij( $k_{g(\theta)}$ ) = 1,表示炉次Lij的第θ个操作在g类设 备上的第 $k_{g(\theta)}$ 个设备上加工;否则, yij( $k_{g(\theta)}$ ) = 0; xij( $k_{g(\theta)}$ ) 称为时间变量.炉次Lij的第θ个操作在 第g类设备的第 $k_{g(\theta)}$ 个机器上加工的开始时间. 
下载: 导出CSV
表 1 三个浇次10个炉次计划的初始数据
Table 1 Initial data of three cast including ten charges
浇次号 炉次号 制造命令号 钢号 精炼方式 浇铸目的地 1 115578 DV3943D1 R 1#CC 1 2 115579 DT0192D1 R 1#CC 3 115580 DV3948D1 R 1#CC 4 115769 DT0138D1 R 1#CC 5 118275 AP0740D5 C 2#CC 2 6 118277 AP0740D5 C 2#CC 7 118281 DV3943D1 R 2#CC 8 461348 DV3943D1 R 3#CC 3 9 461349 DV3943D1 R 3#CC 10 461350 DV3943D1 RK 3#CC
下载: 导出CSV
表 2 基于动态规划的设备指派结果
Table 2 Equipment assignment base on dynamic programming
浇次号 炉次号 设备指派结果 设备处理时间 运输时间(分钟) 1 1 2#LD-1#RH-1#CC 35,36,48 8,14 2 2#LD-1#RH-1#CC 35,36,39 8,14 3 2#LD-1#RH-1#CC 35,36,52 8,14 4 2#LD-1#RH-1#CC 35,36,45 8,14 5 3#LD-1#CAS-2#CC 35,30,49 9,12 2 6 3#LD-1#CAS-2#CC 35,30,61 9,12 7 3#LD-2#RH-2#CC 35,36,42 9,15 8 1#LD-3#RH-3#CC 35,36,64 8,20 3 9 1#LD-3#RH-3#CC 35,36,64 8,20 10 1#LD-3#RH-KIP-3#CC 35,36,25,43 8,9,19
下载: 导出CSV
表 3 基于动态规划的10个炉次粗调度时刻表
Table 3 Ten charges rough schedule base on dynamic programming
炉次号 转炉 精炼1 精炼2 连铸 始 末 始 末 始 末 始 末 1 5:44 6:19 6:27 7:03 - - 7:17 8:05 2 6:32 7:07 7:15 7:51 - - 8:05 8:44 3 7:11 7:46 7:54 8:30 - - 8:44 9:36 4 8:03 8:38 8:46 9:22 - - 9:36 10:21 5 5:44 6:19 6:28 6:58 - - 7:10 7:59 6 6:33 7:08 7:17 7:47 - - 7:59 9:00 7 7:25 8:00 8:09 8:45 - - 9:00 9:42 8 5:46 6:21 6:29 7:05 - - 7:25 8:29 9 6:50 7:25 7:33 8:09 - - 8:29 9:33 10 7:21 7:56 8:04 8:40 8:49 9:14 9:33 10:16
下载: 导出CSV
表 4 10 个炉次机器冲突解消后的调度表
Table 4 Ten charges schedule table after conflicts eliminated
炉次号 转炉 精炼1 精炼2 连铸 始 末 始 末 始 末 始 末 1 5:44 6:19 6:27 7:03 - - 7:17 8:05 2 6:32 7:07 7:15 7:51 - - 8:05 8:44 3 7:11 7:46 7:54 8:30 - - 8:44 9:36 4 8:03 8:38 8:46 9:22 - - 9:36 10:21 5 5:44 6:19 6:28 6:58 - - 7:10 7:59 6 6:33 7:08 7:17 7:47 - - 7:59 9:00 7 7:25 8:00 8:09 8:45 - - 9:00 9:42 8 5:46 6:21 6:29 7:05 - - 7:25 8:29 9 6:45 7:20 7:28 8:04 - - 8:29 9:33 10 7:21 7:56 8:04 8:40 8:49 9:14 9:33 10:16
下载: 导出CSV
-
[1] 吴启迪, 乔非, 李莉, 吴莹. 基于数据的复杂制造过程调度. 自动化学报, 2009, 35(6): 807-813 doi: 10.3724/SP.J.1004.2009.00807Wu Qi-Di, Qiao Fei, Li Li, Wu Ying. Data-based scheduling for complex manufacturing processes. Acta Automatica Sinica, 2009, 35(6): 807-813 doi: 10.3724/SP.J.1004.2009.00807 [2] 王秀英, 柴天佑, 郑秉霖. 炼钢—连铸智能调度软件的开发及应用. 计算机集成制造系统, 2006, 12(8): 1220-1226 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJJ200608010.htmWang Xiu-Ying, Chai Tian-You, Zheng Bing-Lin. Intelligent scheduling software & its application in steelmaking and continuous casting. Computer Integrated Manufacturing Systems, 2006, 12(8): 1220-1226 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJJ200608010.htm [3] Missbauer H, Hauber W, Stadler W. A scheduling system for the steelmaking-continuous casting process. A case study from the steel-making industry. International Journal of Production Research, 2009, 47(15): 4147-4172 [4] Pacciarelli D, Pranzo M. Production scheduling in a steelmaking-continuous casting plant. Computers and Chemical Engineering, 2004, 28(12): 2823-2835 doi: 10.1016/j.compchemeng.2004.08.031 [5] 黄敏, 付亚平, 王洪峰, 朱兵虎, 王兴伟. 设备带有恶化特性的作业车间调度模型与算法. 自动化学报, 2015, 41(3): 551-558 http://www.aas.net.cn/CN/abstract/abstract18633.shtmlHuang Min, Fu Ya-Ping, Wang Hong-Feng, Zhu Bing-Hu, Wang Xing-Wei. Job-shop scheduling model and algorithm with machine deterioration. Acta Automatica Sinica, 2015, 41(3): 551-558 http://www.aas.net.cn/CN/abstract/abstract18633.shtml [6] Bellabdaoui A, Teghem J. A mixed-integer linear programming model for the continuous casting planning. International Journal of Production Economics, 2006, 104(2): 260-270 doi: 10.1016/j.ijpe.2004.10.016 [7] Mao K, Pan Q K, Pang X F, Chai T Y. A novel Lagrangian relaxation approach for a hybrid flowshop scheduling problem in the steelmaking-continuous casting process. European Journal of Operational Research, 2014, 236(1): 51-60 doi: 10.1016/j.ejor.2013.11.010 [8] Tang L X, Zhao Y, Liu J Y. An improved differential evolution algorithm for practical dynamic scheduling in steelmaking-continuous casting production. IEEE Transactions on Evolutionary Computation, 2014, 18(2): 209-225 doi: 10.1109/TEVC.2013.2250977 [9] Sbihi A, Bellabdaoui A, Teghem J. Solving a mixed integer linear program with times setup for the steel-continuous casting planning and scheduling problem. International Journal of Production Research, 2014, 52(24): 7276-7296 doi: 10.1080/00207543.2014.919421 [10] 俞胜平, 柴天佑. 开工时间延迟下的炼钢—连铸生产重调度方法. 自动化学报, 2016, 42(3): 358-374 http://www.aas.net.cn/CN/abstract/abstract18826.shtmlYu Sheng-Ping, Chai Tian-You. Rescheduling method for starting time delay in steelmaking and continuous casting production processes. Acta Automatica Sinica, 2016, 42(3): 358-374 http://www.aas.net.cn/CN/abstract/abstract18826.shtml [11] Tan Y Y, Liu S X. Models and optimisation approaches for scheduling steelmaking-refining-continuous casting production under variable electricity price. International Journal of Production Research, 2014, 52(4): 1032-1049 doi: 10.1080/00207543.2013.828179 [12] 李铁克, 苏志雄. 炼钢连铸生产调度问题的两阶段遗传算法. 中国管理科学, 2009, 17(5): 68-74 http://www.cnki.com.cn/Article/CJFDTOTAL-ZGGK200905010.htmLi Tie-Ke, Su Zhi-Xiong. Two-stage genetic algorithm for SM-CC production scheduling. Chinese Journal of Management Science, 2009, 17(5): 68-74 http://www.cnki.com.cn/Article/CJFDTOTAL-ZGGK200905010.htm [13] Atighehchian A, Bijari M, Tarkesh H. A novel hybrid algorithm for scheduling steel-making continuous casting production. Computers & Operations Research, 2009, 36(8): 2450-2461 http://cn.bing.com/academic/profile?id=2060539563&encoded=0&v=paper_preview&mkt=zh-cn [14] Pan L, Yu S P, Zheng B L, Chai T Y. Cast batch planning for steelmaking and continuous casting based on ant colony algorithm. In: Proceedings of the 2010 International Symposium on Computational Intelligence and Design. Hangzhou, China: IEEE, 2010. 244-247 [15] Li J Q, Pan Q K, Mao K, Suganthan P N. Solving the steelmaking casting problem using an effective fruit fly optimisation algorithm. Knowledge-Based Systems, 2014, 72: 28-36 doi: 10.1016/j.knosys.2014.08.022 [16] Pan Q K. An effective co-evolutionary artificial bee colony algorithm for steelmaking-continuous casting scheduling. European Journal of Operational Research, 2016, 250(3): 702-714 doi: 10.1016/j.ejor.2015.10.007 [17] Wang X Y, Jiang X J, Wang H H. Optimal modeling and analysis of steelmaking and continuous casting production scheduling. In: Proceedings of the 11th World Congress on Intelligent Control and Automation. Shenyang, China: IEEE, 2014. 5057-5062 [18] 王秀英. 炼钢—连铸混合优化调度方法及应用[博士学位论文], 东北大学, 中国, 2012Wang Xiu-Ying. Hybrid Optimization Scheduling Method of Steelmaking and Continuous Casting and its Application [Ph.D. dissertation], Northeastern University, China, 2012 [19] 王秀英, 柴天佑, 郑秉霖. 炼钢—连铸调度模型参数优化设定方法. 系统工程学报, 2011, 26(4): 531-537 http://www.cnki.com.cn/Article/CJFDTOTAL-XTGC201104015.htmWang Xiu-Ying, Chai Tian-You, Zheng Bing-Lin. Parameter optimization setting of steel making and continuous casting scheduling model. Journal of Systems Science and Systems Engineering, 2011, 26(4): 531-537 http://www.cnki.com.cn/Article/CJFDTOTAL-XTGC201104015.htm -
点击查看大图
图(3) / 表(5)
计量
- 文章访问数: 1613
- HTML全文浏览量: 156
- PDF下载量: 898
- 被引次数: 0
