融合约束满足和遗传优化的炼钢连铸生产调度

摘要/Abstract

摘要： 针对炼钢连铸生产调度多阶段、多并行机、多约束的特点,提出一种约束满足技术与遗传优化相结合的混合算法,从问题分割、解的可行性和解的较优性三个层面进行算法设计:首先利用基于逻辑的Benders分解法将原问题简化为约束相对较少的主/子问题;再利用约束满足技术设定主问题求解规则、子问题解的生成条件、冲突识别方法与冲突消解策略,以保证所求解可行;最后采用遗传算法的迭代进化,完成所求解的收敛。相关实例证实了所研制算法的有效性,从单/双/多工序时间变化分析其对算法运行时间、不可行解总数、冲突消解能力的影响,并得出线性回归方程,利用近优性检验验证了算法的近优性。

关键词: 炼钢连铸, 生产调度, 约束满足遗传算法, 资源冲突, 冲突消解

Abstract: Aiming at the characteristics of multiple stages,multiple parallel machines and multiple constraints in production scheduling of steelmaking-continuous casting,a hybrid algorithm by combining constraint satisfaction with genetic algorithm was put forward,which solved the original problem from the level of problem,feasibility and optimality respectively.The original problem was simplified into the primary and sub-problems based on logical Benders decomposition so as to reduce its complexity.The constraint satisfaction technology was employed to make rules during solving primary problem,generating solutions for sub-problems,recognizing and resolving conflicts with the goal of ensuring the feasibility of solutions.By using the iterative evolution of genetic algorithm,the convergence of solution was obtained.Through adjusting single/double/multiple process times,relationships among operation times,the number of infeasible solutions and the number of conflict resolution were depicted by correlation analyses,and the validity and effectiveness of the proposed algorithm were verified in further experimental studies.

Key words: steelmaking-continuous casting, production scheduling, constraint satisfaction genetic algorithm, resource conflict, conflict resolution

中图分类号:

F224

陈立1,2,唐秋华1,陈伟明2,Floudas.C.A1,李明1. 融合约束满足和遗传优化的炼钢连铸生产调度[J]. .

CHEN Li1,2,TANG Qiu-hua1+,CHEN Wei-ming2,FLOUDAS C.A1,LI Ming1. Production scheduling of steelmaking-continuous casting integrated hybridizing constraint satisfaction and genetic optimization[J]. .

参考文献

［1］TANG Lixin,YANG Zihou,WANG Mengguang.Model and algorithm of furnace charge plan for steelmaking-continuous casting production scheduling［J］.Journal of Northeastern University,1996,8(4):439-558(in Chinese).［唐立新,杨自厚,王梦光.炼钢—连铸最优炉次计划模型与算法［J］.东北大学学报,1996,8(4):439-558.］
[2]SUN Fuquan,TANG Lixin,ZHENG Binglin.The steelmaking continuous casting production scheduling based on expert system［J］.Metallurgical Industry Automation,1998(6):31-33(in Chinese).［孙福权,唐立新,郑秉霖.炼钢—连铸生产调度专家系统［J］.冶金自动化,1998(6):31-33.］
[3]TANG Lixin,LUH P B,LIU Jiyin,et al.Steel-making process scheduling using lagrangian relaxation［J］.International Journal of Production Research,2002,40(1):55-70.
[4]YU Shengping,WANG Xiuying,ZHENG Binglin.Dynamic scheduling for steelmaking and continuous casting based on the programming model with varying constraints［J］.Control Theory & Applications,2009,26(7):772-775(in Chinese).［俞胜平,王秀英,郑秉霖.基于变约束规划模型的炼钢连铸动态调度［J］.控制理论与应用,2009,26(7):772-775.］
[5]YU Shengping,CHEN Wenming,PANG Xinfu,et al.Simulating system of dynamic scheduling for steelmaking and continuous casting based on graphic edit platform［J］.Journal of System Simulation,2009,21(16);5145-5149(in Chinese).［俞胜平,陈文明,庞新富,等.基于图形化编辑平台的炼钢连铸动态调度仿真系统［J］.系统仿真学报,2009,21(16);5145-5149.］
[6]SUN Ling,LI Tieke.Constraint satisfaction algorithm of batch planning for steel making-continuous casting-hot rolling［J］.Computer Integrated Manufacturing Systems,2007,13(5):940-944(in Chinese).［孙玲,李铁克.炼钢—连铸-热轧批量计划的约束满足算法［J］.计算机集成制造系统,2007,13(5):940-944.］
[7]GUO Dongfen,LI Tieke.Application of constraint satisfaction technology in slab sequencing problem of hot rolling scheduling［J］.Computer Engineering and Applications,2007,43(9):1-3(in Chinese).［郭冬芬,李铁克.约束满足技术在板坯排序中的应用［J］.计算机工程与应用,2007,43(9):1-3.］
[8]LIU Guanghang,LI Tieke.A Steelmaking-continuous casting production scheduling model and its heuristic algorithm［J］.Systems Engineering,2002,20(6):44-48(in Chinese).［刘光航,李铁克.炼钢—连铸生产调度模型及启发式算法［J］.系统工程,2002,20(6):44-48.］
[9]WANG Chao,LI Tieke,ZHANG Wenxue.Dynamic scheduling for steelmaking-continuous casting based on human-computer interaction［J］.Application Research of Computers,2011,28(4):1378-1381(in Chinese).［王超,李铁克,张文学.基于人机交互的炼钢连铸动态调度［J］.计算机应用研究,2011,28(4):1378-1381.］
[10]PANG Xinfu,YU Shengping,ZHENG Binglin,et al.Complete modification rescheduling method and its application for steelmaking and continuous casting［C］//Proceedings of the 17th International Federation of Automatic Control.Amsterdam,the Netherlands:Elsevier,2008:12837-12842.
[11]CUI Zhihua,GAO Huimin,ZENG Jianchao.A nonlinear genetic algorithm to solve continuous casting pro duction scheduling［J］.Computer Engineering and Applications,2004,40(35):205-207(in Chinese).［崔志华,高慧敏,曾建潮.一种求解连铸生产调度问题的非线性遗传算法［J］.计算机工程与应用,2004,40(35):205-207.］
[12]XIAO Yongjun,WANG Jing,ZHANG Wenxue.Research on rescheduling of steelmaking and continuous casting hybrid flowshop［J］.Microcomputer Information,2009,25(9-3):12-14(in Chinese).［肖拥军,王晶,张文学.炼钢—连铸混合流水车间重调度研究［J］.微计算机信息,2009,25(9-3):12-14.］
[13]SUN Jigui,GAO Jian,ZHANG Yonggang.A mini-conflict repair based algorithm for solving dynamic constraint satisfaction problems［J］.Journal of Computer Research and Development,2007,44(12):2078-2084(in Chinese).［孙吉贵,高健,张永刚.一个基于最小冲突修补的动态约束满足求解算法［J］.计算机研究与发展,2007,44(12):2078-2084.］
[14]COWLING P I,OUELHADJ D,PETROVIC S.Dynamic scheduling of steel casting and milling using multi-Agents［J］.Production Planning & Control,2004,15(2);178-188.
[15]WANG Xiuying,CHAI Tianyou,ZHENG Binglin.Intelligent scheduling software & its application in steelmaking and continuous casting［J］.Computer Integrated Manufacturing Systems,2006,12(8):1220-1226(in Chinese).［王秀英,柴天佑,郑秉霖.炼钢连铸智能调度软件的开发及应用［J］.计算机集成制造系统,2006,12(8):1220-1226.］
[16]ZENG Qihong.Solving problem of cast scheduling in steel-making cast with genetic algorithm［J］.Journal of Anshan Normal University,2004,12(6):70-73(in Chinese).［曾齐红.基于遗传算法求解炼钢—连铸浇次排序问题［J］.鞍山师范学院学报,2004,12(6):70-73.］
[17]SHAW K J,NG C,KOVACS B W.Cyclooxygenase gene expression in human endometrium and decidua［J］.Prostaglandins,Leukotrienes and Essential Fatty Acids,1994,50(5):239-243
[18]NORTCLIFFE A L,THOMPSON M,SHAW K J.A framework for modelling in S88 constructs for scheduling purposes［J］.ISA Transactions,2001,40(3);295-305.

