Modelling and Optimization Methods for the Sequencing Problem with Batching Decision in the Continuous-casting and Rolling Production
-
摘要: 以长材产线为背景, 研究了炉次在连铸及轧制阶段的组批及批排序问题. 与以往将连铸、轧制分开研究不同, 本文同时考虑连铸和轧制阶段对组批及批排序的要求, 还考虑了下游工序精整机组负荷均衡生产的要求. 为该问题建立了新的混合整数规划(Mixed integer programming, MIP) 模型. 由于问题的NP-hard 属性和模型的大规模特征, 以及工业应用的实际要求, 本文提出了改进的分散搜索(Scatter search, SS) 算法用于求解该问题. 在改进的SS 算法中, 利用解的相关性质来限制搜索空间, 并将变邻域搜索策略引入, 从而结合解的多样性及邻域互补性特点, 充分发挥算法混合的优势. 实际数据的计算结果验证了改进SS 算法的有效性.Abstract: In this paper, we take the long steel production line as research background, and investigate the charge batching and batch sequencing problem on the continuous-caster and the rolling machine. Different from the previous research in which the casting and rolling stages are disjoined, in this study the batching and batch sequencing requirements on both stages are considered simultaneously, as well as the requirement on balanc-ing the workloads on different finishing machines downstream. A novel mixed integer programming (MIP) model is developed. Because of the NP-hardness of the problem and the huge size of MIP model, along with practical requirement for industry appli-cation, we propose an improved scatter search (SS) algorithm to solve the problem. In this algorithm, the search space is reduced by some optimal properties and the variable neighborhood search strategy is introduced such that the diversification and the com-plementary advantage of difference neighborhoods are combined and the merits of hybrid algorithms are exploited. The compu-tational results on practical data demonstrate the efficiency of the improved scatter search algorithm.
-
[1] Dorn J, Shams R. Scheduling high-grade steelmaking. IEEE Expert, 1996, 11(1): 28-35[2] Box R E, Herbe D G. A scheduling model for LTV Steel's Cleveland Works' twin strand continuous slab caster. Interfaces, 1988, 18(1): 42-56[3] Chang S Y, Chang M R, Hong Y S. A lot grouping algorithm for a continuous slab caster in an integrated steel mill. Production Planning and Control, 2000, 11(4): 363-368[4] Harjunkoski I, Grossmann I E. A decomposition approach for the scheduling of a steel plant production. Computers and Chemical Engineering, 2001, 25: 1647-1660[5] Tang L X, Wang G S. Decision support system for the batching problems of steelmaking and continuous-casting production. Omega, 2008, 36(6): 976-991[6] 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[7] 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 and Steel Complex. European Journal of Operational Research, 2000, 124(2): 267-282[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 Jun, Liu Quan-Li, Wang Wei. Models and algorithms of production scheduling in tandem cold rolling. Acta Automatica Sinica, 2008, 34(5): 565-573(赵珺, 刘全利, 王伟. 冷轧生产调度模型及算法. 自动化学报, 2008, 34(5): 565-573)[10] Wang Li, Zhao Jun, Wang Wei. Rescheduling method in production process of cold rolling based on the partial reconfigurable production. Acta Automatica Sinica, 2011, 37(1): 99 -106(王利, 赵珺, 王伟. 基于部分生产重构的冷轧生产重调度方法. 自动化学报, 2011, 37(1): 99-106)[11] 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[12] 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[13] 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)[14] Zhu Bao-Lin, Yu Hai-Bin. Production scheduling model and algorithm for steel making-continuous casting-hot rolling processes. Computer Integrated Manufacturing Systems, 2003, 9(1): 33-36(朱宝琳, 于海斌. 炼钢-连铸-热轧生产调度模型及算法研究. 自计算机集成制造系统, 2003, 9(1): 33-36)[15] 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)[16] Marti R, Laguna M, Glover F. Principles of scatter search. European Journal of Operational Research, 2006, 169(2): 359-372[17] Caballero R, Laguna M, Martí R, Molina J. Scatter tabu search for multiobjective clustering problems. Journal of the Operational Research Society, 2011, 62(11): 2034-2046[18] Nasiri M M, Kianfar F. A hybrid scatter search for the partial job shop scheduling problem. International Journal of Advanced Manufacturing Technology, 2011, 52(9-12): 1031- 1038[19] Cano-Belmán J, Ríos-Mercado R Z, Bautista J. A scatter search based hyper-heuristic for sequencing a mixed-model assembly line. Journal of Heuristics, 2010, 16(6): 749-770[20] Garcia-López F, Melián-Batista B, Moreno-Pérez J A, Moreno-Vega J M. Parallelization of the scatter search for the p-median problem. Parallel Computing, 2003, 29(5): 575 -589[21] Debels D, De Reyck B, Leus R, Vanhoucke M. A hybrid scatter search/electromagnetism meta-heuristic for project scheduling. European Journal of Operational Research, 2006, 69(2): 638-653[22] Bai Jie, Yang Gen-Ke, Pan Chang-Chun, Sun Kai. A revised scatter search algorithm for path planning of multiple UAVs. Journal of Shanghai Jiao Tong University, 2011, 45(2): 173-178(白杰, 杨根科, 潘常春, 孙凯. 于改进分散搜索算法的无人机路径规划. 上海交通大学学报, 2011, 45(2): 173-178)[23] Mladenović N, Hansen P. Variable neighborhood search. Computers and Operations Research, 1997, 24(11): 1097- 1100[24] Xu Y, Qu R. A hybrid scatter search meta-heuristic for delay-constrained multicast routing problems. Applied Intelligence, 2012, 36(1): 229-241[25] Tang L X, Wang X P. A scatter search algorithm for a multistage production scheduling problem with blocking and semi-continuous batching machine. IEEE Transactions on Control Systems Technology, 2011, 19(5): 976-989
点击查看大图
计量
- 文章访问数: 1749
- HTML全文浏览量: 51
- PDF下载量: 1205
- 被引次数: 0