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

Production scheduling of steelmaking-continuous casting integrated hybridizing constraint satisfaction and genetic optimization

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

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.