Abstract: Aiming at the complex product scheduling problem with hierarchical coupling constraints,a Hybrid Evolutionary Algorithm with Diversification Control(HEA-DC)was proposed.An analysis was conducted at the theoretical level to determine the feasibility of the operation movement,and a neighborhood structure was designed to ensure feasibility.In HEA-DC,an encoding method based on operation constraint degree was adopted to ensure the feasibility of all initial solutions,and the feasible crossover operator was designed to satisfy the complex product's processing and assembly sequence constraints.In addition,a population updating strategy based on neighborhood penalty was introduced to avoid premature convergence of the algorithm.Through comparing with the results of five current advanced algorithms,the advantages of HEA-DC in both solution quality and stability were verified,and the known optimal solutions of 11 instances were also updated.

Key words: integrated scheduling, hybrid evolutionary algorithms, neighborhood, diversity control

摘要： 针对具有分层耦合约束的复杂产品综合调度问题,提出一种多样性控制的混合进化算法(HEA-DC)。首先从理论层面分析了工序移动的可行判定条件,设计了一种保证可行性的邻域结构;其次,在算法设计方面,提出一种基于工序约束度的编码方法,以保证所有初始解的可行性;同时,设计了满足复杂产品加工装配顺序约束的交叉算子。此外,为避免算法过早收敛,引入了基于邻域惩罚的种群更新策略。最后,通过与当前5种先进算法测试结果进行对比,验证了所提算法在求解质量与稳定性方面的优势,并更新了11个算例的已知最优解。

关键词: 综合调度, 混合进化算法, 邻域结构, 多样性控制