基于差分进化和迭代式分解的炼钢-连铸调度算法研究
|
摘要
炼钢-连铸是钢铁生产过程中的重要阶段,实现炼钢-连铸过程的优化调度对提高生产效率和产品质量、降低能耗/物耗、降低生产成本等具有重要作用。同时,炼钢-连铸生产调度是一类重要的复杂调度问题,其具有约束复杂、不确定动态事件多、对调度算法实时性要求高等复杂性,研究炼钢-连铸生产调度问题具有重要的理论意义和实用价值。本文以提高生产效率、降低能耗/物耗为主要目标,研究了炼钢-连铸生产过程的静态调度问题和动态调度问题。论文所做的主要工作如下:
本文首先研究了以最小化完工时间和最小化加权等待时间为调度目标、具有强约束特点的炼钢-连铸静态调度问题。在对该类调度问题进行模型描述的基础上,将迭代式分解、预测机制与差分进化算法相结合,提出了一种基于差分进化和迭代式分解的调度算法,并进行了编程实现。其中,采用差分进化算法对连铸机分派方案及各浇次的加工优先级进行全局优化,并将基于预测机制的迭代式分解算法用于上述差分进化的解码过程,以对上述调度问题进行高效的局部优化。
然后针对炼钢-连铸生产过程动态调度问题,在对调度相关动态事件进行分类的基础上,提出了炼钢-连铸生产过程动态调度问题解决方案。其中,根据动态事件的类别及扰动大小采用不同的动态调度算法——动态调整算法和重调度算法来求解该类动态调度问题。其中,动态调整算法主要针对具有较小扰动的动态事件,该类算法采用基于预测机制的迭代式分解算法,并融合相关调度专家经验进行动态调度;重调度算法主要针对具有较大扰动的动态事件,该类算法采用基于差分进化和迭代式分解的调度方法进行重调度,以实现全局动态调度。同时,基于上述动态调度问题解决方案,分别针对钢水质量不达标动态事件和设备故障动态事件两类常见的炼钢-连铸调度相关动态事件,提出了两种动态调度算法并进行了编程实现。
数值计算结果表明本文所提出的基于差分进化和迭代式分解的炼钢-连铸调度算法是有效的。
Steelmaking and continuous casting (SCC) is an important stage in the whole iron and steel production process, and the scheduling of SCC is essential for improving production efficiency and production quality, decreasing energy/material consumption and reducing production cost. Meanwhile, the SCC scheduling problem is a kind of complex scheduling problem, which is characterized as complex constraints, large number of dynamic events and high requirements for real-time. Therefore, the study of the SCC scheduling problem is of great theoretical significance and practical value. To increase production efficiency and reduce material consumption and energy consumption, this dissertation studies the SCC static scheduling problem and SCC dynamic scheduling problem. The main work of this dissertation is as follows.
This paper studies the SCC static scheduling problem with the scheduling objective of minimizing the completion time and the weighted waiting time. On the basis of model description of this kind of scheduling problem, this paper proposes and realizes a scheduling algorithm (a scheduling Algorithm based on Differential evolution and Iterative decomposition, ADI) that combines problem decomposition, prediction mechanism and differential evolution algorithm (DE). In the proposed ADI, the DE algorithm is used for the global optimization of machine assignment policies and the processing priority levels of casts, and an iterative decomposition algorithm based on prediction mechanism (IDP) is designed as the decoding process of differential evolution algorithm for efficient exploitation.
For the SCC dynamic scheduling problem, this paper proposes a solution framework based on the classification of dynamic events related to the SCC scheduling problem. In the solution framework, different dynamic scheduling algorithms are employed for different categories of dynamic events as well as their disturbance levels. These dynamic algorithms include dynamic adjustment algorithms and rescheduling algorithms. Based on the original scheduling schemes and IDP combined with the experts’experience, the dynamic adjustment algorithms are employed for the scheduling related dynamic events with a small disturbance level. And based on ADI, the rescheduling algorithms are employed for the dynamic events with large disturbance levels to realize global optimization of the dynamic scheduling problem. Meanwhile, considering that the dynamic events of poor quality of molten steel and equipment fault are two types of common scheduling related dynamic events in SCC process, this paper proposes and realizes two dynamic scheduling algorithms respectively based on the solution framework for the SCC dynamic scheduling problem mentioned above.
Numerical computations show that the proposed algorithms in this paper are effective for the SCC scheduling problem.
本文首先研究了以最小化完工时间和最小化加权等待时间为调度目标、具有强约束特点的炼钢-连铸静态调度问题。在对该类调度问题进行模型描述的基础上,将迭代式分解、预测机制与差分进化算法相结合,提出了一种基于差分进化和迭代式分解的调度算法,并进行了编程实现。其中,采用差分进化算法对连铸机分派方案及各浇次的加工优先级进行全局优化,并将基于预测机制的迭代式分解算法用于上述差分进化的解码过程,以对上述调度问题进行高效的局部优化。
然后针对炼钢-连铸生产过程动态调度问题,在对调度相关动态事件进行分类的基础上,提出了炼钢-连铸生产过程动态调度问题解决方案。其中,根据动态事件的类别及扰动大小采用不同的动态调度算法——动态调整算法和重调度算法来求解该类动态调度问题。其中,动态调整算法主要针对具有较小扰动的动态事件,该类算法采用基于预测机制的迭代式分解算法,并融合相关调度专家经验进行动态调度;重调度算法主要针对具有较大扰动的动态事件,该类算法采用基于差分进化和迭代式分解的调度方法进行重调度,以实现全局动态调度。同时,基于上述动态调度问题解决方案,分别针对钢水质量不达标动态事件和设备故障动态事件两类常见的炼钢-连铸调度相关动态事件,提出了两种动态调度算法并进行了编程实现。
数值计算结果表明本文所提出的基于差分进化和迭代式分解的炼钢-连铸调度算法是有效的。
Steelmaking and continuous casting (SCC) is an important stage in the whole iron and steel production process, and the scheduling of SCC is essential for improving production efficiency and production quality, decreasing energy/material consumption and reducing production cost. Meanwhile, the SCC scheduling problem is a kind of complex scheduling problem, which is characterized as complex constraints, large number of dynamic events and high requirements for real-time. Therefore, the study of the SCC scheduling problem is of great theoretical significance and practical value. To increase production efficiency and reduce material consumption and energy consumption, this dissertation studies the SCC static scheduling problem and SCC dynamic scheduling problem. The main work of this dissertation is as follows.
This paper studies the SCC static scheduling problem with the scheduling objective of minimizing the completion time and the weighted waiting time. On the basis of model description of this kind of scheduling problem, this paper proposes and realizes a scheduling algorithm (a scheduling Algorithm based on Differential evolution and Iterative decomposition, ADI) that combines problem decomposition, prediction mechanism and differential evolution algorithm (DE). In the proposed ADI, the DE algorithm is used for the global optimization of machine assignment policies and the processing priority levels of casts, and an iterative decomposition algorithm based on prediction mechanism (IDP) is designed as the decoding process of differential evolution algorithm for efficient exploitation.
For the SCC dynamic scheduling problem, this paper proposes a solution framework based on the classification of dynamic events related to the SCC scheduling problem. In the solution framework, different dynamic scheduling algorithms are employed for different categories of dynamic events as well as their disturbance levels. These dynamic algorithms include dynamic adjustment algorithms and rescheduling algorithms. Based on the original scheduling schemes and IDP combined with the experts’experience, the dynamic adjustment algorithms are employed for the scheduling related dynamic events with a small disturbance level. And based on ADI, the rescheduling algorithms are employed for the dynamic events with large disturbance levels to realize global optimization of the dynamic scheduling problem. Meanwhile, considering that the dynamic events of poor quality of molten steel and equipment fault are two types of common scheduling related dynamic events in SCC process, this paper proposes and realizes two dynamic scheduling algorithms respectively based on the solution framework for the SCC dynamic scheduling problem mentioned above.
Numerical computations show that the proposed algorithms in this paper are effective for the SCC scheduling problem.
引文
[1]李晓红.钢铁行业2005年深度分析报告. http://download.btnd.cn/download/2005/2/20 052161543454.doc
[2]宁树实.炼钢-连铸-热轧一体化生产调度研究及应用:[博士论文].大连:大连理工大学,2006
[3]高慧敏,曾建潮.钢铁生产调度智能优化与应用.北京:冶金工业出版社.2006,1~3
[4] Harjunkoski I, Grossmann. A decomposition approach for the scheduling of a steel plant production . Computers and Chemical Engineering, 2001, 25(11-12): 1647~1660.
[5]朱宝琳,于海滨,黄小原,等.炼钢_热轧一体化计划问题研究.信息与控制,2006, 35(4):537~540
[6]唐立新. CIMS下生产批量计划理论及其应用.北京:科学出版社,1999. 156~160
[7]郑秉霖,胡琨元,常春光.一体化钢铁生产计划系统的研究现状与展望.控制工程, 2003,10(1):6~10
[8] Redwine C N, Wismer D A. Mixed integer programming model for scheduling orders in a steel mill. Journal of Optimization Theory and Applications, 1974, 14(9): 305~318
[9] Chang S Y, Chang M R, Hong Y. A lot grouping algorithm for a continuous slab caster in an integrated steel mill. Production Planning and Control, 2000, 11(4): 363~368
[10] Sato S, Yamaoka T, Aoki Y, et al. Development of integrated scheduling system for iron and steel works. International Journal of Production Research, 1977, 15(11): 539~552
[11]李霄峰,徐立云,邵惠鹤,等.炼钢连铸系统的动态调度模型和启发式调度算法.上海交通大学学报.2001,35(11):1658~1662
[12]冯振军,杨根科,杜斌,等.炼钢连铸调度的启发式和线性规划两步优化算法.冶金自动化,2005,29(4):18~22
[13]周永良,刘浏,何平,等.求解炼钢-连铸排产问题FCFS算法.自动化技术与应用,2003,22(5):52~55
[14] Welbank, M. A Review of Knowledge acquisition Techniques for Expert Systems. British Telecommunications Research Laboratories Technical Report, Ipswich, England. 1983
[15] Sato S, Yamaoka T, Aoki Y, Ueda T. Development of integrated production scheduling system for iron and steel works. International Journal of Production Research, 1977, 15(6): 539~552
[16] Shah M J, Damian R, Silverman J. Knowledge based dynamic scheduling in a steel plant. Sixth Conference on Artificial Intelligence Applications. Washington D.C., USA: IEEE, 1990.108~113
[17] Tang LX, Liu JY, Rong AY, Yang ZH. A review of planning and scheduling systems and methods for integrated steel production. European Journal of Operational Research, 2001, 133(1): 1~20
[18]王秀英,柴天佑,郑秉霖.炼钢-连铸智能调度软件的开发及应用.计算机集成制造系统, 2006, 12(8): 1220~1234
[19] Fox M. Constraint directed search: a case study in job shop scheduling: [Ph.D. Dissertation]. Pittsburgh: Carnegie Mellon University, 1983
[20] Epp H P, Kalin M G, Miller D P, Karwan K R, Sweigart J R. An interactive, adaptive, real-time scheduler for steel-making. in: Karwan K, Swiegart J (eds) Proceedings of the Third International Conference, Expert Systems and the Leading Edge in Production and Operations Management. Hilton Head Island,SC,USA,1989. 495~504
[21]郭东芬,李铁克.基于约束满足方法求解炼钢—连铸生产调度问题.信息与控制,2005,34(6):753~764
[22]孙玲,李铁克.炼钢-连铸-热轧批量计划的约束满足算法.计算机集成制造系统,2007,13(5):940~944
[23] Dechter R, Frost D. Bach racking algorithms for constraint satisfaction problems. University of California, Irvine, Tech. Rep, 1999.
[24] Kouiss K, Pierreval H, Mebarki N. Using multi-agent architecture in FMS for dynamic scheduling. Journal of Intelligent Manufacturing,1997, 8(1): 41~47
[25]乔兵,孙志俊,朱剑英.基于Agent的分布式动态作业车间调度.信息与控制,2001,30(4):292~296
[26] 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
[27] Holland J. Adaptation In Natural And Artificial Systems. In: University of Michigan Press. 1975
[28] Tang L X, Liu J Y, Rong A Y, Yang Z H. A multiple traveling salesman problem model for the hot rolling scheduling in Baoshan Iron and Steel Complex. European Journal of Operational Research, 2000, 124(2): 267~282
[29] Hamada K, Baba T, Sato K, Yufu M. Hybridizing a genetic algorithm with algorithm with rule-based reasoning for production planning. IEEE Expert, 1995, 10(5): 60~67
[30] Liu M, Hao J H, Wu C. A prediction based Iterative decomposition algorithm for scheduling large-scale job shops. Mathematical and Computer Modelling, 2008, (47) 411~421
[31] Numao M, Morishita S. A scheduling environment for steel-making processes. Proceedingsof Fifth Conference on Artificial Intelligence Applications. Washington D.C., USA: IEEE, 1989. 279~286
[32] Huegler, Vasko. Metaheuristics for meltshop scheduling in the steel industry, Journal of the operational research society, 2007,58:791~796
[33]宁树实,王伟,潘学军.基于准时制思想的炼钢-连铸生产动态调度算法.信息与控制,2007,36(1):56~62
[34] Jian W, Xue Y C, Du H B. IECON 2005. in: Thirty-First Annual Conference of the IEEE Industrial Electronics Society. 2005, 3: 108~111
[35] Fujii S, Tanimoto S, Tomiyama S. Genetic algorithm with reduction of search space using operational constraints and its application to scheduling system for steelmaking process. Tetsu to Hagane-Journal of the iron and steel institute of Japan, 2003, 89: 1220~1226
[36] Storn R, Price K. Differential evolution—a simple and efficient adaptive scheme for global optimization over continuous spaces. Berkeley: University of California, 2006
[37]刘明广.差异演化算法及其改进.系统工程,2005,23(2):108~111
[38]刘波,王凌,金以慧.差分进化算法研究进展.控制与决策,2007,22(7):727~729
[39] Huang F Z, Wang L, He Q. An effective co-evolutionary differential evolution for constrained optimization. Applied Mathematics and Computation. 2007, 186(1):340~356
[40] Babu B V, Jehan M M L. Differential evolution for multi-objective optimization. Evolutionary Computation. 2003, 4:2696~2703
[41]周艳平,顾幸生.差分进化算法研究进展.化工自动化及仪表,2007,34(3):1~5
[42] Price K V. An Introduction to Differential Evolution. In: Corne D, Dorigo M, Glover F New Ideas in Optimization, 1999, Page(s):79~108
[43] Gamperle R, Dmuller S, Koumoutsakos P. A parameter study for differential evolution. in: International Conference on Advances in Intelligent Systems, Fuzzy Systems, Evolutionary Computation. 2002. 293~298;
[44]钱晓龙,唐立新,刘文新.动态调度的研究方法综述.控制与决策,2001,16(2):141~145
[45] Tang L X, Liu J Y, Rong A Y. A review of planning and scheduling systems and methods for integrated steel production. European Journal of Operational Research. 2001,133(1):1~20
[46] Cowling P I, Ouelhadj D, Petrovic S. Dynamic scheduling of steel casting and milling using multi-agents. Production Planning & Control. 2004, 15(2):178~188
[47]庞新富,俞胜平,郑秉霖,等.炼钢连铸动态调度方法及其应用.石油化工高等学校学报,2007,20(3):60~63
[48] Tang L X, Liu W X, Liu J Y. A neural network model and algorithm for the hybrid flow shop scheduling problem in a dynamic environment. Journal of Intelligent Manufacturing 2005, 16(3): 361~370
[49] Vieira G E, Herrmann J W, Lin E. Rescheduling manufacturing systems: a framework of strategies, policies, and methods. Journal of Scheduling, 2003, 6(1): 39~62.
[2]宁树实.炼钢-连铸-热轧一体化生产调度研究及应用:[博士论文].大连:大连理工大学,2006
[3]高慧敏,曾建潮.钢铁生产调度智能优化与应用.北京:冶金工业出版社.2006,1~3
[4] Harjunkoski I, Grossmann. A decomposition approach for the scheduling of a steel plant production . Computers and Chemical Engineering, 2001, 25(11-12): 1647~1660.
[5]朱宝琳,于海滨,黄小原,等.炼钢_热轧一体化计划问题研究.信息与控制,2006, 35(4):537~540
[6]唐立新. CIMS下生产批量计划理论及其应用.北京:科学出版社,1999. 156~160
[7]郑秉霖,胡琨元,常春光.一体化钢铁生产计划系统的研究现状与展望.控制工程, 2003,10(1):6~10
[8] Redwine C N, Wismer D A. Mixed integer programming model for scheduling orders in a steel mill. Journal of Optimization Theory and Applications, 1974, 14(9): 305~318
[9] Chang S Y, Chang M R, Hong Y. A lot grouping algorithm for a continuous slab caster in an integrated steel mill. Production Planning and Control, 2000, 11(4): 363~368
[10] Sato S, Yamaoka T, Aoki Y, et al. Development of integrated scheduling system for iron and steel works. International Journal of Production Research, 1977, 15(11): 539~552
[11]李霄峰,徐立云,邵惠鹤,等.炼钢连铸系统的动态调度模型和启发式调度算法.上海交通大学学报.2001,35(11):1658~1662
[12]冯振军,杨根科,杜斌,等.炼钢连铸调度的启发式和线性规划两步优化算法.冶金自动化,2005,29(4):18~22
[13]周永良,刘浏,何平,等.求解炼钢-连铸排产问题FCFS算法.自动化技术与应用,2003,22(5):52~55
[14] Welbank, M. A Review of Knowledge acquisition Techniques for Expert Systems. British Telecommunications Research Laboratories Technical Report, Ipswich, England. 1983
[15] Sato S, Yamaoka T, Aoki Y, Ueda T. Development of integrated production scheduling system for iron and steel works. International Journal of Production Research, 1977, 15(6): 539~552
[16] Shah M J, Damian R, Silverman J. Knowledge based dynamic scheduling in a steel plant. Sixth Conference on Artificial Intelligence Applications. Washington D.C., USA: IEEE, 1990.108~113
[17] Tang LX, Liu JY, Rong AY, Yang ZH. A review of planning and scheduling systems and methods for integrated steel production. European Journal of Operational Research, 2001, 133(1): 1~20
[18]王秀英,柴天佑,郑秉霖.炼钢-连铸智能调度软件的开发及应用.计算机集成制造系统, 2006, 12(8): 1220~1234
[19] Fox M. Constraint directed search: a case study in job shop scheduling: [Ph.D. Dissertation]. Pittsburgh: Carnegie Mellon University, 1983
[20] Epp H P, Kalin M G, Miller D P, Karwan K R, Sweigart J R. An interactive, adaptive, real-time scheduler for steel-making. in: Karwan K, Swiegart J (eds) Proceedings of the Third International Conference, Expert Systems and the Leading Edge in Production and Operations Management. Hilton Head Island,SC,USA,1989. 495~504
[21]郭东芬,李铁克.基于约束满足方法求解炼钢—连铸生产调度问题.信息与控制,2005,34(6):753~764
[22]孙玲,李铁克.炼钢-连铸-热轧批量计划的约束满足算法.计算机集成制造系统,2007,13(5):940~944
[23] Dechter R, Frost D. Bach racking algorithms for constraint satisfaction problems. University of California, Irvine, Tech. Rep, 1999.
[24] Kouiss K, Pierreval H, Mebarki N. Using multi-agent architecture in FMS for dynamic scheduling. Journal of Intelligent Manufacturing,1997, 8(1): 41~47
[25]乔兵,孙志俊,朱剑英.基于Agent的分布式动态作业车间调度.信息与控制,2001,30(4):292~296
[26] 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
[27] Holland J. Adaptation In Natural And Artificial Systems. In: University of Michigan Press. 1975
[28] Tang L X, Liu J Y, Rong A Y, Yang Z H. A multiple traveling salesman problem model for the hot rolling scheduling in Baoshan Iron and Steel Complex. European Journal of Operational Research, 2000, 124(2): 267~282
[29] Hamada K, Baba T, Sato K, Yufu M. Hybridizing a genetic algorithm with algorithm with rule-based reasoning for production planning. IEEE Expert, 1995, 10(5): 60~67
[30] Liu M, Hao J H, Wu C. A prediction based Iterative decomposition algorithm for scheduling large-scale job shops. Mathematical and Computer Modelling, 2008, (47) 411~421
[31] Numao M, Morishita S. A scheduling environment for steel-making processes. Proceedingsof Fifth Conference on Artificial Intelligence Applications. Washington D.C., USA: IEEE, 1989. 279~286
[32] Huegler, Vasko. Metaheuristics for meltshop scheduling in the steel industry, Journal of the operational research society, 2007,58:791~796
[33]宁树实,王伟,潘学军.基于准时制思想的炼钢-连铸生产动态调度算法.信息与控制,2007,36(1):56~62
[34] Jian W, Xue Y C, Du H B. IECON 2005. in: Thirty-First Annual Conference of the IEEE Industrial Electronics Society. 2005, 3: 108~111
[35] Fujii S, Tanimoto S, Tomiyama S. Genetic algorithm with reduction of search space using operational constraints and its application to scheduling system for steelmaking process. Tetsu to Hagane-Journal of the iron and steel institute of Japan, 2003, 89: 1220~1226
[36] Storn R, Price K. Differential evolution—a simple and efficient adaptive scheme for global optimization over continuous spaces. Berkeley: University of California, 2006
[37]刘明广.差异演化算法及其改进.系统工程,2005,23(2):108~111
[38]刘波,王凌,金以慧.差分进化算法研究进展.控制与决策,2007,22(7):727~729
[39] Huang F Z, Wang L, He Q. An effective co-evolutionary differential evolution for constrained optimization. Applied Mathematics and Computation. 2007, 186(1):340~356
[40] Babu B V, Jehan M M L. Differential evolution for multi-objective optimization. Evolutionary Computation. 2003, 4:2696~2703
[41]周艳平,顾幸生.差分进化算法研究进展.化工自动化及仪表,2007,34(3):1~5
[42] Price K V. An Introduction to Differential Evolution. In: Corne D, Dorigo M, Glover F New Ideas in Optimization, 1999, Page(s):79~108
[43] Gamperle R, Dmuller S, Koumoutsakos P. A parameter study for differential evolution. in: International Conference on Advances in Intelligent Systems, Fuzzy Systems, Evolutionary Computation. 2002. 293~298;
[44]钱晓龙,唐立新,刘文新.动态调度的研究方法综述.控制与决策,2001,16(2):141~145
[45] Tang L X, Liu J Y, Rong A Y. A review of planning and scheduling systems and methods for integrated steel production. European Journal of Operational Research. 2001,133(1):1~20
[46] Cowling P I, Ouelhadj D, Petrovic S. Dynamic scheduling of steel casting and milling using multi-agents. Production Planning & Control. 2004, 15(2):178~188
[47]庞新富,俞胜平,郑秉霖,等.炼钢连铸动态调度方法及其应用.石油化工高等学校学报,2007,20(3):60~63
[48] Tang L X, Liu W X, Liu J Y. A neural network model and algorithm for the hybrid flow shop scheduling problem in a dynamic environment. Journal of Intelligent Manufacturing 2005, 16(3): 361~370
[49] Vieira G E, Herrmann J W, Lin E. Rescheduling manufacturing systems: a framework of strategies, policies, and methods. Journal of Scheduling, 2003, 6(1): 39~62.