[1]	秦旋,房子涵,张赵鑫. 考虑资源约束的预制构件多目标生产调度优化[J]. 计算机集成制造系统, 2021, 27(8): 2248-2259.
[2]	马丽萌,乔非,马玉敏,刘鹃. 基于SO-GP的智能车间组合调度规则挖掘[J]. 计算机集成制造系统, 2021, 27(5): 1351-1360.
[3]	高长元,栾兆东,张树臣,王京. 基于残缺历史数据信息的需方参与的协同设计冲突消解博弈模型[J]. 计算机集成制造系统, 2020, 26(5期): 1345-1354.
[4]	吴秀丽,张志强,赵宁,李俊青. 超启发式文化基因算法优化生产与预维修集成调度问题[J]. 计算机集成制造系统, 2019, 25(第8): 1885-1896.
[5]	王旭亮,柴旭东,张程,赵晓芳. 云制造环境下跨企业协同生产调度算法[J]. 计算机集成制造系统, 2019, 25(第2): 412-420.
[6]	费杨阳,马慧民. 批—离散机重入车间调度与设备维护联合优化[J]. 计算机集成制造系统, 2019, 25(第1): 44-52.
[7]	袁帅鹏,李铁克,王柏琳. 多目标炼钢—连铸生产调度的改进带精英策略的快速非支配排序遗传算法[J]. 计算机集成制造系统, 2019, 25(第1): 115-124.
[8]	张燕华,陈伟达,孟祥虎. 基于PBIL算法的炼钢生产低碳调度问题[J]. 计算机集成制造系统, 2018, 24(第10): 2407-2414.
[9]	姜天华. 基于灰狼优化算法的低碳车间调度问题[J]. 计算机集成制造系统, 2018, 24(第10): 2428-2435.
[10]	杨宏兵,沈露,成明,陶来发. 带退化效应多态生产系统调度与维护集成优化[J]. 计算机集成制造系统, 2018, 24(第1): 80-88.
[11]	廖雯竹,张秀芳,江敏. 成组方式下考虑故障率限制的生产调度模型[J]. 计算机集成制造系统, 2017, 23(第3期): 599-608.
[12]	龚永民,郑忠,龙建宇,高小强. 连铸机开浇炉次与时间决策的多目标优化[J]. 计算机集成制造系统, 2017, 23(第2期): 261-272.
[13]	廖雯竹,张秀芳. 成组生产方式下生产调度和设备维护的多目标联合决策问题[J]. 计算机集成制造系统, 2017, 23(第1期): 82-92.
[14]	王磊,郭顺生,李西兴,杜百岗,彭兆. 基于改进蚁群算法的多主体制造资源配置冲突协调方法[J]. 计算机集成制造系统, 2017, 23(第12): 2561-2570.
[15]	苏志雄,伊俊敏. 基于正逆序策略的混合流水车间遗传调度算法[J]. 计算机集成制造系统, 2016, 22(第4期): 1059-1069.