考虑不确定加工时间的炼钢—连铸过程柔性调度方法
|
摘要
针对加工时间存在不确定性的炼钢—连铸调度问题,构造了一种基于有向图网络的柔性调度模型,并提出一种基于分布估计的优化算法。在柔性调度模型中,使用有向图网络描述调度解的柔性决策,然后设置时间缓冲以保护不确定条件下调度解的性能指标和可行性;在优化算法中,使用基于工序关联的概率模型描述决策变量之间的关联关系以产生高质量的新种群,并采用随机仿真方法对柔性调度解的期望性能进行评价。在仿真过程中,运用最优计算量分配技术对有限计算资源进行动态分配以提高种群的评价效率。通过基于实际生产数据的问题实例和数值实验验证了所提柔性调度方法的有效性。
To solve the Steelmaking-Continuous Casting(SCC)scheduling problem with uncertain processing times,a directed graph-based flexible scheduling model was introduced,and an Estimation of Distribution Algorithm(EDA)was proposed.In the scheduling model,a directed graph model was used to describe flexible decisions and set time buffers for protecting the performance and feasibility of scheduling solution under uncertain environments.In the optimization algorithm,a stage-associated probabilistic model was developed to illustrate the relationship between decision variables,which could generate new high-quality populations.The stochastic simulation was used to evaluate the expected performance of flexible scheduling solutions.In the simulation,the Optimal Computing Budget Allocation(OCBA)technique was applied to allocate the limited computing resource for improving the evaluation efficiency of the population.The problem instances and computational results based on the practical production data demonstrated the effectiveness of the proposed flexible scheduling approach.
To solve the Steelmaking-Continuous Casting(SCC)scheduling problem with uncertain processing times,a directed graph-based flexible scheduling model was introduced,and an Estimation of Distribution Algorithm(EDA)was proposed.In the scheduling model,a directed graph model was used to describe flexible decisions and set time buffers for protecting the performance and feasibility of scheduling solution under uncertain environments.In the optimization algorithm,a stage-associated probabilistic model was developed to illustrate the relationship between decision variables,which could generate new high-quality populations.The stochastic simulation was used to evaluate the expected performance of flexible scheduling solutions.In the simulation,the Optimal Computing Budget Allocation(OCBA)technique was applied to allocate the limited computing resource for improving the evaluation efficiency of the population.The problem instances and computational results based on the practical production data demonstrated the effectiveness of the proposed flexible scheduling approach.
引文
[1]ZHENG Zhong,LONG Jianyu,GAO Xiaoqiang,et al.Present situation and prospect of production control technology focusing on planning and scheduling in iron and steel enterprise[J].Computer Integrated Manufacturing Systems,2014,20(11):11:2260-2274(in Chinese).[郑忠,龙建宇,高小强,等.钢铁企业以计划调度为核心的生产运行控制技术现状与展望[J].计算机集成制造系统,2014,20(11):2260-2274.]
[2]TAN Yuanyuan,SONG Jianhai,LIU Shixin.A hybrid twophase algorithm and mathematical model for steelmaking and continuous casting with controllable processing time[J].Control Theory&Practice,2012,29(6):12-22(in Chinese).[谭园园,宋健海,刘士新.加工时间可控的炼钢调度问题两阶段模型及优化算法[J].控制理论与应用,2012,29(6):12-22.]
[3]LI Z,IERAPETRITOU M.Process scheduling under uncertainty:Review and challenges[J].Computers&Chemical Engineering,2008,32(4):715-727.
[4]LIN Guanghang,LI Tieke.A Steelmaking-continuous casting production scheduling model and its heuristic algorithm[J].System Engineering,2002,20(6):44-48(in Chinese).[刘光航,李铁克.炼钢-连铸生产调度模型及启发式算法.系统工程,2002,20(6):44-48.]
[5]BELLABDAOUI A,FIORDALISO A,TEGHEM J.A heuristic algorithm for scheduling the steelmaking continuous casting process[J].Pacific Journal of Optimization,2005,1(3):447-464.
[6]TANG L X,LUH P B,LIU J Y,FANG L.Steel-making process scheduling using Lagrangian relaxation[J].International Journal of Production Research.2002,40(1):55-70.
[7]WANG Xiuying,FENG Hui,REN Zhikao,et al.Two-stage optimal modeling and algorithm of production scheduling for steelmaking and continuous casting[J].Acta Automatica Sinica,2016,42(11):1702-1710(in Chinese).[王秀英,冯惠,任志考,等.面向炼钢-连铸调度过程的两阶段优化模型与算法[J].自动化学报,2016,42(11):1702-1710.]
[8]XUAN H,TANG L X.Scheduling a hybrid flowshop with batch production at the last stage[J].Computers&Operations Research,2007,34(9):2718-2733.
[9]HARJUNKOSKI I,GROSSMANN I E.A decomposition approach for the scheduling of a steel plant production[J].Computers and Chemical Engineering,2001,25(11/12):1647-1660.
[10]XU Zhaojun,ZHENG Zhong,GAO Xaioqiang.HGA combined with priority strategy for production planning of steelmaking-continuous castin[J].Control and Decision,2016,31(8):1394-1400(in Chinese).[徐兆俊,郑忠,高小强.炼钢连铸生产调度的优先级策略混合遗传算法[J].控制与决策,2016,31(8):1394-1400.]
[11]PAN Q K,WANG L,MAO K,et al.An effective artificial bee colony algorithm for a real-world hybrid flowshop problem in steelmaking process[J].IEEE Transactions on Automation Science and Engineering,2013,10(2):307-322.
[12]LI J Q,PAN Q K,MAO K,et al.Solving the steelmaking casting problem using an effective fruit fly optimisation algorithm[J].Knowledge-Based Systems,2014,72:28-36.DOI:10.1016/j.knosys.2014.08.022.
[13]CHEN Li.TANG Qiuhua,CHEN Weiming,et al.Production scheduling of steelmaking-continuous casting integrated hybridizing constraint satisfaction and genetic optimization[J].Computer Integrated Manufacturing Systems,2013,19(11):2834-2846(in Chinese).[陈立,唐秋华,陈伟明,等.融合约束满足和遗传优化的炼钢连铸生产调度[J].计算机集成制造系统,2013,19(11):2834-2846.]
[14]OUELHADJ D,COWLING P I,PETROVIC S.Utility and stability measures for agent-based dynamic scheduling of steel continuous casting[C]//Proceedings of the IEEE International Conference on Robotics and Automation.Washington,D.C.,USA:IEEE,2003,1:175-180.
[15]ROY R,ADESOLA B A,THORNTON S.Development of a knowledge model for managing schedule disturbance in steel-making[J].International Journal of Production Research,2004,42(18):3975-3994.
[16]HOU D L,LI T K.Analysis of random disturbances on shop floor in modern steel production dynamic environment[J].Procedia Engineering,2012,29(4):663-667.
[17]WANG Bailin,LI Tieke,ZHANG Chunsheng,et al.Dynamic CSP based scheduling algorithm for steelmaking and continuous casting with conticaster breakdown[J].Computer Integrated Manufacturing Systems,2011,17(10):2185-2194(in Chinese).[王柏琳,李铁克,张春生,等.基于动态约束满足的考虑连铸机故障的炼钢连铸调度算法[J].计算机集成制造系统,2011,17(10):2185-2194.]
[18]PANG Xinfu,YU Shengping,LUO Xiaochuan,et al.Hybrid Job shop rescheduling method and its application for steelmaking-casting[J].Systems Engineering-Theory&Practice,2012,32(4):826-838(in Chinese).[庞新富,俞胜平,罗小川,等.混合Job shop炼钢-连铸重调度方法及其应用[J].系统工程理论与实践,2012,32(4):826-838.]
[19]LONG J,ZHENG Z,GAO X Q.Dynamic scheduling in steelmaking-continuous casting production for continuous caster breakdown[J].International Journal of Production Research,2016,55(11):1-20.
[20]MAO K,PAN Q K,PANG X F,et al.An effective Lagrangian relaxation approach for rescheduling a steelmakingcontinuous casting process[J].Control Engineering Practice,2014,30(9):67-77.
[21]TANG L,ZHAO Y,LIU J.An improved differential evolution algorithm for practical dynamic scheduling in steelmaking-continuous casting production[J].IEEE Transactions on Evolutionary Computation,2014,18(2):209-225.
[22]YU ShengPing,CHAI TianYou.Rescheduling method for starting time delay in steelmaking and continuous casting production processes[J].Acta Automatica Sinica,2016,42(3):358-374(in Chinese).[俞胜平,柴天佑.开工时间延迟下的炼钢-连铸生产重调度方法[J].自动化学报,2016,42(3):358-374.]
[23]YU S,CHAI T,TANG Y.An effective heuristic rescheduling method for steelmaking and continuous casting production process with multirefining modes[J].IEEE Transactions on Systems Man&Cybernetics Systems,2016,46(12):1675-1688.
[24]GOLDRATT E M.Critical chain:a business novel[M].Great Barrington,Mass.,USA:North River Press,1997.
[25]LARRANAGA P,KARSHENAS H,BIELZA C,et al.Areview on probabilistic graphical models in evolutionary computation[J].Journal of Heuristics,2012,18(5):795-819.
[26]CHEN S H,CHEN M C.Addressing the advantages of using ensemble probabilistic models in estimation of distribution algorithms for scheduling problems[J].International Journal of Production Economics,2013,141(1):24-33.
[27]WANG Shengyao,WANG Ling,XU Ye,et al.An estimation of distribution algorithm for solving hybrid flow-shop scheduling problem[J].Acta Automatica Sinica,2012,38(3):437-443(in Chinese).[王圣尧,王凌,许烨,等.求解混合流水车间调度问题的分布估计算法[J].自动化学报,2012,38(3):437-443.]
[28]CHEN C H,LIN J,YUCESAN E,et al.Simulation budget allocation for further enhancing the efficiency of ordinal optimization[J].Discrete Event Dynamic Systems,2000,10(3):251-270.
[29]GOLDBERG D E,DEB K.A comparative analysis of selection schemes used in genetic algorithms[J].Foundations of genetic algorithms,1991,1:69-93.
[30]ZHANG Q,MUHLENBEIN H.On the convergence of a class of estimation of distribution algorithms[J].IEEETransactions on Evolutionary Computation,2004,8(2):127-136.
[31]MONTGOMERY D C.Design and analysis of experiments[M].6th ed.Hoboken,N.J.,USA:John Wiley&Sons,2005.
[32]ALMEDER C,HARTL R F.A metaheuristic optimization approach for a real-world stochastic flexible flow shop problem with limited buffer[J].International Journal of Production Economics,2013,145(1):88-95.
[2]TAN Yuanyuan,SONG Jianhai,LIU Shixin.A hybrid twophase algorithm and mathematical model for steelmaking and continuous casting with controllable processing time[J].Control Theory&Practice,2012,29(6):12-22(in Chinese).[谭园园,宋健海,刘士新.加工时间可控的炼钢调度问题两阶段模型及优化算法[J].控制理论与应用,2012,29(6):12-22.]
[3]LI Z,IERAPETRITOU M.Process scheduling under uncertainty:Review and challenges[J].Computers&Chemical Engineering,2008,32(4):715-727.
[4]LIN Guanghang,LI Tieke.A Steelmaking-continuous casting production scheduling model and its heuristic algorithm[J].System Engineering,2002,20(6):44-48(in Chinese).[刘光航,李铁克.炼钢-连铸生产调度模型及启发式算法.系统工程,2002,20(6):44-48.]
[5]BELLABDAOUI A,FIORDALISO A,TEGHEM J.A heuristic algorithm for scheduling the steelmaking continuous casting process[J].Pacific Journal of Optimization,2005,1(3):447-464.
[6]TANG L X,LUH P B,LIU J Y,FANG L.Steel-making process scheduling using Lagrangian relaxation[J].International Journal of Production Research.2002,40(1):55-70.
[7]WANG Xiuying,FENG Hui,REN Zhikao,et al.Two-stage optimal modeling and algorithm of production scheduling for steelmaking and continuous casting[J].Acta Automatica Sinica,2016,42(11):1702-1710(in Chinese).[王秀英,冯惠,任志考,等.面向炼钢-连铸调度过程的两阶段优化模型与算法[J].自动化学报,2016,42(11):1702-1710.]
[8]XUAN H,TANG L X.Scheduling a hybrid flowshop with batch production at the last stage[J].Computers&Operations Research,2007,34(9):2718-2733.
[9]HARJUNKOSKI I,GROSSMANN I E.A decomposition approach for the scheduling of a steel plant production[J].Computers and Chemical Engineering,2001,25(11/12):1647-1660.
[10]XU Zhaojun,ZHENG Zhong,GAO Xaioqiang.HGA combined with priority strategy for production planning of steelmaking-continuous castin[J].Control and Decision,2016,31(8):1394-1400(in Chinese).[徐兆俊,郑忠,高小强.炼钢连铸生产调度的优先级策略混合遗传算法[J].控制与决策,2016,31(8):1394-1400.]
[11]PAN Q K,WANG L,MAO K,et al.An effective artificial bee colony algorithm for a real-world hybrid flowshop problem in steelmaking process[J].IEEE Transactions on Automation Science and Engineering,2013,10(2):307-322.
[12]LI J Q,PAN Q K,MAO K,et al.Solving the steelmaking casting problem using an effective fruit fly optimisation algorithm[J].Knowledge-Based Systems,2014,72:28-36.DOI:10.1016/j.knosys.2014.08.022.
[13]CHEN Li.TANG Qiuhua,CHEN Weiming,et al.Production scheduling of steelmaking-continuous casting integrated hybridizing constraint satisfaction and genetic optimization[J].Computer Integrated Manufacturing Systems,2013,19(11):2834-2846(in Chinese).[陈立,唐秋华,陈伟明,等.融合约束满足和遗传优化的炼钢连铸生产调度[J].计算机集成制造系统,2013,19(11):2834-2846.]
[14]OUELHADJ D,COWLING P I,PETROVIC S.Utility and stability measures for agent-based dynamic scheduling of steel continuous casting[C]//Proceedings of the IEEE International Conference on Robotics and Automation.Washington,D.C.,USA:IEEE,2003,1:175-180.
[15]ROY R,ADESOLA B A,THORNTON S.Development of a knowledge model for managing schedule disturbance in steel-making[J].International Journal of Production Research,2004,42(18):3975-3994.
[16]HOU D L,LI T K.Analysis of random disturbances on shop floor in modern steel production dynamic environment[J].Procedia Engineering,2012,29(4):663-667.
[17]WANG Bailin,LI Tieke,ZHANG Chunsheng,et al.Dynamic CSP based scheduling algorithm for steelmaking and continuous casting with conticaster breakdown[J].Computer Integrated Manufacturing Systems,2011,17(10):2185-2194(in Chinese).[王柏琳,李铁克,张春生,等.基于动态约束满足的考虑连铸机故障的炼钢连铸调度算法[J].计算机集成制造系统,2011,17(10):2185-2194.]
[18]PANG Xinfu,YU Shengping,LUO Xiaochuan,et al.Hybrid Job shop rescheduling method and its application for steelmaking-casting[J].Systems Engineering-Theory&Practice,2012,32(4):826-838(in Chinese).[庞新富,俞胜平,罗小川,等.混合Job shop炼钢-连铸重调度方法及其应用[J].系统工程理论与实践,2012,32(4):826-838.]
[19]LONG J,ZHENG Z,GAO X Q.Dynamic scheduling in steelmaking-continuous casting production for continuous caster breakdown[J].International Journal of Production Research,2016,55(11):1-20.
[20]MAO K,PAN Q K,PANG X F,et al.An effective Lagrangian relaxation approach for rescheduling a steelmakingcontinuous casting process[J].Control Engineering Practice,2014,30(9):67-77.
[21]TANG L,ZHAO Y,LIU J.An improved differential evolution algorithm for practical dynamic scheduling in steelmaking-continuous casting production[J].IEEE Transactions on Evolutionary Computation,2014,18(2):209-225.
[22]YU ShengPing,CHAI TianYou.Rescheduling method for starting time delay in steelmaking and continuous casting production processes[J].Acta Automatica Sinica,2016,42(3):358-374(in Chinese).[俞胜平,柴天佑.开工时间延迟下的炼钢-连铸生产重调度方法[J].自动化学报,2016,42(3):358-374.]
[23]YU S,CHAI T,TANG Y.An effective heuristic rescheduling method for steelmaking and continuous casting production process with multirefining modes[J].IEEE Transactions on Systems Man&Cybernetics Systems,2016,46(12):1675-1688.
[24]GOLDRATT E M.Critical chain:a business novel[M].Great Barrington,Mass.,USA:North River Press,1997.
[25]LARRANAGA P,KARSHENAS H,BIELZA C,et al.Areview on probabilistic graphical models in evolutionary computation[J].Journal of Heuristics,2012,18(5):795-819.
[26]CHEN S H,CHEN M C.Addressing the advantages of using ensemble probabilistic models in estimation of distribution algorithms for scheduling problems[J].International Journal of Production Economics,2013,141(1):24-33.
[27]WANG Shengyao,WANG Ling,XU Ye,et al.An estimation of distribution algorithm for solving hybrid flow-shop scheduling problem[J].Acta Automatica Sinica,2012,38(3):437-443(in Chinese).[王圣尧,王凌,许烨,等.求解混合流水车间调度问题的分布估计算法[J].自动化学报,2012,38(3):437-443.]
[28]CHEN C H,LIN J,YUCESAN E,et al.Simulation budget allocation for further enhancing the efficiency of ordinal optimization[J].Discrete Event Dynamic Systems,2000,10(3):251-270.
[29]GOLDBERG D E,DEB K.A comparative analysis of selection schemes used in genetic algorithms[J].Foundations of genetic algorithms,1991,1:69-93.
[30]ZHANG Q,MUHLENBEIN H.On the convergence of a class of estimation of distribution algorithms[J].IEEETransactions on Evolutionary Computation,2004,8(2):127-136.
[31]MONTGOMERY D C.Design and analysis of experiments[M].6th ed.Hoboken,N.J.,USA:John Wiley&Sons,2005.
[32]ALMEDER C,HARTL R F.A metaheuristic optimization approach for a real-world stochastic flexible flow shop problem with limited buffer[J].International Journal of Production Economics,2013,145(1):88-95.